基于多Agent的柔性作業車間調度研究

潘 穎， 孫 偉， 馬 躍， 馬 沁 怡

（1.大連理工大學 機械工程學院，遼寧 大連 116024；2.大連海洋大學 機械學院，遼寧 大連 116023）

0 引 言

近年來，具有多目標優化的柔性作業車間調度問題（flexible job－shop scheduling problem，簡稱FJSP）成為研究的熱點[1].在實際調度過程中，需要綜合考慮生產的各個環節和因素，對多個目標進行分析決策，而通常這些目標之間又是相互沖突的.與傳統的作業車間調度比較，FJSP是傳統 作 業 車 間 調 度 問 題 （job－shop scheduling problem，JSP）的擴展，是更復雜的 NP－Hard問題[2]，其任務中的每道工序可在多臺機床上進行，并且在不同的機床上所需時間不同.FJSP減少了機器約束，擴大了可行解的搜索范圍，增加了問題的難度.因此，FJSP除了要解決JSP中的確定加工順序外，還要解決某工序由哪臺機床進行的問題，因而求解更加復雜.

近年來，多目標FJSP的研究出現了很多新的智能優化方法[3～7]，使得多目標FJSP的研究方法向多元化方向發展.其中，遺傳算法利用生物進化機制，在一個較大的初始解空間中通過優勝劣汰的方法進行優化求解，具有尋優能力強、計算速度快、原理簡單、魯棒性好、通用性強、不受限制性條件的約束，具有隱含并行性和全局解空間搜索能力的特點，因此，在生產調度領域得到廣泛應用，用遺傳算法解決FJSP近年也取得了豐碩的成果[8].

同時，多Agent系統（MAS）由于其本身的分散自治性、網絡合作性、結構開放性、智能性等特點，也已成為調度研究領域的前沿和熱點[9].

針對多目標FJSP的特點，本文提出一種基于多Agent的多目標柔性作業車間調度方法，運用MAS對柔性車間生產調度過程建模，其中特別構建策略Agent來實現調度及生產上的實時調控，并在策略Agent中封裝改進的遺傳算法，最后通過實例對所提的調度方法進行驗證.

1 基于MAS的調度模型

1.1 問題描述

設生產系統有n個工件，每個工件有p個工序.各工序均可在m臺設備中的一臺或多臺上進行.由于各設備的性能、特點不同，某設備k對各個工序Oij的加工時間為Tkij（其中工件號i∈N＝ ｛1，2，…，n｝，工序號j∈P＝ ｛1，2，…，p｝，設備號k∈M＝ ｛1，2，…，m｝）.

取設計變量

其中0－1變量表示工序和設備的選擇關系＝1表示工序Oij在設備k上進行；整數變量ORDij表示工序Oij的加工順序，數值小者順序靠前.

多目標FJSP優化數學模型如下：式（3）是根據權重W不同，分別取最長完工期、單臺設備最大負載、全部設備總負載和總加工成本，或它們的任意組合最小化為優化目標，并計算工序的完成時刻；式（4）表示設備k的工作時間；式（5）表示全部設備的總工作時間；式（6）表示總加工成本；式（7）保證每工序只在一臺設備上進行；式（8）保證同一工件各工序的順序；式（9）保證ORDij取得1～pn的組合；式（10）保證各工序的開始加工時刻或者為零，或者要在同一設備前一工序完工之后.即

式中：中間變量STij、ETij表示工序Oij的加工開始與完成時刻；METk、MWT表示設備k的工作時間和全部設備的總工作時間；COST為總加工成本；Ck為設備k的工時成本.

1.2 基于MAS的車間調度模型

本調度系統主要由設備Agent（device agent，DA）、任務 Agent（task agent，TA）和策略Agent（strategy agent，SA）組成，如圖1所示.TA與DA、TA與SA、TA與TA之間可以通信.TA在確定好DA后，會在DA對應的設備時間軸上選擇合適的位置，也即安排工序至此設備，實現調度功能.

圖1 基于MAS的柔性作業車間調度模型Fig.1 FJSP model based on MAS

1.2.1 設備 Agent 設備 Agent（結構見圖2）是車間中加工設備的代理，每臺加工設備對應一個設備Agent，設備Agent通過設備接口可獲得加工設備的技術參數和設備狀態等信息，再把加工任務發送給加工設備執行.設備Agent可與任務Agent交互信息，實現任務資源分配，并向任務Agent反饋狀態信息.

圖2 設備Agent結構Fig.2 Structure of device agent

Agent可分為慎思型、反應型和混合型.設備Agent本身不需要具有判斷和推理能力，它的主要作用是動態地標定自身狀態，并激發其他Agent的進程，因此，設備Agent被設計成反應型Agent.

1.2.2 任務 Agent 任務 Agent（結構見圖3）為慎思型.它根據到達的任務動態地生成.每道工序會對應一個任務Agent，該工序的生產調度過程及相關數據都由其對應的任務Agent管理.任務Agent撤銷即代表該工序已完成.日志數據庫中保存生產調度過程中形成的數據.

圖3 任務Agent結構Fig.3 Structure of task agent

任務Agent通過與策略Agent交互，將設備Agent投招標和優化目標等信息及時傳遞給策略Agent，然后從策略Agent得到調度方案后調配，最終將生產任務下達到設備，確定工序的加工設備和開始加工時間.

任務Agent與其他任務Agent交互信息，傳遞完成任務所必須滿足的前繼和后繼條件，在滿足先后順序約束的條件下使任務能實現實時推進；與設備Agent交互信息，為任務分配適當的資源，并監測和監控任務的執行情況及資源的負載情況；與策略Agent交互信息，實現實時動態調度.

1.2.3 策略 Agent 策略 Agent（結構見圖4）為慎思型.其與任務Agent交互可實現動態實時調度，且因其內部封裝了算法和調度規則，其在接受任務Agent的信息后，能提供不同調度方案并返回任務Agent；提供人機接口，可調整算法參數，制定新的調度方案.

策略Agent是基于MAS的車間調度核心部分，對車間的動態調度有效執行起關鍵作用.考慮到job－shop中存在的多目標優化、柔性作業、有JIT要求等調度問題，在策略Agent中特別封裝了一種改進遺傳算法，以實現車間調度所應達到的高效、穩定.本文并沒有把算法規則封裝在任務Agent中，而是獨立設計了一個策略Agent，這既保證了系統的可重構性、柔性，也便于系統的維護和升級.策略Agent模塊中設置了人機接口，保證當生產過程中有插單等緊急情況時，有可提供人工干預調度的能力.

圖4 策略Agent結構Fig.4 Structure of strategy agent

1.2.4 Agent間的協作模型 多Agent系統運作的基礎是彼此間的通信與協作.本文采用合同網方式實現多Agent的控制，通過任務招標、投標和訂立合同進行合作.

（1）Agent間的協作

利用招標－投標－中標機制，任務Agent確定完成某一任務的設備Agent，設備Agent與此任務Agent簽訂合同后執行相應生產任務.在整個生產過程中，任務Agent將遇到的緊急突發狀況（如人員和設備的選擇與沖突等）反饋至策略Agent，由策略Agent提供相應解決方案，根據情況或者由系統自帶算法調整重排生產任務，或者通過人機交互，手動重排生產任務.

（2）合同網機制

任務 Agent：TA＝ ｛TA1，TA2，…，TA np｝，np為分解后的工序數.傳遞如下消息內容：｛Qij，Dij，Lij，Cij，DSij｝；Qij為工序Oij的作業量，Dij為該任務所需設備表，Lij為完工期限，Cij為其他約束，DS ij為任務描述.然后由任務Agent并發地向可加工該工序的所有的設備Agent廣播，消息格式為｛Qij，Oij，Lij，Cij，DSij｝；Qij為需執行的作業量，Oij為作業名稱，Lij為完工期限，Cij為其他約束，DSij為任務描述.設備Agent收到招標書后，根據標書內容（任務時間、優先級等）和自己的能力、狀態等決定是否投標.按如下格式返回任務Agent：｛TB k，Qk，T k｝；TB k為該設備可執行的時間段表，Qk為保證期限的最大作業量，Tk為期限截止前該設備可利用時間.任務Agent根據收到的標書和自身的策略進行評價，選出中標者，并將任務分配給中標的設備Agent，確認消息，格式為｛Oij，Qij，Lij，Cij，DSij｝；Oij為作業名稱，Qij為需執行的作業量，Lij為完工期限，Cij為任務約束，DSij為任務描述[10].中標者更新自身知識庫，執行子任務并返回結果，如果最大作業量小于任務要求作業量，任務Agent會考慮由數個設備承擔；如仍無法辦到，則通知策略Agent無法承擔所分配任務；策略Agent若根據一定的規則調整未果，則發出警報，操作人員可通過人機接口，手動強制執行或調整生產計劃，必要時或尋求外協.

最后，任務Agent提交給車間生產任務管理系統任務的完成情況，同時注銷相應的任務Agent.在建立合同關系之后，任務Agent還需監測任務的執行情況，只要發現設備Agent處于過載、故障等狀態，就必須進行資源的轉移分配.如任務Agent自身不能調停處理，需反饋至策略Agent，策略Agent會根據需要修改計劃.所采用的多Agent的控制過程（基于合同網機制）如圖5所示.

圖5 合同網中投招標機制圖Fig.5 Tendering－bidding mechanism graph of contract net

2 基于遺傳優化的MAS調度算法設計

如前文所述，策略Agent為本MAS調度系統的核心一環，其中封裝了改進的遺傳算法以解決實際車間多目標優化的柔性作業調度問題，常見柔性作業車間調度加工時間如表1所示.

本文對于非完全柔性工序（即存在某設備k不能用來完成工序Oij），人為地將加工時間T kij改為很大值，如取為1000.這樣在優化過程中，算法會自動規避這樣的工序設備選擇.同時引入對所有設備加工時間都是0的虛工序，可以保證各工件的工序數一致.于是原問題工時表變為表2.

表1 一般的柔性作業車間調度問題加工時間Tab.1 Processing time of general FJSP

表2 規劃為標準FJSP后的加工時間表Tab.2 Processing time after transforming into standard FJSP

2.1 多目標優化

實際車間通常會有不同的目標要求，生產中常見的優化目標為最長完工期、單臺設備最大負載、全部設備總負載和總加工成本最小化.本文分兩步實現多目標規劃：第一步分別取各單目標為遺傳算法的適應度函數，得到各自的較優值z＊1、z＊2、z＊3和z＊4；第二步取各目標的歸一化加權組合作為適應度函數進行遺傳優化.權重可根據實際情況進行設置調整，或者自動調整（如側重總加工成本最小化，可設置其相應權重系數大于其他目標函數權重系數）.實驗證明，通過合理調整權重，該方法能較好地協調各目標，快速獲得具有實際應用價值的解.

2.2 遺傳算法設計

（1）編碼方式

本文采用直接編碼，由兩部分組成：第一部分為基于工序排列的編碼，用來確定工序的加工順序；第二部分為基于機器分配的編碼，用來選擇每道工序的加工機器.編碼

圖6 解碼流程圖Fig.6 Flow chart of decoding

表示工序O31第1個安排，在M4上加工；工序O11第2個安排，在M1上加工；其余依次類推.

（2）群體初始化

隨機生成population size個染色體個體.

（3）適應度函數

直接取目標函數為適應度函數.

（4）解碼方式

解碼分為3個步驟：首先按基因中的順序與設備選擇，依次將各工序投射對應到設備；然后考慮各工序加工時間進行整理，獲得各工序的開始和結束時刻、各設備工作時間和結束時刻、車間工作終止時刻ENDTIME；最后按照單目標或多目標要求生成適應度函數.解碼過程的流程圖如圖6所示.PUTIN（x，y）為插入矩陣，x代表插入順序，PUTIN（x，1）、PUTIN（x，2）、PUTIN（x，3）分別代表工件號、工序號和設備號；ST（i，j）、ET（i，j）、MET（k）、MWT（k）分別代表工序開始時刻、結束時刻、設備空閑時刻和設備工作時間；F（i，j）是工序插入完成標志；pn為工序總數.

（5）遺傳算子的設計

①選擇算子：選擇操作采用精英機制（elite），即直接將適應度最好的elite count個染色體個體直接遺傳到下一代.

②交叉與變異算子：交叉操作和變異操作的父代在精英機制后剩下的個體中產生，采用錦標制tournament即從隨機選取的tournament size個染色體個體中選擇適應度最好的個體作為交叉與變異的父代；在生成的父代中按crossover fraction進行交叉，余下部分進行變異操作.

a.交叉算子

選擇兩個父代，等比隨機進行交叉.有兩種方式：總體取父代1，某插入順序取父代2，這會出現不合理排列，在解碼過程會解決；總體取父代1，某設備選擇改為父代2.

b.變異算子

按比例隨機選擇進行3種交叉：調換插入順序；調換設備；隨機更改設備.其中第3條能保證排除弱智方案.

可見，以上的算子可以保證子代的基因值總是有效的，這樣就保證了算法運行時不會生成無效基因，從而有利于提高算法的可靠性和效率.

（6）遺傳算法的操作步驟

①初始化，隨機生成population size個染色體個體；

②求解各單目標最優值；

③構造等權多目標函數；

④利用GA搜索；

⑤判斷優化結果能否被接受，是則終止，否則繼續；

⑥人工：根據方案指標與實際需求，決定調整方向；自動：根據方案指標與范圍約束，決定調整方向，或根據模糊規則決定調整方向；

⑦根據⑥的決策調整權重；

⑧轉④.

（7）運行參數

遺傳算法的運行參數為populationsize＝200，elitecount＝ 7，tournamentsize＝ 3，crossoverfraction＝0.2，generations＝200.

3 實例驗證

山西太原某公司機械車間的調度屬于典型的多目標柔性job－shop調度，該制造單元有9臺進口設備，包括并行機和多功能加工中心，各加工設備代號、每單位工時的加工成本，及對不同工件各工序的加工時間如表3、4和5所示.

應用本文提出的基于多Agent的車間調度模型及優化調度算法開發了生產管理軟件.圖7為多目標調度參數界面，可選擇調度任務，并可選擇預調度先查看調度結果.如有不合適之處，可人工調整；如果符合，則可選擇正式調度并執行“開始”.在優化參數一欄，可人工修改遺傳算法參數，否則就是系統默認的參數值.優化目標部分，在各優化目標后面方框中的數字代表不同權重，數值大小可調.優化參數和優化目標權重值的調整會影響調度時間和結果，可根據工廠車間實際要求做出調整.多目標優化的選擇，只要在優化目標處勾選相應的目標即可.如圖8顯示的是以成本和工期最小為多目標優化的甘特圖，在優化目標處選中“最小成本”和“最短工期”，“0%”表明該道工序尚未進行，完成進度為0.圖9顯示的是最小成本、最短工期和最小全部設備負載為多目標的優化調度甘特圖.調度結果顯示為不同設備加工不同工序的甘特圖.

表3 設備代號對應表Tab.3 Corresponding device code

表4 設備加工成本Tab.4 Processing cost of device

表5 設備加工時間表Tab.5 Processing time of device

綜上可知，該車間優化調度系統可動態及時調整調度結果，并可人工調整相應參數以滿足不同的調度要求，最終實現車間實時動態多目標調度.

圖7 多目標調度參數界面Fig.7 Parameters interface of multi－objective scheduling

圖8 多目標優化（成本＋工期最小）調度結果Fig.8 Scheduling result of multi－objective optimization（minimum cost and makespan）

圖9 多目標優化（成本＋總負載＋工期最小）調度結果Fig.9 Scheduling result of multi－objective optimization （minimum cost，total load and makespan）

4 結 論

本文針對多目標柔性作業車間調度問題提出的基于多Agent的車間調度系統結構簡單，便于系統維護和升級，并保證了系統的可重構性和柔性，能滿足車間柔性作業、多目標優化等實際問題的要求.實踐證明，該調度系統適用于復雜的柔性車間作業調度環境，適應性和自治性較高，能保證車間生產持續優化地進行，應用前景廣闊.

[1]GAO Jie，GEN Mitsuo，SUN Lin－yan，etal.A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems[J].Computers ＆ Industrial Engineering，2007，53（3）：149－162

[2]BLAZEWICZ J，FINKE G，HAOPT G.New trends in machine scheduling [J].European Journal of Operational Research，1988，37（2）：303－317

[3]CHEN H，IHLOW J，LEHMANN C.A genetic algorithm for flexible job－shop scheduling [C]//IEEE International Conference on Robotics and Automation.Detroit：IEEE，1999：1120－1135

[4]JIA H Z，NEE A Y C，FUH JY H，etal.A modified genetic algorithm for distributed scheduling problems[J].International Journal of Intelligent Manufacturing，2003，14（3）：351－362

[5]HO N B，TAY J C.GENACE：An efficient cultural algorithm for solving the flexible job－shop problem[C]//IEEE International Conference on Robotics and Automation.Detroit：IEEE，2004：1759－1766

[6]KACEM I，HAMMADI S，BORNE P.Approach by localization and multiobjective evolutionary optimization for flexible job－shop scheduling problems[J].IEEE Transactions on Systems， Man，and Cybernetics，Part C，2002，32（1）：1－13

[7]KACEM I，HAMMADI S，BORNE P.Pareto —optimality approach for flexible job－shop scheduling problems：hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation，2002，60（2）：245－276

[8]PEZZELLA F，MORGANTI G，CIASCHETTI G.A genetic algorithm for the flexible job－shop scheduling problem [J].Computers ＆ Operations Research，2008，35（5）：3202－3212

[9]饒運清，謝 暢，李淑霞.基于多Agent的Job Shop調度方法研究[J].中國機械工程，2004，15（5）：873－877

[10]潘 穎，張文孝.基于多agent的離散制造業制造執行系統框架研究[J].計算機應用研究，2009，26（1）：244－249