多Agent分布式車間動(dòng)態(tài)調(diào)度仿真系統(tǒng)研究

宋 娟

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

0 引言

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

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

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

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

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

生產(chǎn)調(diào)度系統(tǒng)由管理Agent、資源Agent和工件Agent組成，從面向?qū)ο蟮挠^點(diǎn)看，這些Agent分布在不同的物理環(huán)境中，通過(guò)局域網(wǎng)連接在一起。考慮到系統(tǒng)的規(guī)模需要，在仿真系統(tǒng)中，系統(tǒng)層設(shè)有1個(gè)管理Agent，每個(gè)單元設(shè)一個(gè)單元管理Agent，下設(shè)若干資源Agent和工件Agent。

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

2 MASS仿真系統(tǒng)設(shè)計(jì)

2.1 面向?qū)ο蟮腗ASS仿真功能模型

按照上述系統(tǒng)模型，設(shè)計(jì)了面向?qū)ο蟮姆抡嫦到y(tǒng)功能，結(jié)構(gòu)如圖2所示。

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

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

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

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

2.3 通信的實(shí)現(xiàn)

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

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

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

3.1 實(shí)驗(yàn)系統(tǒng)結(jié)構(gòu)

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

3.2 仿真實(shí)驗(yàn)

設(shè)計(jì)本次試驗(yàn)的目的是驗(yàn)證MASS的可行性。試驗(yàn)中，任務(wù)的分配與執(zhí)行調(diào)度選擇先進(jìn)先出（FIFO）調(diào)度策略。

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

[2] 喬兵, 等. 基于Agent的分布式動(dòng)態(tài)作業(yè)車間調(diào)度[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實(shí)戰(zhàn)[M]. 北京: 機(jī)械出版社,2010.