基于改進合同網(wǎng)協(xié)議的集群化管理調(diào)度模式研究

梁凱歌，趙一行，劉婉瑩，劉晨，裴玲

（河海大學(xué) 機電工程學(xué)院，江蘇 常州 213022）

0 引言

隨著人們消費觀念的變化，產(chǎn)品多樣化對傳統(tǒng)制造業(yè)提出了新的要求，傳統(tǒng)的單一品種、大批量的生產(chǎn)模式已經(jīng)不再適用于多品種、小批量、多樣化的市場需求，目前傳統(tǒng)制造業(yè)正在向著提高生產(chǎn)效率、降低生產(chǎn)成本、更加智能化的方向轉(zhuǎn)型升級。隨著對智能化車間研究的深入，對車間資源調(diào)度問題的研究也逐步轉(zhuǎn)向主動調(diào)度[1]、動態(tài)調(diào)度。多Agent系統(tǒng)（Multi-Agent System，MAS）[2]是由多個智能個體所組成的車間系統(tǒng)，在制造車間概念下的Agent具有通信、決策的能力，而多Agent群體則具有自組織、相互協(xié)商的功能。合同網(wǎng)協(xié)議（Contract net protocol, CNP）[3]機制為Agent交互提供了一種有效的協(xié)商機制。

CNP機制的思想是模擬市場競標原則，由任務(wù)發(fā)布Agent發(fā)起招標，有加工能力的Agent反饋自身運行狀況作為標書參與競標，任務(wù)發(fā)布Agent綜合評價建立中標連接，CNP機制為Agent交互提供了一種有效的協(xié)商機制，在實踐中取得了較為成功的運用，但是CNP機制本質(zhì)上是求取單步最優(yōu)解的機制[4]，在提高車間生產(chǎn)效率、均衡設(shè)備負載、改善車間整體運行效果方面優(yōu)勢有限。為改善傳統(tǒng)的CNP機制單步優(yōu)化的局限性，管晨丞[4]提出了一種基于區(qū)間協(xié)同拍賣策略的改進多Agent車間調(diào)度模型，引入了軟體規(guī)劃Agent，在一定時間窗口內(nèi)對調(diào)度方案進行組合優(yōu)化；張澤群[5]提出了一種改進CNP機制，引入了系統(tǒng)監(jiān)管類Agent對系統(tǒng)關(guān)心的全局信息進行監(jiān)控和預(yù)測，在調(diào)度結(jié)果超出約束條件時對系統(tǒng)運行進行干預(yù)；趙良輝[6]提出了一種無拍賣的動態(tài)Agent調(diào)度模型，對加工設(shè)備進行分類管理，利用資源Agent對不同種類的所有加工設(shè)備的時間流進行管理。

此外，實際車間生產(chǎn)往往伴隨著加工任務(wù)隨時到達的不確定性[7]，即對同一批次多個加工任務(wù)的下發(fā)時時發(fā)生，下發(fā)時常伴隨著數(shù)個加工任務(wù)的第一道工序為同一種加工類型的情況，現(xiàn)有的研究往往是對加工任務(wù)進行單個、多次下發(fā)，實時性受限；或調(diào)度系統(tǒng)進行重新調(diào)度[8-10]，大大加重調(diào)度系統(tǒng)的運行負荷。

基于上述研究，本文提出了一種對車間同類加工資源進行集群化管理的調(diào)度模式，可以對同一時刻到達某類加工設(shè)備的多個任務(wù)統(tǒng)一進行處理，實現(xiàn)單個任務(wù)的最小完工時間和同一時刻到達某類加工設(shè)備的多個任務(wù)負載分配均衡的多目標優(yōu)化。

1 基于改進合同網(wǎng)協(xié)議的集群化管理調(diào)度模式模型構(gòu)建

1.1 集群化管理模型

本文引入集群化和集群調(diào)度機概念，對車間加工資源按集群化進行管理。集群化管理框架如圖1所示。

圖1 集群化管理框架

集群調(diào)度機包含管理模塊、通信模塊、決策模塊。管理模塊對集群內(nèi)所有設(shè)備進行注冊，管理本集群內(nèi)各加工設(shè)備的基本信息；通信模塊負責(zé)該設(shè)備集群與車間服務(wù)器、本集群內(nèi)加工設(shè)備，車間其他加工設(shè)備進行通信；決策模塊中封裝有多目標優(yōu)化算法，當(dāng)調(diào)度機收到單個或多個任務(wù)請求時，向集群內(nèi)設(shè)備進行問詢，進而對單個任務(wù)或多個同時到達的任務(wù)進行多目標優(yōu)化，得出最優(yōu)的調(diào)度結(jié)果。

1.2 數(shù)學(xué)模型

1.2.1 條件假設(shè)

為更直觀、清晰地表述本文所述的調(diào)度模式，做出以下假設(shè)作為約束條件：1）每個加工任務(wù)有多道加工工序；2）不考慮物料在加工車間的運輸時間；3）同類加工設(shè)備加工能力相同，負載以加工時間衡量；4）一臺設(shè)備在同一時刻只能對一個加工任務(wù)進行加工。

1.2.2 加工任務(wù)緊急程度描述

緊急訂單是制造車間加工過程中最常見的不確定擾動之一，為解決緊急訂單問題，本文對加工任務(wù)的緊急程度進行描述。Egi表示第i個加工任務(wù)的緊急程度，按距交貨期時間與加工任務(wù)剩余加工時間之比區(qū)分，緊急程度高的加工任務(wù)具有優(yōu)先分配加工設(shè)備的特權(quán)。公式描述如下：

1.2.3 加工設(shè)備投標內(nèi)容描述

本文針對的優(yōu)化目標為單個任務(wù)最小完工時間和同一時刻到達某類加工設(shè)備的多個任務(wù)負載分配均衡，加工設(shè)備進行投標時標書內(nèi)容為自身最早空閑時間。

式中：Mw為加工設(shè)備當(dāng)前剩余加工時間；w為加工設(shè)備編號；p為加工設(shè)備緩沖區(qū)工件數(shù)；mtkz表示緩沖區(qū)內(nèi)待加工工件待加工工序的預(yù)計總加工時間;Tu為本設(shè)備最早空閑時間。

1.2.4 調(diào)度機決策機制描述

集群調(diào)度機根據(jù)收到的標書進行任務(wù)分配，集群調(diào)度機接收到任務(wù)集及標書集后按緊急程度數(shù)值對任務(wù)集進行排序，緊急程度高的任務(wù)具有優(yōu)先分配加工設(shè)備的特權(quán)，調(diào)度機遵循的目標函數(shù)為

式中：m為被安排加工任務(wù)的加工設(shè)備數(shù)；dtk為第k臺加工設(shè)備預(yù)計完成分配加工任務(wù)的時間；Ω為均衡度方差，Ω越小表示對同一時刻到達該類加工設(shè)備的多個任務(wù)負載分配越均衡。

2 基于改進合同網(wǎng)協(xié)議的集群化管理調(diào)度策略

集群調(diào)度機是本種車間資源的均衡調(diào)度裝置，當(dāng)車間接收到一批新的加工任務(wù)或某工件的本道工序加工完成后，對應(yīng)地由車間服務(wù)器或當(dāng)前加工設(shè)備向下一道工序所用加工設(shè)備類型的集群調(diào)度機發(fā)送請求信息，集群調(diào)度機向本集群內(nèi)所有加工設(shè)備進行招標，通過優(yōu)化算法得出最優(yōu)的調(diào)度方案，具體調(diào)度策略如圖2所示。

圖2 基于改進合同網(wǎng)協(xié)議的集群化管理調(diào)度策略

集群調(diào)度機收到同時到達的多個任務(wù)后向集群內(nèi)所有加工設(shè)備發(fā)布招標信息：1） 集群內(nèi)加工設(shè)備對自身狀況進行計算，將自身最早空閑可用時刻作為標書反饋給集群調(diào)度機進行競標；2）集群調(diào)度機對加工任務(wù)的緊急程度進行計算，依據(jù)緊急程度對任務(wù)序列進行升值排序；3）集群調(diào)度機按照任務(wù)序列順序和收到的標書分配加工設(shè)備，緊急程度高的加工任務(wù)優(yōu)先分配加工設(shè)備，得到多種組合的調(diào)度方案；4）集群調(diào)度機對每種調(diào)度方案進行評估，根據(jù)決策依據(jù)選擇Ω最小的調(diào)度方案作為最優(yōu)調(diào)度結(jié)果；5）集群調(diào)度機向集群內(nèi)對應(yīng)設(shè)備發(fā)送調(diào)度結(jié)果；6）集群內(nèi)設(shè)備向集群調(diào)度機回復(fù)確認信息，調(diào)度完成。

3 實驗驗證

為驗證本文提出的調(diào)度機制的可行性，使用MATLAB進行了模擬仿真實驗。實驗的初始條件設(shè)定為：1）有4類加工資源，分別為車床、銑床、鉆床、磨床；2）各種加工資源數(shù)量為車床2臺、銑床2臺、磨床2臺，由集群調(diào)度機進行集群化管理，此外設(shè)置鉆床1臺；3）有6個任務(wù)工件需要加工，各任務(wù)工件加工工序信息如表1、表2所示。

表2 T0時刻開始加工的加工任務(wù)信息

起始時刻表1中的工件1、2、3同時開始加工，T0時刻表格2中的工件4、5、6同時開始加工，以此來模擬加工過程中投入新的加工訂單，本實驗中T0取2.5 h，調(diào)度結(jié)果的甘特圖如圖3所示。

圖3 調(diào)度結(jié)果甘特圖

表1 起始時刻開始加工的加工任務(wù)信息

T0時刻車間接收到新訂單，工件4、5、6投入生產(chǎn)，三者第一道工序均為銑削，此時工件2也到達銑削工序，集群調(diào)度機同時對4個任務(wù)請求、2臺銑床進行任務(wù)分配，結(jié)果顯示，最佳調(diào)度結(jié)果中緊急程度高的工件2、4優(yōu)先加工，且同一時刻到達銑床集群的加工任務(wù)負載分配均衡。

4 結(jié)論

車間資源配置的合理性直接決定著產(chǎn)品的生產(chǎn)總時長以及生產(chǎn)車間的運行效率、生產(chǎn)效益，本文重點研究了對同類加工資源有多個任務(wù)同時到達的問題以及緊急訂單問題，提出了一種對車間同類加工資源進行集群化管理的調(diào)度模式，并通過仿真實驗證明了本文調(diào)度方案的可行性，實驗結(jié)果表明，本方案能夠有效地解決車間實時接受新訂單、同一時刻有多個任務(wù)到達某類加工設(shè)備、緊急訂單等問題，使制造系統(tǒng)呈現(xiàn)出智能性、高效性。