謝志強，周 偉，楊 靜

(1.哈爾濱理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150080；2.哈爾濱工程大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001)

0 引言

產(chǎn)品調(diào)度問題是對有限設(shè)備、人員等資源進行調(diào)配，以獲取最優(yōu)的時間效率和設(shè)備使用率為目的的活動。調(diào)度效果直接影響企業(yè)的生產(chǎn)效率和社會效益，具有重要的研究意義，受到了社會學(xué)、管理學(xué)、運籌學(xué)等領(lǐng)域?qū)＜业囊恢玛P(guān)注。

在20世紀初期，任務(wù)的調(diào)度和分配被認為是一個基于圖論、數(shù)學(xué)程序設(shè)計方法、啟發(fā)式方法等的問題[1]。1967年，CONWAY等[2]發(fā)表的文獻被公認為調(diào)度理論研究的標志性文章。70年代，調(diào)度研究的標志性工作是其理論研究已發(fā)展成為一門系統(tǒng)的應(yīng)用學(xué)科，但未開展深入的實踐研究。80年代，調(diào)度研究的標志性工作是在應(yīng)用領(lǐng)域開展的研究已經(jīng)能夠解決實際問題。例如SCHUSTER等[3]用線性規(guī)劃方法解決了材料的調(diào)度分配等。

隨著調(diào)度工作從理論到實踐的發(fā)展，人工智能、智能控制等調(diào)度方法迅速發(fā)展。學(xué)者們針對調(diào)度及調(diào)度效率問題進行了大量的研究，根據(jù)加工的難易程度，可分為單機調(diào)度、車間調(diào)度、流水線車間調(diào)度、開放式車間調(diào)度等，例如陳喬鑫等[4]設(shè)計了一種車載邊緣計算中推理任務(wù)實時調(diào)度策略，李明等[5]采用新型帝國競爭算法提出了考慮準備時間和關(guān)鍵目標的柔性作業(yè)車間調(diào)度問題。根據(jù)加工的任務(wù)特征，可分為靜態(tài)和動態(tài)兩種調(diào)度。根據(jù)優(yōu)化的方法策略，可分為數(shù)學(xué)規(guī)劃、虛擬仿真、控制理論等，例如李小林等[6]針對考慮工件釋放時間和柔性維護的單機調(diào)度問題，建立了整數(shù)規(guī)劃模型并進行線性化，楊艷芳等[7]對具有工序剛性約束的裝配線提出了基于并行工位設(shè)計和裝配序列規(guī)劃的多目標優(yōu)化方法。根據(jù)調(diào)度問題所采用的計算機算法，可分為專家系統(tǒng)算法、人工神經(jīng)網(wǎng)絡(luò)算法、智能搜索算法、目標任務(wù)算法、云計算和大數(shù)據(jù)算法等，例如徐洪智等[8]解決了異構(gòu)多處理器系統(tǒng)執(zhí)行并行任務(wù)時最小化系統(tǒng)資源并保證可靠性的問題，郝春亮等[9]運用大數(shù)據(jù)技術(shù)完成了集群調(diào)度的4種結(jié)構(gòu)問題，胡曉陽等[10]針對受運輸時間和運輸資源約束的柔性作業(yè)車間調(diào)度問題，提出一種融合貪心啟發(fā)式規(guī)則的改進迭代局部搜索算法，郭偉飛等[11]提出了基于設(shè)計結(jié)構(gòu)矩陣和遺傳算法的綜合調(diào)度算法，文一憑等[12]構(gòu)建了云際協(xié)作環(huán)境下能耗與成本感知的工作流調(diào)度模型，并提出一種相應(yīng)的云工作流調(diào)度方法。

本文在同時考慮加工和裝配的綜合調(diào)度領(lǐng)域，針對多品種單件或小批量的樹狀復(fù)雜產(chǎn)品的調(diào)度問題，提出了一種考慮層級調(diào)度次序的資源協(xié)同綜合調(diào)度算法。算法提出了同層工序數(shù)較多的復(fù)雜產(chǎn)品如何提高設(shè)備利用率、縮短總加工用時的問題并給出了建模；具體闡述了算法中的優(yōu)先級調(diào)度策略、葉節(jié)點調(diào)度策略和短用時調(diào)度策略；利用Petri網(wǎng)進行了調(diào)度設(shè)計和仿真實驗；最后通過實驗對比分析表明了本文算法的有效性。

1 研究背景

隨著調(diào)度相關(guān)研究的不斷深入，沈亞菲等[13]首次提出了關(guān)于多品種、小批量生產(chǎn)的調(diào)度問題，采用人為控制調(diào)度區(qū)間的加班算法壓縮了加工工時。

為了更好地解決多品種、小批量復(fù)雜產(chǎn)品調(diào)度問題，文獻[14]提出了將“單件或小批量產(chǎn)品加工和裝配一同處理的綜合調(diào)度”[14]，并針對調(diào)度的優(yōu)化算法開展了系統(tǒng)的深入研究[15-19]，取得了較豐富的成果。代表性成果如下：文獻[19]采用考慮串行工序擇時的算法，在縱橫兼顧的基礎(chǔ)上進一步優(yōu)化了調(diào)度算法，但是當相同設(shè)備上出現(xiàn)葉節(jié)點工序時，串行工序序列間會產(chǎn)生很多無法利用的加工空隙；文獻[20]提出了擬關(guān)鍵路徑的算法，該算法在考慮加工工序約束關(guān)系的前提下，以產(chǎn)品縱向加工為主線構(gòu)建關(guān)鍵路徑，并對關(guān)鍵路徑上的工序進行優(yōu)先加工，但是這種方法沒能考慮橫向工序?qū)φ{(diào)度結(jié)果的整體影響；文獻[21]提出考慮后續(xù)工序的擇時算法，雖然考慮了工序間緊前緊后工序的制約關(guān)系，也考慮到了串行和并行工序?qū)φ{(diào)度工序的整體影響，但是忽略了對空閑設(shè)備的充分利用；文獻[22]采用可動態(tài)生產(chǎn)具有優(yōu)先級工序集的算法，在縱橫兼顧的基礎(chǔ)上進一步優(yōu)化了調(diào)度算法，但是采用動態(tài)思想的算法仍然以縱向調(diào)度為主線，降低了具有約束關(guān)系的緊前緊后工序之間的銜接度。

上述綜合調(diào)度算法雖然提高了樹狀復(fù)雜產(chǎn)品的調(diào)度效果，但是以縱向加工為主的思想，忽略了橫向同層工序?qū)?fù)雜產(chǎn)品總體調(diào)度的影響，使得工序間緊前緊后約束關(guān)系和設(shè)備利用率都受到了影響。

針對同層工序數(shù)較多的樹狀復(fù)雜產(chǎn)品，本文提出了一種考慮層級調(diào)度次序的資源協(xié)同綜合調(diào)度算法。算法在層優(yōu)先原則的前提下，充分考慮加工工序自身屬性，通過優(yōu)先調(diào)度同層葉節(jié)點工序和加工用時較短工序的算法，兼顧了產(chǎn)品工藝樹中橫縱的并行問題，進一步充分利用了設(shè)備的空閑時間。再將加工產(chǎn)品的設(shè)備對應(yīng)Petri網(wǎng)結(jié)構(gòu)中的庫所，產(chǎn)品的工序?qū)?yīng)Petri網(wǎng)結(jié)構(gòu)中的變遷，通過算法計算并賦予Token值，完成觸發(fā)變遷，仿真實現(xiàn)綜合調(diào)度。

2 問題及建模

根據(jù)文獻[14]的定義，將加工設(shè)備和裝配設(shè)備統(tǒng)一定義為設(shè)備，將加工和裝配統(tǒng)一定義為加工[14]；用樹狀結(jié)構(gòu)表示產(chǎn)品加工工藝，樹中節(jié)點對應(yīng)加工工序，包含加工時間、加工設(shè)備及加工的順序等信息，并且要求必須滿足：

(1)工序和設(shè)備具有唯一匹配性；

(2)設(shè)備加工工序時，具有時間確定性，即某一時刻設(shè)備只能加工一道工序；

(3)每道工序可以被加工的充分必要條件是其所有緊前工序均加工完畢或者沒有緊前工序；

(4)工序加工具有連續(xù)性，即工序從開始加工直到加工結(jié)束是一個完整且連續(xù)的過程；

(5)所有工序加工完畢的總用時為產(chǎn)品的總加工時間。

假設(shè)某個復(fù)雜產(chǎn)品A加工工藝樹如圖1所示，包含11道加工工序；樹狀結(jié)構(gòu)中的每個節(jié)點表示加工工序：A1～A11。每個工序包含3種信息，分別是工序序號、工序?qū)?yīng)的加工設(shè)備序號和工序自身加工用時。箭頭表示工序的緊前緊后約束關(guān)系，如工序A1在設(shè)備M2上加工，加工用時為4工時，其緊前工序為工序A7和A8，緊后工序為工序A3。即工序A5必須在工序A7和A8全部加工結(jié)束后，才可以開始加工，而工序A3必須在工序A5加工結(jié)束后才可以開始加工。

假設(shè)復(fù)雜產(chǎn)品共有n個工序，在m臺設(shè)備上加工，綜合調(diào)度的已知條件為：

(1)n個加工工序序列{P1,P2,…Pn}；

(2)m臺加工設(shè)備序列{M1,M2,…Mn}；

(3)每個工序自身加工時間ti(其中1≤i≤n)。

約束條件為：除了葉節(jié)點工序具有緊后工序、根節(jié)點工序具有緊前工序以外，其他所有節(jié)點工序均存在緊前緊后工序約束關(guān)系，在一道工序連續(xù)加工完成后，其后序約束工序才可以開始加工。

求解問題為：合理調(diào)度各個工序，確定各工序的開始加工時間，使得復(fù)雜產(chǎn)品總體加工用時更少。

建立如下問題模型：

資源條件：

P(i+1)m-Pim≥0；

(1)

約束條件：

STi+1-STi≥ti；

(2)

求解問題：

α,β∈[0,1]。

(3)

其中：

Pim表示第m個設(shè)備上正在加工的第i個工序；

STi表示第i個工序開始加工時間；

Ti表示復(fù)雜產(chǎn)品加工總用時；

PTi表示第i個工序的層優(yōu)先級；

LN表示葉節(jié)點工序。

式(1)表示在同一設(shè)備m上第i個工序加工完成后第i+1個工序才可以開始加工；式(2)表示工序間的緊前約束關(guān)系，STi為第i個工序開始加工時間；式(3)表示求解問題為使得復(fù)雜產(chǎn)品總體加工用時Ti最少，包括工序的層優(yōu)先級PTi、工序是否為葉節(jié)點工序和工序自身加工時間ti等因素，其中α為葉節(jié)點工序的判斷系數(shù)，β為同層自身加工用時較短的工序判斷系數(shù)。因為本文算法包含短用時策略，所以不選取β=0的情況。無論葉節(jié)點工序還是非葉節(jié)點工序，當其不唯一時都需要判斷工序自身加工用時，即存在α=0∩β=1和α=1∩β=1兩種情況。

3 算法設(shè)計

3.1 算法描述

因為緊前工序的優(yōu)先調(diào)度對加快整個產(chǎn)品的調(diào)度過程至關(guān)重要，所以本文考慮層級調(diào)度次序的綜合調(diào)度算法提出優(yōu)先級調(diào)度策略、葉節(jié)點調(diào)度策略和短用時調(diào)度策略三級判斷機制。通過優(yōu)先級調(diào)度策略的工序最早開始加工思想、葉節(jié)點調(diào)度策略的減少設(shè)備空閑時間段思想和短用時調(diào)度策略的提高工序間緊密度思想的綜合運用來提高設(shè)備利用率，從而達到縮短復(fù)雜產(chǎn)品總加工用時的優(yōu)化目的。具體描述如下：

步驟1根據(jù)工藝樹的結(jié)構(gòu)特征，確定工藝樹的層序，并設(shè)置優(yōu)先級。

步驟2判斷優(yōu)先級最高的節(jié)點工序是否唯一，如果是，則根據(jù)優(yōu)先級調(diào)度策略調(diào)度優(yōu)先級高的工序，如果否，則轉(zhuǎn)步驟3。

步驟3當優(yōu)先級相同的工序不唯一時，根據(jù)葉節(jié)點調(diào)度策略進行選擇，調(diào)度優(yōu)先級相同的葉節(jié)點工序。

步驟4若以上3個步驟仍然不能唯一確定加工工序時，根據(jù)短用時策略調(diào)度自身加工用時較短的工序；直到所有工序全部加工結(jié)束，算法框架流程圖如圖2所示。

3.2 優(yōu)先級調(diào)度策略

根據(jù)“減少并行工序加工時間”原則，文獻[23]針對復(fù)雜產(chǎn)品工藝樹中的加工工序提出了工序優(yōu)先級問題，即將工序調(diào)度的優(yōu)先順序定義為工序的優(yōu)先級[23]。假設(shè)產(chǎn)品加工工藝樹有n層，則將根節(jié)點工序的優(yōu)先級定義為1；根節(jié)點工序的所有后裔節(jié)點工序的優(yōu)先級定義為2，同層工序節(jié)點作為兄弟節(jié)點；以此類推，直到第n層所有節(jié)點的優(yōu)先級定義為n。定義根節(jié)點工序的優(yōu)先級最低，第n層上工序的優(yōu)先級最高。

優(yōu)先級策略具有兩點優(yōu)勢：①可以最早開始加工約束力強的緊前工序；②優(yōu)先級調(diào)度策略是以“層”為單位，不限制加工工序必須都在同一設(shè)備上加工。

3.3 葉節(jié)點調(diào)度策略

無論工序節(jié)點位于復(fù)雜工藝樹的哪一層，只要沒有緊前工序的節(jié)點，均視為葉節(jié)點。如前所述，確定了各工序的層優(yōu)先級后，若存在層優(yōu)先級相同的工序{Pm1,Pm2,…Pmn}，則判斷{Pm1,Pm2,…Pmn}序列中是否存在葉節(jié)點，若存在且唯一存在Pm1(1≤i≤n)為葉節(jié)點，則優(yōu)先調(diào)度。

葉節(jié)點工序調(diào)度策略具有兩點優(yōu)勢：①葉節(jié)點工序的優(yōu)先調(diào)度能夠帶動其后續(xù)所有工序均較早開始加工；②因為葉節(jié)點工序沒有緊前工序的約束，所以能夠充分利用設(shè)備的空閑時間，從而提高設(shè)備的利用率。

3.4 短用時調(diào)度策略

根據(jù)“設(shè)備忙”原則，文獻[22]指出在相同設(shè)備上加工的工序序列，當工序具有相同的路徑長度時應(yīng)該調(diào)度用時少的工序。

在葉節(jié)點工序優(yōu)先調(diào)度策略的基礎(chǔ)上，引入短用時調(diào)度策略，即若在加工工藝樹的第i層上，存在工序{Pi1,Pi2,…Pin}均為葉節(jié)點工序時，則優(yōu)先調(diào)度自身加工用時較短的工序。短用時調(diào)度策略具有兩點優(yōu)勢：①充分利用了工序自身加工用時的屬性；②提高了工序間的緊密度。

3.5 算法復(fù)雜度分析

假設(shè)復(fù)雜產(chǎn)品的加工工序數(shù)、加工設(shè)備數(shù)和每道工序的自身加工用時等信息均已知，分別設(shè)為n、m、t，則本文算法復(fù)雜度分析如下：

(1)將復(fù)雜產(chǎn)品的加工工藝圖轉(zhuǎn)化為工藝樹，樹中節(jié)點對應(yīng)工序，約束關(guān)系對應(yīng)節(jié)點位置，確定根節(jié)點為最后一道完成加工的工序，其優(yōu)先級為1；依據(jù)產(chǎn)品工藝中嚴密的緊前緊后關(guān)系，依次確定工藝樹的各層節(jié)點及對應(yīng)的層優(yōu)先級，因此建立各個節(jié)點的層優(yōu)先級需要操作n次，即確定層優(yōu)先級的時間復(fù)雜度為O(n)。在已經(jīng)確定了層優(yōu)先級的節(jié)點中查找優(yōu)先級最高的節(jié)點是一個比較簡單的過程，其時間復(fù)雜度也為O(n)。因此優(yōu)先級調(diào)度策略的總體時間復(fù)雜度為O(n)。

(2)在已知工藝樹結(jié)構(gòu)的前提下，判斷葉節(jié)點工序需要操作n次，其算法時間復(fù)雜度也為O(n)。對于葉節(jié)點工序按照自身加工用時由小到大的排序，所用的時間同樣為O(n)。在最壞情況下，復(fù)雜產(chǎn)品工藝樹為完全多叉樹，則查找和排序所用的時間為n2，即時間復(fù)雜度為O(n2)。

上述兩點的操作次數(shù)之和為算法的總時間復(fù)雜度，即max{O(n),O(n2)}=O(n2)。

算法框架表述如算法1所示：

算法1考慮層級調(diào)度次序的綜合調(diào)度算法。

DispathProcedure(T);

For each node Wi∈ T do

Set(V)←Compute priority to Wi; /*計算工藝樹中各個節(jié)點的優(yōu)先級*/

For each node Vi∈ V do

Set(S)←Highest priority to Vi;/*通過優(yōu)先級策略確定可最早開始加工的節(jié)點*/

For each node Si∈S do

If unique to Si then /*判斷優(yōu)先級最高的節(jié)點是否唯一*/

dispath Si;

Else if Leaf Node to Sithen /*葉節(jié)點策略*/

dispath Si;

Else

Shortest Time to Si/*通過短用時策略確定加工工時最短的節(jié)點*/

dispath Si;

End if

End For

End For

End For

4 Petri網(wǎng)調(diào)度設(shè)計

作為圖形化的系統(tǒng)建模工具，Petri網(wǎng)可以非常直觀地描述離散、異步和并發(fā)等過程[24]，多用于分布式并發(fā)系統(tǒng)的建模與分析。Petri網(wǎng)的建模仿真能夠直觀地描述系統(tǒng)結(jié)構(gòu)、展現(xiàn)流程情況、模擬系統(tǒng)的運行[25]。早在1990年，龐小紅等[26]就將Petri網(wǎng)的相關(guān)知識應(yīng)用于常規(guī)調(diào)度算法中，后來Petri網(wǎng)在求解制造系統(tǒng)的調(diào)度問題中又得到了廣泛的應(yīng)用[27-34]，體現(xiàn)了Petri網(wǎng)較好的建?；A(chǔ)。

本文建模采用基本Petri網(wǎng)[34]，包括4個基本元素，分別是庫所(place)、變遷(transition)、有向弧(arc)、令牌(token)。以圓形節(jié)點表示庫所(place)，對應(yīng)工序加工設(shè)備；以短豎線表示變遷(transition)，對應(yīng)加工工序；有向弧表示兩種偏序關(guān)系：由庫所指向變遷的關(guān)系、由變遷指向庫所的關(guān)系；通過算法計算令牌(token)值，并根據(jù)算法的判斷機制更新令牌(token)，調(diào)度相應(yīng)工序。

為便于理解本文算法的思想和優(yōu)點，現(xiàn)仍以圖1所示的實例進行建模仿真。

按照實例分解各工序?qū)?yīng)加工設(shè)備、緊前緊后關(guān)系和加工時間，如表1所示。

表1 產(chǎn)品A加工設(shè)備工序表

對應(yīng)前述調(diào)度策略將產(chǎn)品A進行分解：

(1)按照圖3所示的產(chǎn)品A工藝圖，確定產(chǎn)品A的各個工序的優(yōu)先級，共有6級，其中工序A11的優(yōu)先級為6，優(yōu)先級最高；工序A7、A8、A9、A10的優(yōu)先級同為5，排在第2位；工序A5、A6的優(yōu)先級同為4，排在第3位；工序A3、A4的優(yōu)先級同為3，排在第4位；工序A2的優(yōu)先級同為5，排在第5位；根節(jié)點工序A1的優(yōu)先級最低，為1；

(2)遍歷產(chǎn)品A之后，優(yōu)先級最高的6級工序只有A11，因此調(diào)度A11；

(3)優(yōu)先級次之的5級工序有4個，因此判斷這些工序是否為葉節(jié)點；

(4)同為5級的A8、A9、A10均為葉節(jié)點，因此根據(jù)加工用時較短的原則確定調(diào)度工序順序為A8、A9、A10，至此產(chǎn)品A的調(diào)度順序為A11、A8、A9、A10、A7；

(5)同理確定優(yōu)先級為4的工序調(diào)度順序為A6、A5；優(yōu)先級為3的工序調(diào)度順序為A3、A4；

(6)最終確定產(chǎn)品A的調(diào)度順序為A11、A8、A9、A10、A7、A6、A5、A3、A4、A2、A1，具體分解結(jié)果如表2所示，調(diào)度過程如表3所示。

表2 產(chǎn)品A調(diào)度策略分解表

表3 本文算法調(diào)度過程

根據(jù)上述分析，在Platform Independent Petri Net Editor V4.3上建立復(fù)雜產(chǎn)品A的Petri網(wǎng)模型，如圖3所示。

在圖3的Petri網(wǎng)建模圖中，變遷的激發(fā)與令牌間的關(guān)聯(lián)條件是：當輸入庫所擁有令牌時，才能激發(fā)變遷。當某個具體變遷觸發(fā)后，對應(yīng)的輸入庫所的令牌將被消耗，并為輸出庫所產(chǎn)生令牌。在圖2與圖1的對應(yīng)關(guān)系中，模型中庫所P1、P2和P3分別對應(yīng)復(fù)雜產(chǎn)品A調(diào)度系統(tǒng)中的設(shè)備M1、設(shè)備M2和設(shè)備M3，變遷T1～T11分別對應(yīng)工序A1～A11。庫所P1對應(yīng)3個變遷：T10、T7和T2，具體作用是T10的輸入庫所、T7和T2的輸出庫所。庫所P2對應(yīng)5個變遷：T11、T9、T5、T4和T1，具體作用是T11的輸入庫所、T9、T5、T4和T1的輸出庫所。庫所P3對應(yīng)3個變遷：T8、T6和T3，具體作用是T8的輸入庫所、T6和T3輸出庫所。

庫所和變遷之間存在以下3種狀態(tài)：①變遷之間的彼此相互獨立的并發(fā)狀態(tài)，不存在任何約束關(guān)系，即每個變遷在各自的庫所中可以被優(yōu)先激發(fā)，例如變遷T8、T10和T11在t=0時刻同時擁有令牌，分別在庫所P3、P1和P2同時被激發(fā);②變遷之間具有緊前緊后約束關(guān)系的順序狀態(tài)，每一個變遷只有其前序約束變遷激發(fā)釋放令牌后，才能在對應(yīng)的庫所中擁有令牌，進入激發(fā)狀態(tài)，變遷T1、T2、T3、T4、T5、T6和T7都屬于這種狀態(tài)，例如變遷T3必須在變遷T5消耗后，即t=21時刻才能在庫所P3中被允許發(fā)生激發(fā)并消耗;③變遷之間具有庫所約束關(guān)系的順序狀態(tài)，在這種狀態(tài)中，一個庫所往往對應(yīng)多個變遷，例如T9與變遷T11，只有變遷T11觸發(fā)完畢后變遷T9才能在其共同擁有的庫所P2中擁有令牌。

仿真調(diào)度過程如下：

在t=0時刻，庫所P1、P2和P3同時擁有令牌，變遷T10、T11和T8被允許發(fā)生激發(fā)；在t=4時刻，庫所P2中變遷T11消耗完畢、釋放令牌，變遷T9擁有令牌，被激發(fā)；在t=6時刻，庫所P3中變遷T8消耗完畢、釋放令牌；在t=8時刻，庫所P1中變遷T10消耗完畢、釋放令牌，變遷T7擁有令牌，被激發(fā)；在t=11時刻，庫所P2中變遷T9消耗完畢、釋放令牌，庫所P3中變遷T6擁有令牌，被激發(fā)；在t=14時刻，庫所P3中變遷T6消耗完畢、釋放令牌，庫所P1中變遷T7消耗完畢、釋放令牌，庫所P2中變遷T5擁有令牌，被激發(fā)；在t=21時刻，庫所P2中變遷T5消耗完畢、釋放令牌，變遷T4擁有令牌，被激發(fā)；在t=27時刻，庫所P3中變遷T3消耗完畢、釋放令牌；在t=29時刻，庫所P2中變遷T4消耗完畢、釋放令牌，庫所P1中變遷T2擁有令牌，被激發(fā)；在t=36時刻，庫所P1中變遷T2消耗完畢、釋放令牌，庫所P2中變遷T1擁有令牌，被激發(fā)；在t=40時刻，庫所P2中變遷T1消耗完畢，至此所有變遷結(jié)束活動。

Petri網(wǎng)仿真運行的狀態(tài)由令牌在庫所的分布決定，如圖4所示。因為實例中包含11道工序，所以實驗中激發(fā)參數(shù)值設(shè)置為Token數(shù)量11，庫所P1、P2、P3對應(yīng)的Token值和置信區(qū)間近似值分別為3和2，5和7，2和5。在運行過程中當某個具體變遷觸發(fā)完畢后，依據(jù)約束關(guān)系的下一個變遷等待發(fā)生，且均具有確定的狀態(tài)和對應(yīng)的時刻，仿真實驗有效。

各庫所、變遷的對應(yīng)關(guān)系如表4所示。

表4 Petri網(wǎng)模型各庫所與變遷對應(yīng)關(guān)系

5 實例對比分析

下面將本文考慮層級調(diào)度次序的綜合調(diào)度算法，分別與同研究領(lǐng)域的文獻[19]的考慮串行工序緊密度的擇時算法、文獻[20]的擬關(guān)鍵路徑算法、文獻[21]的考慮后續(xù)工序的擇時算法和文獻[22]的可動態(tài)生成具有優(yōu)先級工序集算法進行對比分析，結(jié)果表明本文算法的加工用時更少，算法優(yōu)化效果更好。

5.1 甘特圖與Petri網(wǎng)關(guān)聯(lián)分析

在圖2的Petri網(wǎng)建模與圖5的甘特圖映射關(guān)系中，建模結(jié)構(gòu)在具體時刻均對應(yīng)工序的加工狀態(tài)。

在t=0時刻，設(shè)備M1上，葉節(jié)點工序A10作為輸入庫所P1的變遷擁有令牌被激發(fā)；設(shè)備M2上，層優(yōu)先級最高為6的工序A11作為輸入庫所P2的變遷擁有令牌被激發(fā)。設(shè)備M3上，同層自身加工用時最短的葉節(jié)點工序A8作為輸入庫所P3的變遷擁有令牌被激發(fā)。同為優(yōu)先級為5的葉節(jié)點工序A9雖然優(yōu)先級高于工序A10，但因為庫所P2的變遷在t=4時刻才能釋放，所以工序A9需要在A11加工完畢后才可以在設(shè)備M2上開始加工。

在t=4時刻，設(shè)備M2上，層優(yōu)先級為6的工序A11加工完畢后釋放資源，優(yōu)先級為5的工序A9才擁有令牌被激發(fā)。

因為工序A11為工序A7的緊前工序，所以工序A7在工序A11加工結(jié)束后才可以開始加工；又因為庫所P1中變遷T7必須在變遷T10消耗后才可以被激發(fā)，所以工序A7在t=8時刻在設(shè)備M1上開始加工，并在t=15時刻加工完畢。至此，優(yōu)先級為5的同層工序全部加工完畢。

如上所述，優(yōu)先級為3的同層工序A3和A4在t=27時刻全部加工完畢；優(yōu)先級為2的工序A2在t=36時刻加工完畢；優(yōu)先級為1的工序A1在t=40時刻加工完畢；如圖5所示，復(fù)雜產(chǎn)品A總體加工用時為40工時。

依據(jù)本文算法和Petri網(wǎng)建模中資源先激發(fā)后消耗過程，庫所P1分別在t=0時刻、t=8時刻和t=29時刻獲得資源觸發(fā)變遷T10、T7和T2，即對應(yīng)工序A10、A7和A2開始加工，在t=36時刻設(shè)備M1完成所有加工任務(wù)。庫所P2分別在t=0時刻、t=4時刻、t=15時刻、t=21時刻和t=36時刻獲得資源觸發(fā)變遷T11、T9、T5、T4和T1，即對應(yīng)工序A11、A9、A5、A4和A1開始加工，在t=40時刻設(shè)備M2完成所有加工任務(wù)。庫所P3分別在t=0時刻、t=11時刻和t=21時刻獲得資源觸發(fā)變遷T8、T6和T3，即對應(yīng)工序A8、A6和A3開始加工，在t=27時刻設(shè)備M3完成所有加工任務(wù)。因此，復(fù)雜產(chǎn)品A的總體加工用時為設(shè)備M1、M2、M3的最長加工用時，即40工時。

5.2 五種算法甘特圖對比

仍以圖1所示的產(chǎn)品A加工工藝圖為例，文獻[19]和文獻[21]的算法具有相同之處，即將復(fù)雜產(chǎn)品工藝樹結(jié)構(gòu)劃分成若干個可以一同調(diào)度的工序序列；不同之處則是二者的“擇時”思想。文獻[19]的考慮串行工序緊密度的擇時算法的“擇時”思想是依次調(diào)度待調(diào)度序列總加工用時最小和最早的工序(組)。采用文獻[19]的算法將產(chǎn)品A加工工藝圖逆置后，工序調(diào)度順序為(A11、A7、A5、A3、A10、A6、A4、A8、A9、A2、A1)，加工甘特圖如圖6所示，總加工用時為45工時。

文獻[20]的擬關(guān)鍵路徑法首先計算出所有唯一具有緊前緊后約束關(guān)系工序(組)的加工總用時，按總用時從長到短依次調(diào)度；然后在已經(jīng)排列完成的工序(組)中插入不存在緊前或者緊后工序的獨立工序，工序調(diào)度順序為(A11、A7、A8、A5、A3、A9、A10、A6、A4、A2、A1)，加工甘特圖如圖7所示，加工總工時為46工時。

文獻[21]的考慮后續(xù)工序擇時算法采用“排序+擇時”的策略，首先根據(jù)工序節(jié)點的位置，選出只有串行關(guān)系的工序(組)，組成排序序列，并按序列路徑長度降序依次調(diào)度；擇時策略是以選擇最接近調(diào)度目標的方案為主，依次選擇已調(diào)度工序中后續(xù)工序中加工開始時間最早的調(diào)度方案，工序調(diào)度順序為(A11、A7、A5、A3、A2、A1、A10、A6、A4、A9、A8)，加工甘特圖如圖8所示，加工總工時為43工時。

文獻[22]的可動態(tài)生成具有優(yōu)先級工序集的算法采用“層優(yōu)先、短用時、長路徑”策略，即優(yōu)先調(diào)度層優(yōu)先級高的工序，若工序?qū)觾?yōu)先級相同，則優(yōu)先調(diào)度加工用時較短的工序，若加工用時也相同，則優(yōu)先調(diào)度處在長路徑上的工序；當上述調(diào)度方法出現(xiàn)可調(diào)度工序和不可調(diào)度工序時，則根據(jù)“設(shè)備忙”的原則動態(tài)調(diào)整，工序調(diào)度順序為(A11、A8、A7、A9、A10、A6、A5、A3、A4、A2、A1)，加工甘特圖如圖9所示，加工總工時為44工時。

本文算法工序調(diào)度順序為(A11、A8、A9、A10、A7、A6、A5、A3、A4、A2、A1)，加工甘特圖如圖5所示，加工總工時為40工時。4種算法調(diào)度結(jié)果對比分析如表5所示。

5.3 對比結(jié)果分析

由表5可知，本文算法的產(chǎn)品完成加工用時最少，設(shè)備利用率最高。本文算法調(diào)度結(jié)果優(yōu)于其他四種算法，主要是因為：

表5 五種算法調(diào)度結(jié)果對比分析

(1)本文算法優(yōu)先調(diào)度對結(jié)果有重要影響的長路徑工序；在不改變待加工工序緊前和緊后工序的前提下，兼顧同層橫向工序，提高了工序并行調(diào)度的機率。

(2)文獻[19]、文獻[20]和文獻[21]三種算法都沒能充分實現(xiàn)工序間的并行處理，出現(xiàn)了重縱輕橫的現(xiàn)象；文獻[22]的算法沒能充分考慮縱向工序的約束關(guān)系，出現(xiàn)了重橫輕縱的現(xiàn)象。

文獻[19]考慮串行工序緊密度的擇時算法，注重使用“擇時”的調(diào)度策略來確定工序開始加工的時間點，同樣沒有充分考慮到設(shè)備的利用率。在圖6中，設(shè)備M1在t=19～t=34連續(xù)的時間里一直處于空閑狀態(tài)，設(shè)備M3在t=4～t=16的這段時間里也沒有加工工序，因而導(dǎo)致了對復(fù)雜產(chǎn)品加工過程的整體影響。

文獻[20]的擬關(guān)鍵路徑法算法，雖然充分考慮了縱向關(guān)系工序的調(diào)度與最終調(diào)度結(jié)果之間的決定性關(guān)系，卻忽略了橫向工序的并行性，使設(shè)備產(chǎn)生了較多空閑時間段，影響了設(shè)備的利用率。

文獻[21]的考慮后續(xù)工序擇時算法，雖然考慮了工序間緊前緊后工序的制約關(guān)系，也考慮到了串行和并行工序?qū)φ{(diào)度工序的整體影響，但同樣忽略了對空閑設(shè)備的充分利用。

在圖7和圖8的兩種算法加工甘特圖中，設(shè)備M1在t=0～t=4時刻、設(shè)備M2在t=4～t=11時刻、設(shè)備M3在t=6～t=17時刻的時間內(nèi)，均產(chǎn)生了不可利用的設(shè)備空間。

文獻[22]的可動態(tài)生產(chǎn)具有優(yōu)先級工序集的算法，在縱橫兼顧的基礎(chǔ)上進一步優(yōu)化了調(diào)度算法，但是該算法仍然以縱向調(diào)度為主線，降低了具有約束關(guān)系的緊前緊后工序之間的銜接度。在圖9中，M3在t=7～t=19的12個工時內(nèi)一直處于空閑狀態(tài)。

如圖5所示，本文算法在t=0～t=4的時間段內(nèi)設(shè)備M1上A10正在加工、設(shè)備M2上A11正在加工、設(shè)備M3上A8正在加工；在t=4～t=11的時間段內(nèi)設(shè)備M1上A10和A7緊密銜接加工、設(shè)備M2上A11和A9緊密銜接加工、設(shè)備M3上A8加工完畢后，A6開始加工。并且，在本文算法中工序A6在t=11時刻開始加工，早于其他4種算法的加工開始時間，從而導(dǎo)致了A6后序工序的加工時間也隨之提前，進而縮短了產(chǎn)品A的總體用時。

6 結(jié)束語

本文針對同層工序數(shù)較多的復(fù)雜產(chǎn)品綜合調(diào)度問題，在遵循層優(yōu)先原則基礎(chǔ)上，充分考慮工序自身在復(fù)雜產(chǎn)品結(jié)構(gòu)中的位置和加工用時等特性，設(shè)計了考慮層級調(diào)度次序的資源協(xié)同調(diào)度算法。在理論闡述分析算法兼顧了產(chǎn)品工藝樹中橫向工序并行處理力度的基礎(chǔ)上，又通過Petri網(wǎng)建模仿真驗證了算法較好地利用了設(shè)備的空閑時間，提高了設(shè)備的整體利用率，從而達到縮短復(fù)雜產(chǎn)品總加工用時的優(yōu)化目的。

本文算法為解決綜合調(diào)度問題提供了新的方法，擴展了解決問題的思路，有一定理論和實際意義。未來，還可以在以下3方面開展深入研究：①引入更多的優(yōu)化算法來提高解決綜合調(diào)度問題的能力；②需要考慮具有特殊約束關(guān)系結(jié)構(gòu)的綜合調(diào)度問題；③多目標綜合調(diào)度問題。