基于信息素的協(xié)調(diào)機(jī)制與任務(wù)分配研究

王 雷 唐敦兵 袁偉東

1.南京航空航天大學(xué)，南京，210016 2.中國(guó)船舶重工集團(tuán)公司第七0二研究所，無(wú)錫，214082

0 引言

隨著以全球化、動(dòng)態(tài)化和用戶驅(qū)動(dòng)為顯著特征的市場(chǎng)競(jìng)爭(zhēng)的加劇，制造業(yè)面臨著越來(lái)越大的挑戰(zhàn)。因此，現(xiàn)代制造系統(tǒng)的運(yùn)行環(huán)境越來(lái)越充滿了不確定性，系統(tǒng)的生產(chǎn)任務(wù)經(jīng)常是動(dòng)態(tài)變化的，如不可預(yù)知任務(wù)的到達(dá)、增加和減少等。這些諸多的不確定因素，要求制造系統(tǒng)有一個(gè)良好的協(xié)調(diào)機(jī)制來(lái)快速地響應(yīng)這些不確定性，從而在滿足制造環(huán)境約束（如加工先后次序、交貨期、設(shè)備負(fù)荷率等）的前提下，使得任務(wù)與資源得到合理的匹配。目前，任務(wù)分配的求解方法主要有基于拉格朗日松弛法的協(xié)調(diào)[1]、基于合同網(wǎng)（contract net protocol，CNP）的協(xié)調(diào)以及改進(jìn)的CNP協(xié)調(diào)[2－5]、基于Petri網(wǎng)的協(xié)調(diào)[6－7]和基于生物行為的協(xié)調(diào)[8－9]等。

然而，拉格朗日松弛法也是一種給予最優(yōu)化方法的啟發(fā)式算法，因?yàn)樗惶峁┍ＷC最優(yōu)化的解。因此，這種方法并沒(méi)有得到廣泛的應(yīng)用?；赑N協(xié)調(diào)方法具有較強(qiáng)的建模能力，但存在建模復(fù)雜、效率低等問(wèn)題。CNP模型可以成功地解決一個(gè)任務(wù)Agent在多個(gè)資源Agent之間的分配問(wèn)題?；贑NP的協(xié)作是一種顯式的協(xié)調(diào)機(jī)制，即參與合作的一方明確地向另一方提出合作要求。但隨著任務(wù)的復(fù)雜，系統(tǒng)環(huán)境的動(dòng)態(tài)變化，傳統(tǒng)的CNP模型越來(lái)越顯示其突出的問(wèn)題，影響了協(xié)商過(guò)程中任務(wù)完成的效率，因此，出現(xiàn)了改進(jìn)的CNP協(xié)調(diào)機(jī)制。對(duì)基于CNP協(xié)調(diào)機(jī)制的改進(jìn)主要是引進(jìn)他信度和閾值等概念，以達(dá)到提高CNP合作效率的目的[2－3]。盡管如此，基于 CNP協(xié)調(diào)機(jī)制仍然存在以下問(wèn)題，如信息通信量大[9－10]、資源消耗大、計(jì)算量大、計(jì)算效率低、不確定性突出、決策效率低、容易出現(xiàn)死鎖現(xiàn)象等。

基于生物行為的協(xié)調(diào)方法源自對(duì)群居動(dòng)物行為的觀察。螞蟻的探路方法就是一個(gè)很好的實(shí)例[11]。螞蟻在尋找從蟻穴到食物源的路徑時(shí)，不能從外界環(huán)境中得到任何關(guān)于路徑的全局信息。螞蟻會(huì)在它經(jīng)過(guò)的路徑上留下一定量的化學(xué)物質(zhì)（信息素），并可以感知到路徑上的信息素。通過(guò)這種化學(xué)物質(zhì)，使得蟻群具有強(qiáng)大的尋優(yōu)能力。與基于CNP的談判方法不同，基于行為的方法是一種隱式合作，各螞蟻之間沒(méi)有明確直接的協(xié)調(diào)與合作行為，各個(gè)螞蟻甚至可以不知道其他螞蟻的存在。各個(gè)螞蟻只是依據(jù)系統(tǒng)的“暗示”來(lái)采取行動(dòng)[12]。各個(gè)螞蟻依據(jù)其內(nèi)建的合作機(jī)制采取行動(dòng)，每個(gè)螞蟻的行動(dòng)都在一定程度上對(duì)群體的利益做出貢獻(xiàn)。蟻群優(yōu)化算法（ant colony optimization，ACO）就是依照螞蟻覓食原理，設(shè)計(jì)出來(lái)的一種群智能算法，該算法在任務(wù)分配問(wèn)題[13]、作業(yè)調(diào)度[14]等組合優(yōu)化問(wèn)題上得到了廣泛的研究與應(yīng)用，但關(guān)于蟻群算法的研究幾乎都是從優(yōu)化的角度去考慮的。

本文針對(duì)CNP協(xié)調(diào)機(jī)制在制造系統(tǒng)任務(wù)分配過(guò)程中存在的問(wèn)題，基于生物行為的協(xié)調(diào)方法，設(shè)計(jì)了基于信息素的隱式協(xié)調(diào)方法，從控制的角度研究生產(chǎn)任務(wù)分配的協(xié)調(diào)控制問(wèn)題，并通過(guò)具體實(shí)例驗(yàn)證了該方法的有效性和可行性，為任務(wù)分配的協(xié)調(diào)控制提供一種可行的解決方案。

1 制造系統(tǒng)任務(wù)分配模型

制造系統(tǒng)的任務(wù)一般能夠在許多單元內(nèi)部完成加工，問(wèn)題是如何在滿足單元負(fù)荷率的前提下，保證總的加工成本最小?；诖?，本文首先建立如下以成本為目標(biāo)的數(shù)學(xué)模型和約束條件：

式中，j為任務(wù)，j＝1，2，…，n；i為制造單元，i＝1，2，…，m；k為單元i的設(shè)備；tjik為任務(wù)j在單元i中的設(shè)備k上加工所需要的加工時(shí)間；dj為任務(wù)j的交貨期；cji為任務(wù)j在單元i中加工的完成時(shí)間；cjik為任務(wù)j在單元i中的設(shè)備k上加工的完成時(shí)間，cjik＝cji（k－1）＋tjik；αji為任務(wù)j在單元i中的單位加工成本；βji為任務(wù)j在單元i中的單位庫(kù)存成本；γji為任務(wù)j在單元i中的單位延遲懲罰成本；Qj為任務(wù)j的數(shù)量；Tji為任務(wù)j在單元i中完成的最大遲誤時(shí)間，Tji＝max（0，cji－dj）；Eji為任務(wù)j在單元i中完成的最大提前交貨時(shí)間，Eji＝max（0，dj－cji）；f為任務(wù)j在單元i中的總成本；f1為任務(wù)j在單元i中的加工成本；f2為任務(wù)j在單元i中的庫(kù)存成本；f3為任務(wù)j在單元i中的延遲懲罰成本；f4為單元i的負(fù)荷率。

式（1）表示總成本，由加工成本（式（2））、庫(kù)存成本（式（3））和延遲懲罰成本（式（4））三部分組成。式（5）表明單元i的最大負(fù)荷率要小于1。

2 基于信息素的協(xié)調(diào)方法設(shè)計(jì)

在本文所設(shè)計(jì)的協(xié)調(diào)方法中，信息素僅僅被用作一種通信介質(zhì)。在基于Multi－Agent的車間層控制系統(tǒng)中，存在著多種Agent，如任務(wù)Agent、單元Agent和資源Agent等。為了更好地傳播信息素信息，不同的Agent（任務(wù)Agent、單元Agent和資源Agent）需要釋放相應(yīng)的螞蟻Agent。這些螞蟻Agent攜帶著信息素信息在車間系統(tǒng)中游蕩，以便有效地協(xié)調(diào)任務(wù)的加工。

在這個(gè)基于信息素的協(xié)調(diào)方法中，不同的螞蟻Agent有不同的游動(dòng)方向，它們能夠攜帶信息素信息向下游或向上游游動(dòng)。任務(wù)螞蟻Agent游動(dòng)方向是從上游到下游，然而，單元螞蟻Agent游動(dòng)方向是從下游到上游。它們分別釋放信息素信息到公共的環(huán)境中（圖1），這些信息以一定的時(shí)間周期被更新和保存。通過(guò)這種方式，這些信息素信息就可以被其他螞蟻Agent所感知并利用。

圖1 螞蟻Agent協(xié)調(diào)過(guò)程

由車間層向單元層傳遞信息素的信息用三元組來(lái)表示，即

式中，task＿id為任務(wù)的編號(hào)信息；quantity為任務(wù)數(shù)量信息；I為加工信息，包括加工工序、每一道工序需要的設(shè)備、交貨期等信息。

相反，由單元層向車間層傳遞的信息素信息也用三元組來(lái)表示，即

式中，cell＿id為單元的編號(hào)信息；c為成本信息；l為單元的負(fù)荷率信息。

當(dāng)任務(wù)到達(dá)到車間層，首先由任務(wù)Agent釋放一個(gè)任務(wù)螞蟻Agent，該任務(wù)螞蟻Agent攜帶著信息素信息ρ（task＿id，quantity，i）向下游移動(dòng)，然后該任務(wù)螞蟻Agent根據(jù)以下步驟選擇最具有吸引力的單元來(lái)加工該生產(chǎn)任務(wù)：

（1）上游的任務(wù)螞蟻Agent釋放信息素信息ρ（task＿id，quantity，i）到公共環(huán)境中。

（2）下游的任務(wù)螞蟻Agent感知該信息素信息ρ（task＿id，quantity，i）。

（3）如果下游的單元螞蟻Agent有能力接受該任務(wù)，那么單元螞蟻Agent將ρ（task＿id，quantity，i）信息經(jīng)過(guò)計(jì)算轉(zhuǎn)化成自己的信息素信息ρ（cell＿id，c，l），然后該單元螞蟻 Agent向上游游動(dòng)并將此信息釋放到公共環(huán)境中。

（4）當(dāng)任務(wù)螞蟻Agent感知一個(gè)較為合適的加工單元的信息素信息，然后將該信息進(jìn)行保存，在保存之前首先檢查該信息的有效性。

If（任務(wù)螞蟻Agent沒(méi)有該單元的信息）Then

｛保存該單元的信息素信息ρ（cell＿id，c，l）；｝

Else

｛任務(wù)螞蟻Agent對(duì)該單元的信息素信息進(jìn)行有效性檢查：

｛If（l＜1）Then

｛選擇該單元來(lái)加工該任務(wù)，并且更新該單元的信息素信息ρ（cell＿id，c，l）。｝

If（l＞1）Then

｛選擇滿足負(fù)荷率條件下的其他具有較小的生產(chǎn)成本的加工單元來(lái)加工該任務(wù)，并且保存該單元的信息素信息ρ（cell＿id，c，l）。｝

｝

｝

（5）重復(fù)步驟（1）～步驟（4）。

（6）結(jié)束信息素的釋放，直到所有的任務(wù)都選擇完合適的單元加工為止。

具體的實(shí)現(xiàn)流程見圖2。

圖2 基于信息素的隱式協(xié)調(diào)流程

3 基于信息素的協(xié)調(diào)機(jī)制效用分析

首先，基于信息素的隱式協(xié)調(diào)機(jī)制所需要的信息通信量小。我們可以通過(guò)一個(gè)簡(jiǎn)單的實(shí)例來(lái)印證這一優(yōu)越性。假設(shè)某一時(shí)刻有n個(gè)任務(wù)需要加工，制造系統(tǒng)中有m個(gè)制造資源都有能力完成這n個(gè)任務(wù)。假設(shè)應(yīng)用合同網(wǎng)的協(xié)調(diào)機(jī)制的話，每一個(gè)任務(wù)都要經(jīng)歷“標(biāo)書信息發(fā)布→投標(biāo)→中標(biāo)通知→簽約”這四個(gè)階段，需要（2m＋2）次通信，因此需要的總的通信量為（2nm＋2n）次。但是，如果利用基于信息素的協(xié)調(diào)方式，完成這些任務(wù)的調(diào)度和加工需要的總信息量為n（m＋2）次。隨著系統(tǒng)的復(fù)雜程度越來(lái)越高，基于信息素的隱式協(xié)調(diào)機(jī)制在通信量上的優(yōu)勢(shì)將會(huì)更加明顯。

其次，基于信息素的隱式協(xié)調(diào)機(jī)制在工作過(guò)程中通過(guò)螞蟻傳播信息素信息，各螞蟻的行動(dòng)策略都是“利他”原則，因此不會(huì)出現(xiàn)沖突和死鎖情況，而且都能夠得到最優(yōu)值或近優(yōu)值。而在基于CNP等的協(xié)調(diào)過(guò)程中，所有制造資源都設(shè)法使各自獲得最大的利益而采取不同的行動(dòng)方式。尤其是規(guī)模比較復(fù)雜時(shí)，盡管經(jīng)過(guò)多次協(xié)商，系統(tǒng)也最終達(dá)不到一致的結(jié)果。因此，合同網(wǎng)對(duì)系統(tǒng)性能的優(yōu)化并沒(méi)有保障。

再次，基于信息素的隱式協(xié)調(diào)機(jī)制中的各螞蟻只需要依據(jù)環(huán)境作為通信中介，加上幾條簡(jiǎn)單的行為規(guī)則和簡(jiǎn)單的通信就能實(shí)現(xiàn)較好的協(xié)調(diào)。各螞蟻的行動(dòng)策略都是“利他”原則，因此，基于信息素的隱式協(xié)調(diào)機(jī)制具有更好的易實(shí)現(xiàn)性。

最后，在基于信息素的隱式協(xié)調(diào)機(jī)制中，如果有資源出現(xiàn)故障，該資源只需要通過(guò)釋放資源螞蟻，然后該資源螞蟻將故障的信息素信息釋放到公共環(huán)境中，就不會(huì)有任務(wù)選擇該資源。當(dāng)有資源新加入制造系統(tǒng)時(shí)，相應(yīng)的資源螞蟻只需要到公共環(huán)境中感知由任務(wù)螞蟻釋放的信息素信息，如果有能力完成任務(wù)的話，只需要將相應(yīng)的任務(wù)信息素信息經(jīng)過(guò)計(jì)算轉(zhuǎn)化成自己的信息素信息，然后釋放到公共環(huán)境中，那么將會(huì)有任務(wù)螞蟻選擇該資源進(jìn)行加工。而在基于合同網(wǎng)的協(xié)調(diào)機(jī)制中，如果在加工過(guò)程中有資源出現(xiàn)故障，然而這個(gè)時(shí)候所有任務(wù)的分配在工件到達(dá)時(shí)都已經(jīng)完成，因此，前道工序任務(wù)的重新分配將直接導(dǎo)致后續(xù)任務(wù)的分配無(wú)效而必須重新分配。在這種情況下，任務(wù)的交貨期等約束常常會(huì)被推遲而得不到保證，任務(wù)的完工時(shí)間、生產(chǎn)成本等指標(biāo)將受到很大的影響。因此，基于信息素的隱式協(xié)調(diào)機(jī)制具有較強(qiáng)的魯棒性。

4 實(shí)例分析

某一生產(chǎn)車間由3個(gè)智能制造單元組成，現(xiàn)有4個(gè)任務(wù)需要加工，此4個(gè)任務(wù)均可在3個(gè)單元內(nèi)完成。單元1由設(shè)備1～設(shè)備4組成，單元2由設(shè)備5～設(shè)備8組成，單元3由設(shè)備9～設(shè)備12組成。任務(wù)的加工數(shù)量以及加工工藝信息見表1。庫(kù)存成本信息、延遲懲罰信息以及交貨期見表2。

表1 任務(wù)工藝信息表

表2 庫(kù)存成本等信息

現(xiàn)采用前面設(shè)計(jì)的基于信息素的協(xié)調(diào)方法對(duì)第一個(gè)訂單A001進(jìn)行協(xié)調(diào)，具體的實(shí)現(xiàn)步驟如前文所述。下面以第一個(gè)訂單A001為例詳細(xì)說(shuō)明各個(gè)單元的信息素信息的由來(lái)。

圖3、圖4和圖5分別為訂單A001在三個(gè)單元中的調(diào)度Gantt圖。根據(jù)圖3、式（2）、式（3）和式（4）求得訂單A001在單元1中的加工成本f1、庫(kù)存成本f2和延遲懲罰成本f3分別為f1＝6×（18×25＋12×20＋15×30）＝6840（元）、f2＝1×（210－135）＝75（元）、f3＝2×0＝0（元）。所以訂單A001在單元1中的總成本f＝f1＋f2＋f3＝6915（元）。又根據(jù)式（4）求得單元1的負(fù)荷率為f4＝max｛18×6，12×6，15×6｝／210＝0.51。因此，單元1的信息素信息可以表示為ρ（cell＿1，6915，0.51）。

圖3 訂單A001在單元1中的調(diào)度Gantt圖

圖4 訂單A001在單元2中的調(diào)度Gantt圖

圖5 訂單A001在單元3中的調(diào)度Gantt圖

同理，單元2和單元3的信息素信息分別可以表示為ρ（cell＿2，5063，0.65）和ρ（cell＿3，6545，0.43）。

因此，通過(guò)同樣的方法，每一個(gè)任務(wù)Agent都選擇合適的單元來(lái)完成其加工，協(xié)調(diào)結(jié)果見表3。從表3中可以看出，對(duì)任務(wù)A001Agent，由于cell＿2 Agent具有最小的加工成本，而且負(fù)荷率小于1，所以選擇該單元來(lái)承擔(dān)該任務(wù)。對(duì)任務(wù)A002 Agent，盡管cell＿2Agent具有最小的加工成本，但是其負(fù)荷率大于1，所以選擇cell＿3Agent來(lái)承擔(dān)該任務(wù)。同樣任務(wù)A003Agent和任務(wù)A004Agent分別選擇cell＿2Agent和cell＿3Agent來(lái)完成。因此，通過(guò)這種隱式的協(xié)調(diào)方法，各個(gè)螞蟻Agent的行為都是“利他”的，不存在反復(fù)協(xié)商的過(guò)程，可以大大減小系統(tǒng)通信量大，避免死鎖現(xiàn)象等。

表3 協(xié)調(diào)結(jié)果

5 結(jié)語(yǔ)

本文對(duì)基于信息素的隱式協(xié)調(diào)方法在制造系統(tǒng)任務(wù)分配中的應(yīng)用進(jìn)行了研究。建立了制造系統(tǒng)任務(wù)分配的數(shù)學(xué)模型。針對(duì)傳統(tǒng)的CNP協(xié)調(diào)機(jī)制在任務(wù)分配過(guò)程中存在的不足，借鑒基于生物行為的協(xié)調(diào)思想，設(shè)計(jì)了基于信息素的隱式協(xié)調(diào)方法，給出了具體的實(shí)現(xiàn)過(guò)程，并分析了其優(yōu)越性。具體的案例驗(yàn)證了該方法的有效性和可行性。下一步的研究方向是提高對(duì)制造系統(tǒng)面臨頻繁的動(dòng)態(tài)干擾的處理能力。

[1]Tanaka S，Araki M.A Branch－and－bound Algorithm with Lagrangian Relaxation to Minimize Total Tardiness on Identical Parallel Machines[J].International Journal of Production Economics，2008，113（1）：446-458.

[2]王玉善，葉東海.多Agent系統(tǒng)中合同網(wǎng)協(xié)議的一種改進(jìn)方案[J].上海師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2005，34（4）：22－27.

[3]宋海剛，陳學(xué)廣.FIPA合同網(wǎng)協(xié)議的一種改進(jìn)方案[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2004，32（7）：31－33.

[4]Aknine S，Pinson S，Shakun M F.An Extended Multi－agent Negotiation Protocol[J].Autonomous Agents and Multi－agent Systems，2004，8（1）：1387－2532.

[5]Vojdani N.Distributed Manufacturing Control Using Fuzzy Contract Net[C]／／Proceedings of IEEE International Conference on Fuzzy Systems，New Orleans，1996：1655－1659.

[6]Hsieh F S.Developing Cooperation Mechanism for Multi－agent Systems with Petri Nets[J].Engineering Applications of Artificial Intelligence，2009，22（4／5）：616－627.

[7]潘全科，左鳳朝，朱劍英.面向綠色制造模式調(diào)度的Petri網(wǎng)模型及優(yōu)化算法[J].機(jī)械工程學(xué)報(bào)，2006，42（9）：48－53.

[8]Paulo L，F(xiàn)rancisco R.ADACOR：A Holonic Architecture for Agile and Adaptive Manufacturing Control[J].Computers in Industry，2006，57（2）：121－130.

[9]Gao Q L，Luo X，Yang S Z.Stigmergic Cooperation Mechanism for Shop Floor Control System[J].International Journal of Advanced Manufacturing Technology，2005，25（7／8）：743－753.

[10]Xiang W，LeeH P.Ant Colony Intelligence in Multi－agent Dynamic Manufacturing Scheduling[J].Engineering Applications of Artificial Intelligence，2008，21（1）：73－85.

[11]Camazine S，Deneubourg J L，F(xiàn)ranks N R，et al.Self－organization in Biological systems[M].Princeton：Princeton University press，2001.

[12]郜慶路，羅欣，楊叔子.分布式制造系統(tǒng)的控制協(xié)調(diào)及其方法分析[J].信息與控制，2003，32（4）：295－299.

[13]王靈霞，張遠(yuǎn)平，吳佩莉.蟻群算法求解分布式系統(tǒng)任務(wù)分配問(wèn)題[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（6）：1472－1474.

[14]李言，劉永，李淑娟，等.面向多訂單的JSP建模及其蟻群算法實(shí)現(xiàn)[J].中國(guó)機(jī)械工程，2009，20（18）：2198－2202.