宋 娟

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

0 引言

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

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

1 MASS仿真系統(tǒng)的組成和相互關系

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

圖1 基于MAS的分布式車間調度系統(tǒng)模型

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

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

2 MASS仿真系統(tǒng)設計

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

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

2.2 Agent之間協(xié)商機制

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

圖2 仿真系統(tǒng)的功能模型

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

2.3 通信的實現(xiàn)

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

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

3 MASS仿真系統(tǒng)實現(xiàn)

3.1 實驗系統(tǒng)結構

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

3.2 仿真實驗

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

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

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

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

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

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

4 結束語

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

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

[2] 喬兵, 等. 基于Agent的分布式動態(tài)作業(yè)車間調度[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] 邱郁惠. 系統(tǒng)分析師UML實戰(zhàn)[M]. 北京: 機械出版社,2010.