湯洪濤　劉　璐　陳　明　魯建廈

浙江工業(yè)大學(xué)，杭州，310032

基于Stigmergy的Holonic控制架構(gòu)與調(diào)度策略

湯洪濤劉璐陳明魯建廈

浙江工業(yè)大學(xué)，杭州，310032

針對(duì)制造執(zhí)行系統(tǒng)遞階式的控制結(jié)構(gòu)以及Stigmergy機(jī)制在Holonic控制架構(gòu)中應(yīng)用的局限性，通過(guò)在Holonic制造系統(tǒng)PROSA參考架構(gòu)基礎(chǔ)上為基本holon以及參謀holon分別設(shè)計(jì)對(duì)應(yīng)的螞蟻holon，構(gòu)建了基于Stigmergy的Holonic控制架構(gòu)，給出了該架構(gòu)下各類holon單元的4種內(nèi)部holon(數(shù)據(jù)holon、決策h(yuǎn)olon、通訊holon和結(jié)構(gòu)holon)，并定義了應(yīng)用于基本holon和參謀holon之間傳遞具體信息以及訂單holon與資源holon之間協(xié)商加工方案的兩種信息素。給出了作業(yè)車間調(diào)度問(wèn)題的數(shù)學(xué)描述，以最長(zhǎng)完成時(shí)間最短為調(diào)度目標(biāo)，提出了在基于Stigmergy的Holonic控制架構(gòu)下各類holon單元以兩種信息素為媒介協(xié)商實(shí)現(xiàn)作業(yè)車間調(diào)度的基本策略，并通過(guò)算例驗(yàn)證了該策略的有效性。

作業(yè)車間調(diào)度；Holonic控制架構(gòu)；Stigmergy協(xié)商機(jī)制；蟻群算法

0　引言

在車間生產(chǎn)過(guò)程中，從調(diào)度的角度看，制造執(zhí)行系統(tǒng)(manufacturing execution system，MES)承擔(dān)的是調(diào)度方案的執(zhí)行工作。MES通常是建立在遞階控制結(jié)構(gòu)上的，其控制信息的傳遞是自上而下的。隨著生產(chǎn)加工的進(jìn)行，MES往往無(wú)法完全遵守初始的調(diào)度方案，需要在出現(xiàn)擾動(dòng)的時(shí)候能夠進(jìn)行準(zhǔn)確的評(píng)估，作出準(zhǔn)確的應(yīng)對(duì)決策。因此，MES需要一種自治的方式來(lái)輔助其完成這一工作[1]。Valckenaers等[2]提出在MES中引入分散化的Holonic控制機(jī)制構(gòu)成HMES(Holonic manufacturing execution system)，改變MES在執(zhí)行初始調(diào)度的過(guò)程中面對(duì)擾動(dòng)時(shí)的響應(yīng)方式，從而保證其魯棒性和敏捷性。

蟻群的Stigmergy機(jī)制是在一組分散分布的實(shí)體之間使用的一種間接協(xié)商機(jī)制，這種協(xié)商機(jī)制十分適合同樣由分布式實(shí)體構(gòu)成的基于Holonic控制架構(gòu)的調(diào)度系統(tǒng)。文獻(xiàn)[3-4]討論了在HMEES中使用Stigmergy協(xié)商機(jī)制的方法。Barbosa等[5]指出，在HMS中引入Stigmergy機(jī)制能夠加強(qiáng)控制系統(tǒng)的自組織性，使系統(tǒng)具有更好的可重構(gòu)性。但是，在上述研究中Stigmergy機(jī)制的應(yīng)用僅限于訂單與資源這兩類實(shí)體中，而對(duì)其他實(shí)體之間如何通訊并未作具體說(shuō)明。

本文從蟻群的Stigmergy機(jī)制的原理及其與車間生產(chǎn)中對(duì)象的映射關(guān)系出發(fā)，構(gòu)建了基于Stigmergy的Holonic控制架構(gòu)以及各類holon的內(nèi)部結(jié)構(gòu)。通過(guò)對(duì)holon單元的內(nèi)部結(jié)構(gòu)以及相互協(xié)商過(guò)程中使用的信息素進(jìn)行定義，把Stigmergy協(xié)商機(jī)制的應(yīng)用范圍擴(kuò)大到Holonic控制架構(gòu)中的所有實(shí)體[6]，從而進(jìn)一步滿足作業(yè)車間調(diào)度系統(tǒng)的高效化和智能化要求。在此基礎(chǔ)上給出了在該架構(gòu)下各類holon單元相互協(xié)商完成作業(yè)車間調(diào)度問(wèn)題的基本策略，并通過(guò)算例驗(yàn)證了該策略的有效性。

1　基于Stigmergy的Holonic控制架構(gòu)

建立基于Stigmergy的Holonic控制架構(gòu)，旨在將Stigmergy協(xié)商機(jī)制在優(yōu)化性能與通訊負(fù)荷方面的優(yōu)勢(shì)與HMES相結(jié)合，在發(fā)揮holon單元自治與協(xié)商特性的同時(shí)兼具良好的優(yōu)化性能與較低的通訊負(fù)荷。這種結(jié)合通過(guò)對(duì)HMES中各類holon設(shè)計(jì)對(duì)應(yīng)的螞蟻holon(ant holon)來(lái)實(shí)現(xiàn)，并通過(guò)定義兩種不同類型的信息素來(lái)打破傳統(tǒng)Stigmergy機(jī)制僅在訂單holon(order holon)與資源holon(resource holon)之間使用的限制，將這一范圍擴(kuò)大到整個(gè)Holonic控制架構(gòu)中，從而進(jìn)一步發(fā)揮Stigmergy機(jī)制在交互協(xié)商方面的優(yōu)勢(shì)。

1.1螞蟻holon的設(shè)計(jì)

在蟻群的Stigmergy機(jī)制中，螞蟻通過(guò)在從食物源返回蟻巢的路徑上釋放“信息素”來(lái)指導(dǎo)自身或其他螞蟻，找到從蟻巢到食物源的最短路徑。文獻(xiàn)[7]通過(guò)分析蟻群覓食機(jī)制中的對(duì)象及其協(xié)調(diào)和控制方式，建立了該機(jī)制與車間生產(chǎn)中對(duì)象的映射關(guān)系，見(jiàn)表1。

表1　螞蟻覓食機(jī)制中的對(duì)象與

在生產(chǎn)車間中，原材料所在的倉(cāng)庫(kù)系統(tǒng)可以視為蟻巢，每臺(tái)可供選擇的設(shè)備可以看作螞蟻覓食道路上的一個(gè)節(jié)點(diǎn)，而設(shè)備的不同加工時(shí)間就像路徑的不同長(zhǎng)度。若以最長(zhǎng)完成時(shí)間最短作為生產(chǎn)調(diào)度的目標(biāo)函數(shù)，則螞蟻用于在蟻巢和食物源之間尋找最短路徑的Stigmergy協(xié)商機(jī)制完全適用于車間的生產(chǎn)調(diào)度。并且這種間接通訊方式也為holon之間協(xié)調(diào)機(jī)制的設(shè)計(jì)提供了啟發(fā)，可以在已有的Holonic控制架構(gòu)中引進(jìn)一種螞蟻holon，如同螞蟻在周圍環(huán)境中散布和感知信息素一樣，負(fù)責(zé)在制造環(huán)境中發(fā)現(xiàn)和傳播信息。

經(jīng)典的Holonic控制架構(gòu)——PROSA架構(gòu)[8]中定義了3種基本holon(資源holon、產(chǎn)品holon和訂單holon)來(lái)分別對(duì)應(yīng)制造系統(tǒng)主要涉及的3個(gè)相對(duì)獨(dú)立方面：資源方面、產(chǎn)品和相關(guān)的工藝技術(shù)方面以及與交貨期和供貨相關(guān)的方面。此外，PROSA架構(gòu)還定義了一種參謀holon(staff holon)用于為這三類基本holon提供專家信息，使基本holon能夠正確解決問(wèn)題。之后出現(xiàn)的一些Holonic控制架構(gòu)多是在PROSA架構(gòu)的基礎(chǔ)上演化改進(jìn)之后提出的[9-10]。因此，可以通過(guò)在PROSA架構(gòu)中添加一類螞蟻holon來(lái)建立基于Stigmergy的Holonic制造執(zhí)行控制架構(gòu)，其中各類holon的從屬關(guān)系如圖1所示。

圖1　基于Stigmergy的Holonic控制架構(gòu)中各類holon的從屬關(guān)系

在基于Stigmergy的Holonic制造執(zhí)行控制架構(gòu)中，基本holon與參謀holon都能以一定的速率來(lái)創(chuàng)建各自對(duì)應(yīng)的螞蟻holon來(lái)負(fù)責(zé)信息的傳播與接收。一方面，與真實(shí)環(huán)境中的螞蟻一樣，螞蟻holon不僅要求數(shù)量很大，而且還要很“便宜”。其中，螞蟻holon的數(shù)量可以通過(guò)設(shè)定創(chuàng)建速率來(lái)調(diào)整。另一方面，“便宜”是因?yàn)槲浵乭olon的內(nèi)部屬性與對(duì)應(yīng)的holon相同，但并不具有與其對(duì)應(yīng)的holon同等的功能，而只是負(fù)責(zé)感知和散發(fā)信息素，所以只需要有限的計(jì)算能力和通訊帶寬[11]，而廢棄這種holon只需釋放一些計(jì)算機(jī)內(nèi)存。

1.2holon單元的內(nèi)部結(jié)構(gòu)

通常情況下生產(chǎn)調(diào)度是由控制架構(gòu)中的所有holon發(fā)揮自治與協(xié)作的特性共同實(shí)現(xiàn)的，holon之間協(xié)作的過(guò)程可能發(fā)生在任何需要的時(shí)間與地點(diǎn)，而且這一過(guò)程通常伴隨著物料流、信息流以及與人的交互作用。所以，1個(gè)holon的基本內(nèi)部結(jié)構(gòu)應(yīng)該包括以下4個(gè)部分：信息數(shù)據(jù)存儲(chǔ)部分、決策制訂部分、通訊處理部分以及物理操作和控制部分。為此，根據(jù)holon中遞歸嵌套的結(jié)構(gòu)特性定義了4種內(nèi)部holon：數(shù)據(jù)holon(data holon)、決策h(yuǎn)olon(decision holon)、通訊holon(communication holon)、結(jié)構(gòu)holon(structure holon)，如圖2所示。

圖2　holon單元的內(nèi)部結(jié)構(gòu)

數(shù)據(jù)holon存儲(chǔ)holon進(jìn)行行為決策所需的信息，包括holon自身屬性信息、其他holon信息等。決策h(yuǎn)olon根據(jù)數(shù)據(jù)holon中的信息進(jìn)行行為決策，相當(dāng)于執(zhí)行制造控制功能，如對(duì)任務(wù)的調(diào)度、執(zhí)行、監(jiān)控以及對(duì)意外擾動(dòng)的響應(yīng)等。holon在一定的知識(shí)和信息基礎(chǔ)上制訂相應(yīng)的決策，在一項(xiàng)決策執(zhí)行之后，就變成新的知識(shí)被holon吸收，所以決策h(yuǎn)olon中除了決策機(jī)制之外，還應(yīng)該包括學(xué)習(xí)機(jī)制和應(yīng)對(duì)突發(fā)情況的自組織和自適應(yīng)機(jī)制。通訊holon負(fù)責(zé)個(gè)體的holon與外界環(huán)境和其他holon的信息交互，支持各holon之間局部信息的分享。結(jié)構(gòu)holon則為相關(guān)的儀器設(shè)備或操作者，負(fù)責(zé)執(zhí)行決策h(yuǎn)olon作出的決策。這4類內(nèi)部holon的屬性見(jiàn)表2，表2中只給出了主要內(nèi)容，未全部列舉。

表2　內(nèi)部holon的屬性

1.3Stigmergy機(jī)制中信息素的定義

本文定義兩種類型的信息素來(lái)供各holon之間進(jìn)行協(xié)商活動(dòng)，從而將Stigmergy機(jī)制的應(yīng)用范圍擴(kuò)大到整個(gè)Holonic控制架構(gòu)中，充分發(fā)揮Stigmergy機(jī)制優(yōu)化性能高、通訊負(fù)荷低、適應(yīng)性強(qiáng)等優(yōu)點(diǎn)。

(1)第一類信息素。第一類信息素在基本holon以及參謀holon之間交換具體信息時(shí)使用。例如，當(dāng)有訂單下達(dá)到生產(chǎn)車間，訂單holon便會(huì)創(chuàng)建order，螞蟻holon在信息發(fā)布holon(information publish holon，IP holon)中留下信息素[N，O]，其中N為訂單編號(hào)，O為訂單信息，來(lái)供產(chǎn)品holon感知并獲得相關(guān)的產(chǎn)品加工知識(shí)。信息發(fā)布holon模擬的是Stigmergy機(jī)制中螞蟻所生活的環(huán)境，它是信息素的載體。這類信息素的運(yùn)行機(jī)制強(qiáng)調(diào)Stigmergy機(jī)制中局部信息素的發(fā)布無(wú)需同步的特性?；緃olon和參謀holon只需不斷通過(guò)螞蟻holon從信息發(fā)布holon中獲取信息素或者將信息素釋放在信息發(fā)布holon中，而無(wú)需通過(guò)約定的時(shí)間和地點(diǎn)交換信息。

(2)第二類信息素。第二類信息素應(yīng)用于訂單holon與資源holon協(xié)商搜索加工路徑的過(guò)程中。這類信息素不包含任何具體內(nèi)容，而是通過(guò)信息素的濃度高低來(lái)反映相應(yīng)的資源holon對(duì)加工任務(wù)的吸引程度。由于在這一過(guò)程中信息素需要被頻繁地感知和更新，故這類信息素通常以數(shù)值形式直接存儲(chǔ)在資源holon中。這類信息素的運(yùn)行機(jī)制模擬Stigmergy機(jī)制中蟻群覓食的過(guò)程。訂單holon創(chuàng)建的螞蟻holon在資源holon構(gòu)成的網(wǎng)狀圖中，根據(jù)信息素的濃度選擇一系列的資源holon節(jié)點(diǎn)，最終構(gòu)成一條完整的加工路徑。由于訂單holon需要同時(shí)處理這兩類信息素，為了區(qū)別以待，訂單holon將創(chuàng)建兩種螞蟻holon(訂單螞蟻holon、路徑螞蟻holon)來(lái)分別對(duì)應(yīng)處理這兩種信息素，即路徑螞蟻holon與資源holon利用第二類信息素完成加工方案的搜索過(guò)程。

這兩類信息素都具有揮發(fā)性，揮發(fā)速率ρ1、ρ2是可以設(shè)定的參數(shù)。對(duì)于第一類信息素，因?yàn)榘唧w內(nèi)容，其揮發(fā)速率ρ1通常較小，但是一旦被感知之后就會(huì)立即消失。如信息素[N，O]一旦被產(chǎn)品螞蟻holon感知，表明產(chǎn)品holon已經(jīng)接受了這一項(xiàng)任務(wù)，信息素[N，O]也就隨之消失。這一特性保證了螞蟻holon感知到的這一類信息素始終是有價(jià)值的、可用的，同時(shí)也保證了信息發(fā)布holon中始終都有一定的可用存儲(chǔ)空間，降低了系統(tǒng)的通訊負(fù)荷。對(duì)于第二類信息素，當(dāng)一條加工路徑最終被選定為最優(yōu)的加工路徑時(shí)，這條路徑上的所有資源holon中的信息素濃度將被加強(qiáng)。不在最優(yōu)路徑上的那些資源holon中的信息素則會(huì)隨時(shí)間的推移不斷揮發(fā)掉，即濃度會(huì)不斷降低。這一過(guò)程將使加工時(shí)間較短的信息素濃度越來(lái)越高，對(duì)加工任務(wù)的吸引力越來(lái)越強(qiáng)，從而使路徑螞蟻holon的路徑搜索過(guò)程逐漸收斂，最終得到最優(yōu)解。

2　調(diào)度策略

2.1調(diào)度問(wèn)題描述

作業(yè)車間調(diào)度問(wèn)題一般可以描述如下：n個(gè)工件Ni(i=1,2,…,n)在m臺(tái)機(jī)器Mk(k=1,2,…,m)上加工，每個(gè)工件由一組加工工序j(1≤j≤qi)組成，每道工序需要在指定的機(jī)器上加工，Oi,k,j表示第i個(gè)工件的第j道工序在機(jī)器Mk上加工。ti,k,j為工件Ni的第j道工序在機(jī)器Mk上的開始加工時(shí)間，Ti,k,j為工件Ni的第j道工序在機(jī)器Mk上的加工時(shí)間；di表示工件Ni的交貨時(shí)間。需要滿足的假設(shè)和約束條件如下。

(1)工件的每道工序一旦開始加工，在完成之前不允許中斷。

(2)不考慮生產(chǎn)過(guò)程中出現(xiàn)的各種擾動(dòng)。

(3)生產(chǎn)過(guò)程中的參數(shù)(如工件的加工時(shí)間、到達(dá)時(shí)間、交貨期等)是確定的。

(4)每臺(tái)機(jī)器在某個(gè)時(shí)刻只能加工一道工序，即工件i和工件p不能同時(shí)被加工：

tp,q,k-ti,j,k≥Ti,j,k

(1)

(5)在工件的前一道工序加工完成之后才能進(jìn)行下一道工序的加工，即

ti,j,k-ti,j-1,k≥Ti,j-1,k

(2)

調(diào)度目標(biāo)為最長(zhǎng)完成時(shí)間最短，即

式中，tik為工件Ni在機(jī)器Mk上的完成時(shí)間。

2.2holon之間的協(xié)商過(guò)程

在本文中，默認(rèn)當(dāng)訂單下達(dá)到生產(chǎn)車間時(shí)，已經(jīng)過(guò)確認(rèn)車間有能力進(jìn)行加工。在不考慮擾動(dòng)的情況下，當(dāng)訂單下達(dá)到生產(chǎn)車間后各類holon之間具體的協(xié)商過(guò)程如圖3所示。圖3的雙箭頭中，虛線表示使用第一類信息素，實(shí)線表示使用第二類信息素。

圖3　各類holon的協(xié)商過(guò)程

協(xié)商過(guò)程具體步驟如下。

(1)當(dāng)訂單下達(dá)到制造車間時(shí)，系統(tǒng)便創(chuàng)建一個(gè)與該訂單對(duì)應(yīng)的訂單holon。

(2)訂單holon通過(guò)訂單螞蟻holon將信息素[N,O]釋放在信息發(fā)布holon上，其中訂單信息O包括訂單要求加工質(zhì)量和交貨期等。

(3)產(chǎn)品螞蟻holon讀取到信息素[N,O]后反饋給產(chǎn)品holon，然后產(chǎn)品holon根據(jù)訂單要求生成設(shè)計(jì)結(jié)果和工藝規(guī)劃，再通過(guò)產(chǎn)品螞蟻holon將信息素[N,P,I]釋放到信息發(fā)布holon上，其中，P代表產(chǎn)品信息，如產(chǎn)品類型、產(chǎn)品設(shè)計(jì)結(jié)果等；I代表產(chǎn)品的加工工藝規(guī)劃。

(4)訂單螞蟻holon讀取到信息素[N,P,I]后，帶回給訂單holon。

(5)訂單holon根據(jù)信息素的內(nèi)容一次性生成一定數(shù)量的路徑螞蟻holon，這些路徑螞蟻holon攜帶工藝規(guī)劃和訂單信息與資源holon進(jìn)行協(xié)商，確定初步的加工方案。

(6)訂單螞蟻holon把確定的加工方案信息素[N,M]釋放到信息發(fā)布holon上，其中，M代表加工方案。

(7)參謀螞蟻holon讀取到信息素[N,M]后，根據(jù)其擁有的專家知識(shí)和經(jīng)驗(yàn)，從全局的角度對(duì)方案進(jìn)行可行性評(píng)定。若該方案可行，則通過(guò)參謀螞蟻holon向信息發(fā)布holon釋放方案確認(rèn)信息素[N,M,OK]，其中OK代表可行。訂單螞蟻holon與資源螞蟻holon讀取到信息素[N,M,OK]后，開始根據(jù)這一方案進(jìn)行加工。否則，參謀holon向信息發(fā)布holon釋放信息素[N,M,NG]，其中NG代表不可行。訂單螞蟻holon與資源螞蟻holon讀取到該信息素后，返回步驟(4)，開始重新生成初步的調(diào)度方案。

2.3加工方案搜索機(jī)制

在2.2節(jié)的步驟(5)中，路徑螞蟻holon與資源holon協(xié)商確定初步加工方案的過(guò)程采用蟻群算法的原理來(lái)實(shí)現(xiàn)，為了能夠完全模擬螞蟻覓食過(guò)程中的路徑形成機(jī)制，需要先根據(jù)訂單構(gòu)建對(duì)應(yīng)的析取圖。圖4是一個(gè)3×4規(guī)模的生產(chǎn)車間調(diào)度問(wèn)題的析取圖。圖4中，節(jié)點(diǎn)U、V是虛擬的起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)；h為節(jié)點(diǎn)編號(hào)，r=1,2,…,10，代表各個(gè)資源holon；每個(gè)節(jié)點(diǎn)編號(hào)上對(duì)應(yīng)的(p,m)表示工件p在機(jī)器m上加工。實(shí)線弧為連接弧，代表加工的路線，如果連接節(jié)點(diǎn)(p,m1)和(p,m2)是實(shí)線弧，則工件p需要先在機(jī)器m1上加工后才能在機(jī)器m2上加工。屬于兩個(gè)工件且需要在同一臺(tái)機(jī)器上加工的兩個(gè)操作由兩條方向相反的虛線弧(又叫析取弧)組成。從一個(gè)節(jié)點(diǎn)發(fā)出的所有弧，其長(zhǎng)度都代表加工時(shí)間，從起點(diǎn)發(fā)出的弧的長(zhǎng)度為0。

圖4　3×4規(guī)模的生產(chǎn)車間調(diào)度問(wèn)題的析取圖

一個(gè)可行的加工方案相當(dāng)于路徑螞蟻holon從起點(diǎn)U出發(fā)，從每對(duì)析取弧中選擇一條直至到達(dá)終點(diǎn)V，并且中間不存在回路，這樣的選擇決定了該臺(tái)機(jī)器加工操作的順序。以最長(zhǎng)完成時(shí)間最短為調(diào)度目標(biāo)，一個(gè)可行加工方案的最長(zhǎng)完成時(shí)間取決于起點(diǎn)U和終點(diǎn)V的最長(zhǎng)路徑。路徑螞蟻holon在由資源holon構(gòu)成的析取圖中從起點(diǎn)到終點(diǎn)的過(guò)程就如同蟻群中螞蟻從蟻巢到食物源的過(guò)程，可以通過(guò)以下過(guò)程來(lái)模擬[12]： 路徑螞蟻holon從析取圖的起點(diǎn)出發(fā)，根據(jù)可選資源holon節(jié)點(diǎn)中的信息素為下一步加工選擇適合的資源holon，直到路徑螞蟻holon遍歷所有的資源holon節(jié)點(diǎn)到達(dá)終點(diǎn)。當(dāng)所有的螞蟻holon都完成路徑選擇到達(dá)終點(diǎn)后，選擇出最優(yōu)的加工路徑，并更新這條路徑上的資源holon節(jié)點(diǎn)中的信息素，整個(gè)過(guò)程如圖5所示。

圖5　路徑螞蟻holon與資源holon的協(xié)商過(guò)程

狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則如下。

(1)狀態(tài)轉(zhuǎn)移規(guī)則。在資源holon的選擇過(guò)程中，路徑螞蟻holon并不是僅僅根據(jù)資源holon節(jié)點(diǎn)的信息素濃度來(lái)單純選擇信息素濃度最高的資源holon節(jié)點(diǎn)，因?yàn)檫@樣容易使路徑螞蟻holon對(duì)節(jié)點(diǎn)選擇過(guò)程陷入局部最優(yōu)，并使最短路徑的求解過(guò)程過(guò)早收斂。為了獲得更好的求解結(jié)果，在選擇過(guò)程中還要增加一些啟發(fā)式信息，來(lái)平衡路徑螞蟻holon在最優(yōu)加工路徑的求解過(guò)程中的隨機(jī)性。因此，路徑螞蟻holon依據(jù)由資源holon節(jié)點(diǎn)的信息素濃度和啟發(fā)式信息共同決定的概率來(lái)選擇下一步的節(jié)點(diǎn)。這一概率定義為[13]

(3)

信息素因子α的大小反映了路徑螞蟻holon在最短路徑搜索中隨機(jī)性因素作用的強(qiáng)度，其值越大，路徑螞蟻holon選擇以前走過(guò)的路徑的可能性越大，搜索的隨機(jī)性越弱。α值過(guò)大也會(huì)使路徑螞蟻holon的搜索過(guò)早陷于局部最優(yōu)。啟發(fā)信息因子β的大小反映了路徑螞蟻holon在最短路徑搜索中先驗(yàn)性、確定性因素作用的強(qiáng)度，其值越大，路徑螞蟻holon在某個(gè)局部點(diǎn)上選擇局部最短路徑的可能性越大。若β=0，蟻群就會(huì)選擇信息素濃度最高的路徑。

(2)信息素更新規(guī)則。路徑螞蟻holon的另一個(gè)功能就是改變最終選定的最優(yōu)路徑上的資源holon節(jié)點(diǎn)的信息素濃度。更新的公式為[14]

(4)

(5)

式中，Q為常數(shù)，表示路徑螞蟻holon完成一次搜索后釋放在所經(jīng)過(guò)的路徑上的信息素總量；Lk為第k個(gè)路徑螞蟻holon從起點(diǎn)U到終點(diǎn)V所經(jīng)過(guò)的總距離。

3　算例分析

本文以6×6的Muth&Thompson JSP基準(zhǔn)問(wèn)題為例來(lái)說(shuō)明上述調(diào)度策略，已知最優(yōu)解為55個(gè)單位時(shí)間。假設(shè)在t時(shí)刻編號(hào)為001的訂單下達(dá)到生產(chǎn)車間，該訂單包含6個(gè)加工任務(wù)以及每個(gè)任務(wù)的加工要求。6臺(tái)加工機(jī)器分別抽象6個(gè)資源holon。

首先，系統(tǒng)為該訂單創(chuàng)建一個(gè)與之對(duì)應(yīng)的訂單holon，訂單holon通過(guò)訂單螞蟻holon將信息素[001,O]釋放在信息發(fā)布holon上。產(chǎn)品螞蟻holon讀取到信息素[001,O]后反饋給產(chǎn)品holon。然后，產(chǎn)品holon根據(jù)訂單要求O生成設(shè)計(jì)結(jié)果和工藝規(guī)劃，見(jiàn)表3。最后，通過(guò)產(chǎn)品螞蟻holon將信息素[001,P,I]釋放到信息發(fā)布holon上。

表3　Muth&Thompson 6×6基準(zhǔn)問(wèn)題

表3中，N1的第一個(gè)加工工序在機(jī)器3上加工，加工時(shí)間為1個(gè)單位時(shí)間；第二個(gè)加工工序機(jī)器1上完成，加工時(shí)間為3個(gè)單位時(shí)間，以此類推。

訂單螞蟻holon讀取到信息素[001,P,I]后，帶回給訂單holon。訂單holon根據(jù)信息素的內(nèi)容一次性生成一定數(shù)量的路徑螞蟻holon，這些路徑螞蟻holon攜帶著工藝規(guī)劃和訂單信息與資源holon進(jìn)行協(xié)商，確定初步的加工方案。加工方案搜索過(guò)程利用MATLAB R2012a編程求解，取最大迭代次數(shù)為200，α=0.8，β=0.4，ρ2=0.5，τ0=1，螞蟻數(shù)為100，Q=1。最后的運(yùn)行結(jié)果如圖6所示。

圖6　最佳加工方案進(jìn)化曲線

訂單螞蟻holon把確定的加工方案信息素[001,M]釋放到信息發(fā)布holon上。參謀螞蟻holon讀取到信息素[001,M]后，根據(jù)其擁有的專家知識(shí)和經(jīng)驗(yàn)從全局的角度評(píng)定該方案可行，之后通過(guò)參謀螞蟻holon向信息發(fā)布holon釋放方案確認(rèn)信息素[001,M,OK]。訂單螞蟻holon讀取到信息素[001,M,OK]后，決定開始根據(jù)這一方案進(jìn)行加工。

上述過(guò)程就是作業(yè)車間中從訂單下達(dá)到提出一個(gè)初始加工方案的完整過(guò)程，最終得到的最長(zhǎng)完成時(shí)間為55個(gè)單位時(shí)間，與已知的最優(yōu)解相同。在此過(guò)程中，基本holon與參謀holon通過(guò)螞蟻holon使用信息素進(jìn)行信息的交互與協(xié)商，最終實(shí)現(xiàn)生產(chǎn)調(diào)度的功能。

4　結(jié)語(yǔ)

本文通過(guò)創(chuàng)建多種屬性的螞蟻holon構(gòu)建了基于Stigmergy的Holonic制造執(zhí)行控制架構(gòu)，并定義了該架構(gòu)下holon單元的內(nèi)部結(jié)構(gòu)，使得holon自治與協(xié)商的過(guò)程更加清晰和明確。通過(guò)定義兩種形式的信息素，使得holon之間協(xié)商所需的信息都能夠通過(guò)信息素的形式來(lái)表達(dá)，為在整個(gè)Holonic控制架構(gòu)中使用Stigmergy機(jī)制提供了必要條件。在此基礎(chǔ)上，提出了在基于Stigmergy的Holonic控制架構(gòu)下各holon單元協(xié)商完成作業(yè)車間調(diào)度問(wèn)題的基本策略，最后通過(guò)一個(gè)基本案例證明了該策略的有效性。本文僅針對(duì)基于Stigmergy的Holonic制造執(zhí)行控制架構(gòu)下的作業(yè)車間調(diào)度問(wèn)題進(jìn)行了初步研究，未考慮調(diào)度執(zhí)行過(guò)程中可能發(fā)生的擾動(dòng)事件，后續(xù)研究將側(cè)重于擾動(dòng)事件對(duì)生產(chǎn)過(guò)程的影響，實(shí)現(xiàn)基于Stigmergy的Holonic制造執(zhí)行控制架構(gòu)下作業(yè)車間的動(dòng)態(tài)調(diào)度。

[1]Valckenaers P, Van Brussel H, Verstraete P, et al.Schedule Execution in Autonomic Manufacturing Execution Systems[J].Journal of Manufacturing Systems，2007，26(2)：75-84.[2]Valckenaers P, Van Brussel H.Holonic Manufacturing Execution Systems[J].CIRP Annals Manufacturing Technology，2005，54(1)：427-432．

[3]Verstraete P，Valckenaers P.Towards Cooperate Planning and Manufacturing Execution Systems[C]//The 12th IFAC Conference.Saint-Etienne,2006:371-376.

[4]Karuna H，Verstraete P，van Brussel H，et al.Production Planning and Control in Bio-inspired Holonic Manufacturing Execution Systems[C]//8th IFAC International Workshop on Intelligent Manufacturing Systems. San Vicente del Raspeig，2007：42-49．

[5]Barbosa J，Leitao P，Trentesaux D，et al.Enhancing ADACOR with Biology Insights Towards Reconfigurable Manufacturing Systems[C]//IECON 2011-37th Annual Conference on IEEE Industrial Electronics Society. Melbourne,2011：2746-2751．[6]WangLei，TangDunbing，GuWenbin，etal.Pheromone-basedCoordinationforManufacturingSystemControl[J].JournalofIntelligentManufacturing，2012，23(3)：747-757.

[7]GaoQinglu，LuoXin，YangShuzi.StigmergicCooperationMechanismforShopFloorControlSystem[J].TheInternationalJournalofAdvancedManufacturingTechnology，2005，25(7)：743-753．

[8]BrusselHV，WynsJ，ValckenaersP，etal.ReferenceArchitectureforHolonicManufacturingSystems:PROSA[J].ComputersinIndustry，1998，37(3)：255-274．

[9]LeitaoP，RestivoF.ADACOR：aHolonicArchitectureforAgileandAdaptiveManufacturingControl[J].ComputersinIndustry，2006，57(2)：121-130．

[10]PujoP,BroissinN,OunnarF.PROSIS:anIsoarchicStructureforHMSControl[J].EngineeringApplicationsofArtificialIntelligence，2009，22(7)：1034-1045．

[11]ValckenaersP,HadeliK,GermainBS，etal.MASCoordinationandControlBasedonStigmergy[J]．ComputersinIndustry，2007，58(7)：621-629．

[12]Scholz-ReiterB，deBeerC，F(xiàn)reitagM，etal.Bio-inspiredandPheromone-basedShop-floorControl[J].InternationalJournalofComputerIntegratedManufacturing，2008，21(2):201-205．

[13]ShiKe，QinXuan.StigmergyBasedAutonomousShopFloorControlwithWirelessSensorNetworks[C]//9thIEEEInternationalConferenceonIndustrialInformatics.Lisbon，2011：375-380．

[14]DorigoM,ManiezzoV,ColorniA.TheAntSystem:OptimizationbyaColonyofCooperatingAgents[J].IEEETransactionsonSystems，ManandCybernetics-PartB，1996，26(1)：1-13．

(編輯陳勇)

A Stigmergy-based Holonic Control Architecture and Scheduling Strategy

Tang HongtaoLiu LuChen MingLu Jiansha

Zhejiang University of Technology,Hangzhou,310032

Aiming at the hierarchical control architecture of manufacturing execution system and the application limitations of Stigmergy in Holonic control architecture, a Stigmergy-based Holonic control architecture was proposed by introducing an ant holon for every basic holon and staff holon.Four internal holons (data holon,decision holon,communication holon and structure holon) were designed for each holon unit.According to different application scopes two types of pheromones were defined. Aiming at the optimization objective of total completion time,a basic Job Shop scheduling strategy achieved by each holon unit under the Stigmergy-based Holonic control architecture was proposed. The validity of the method was verified through an example calculation.

job-shop scheduling; Holonic control architecture; Stigmergy negotiation mechanism; ant colony algorithm

2013-10-16

國(guó)家自然科學(xué)基金資助項(xiàng)目(70971118,71101129)；浙江省自然科學(xué)基金資助項(xiàng)目(Y1111118，LY12E05021)；浙江省科技廳重大科技專項(xiàng)和優(yōu)先主題項(xiàng)目(2009C11164)

TH186DOI：10.3969/j.issn.1004-132X.2015.01.009

湯洪濤，男，1976年生。浙江工業(yè)大學(xué)工業(yè)工程研究所副教授。主要研究方向?yàn)樯a(chǎn)過(guò)程管理、制造執(zhí)行系統(tǒng)、生產(chǎn)計(jì)劃與調(diào)度、生產(chǎn)與物流系統(tǒng)建模與仿真。發(fā)表論文30余篇。劉璐，女，1989年生。浙江工業(yè)大學(xué)工業(yè)工程研究所碩士研究生。陳明，女，1987年生。浙江工業(yè)大學(xué)工業(yè)工程研究所碩士研究生。魯建廈，男，1963年生。浙江工業(yè)大學(xué)工業(yè)工程研究所教授。