多Agent分布式車間動態調度仿真系統研究

宋 娟

（寧夏大學 物理電氣信息學院，銀川 750021）

0 引言

制造車間調度問題（Job Shop Scheduling Problem，JSSP），是典型的NP-hard問題[1]，并且被認為是最難解決的問題之一。另外，由于車間調度問題是多目標的，具有復雜性和動態隨機性，致使不確定時間出現的頻率明顯高于傳統的制造環境，生產調度更多的表現為動態調度問題。

為適應時代化制造系統對柔性和快速重組的要求，提出以分布式MAS作為新的運作模式，綜合OOT技術和CORBA通信機制，設計并實現了一種分布式制造車間調度仿真平臺MASS，實現現代制造車間生產過程的動態調度，為將來MASS的實用化奠定基礎。

1 MASS仿真系統的組成和相互關系

以典型的機械加工車間作為生產調度仿真系統的原型。為了滿足生產調度的功能要求，該車間按照生產單元布局，每個單元中的機器至少能完成一種或是一類工件任務的加工，同時每個工件任務可有一個或多個單元完成。MASS基本布局如圖1所示。

圖1 基于MAS的分布式車間調度系統模型

生產調度系統由管理Agent、資源Agent和工件Agent組成，從面向對象的觀點看，這些Agent分布在不同的物理環境中，通過局域網連接在一起?？紤]到系統的規模需要，在仿真系統中，系統層設有1個管理Agent，每個單元設一個單元管理Agent，下設若干資源Agent和工件Agent。

多Agent系統（Multi-agents System）放松了對集中式、規劃和順序控制的限制，提供了分散控制、應急和并行處理，提供更快速的問題求解。這樣，制造系統便可以通過分布在車間里的資源和個體Agent之間的聯合來實現系統的集成。

2 MASS仿真系統設計

2.1 面向對象的MASS仿真功能模型

按照上述系統模型，設計了面向對象的仿真系統功能，結構如圖2所示。

2.2 Agent之間協商機制

由于車間調度問題是多目標的，具有復雜性和動態隨機性， Agent在做出自身決策的同時還要考慮系統內其他Agent的行為，系統的整體目標需要由Agent共同實現。因此，Agent之間的協作尤為重要。建立良好的協商、合作策略是Agent有效完成調度任務的基礎，也是各Agent解決不同問題所采用具體調度策略的基礎。

圖2 仿真系統的功能模型

在這個系統中有至少兩種Agent：管理Agent（Manage Agent，MA）和 下 級 Agent（Subagent，SA）。在 MASS中，單元 Agent、資源 Agent和工件Agent 都可以看作是MA的subagent。其中，MA負責任務的分解，監視任務的執行，并處理運行結果；SA負責任務的真正執行。

2.3 通信的實現

良好的通信機制是實現Agent之間信息交換與互操作的基礎手段。Agent之間的通信可以采用基于WinSock的消息傳遞機制實現，也可以采用面向對象的中間件技術CORBA實現。這里采用CORBA技術實現MASS底層通信。CORBA作為分布式開放系統的互連協議，可以突破以往基于參數傳遞信息的局限，提供了以對象為中心的互操作技術。

根據Agent通信的要求，運用CORBA復雜對象包裝/傳遞技術，即設計人員必須定義對象的狀態如何在網絡上傳輸的包裝函數（marshalling functions）和接收過程的解包函數（unmarshalling function），定義了三類Agent的IDL接口，可以支持異構Agent之間的通訊與互操作。

3 MASS仿真系統實現

3.1 實驗系統結構

系統按照如圖1所示的布局，在仿真系統中設計了三個生產單元CA(Cell Agent)，每個單元都有三類機床：車床Lathe、磨床Mill和鉆床Dill，每類有若干不同型號的機床可供選擇。每個機器各有一個輸入和輸出緩沖區，分別能存放一個工件；每個單元有一個公共存儲區；每個單元內各設兩個AGV為這些機器運進所需的原料、運出操作完的工件。

3.2 仿真實驗

設計本次試驗的目的是驗證MASS的可行性。試驗中，任務的分配與執行調度選擇先進先出（FIFO）調度策略。

1）管理Agent從調度任務表Task_list中選擇優先級最高的任務，采用多點傳送的方式，參考知識庫中的信息，向有能力的單元CA1、CA2和CA3發布任務。任務包包括訂單編號、工件編號、數量、工序和交貨期，每一項操作信息為一個五元組，運行實例中發布的任務包為：

＜Order_No，Part_No，Quantity，Operation，Due_Date＞ = ＜Order1，Patrt3，2，3，186＞；

2）一旦CA1、CA2和CA3接到發布的任務信息，將接到的任務信息作為一個記錄保存在任務表單Task_list中，參考工藝數據庫中任務相關數據，包括加工設備類型，加工時間和服務成本，加工單元CA1預調度結果；

3）管理Agent從落選的兩個單元Agent中選擇一個作為后備單元，將相關信息保存起來，以備出現機器故障、任務拖延等異常情況時使用，目的是減少事故的處理時間、降低事故損害。同時，管理Agent還要通告單元CA2和CA3，結束該次任務的協商分配、過程。

實驗結果證明了MASS能夠完成預期的調度任務。雖然調度結果不是最優，但MASS調度問題的求解與通訊時間包含在工件的整個加工流動當中，求解時間短，響應速度快，應用于動態調度具有一定優勢。

4 結束語

由于采用多Agent結構與基于CNP的調度協商機制，使現代制造車間動態調度得以有效實施。通過運用面向對象方法對MASS建模，設計并實現了一種開放式、動態變化MASS分布式仿真系統。通過CORBA機制實現了Agent之間的通信，模擬了制造車間多目標優化調度過程。實驗結果證明該系統可應用于MAS控制系統仿真、設計及實際運行控制。Agent具有的智能性、自治性及合作能力等許多優良特性，為解決現代制造系統的車間動態調度問題提供了一條新的有效途徑。

[1] Nabil Nasar, Elsayed EA. Job Shop scheduling with alternative machines[J]. International Journal Production Research, 1990, 28(9): 1595-1609.

[2] 喬兵, 等. 基于Agent的分布式動態作業車間調度[J]. 信息與控制, 2001, 30(4): 293-296.

[3] Garey M R, Johnson D S, Sethi R. The Complexity of Flow-shop and Job shop Scheduling, Math.Oper.Res. 1976,117-129.

[4] 邱郁惠. 系統分析師UML實戰[M]. 北京: 機械出版社,2010.