任 上， 秦江濤

（1.上海理工大學(xué)信息化辦公室，上海 200093；2.上海理工大學(xué)管理學(xué)院，上海 200093）

基于著色Petri網(wǎng)實(shí)現(xiàn)A星算法的生產(chǎn)調(diào)度優(yōu)化研究

任 上1， 秦江濤2

（1.上海理工大學(xué)信息化辦公室，上海 200093；2.上海理工大學(xué)管理學(xué)院，上海 200093）

基于著色Petri網(wǎng)對A星算法進(jìn)行建模，研究生產(chǎn)調(diào)度優(yōu)化問題.利用著色Petri網(wǎng)的理論優(yōu)勢，簡化了大規(guī)模復(fù)雜工藝生產(chǎn)過程的調(diào)度模型過于復(fù)雜的問題.直接建立A星算法的著色Petri網(wǎng)模型，對于生產(chǎn)調(diào)度研究中的跨平臺問題給出了一種解決方法.通過著色Petri網(wǎng)仿真模擬軟件CPN Tools構(gòu)建了基于著色Petri網(wǎng)的A星算法實(shí)例和生產(chǎn)調(diào)度實(shí)例.

著色Petri網(wǎng)；生產(chǎn)調(diào)度；A星算法

生產(chǎn)調(diào)度問題是多年來的研究熱點(diǎn)，其研究方法包括數(shù)學(xué)規(guī)劃方法、啟發(fā)式搜索方法［1-2］、系統(tǒng)仿真方法、人工智能方法及計(jì)算智能方法等［3］.近年來，鑒于Petri網(wǎng)具有嚴(yán)格的數(shù)學(xué)定義和直觀的圖形表示，能夠很好地描述離散系統(tǒng)的同步、并行、共享以及沖突等系統(tǒng)狀態(tài)，許多學(xué)者基于Petri網(wǎng)來研究生產(chǎn)調(diào)度問題.基于Petri網(wǎng)研究生產(chǎn)調(diào)度問題的方法主要有兩種：一是將Petri網(wǎng)作為計(jì)算工具，通過Petri網(wǎng)對生產(chǎn)過程建模，計(jì)算該P(yáng)etri網(wǎng)模型的（可達(dá)）狀態(tài)空間，通過啟發(fā)式算法在狀態(tài)空間中得到生產(chǎn)調(diào)度的最優(yōu)路徑［4］；二是將Petri網(wǎng)模型作為仿真工具，在基于Petri網(wǎng)對生產(chǎn)過程建模的基礎(chǔ)上植入系統(tǒng)性能監(jiān)視器，在仿真模擬過程中實(shí)時地對Petri網(wǎng)模型的性能指標(biāo)數(shù)據(jù)進(jìn)行收集，并將信息反饋給智能算法進(jìn)行生產(chǎn)調(diào)度方案評判.一般選擇遺傳算法作為第二種研究方法中的智能算法［5-7］，其主要流程是將基因編碼設(shè)計(jì)為生產(chǎn)調(diào)度問題中的調(diào)度策略、調(diào)度路徑或模型的激發(fā)順序等，將適應(yīng)度函數(shù)設(shè)計(jì)為調(diào)度時間相關(guān)函數(shù)，通過一定的迭代次數(shù)得到調(diào)度問題的解.

在上述的第二種研究方法中，利用Petri網(wǎng)作為仿真模擬工具結(jié)合遺傳算法研究時，對于適用的生產(chǎn)調(diào)度問題有局限性.這是由于其基因編碼設(shè)計(jì)中一位基因片段只能對應(yīng)一個加工機(jī)器，所以，該方法只適用于待加工工序只在一種機(jī)器上加工的生產(chǎn)系統(tǒng).然而，近年來基于智能算法的研究占了多數(shù)，原因在于基于Petri網(wǎng)模型狀態(tài)空間和啟發(fā)式算法的研究目前主要存在兩個問題.首先當(dāng)生產(chǎn)工藝復(fù)雜化或者系統(tǒng)規(guī)模擴(kuò)大化后，系統(tǒng)的狀態(tài)空間呈現(xiàn)爆炸式膨脹，因此，很難直接求解；其次在Petri網(wǎng)建立的狀態(tài)空間轉(zhuǎn)化為啟發(fā)式算法的輸入數(shù)據(jù)的過程中，沒有專門的軟件平臺支持，因而實(shí)現(xiàn)難度較大［8-9］.本文提出在著色Petri網(wǎng)理論基礎(chǔ)上［10］，將生產(chǎn)調(diào)度系統(tǒng)的（可達(dá)）狀態(tài)通過著色Petri網(wǎng)中的顏色集來描述，并在著色Petri網(wǎng)中構(gòu)建了啟發(fā)式算法的過程，不僅簡化了生產(chǎn)調(diào)度模型，而且解決了利用啟發(fā)式算法的生產(chǎn)調(diào)度研究中跨平臺的問題.最后對一個簡單的生產(chǎn)調(diào)度實(shí)例進(jìn)行建模.

1 基于著色Petri網(wǎng)的生產(chǎn)調(diào)度模型

1.1 著色Petri網(wǎng)

1.2 基于著色Petri網(wǎng)的生產(chǎn)調(diào)度模型

現(xiàn)研究生產(chǎn)調(diào)度問題，該問題涉及多個工件，每個工件有各自不同的加工路徑，加工路徑上的操作稱為該工件的工序，不同工件的不同工序可以在不同的機(jī)器上加工，每臺機(jī)器一次只能加工一個工件的一道工序.在普通的Petri網(wǎng)建模中，庫所存放的托肯是沒有顏色的，托肯往往表示的是狀態(tài)以及個數(shù)，生產(chǎn)調(diào)度模型所有的工件和工序及其加工操作都由相應(yīng)的模塊組成，模型相對比較復(fù)雜和繁瑣，本文通過著色Petri網(wǎng)中顏色集的引入，使得模型簡單易懂.如圖1所示，Job庫所存放的是所有工件的工序，Time Info庫所存放的是不同工序在不同機(jī)器上加工的操作時間信息，Machine庫所存放的是加工機(jī)器，Consequence庫所存放的是加工順路的記錄.其中，TIM E，ORDER，CONSEQUENCE，M ACHINE表示各個庫所存放托肯的顏色.

圖1 基于著色Petri網(wǎng)的生產(chǎn)調(diào)度模型Fig.1 M odel of production scheduling based on colored Petri nets

2 基于著色Petri網(wǎng)實(shí)現(xiàn)A星算法

2.1 A星算法

A星算法是人工智能中典型的啟發(fā)式算法［11］，是狀態(tài)空間求最短路徑最有效的方法之一.A星算法中有一個評估函數(shù)f（x）=g（x）+h（x）.其中，g（x）表示從起點(diǎn)到任意結(jié)點(diǎn)x的實(shí)際距離，h（x）表示任意結(jié)點(diǎn)x到目標(biāo)結(jié)點(diǎn)的估算距離.A星算法的總體思路就是從起點(diǎn)開始選取評估函數(shù)值最優(yōu)的結(jié)點(diǎn)為當(dāng)前的最優(yōu)結(jié)點(diǎn)，并擴(kuò)展該結(jié)點(diǎn)尋找下一個最優(yōu)結(jié)點(diǎn)，直到最優(yōu)節(jié)點(diǎn)為終點(diǎn)，最后從終點(diǎn)回溯到起點(diǎn)記錄下最優(yōu)路徑，其具體流程如圖2所示.S為起始節(jié)點(diǎn)，k為實(shí)際距離.

2.2 基于著色Petri網(wǎng)對A星算法建模

圖2 A星算法流程圖Fig.2 Flow diagra m of A star algorith m

如圖2所示，將A星算法分解為選擇最優(yōu)結(jié)點(diǎn)、判斷目標(biāo)節(jié)點(diǎn)、擴(kuò)展最優(yōu)節(jié)點(diǎn)、更新OPEN表和CLOSED表、回溯最優(yōu)路徑5個算法子模塊.這5個算法子模塊與圖3所示的模型圖中ChooseBest，CheckTarget，Explode，CheckSets，CollectPath這5個變遷相對應(yīng).在基于著色Petri網(wǎng)的A星算法模型中，OpenSet庫所、ClosedSet庫所分別代表了A星算法中的OPEN表和CLOSED表，BestNode庫所存放當(dāng)次迭代中的最優(yōu)節(jié)點(diǎn)，NextNode庫所存放當(dāng)次迭代中最優(yōu)節(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，Path庫所存放搜索出的最優(yōu)路徑.

圖3 基于Petri網(wǎng)實(shí)現(xiàn)A星算法的建模Fig.3 M odeling of A star Algorith m in colored Petri nets

3 基于著色Petri網(wǎng)實(shí)現(xiàn)A星算法實(shí)例

每一個算法單元都是由一個變遷和若干庫所組成，而算法單元的函數(shù)功能就是由變遷中的變遷函數(shù)體現(xiàn)的.在算法單元設(shè)計(jì)之前，首先要定義算法單元之間傳遞數(shù)據(jù)的數(shù)據(jù)類型，在著色Petri網(wǎng)中就是定義庫所中托肯的顏色.

3.1 生產(chǎn)調(diào)度問題描述與顏色集定義

生產(chǎn)調(diào)度問題中的單個工件的狀態(tài)可以用工件、工序和加工機(jī)器這3個參數(shù)來描述，其顏色定義為PRO=product JOB*N U M*M ACH，其中，JOB，N U M，M ACH是分別代表工件、工序、加工機(jī)器的枚舉型顏色集.A星算法中的結(jié)點(diǎn)包含生產(chǎn)調(diào)度系統(tǒng)的狀態(tài)信息，系統(tǒng)狀態(tài)由所有工件的狀態(tài)疊加而成，假設(shè)現(xiàn)要加工2個工件，那么，記錄系統(tǒng)狀態(tài)和評估函數(shù)f值的顏色定義為FX=product PRO* PRO*IN T.表1與表2分別為待加工的2個工件的工藝以及加工時間.在A星算法中從起點(diǎn)搜索到終點(diǎn)后，需要通過結(jié)點(diǎn)信息追溯路徑，需要每個結(jié)點(diǎn)都記錄其父親結(jié)點(diǎn)，因此，將A星算法單元間傳遞的顏色定義為NOD=record fath：FX*self：FX.定義LNOD=list NOD為NOD類型數(shù)據(jù)的列表.

A星算法的子算法單元包括選擇最優(yōu)結(jié)點(diǎn)單元、檢查目標(biāo)結(jié)點(diǎn)單元、擴(kuò)展結(jié)點(diǎn)單元、更新OPEN表和CLOSED表單元以及回溯最優(yōu)路徑單元.本文僅重點(diǎn)介紹擴(kuò)展結(jié)點(diǎn)單元以及更新OPEN表和CLOSED表單元.

表1 生產(chǎn)調(diào)度問題中的產(chǎn)品工藝描述Tab.1 Product operation description in production scheduling problem

表2 生產(chǎn)調(diào)度問題中的工序時間描述Tab.2 Operation time description in production scheduling problem

3.2 擴(kuò)展結(jié)點(diǎn)單元

擴(kuò)展結(jié)點(diǎn)單元的功能是根據(jù)工件工藝信息，擴(kuò)展當(dāng)前最優(yōu)結(jié)點(diǎn)，并計(jì)算它們的評估函數(shù)f值.

如圖4所示，擴(kuò)展結(jié)點(diǎn)單元由Explode變遷以及TempSet，Info，NextNode庫所組成.TempSet庫所傳遞的是當(dāng)前的最優(yōu)結(jié)點(diǎn)，Info庫所包含工藝和加工時間的信息，通過Explode變遷的激發(fā)，生成擴(kuò)展結(jié)點(diǎn)存放到NextNode庫所.

Explode變遷的變遷函數(shù)為List.drop（foldr insert2（foldr insert1 templistinfo）info，1）

其功能為擴(kuò)展當(dāng)前的最優(yōu)結(jié)點(diǎn)，其具體操作是通過insert1函數(shù)查找所有第1個工件的下一步工藝，insert2函數(shù)查找所有第2個工件的下一步工藝，來查找該工件所有可能的下一步加工工藝的過程.

圖4 擴(kuò)展結(jié)點(diǎn)單元Fig.4 Exploding nodes unit

3.3 更新OPEN表和CLOSED表單元

更新OPEN表和CLOSED表單元的功能主要是將最優(yōu)結(jié)點(diǎn)的后繼節(jié)點(diǎn)放入OPEN表中，如果后繼結(jié)點(diǎn)已經(jīng)存在于表中，則比較f值，選取f值較小的結(jié)點(diǎn).

如圖5所示，CheckSets變遷的變遷函數(shù)由2個子表達(dá)式組成，分別是生成newopen列表的表達(dá)式：foldr opencheck opensets nextnodes以及生成newclosed列表的表達(dá)式：foldr closedcheck closedsets nextnodes.其中opencheck和closedcheck為函數(shù)名，它們的定義為

如果擴(kuò)展結(jié)點(diǎn)已經(jīng)存在于OPEN表，則在OPEN表中留下評估函數(shù)f值較小的結(jié)點(diǎn).如果擴(kuò)展結(jié)點(diǎn)已經(jīng)存在于CLOSED表，則比較2個結(jié)點(diǎn)的評估函數(shù)f值.如果擴(kuò)展結(jié)點(diǎn)的f值較大，則忽略，因?yàn)橐呀?jīng)有更優(yōu)的路徑到達(dá)該結(jié)點(diǎn)；如果擴(kuò)展結(jié)點(diǎn)的f值較小，則從CLOSED表中刪除該結(jié)點(diǎn)，并將其加入OPEN表，因?yàn)?，CLOSED表中包含該結(jié)點(diǎn)D，說明該結(jié)點(diǎn)重新返回OPEN表后其f值仍然是最小的，因此，該結(jié)點(diǎn)會在下一步迭代中成為最優(yōu)結(jié)點(diǎn).

圖5 更新O P E N表和CL OSE D表單元Fig.5 Updating of table O P E N and table CL OSE D unit

3.4 完整的A星算法

將全部算法單元合并在一起可以得到A星算法網(wǎng)絡(luò).為了避免各單元之間的運(yùn)行順序失常，給予各單元各自的優(yōu)先級如圖6所示（見下頁）.Petri網(wǎng)中優(yōu)先級的具體定義為，當(dāng)多個變遷的輸入弧表達(dá)式不為空且守衛(wèi)函數(shù)為真時，優(yōu)先級最高的變遷使能，當(dāng)多個變遷的優(yōu)先級同時最高時則同時使能.

如圖6所示，A星算法網(wǎng)絡(luò)中TargetState庫所、Info庫所及OnePath庫所由藍(lán)色標(biāo)簽標(biāo)記. TargetState庫所及Info庫所分別存放著生產(chǎn)調(diào)度系統(tǒng)的目標(biāo)狀態(tài)及工藝信息，是A星算法網(wǎng)絡(luò)的外部輸入，OnePath庫所則作為存放調(diào)度隊(duì)列的庫所，是A星算法網(wǎng)絡(luò)的外部輸出.圖7（見下頁）為在著色Petri網(wǎng)中生產(chǎn)調(diào)度模型與A星算法模型的組合模型，可以看出，使用著色Petri網(wǎng)構(gòu)建A星算法網(wǎng)絡(luò)，從全局建模的角度具有結(jié)構(gòu)簡單、應(yīng)用方便的優(yōu)勢.研究設(shè)備控制、系統(tǒng)應(yīng)急等問題時，在不修改A星算法網(wǎng)絡(luò)的前提下，只要對生產(chǎn)調(diào)度系統(tǒng)建模中A星算法網(wǎng)絡(luò)的使用稍加調(diào)整，就可以實(shí)時交互系統(tǒng)狀態(tài)信息與A星算法的計(jì)算信息，模擬不同的系統(tǒng)狀況.

圖6 A星算法在著色Petri網(wǎng)中的建模實(shí)例Fig.6 M odeling exa m ple of A star Algorith m in colored Petri nets

圖7 生產(chǎn)調(diào)度與A星算法在著色Petri網(wǎng)中的建模Fig.7 M odeling of production scheduling with A star algorith m in colored Petri nets

4 結(jié)束語

利用著色Petri網(wǎng)中顏色集的優(yōu)勢簡化了生產(chǎn)調(diào)度模型，利用CPN Tools建模仿真軟件對生產(chǎn)調(diào)度過程以及A星算法實(shí)例建模，使得基于A星算法的生產(chǎn)調(diào)度研究能夠在統(tǒng)一的著色Petri網(wǎng)平臺上進(jìn)行，克服了跨平臺研究的不便.

［1］ 劉長平，葉春明.求解置換流水車間調(diào)度問題的布谷鳥算法［J］.上海理工大學(xué)學(xué)報(bào)，2013，35（1）：17-20.

［2］ 傅家旗，葉春明，趙偉民.混合量子算法在生產(chǎn)調(diào)度中的應(yīng)用［J］.上海理工大學(xué)學(xué)報(bào)，2009，31（6）：557-561.

［3］ 馬正元，王偉玲，王玉生.生產(chǎn)調(diào)度問題的系統(tǒng)研究［J］.成組技術(shù)與生產(chǎn)現(xiàn)代化，2005，22（1）：10-14.

［4］ 徐俊剛，戴國忠，王宏安.生產(chǎn)調(diào)度理論和方法研究綜述［J］.計(jì)算機(jī)研究與發(fā)展，2004，41（2）：257-267.

［5］ 王國新，寧汝新，王愛民.基于仿真的生產(chǎn)調(diào)度優(yōu)化技術(shù)研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2007，13（7）：1419 -1427.

［6］ 郝東，蔣昌俊，林琳.基于Petri網(wǎng)與GA算法的F M S調(diào)度優(yōu)化［J］.計(jì)算機(jī)學(xué)報(bào)，2005，28（2）：201-208.

［7］ 周衛(wèi)東，楊加敏，賈磊，等.一種Petri網(wǎng)結(jié)合遺傳算法的優(yōu)化方法及應(yīng)用［J］.山東大學(xué)學(xué)報(bào)（工學(xué)版），2005，35（4）：59-63.

［8］ 薛雷，郝躍.基于Petri網(wǎng)的啟發(fā)式生產(chǎn)調(diào)度［J］.自動化學(xué)報(bào)，2002，28（5）：827-831.

［9］ 江志斌.Petri網(wǎng)及其在制造系統(tǒng)建模與控制中的應(yīng)用［M］.北京：機(jī)械工業(yè)出版社，2004.

［10］ Jensen K.Colored Petri nets：a high-levellanguage for system design and analysis［J］.Computer Science，1991（483）：342-416.

［11］ 蔡自興.人工智能及其應(yīng)用［M］.北京：清華大學(xué)出版社，2007.

（編輯：石 瑛）

A Star Algorith m for Scheduling O ptimization Based on Colored Petri Nets

REN Shang1， QIN Jiang-tao2
（1.Inform atization Office，University of Shanghai for Science and Technology，Shanghai 200093，China；2.Business School，University of Shanghai for Science and Technology，Shanghai 200093，China）

The scheduling process and A star algorithm were modeled based on colored Petri nets. The complexity of scheduling process resulting frommass scale and complicated procedures of manufacturing systemwas decreased by taking the advantage of colored Petri nets theory. Moreover，the A star algorithm was modeled based on colored Petri nets directly in order to solve the problemof doing production scheduling on some different software platforms.Apretical modelling example of scheduling and A star algorithm was conducted colored Petri nets by use of the modeling and simulation software CPN Tools.

colored Petri nets；scheduling；A star algorith m

TP 311.1

A

1007-6735（2013）05-0463-06

2012-08-11

國家自然科學(xué)基金資助項(xiàng)目（71071097）

任 上（1988-），男，碩士研究生.研究方向：制造系統(tǒng)生產(chǎn)調(diào)度方法及性能分析.E-mai l：shawn_ren＠163.com