一類流水線車間調(diào)度模型及其算法研究

張元康 齊雪

(安徽科技學院信息與網(wǎng)絡工程學院， 安徽 鳳陽 233100)

1 問題重述

程遠方等人曾研究過一種最基本的流水線車間調(diào)度問題[1]。我們將在此基礎上進一步探討置換流水線車間調(diào)度問題。問題描述如下：某車間生產(chǎn)汽車用金屬管件，車間有3臺機器，分別用于完成彎折金屬管、焊接連接處、裝配各單元3道工序；加工6種加工件，加工件分類為1#、2#、3#、4#、5#、6#；每種加工件都需要經(jīng)過3道工序，首先進行彎折，然后進行焊接，最后進行裝配；在進入工序之后，每項加工工序都不允許打斷，但前后兩道工序之間可以等待一段時間；每臺機器每次只能處理1個加工件。各工序下每種加工件所需耗時如表1所示。

表1 各工序下每種加工件所需耗時 min

假定，在等待進入下一臺機器處理的過程中，不允許排在后面的加工件“插隊”。通常，總加工時間越短，成本越低，因此，需要設計合理的加工順序使總加工時間最短。

2 模型的假設、符號說明與問題分析

2.1 假設

(1) 每個加工件按特定的加工順序進行加工，即彎折→焊接→裝配。

(2) 進入工序之后，每項工序不允許打斷，但緊鄰的工序之間可以等待。

(3) 每臺機器每次只能處理1個加工件，特定機器處理特定的工序。

(4) 等待下一臺機器處理時，不允許排在后面的加工件插隊。

(5) 所有機器同時運轉(zhuǎn)，工件在機器之間的轉(zhuǎn)移時間不計，即機器的準備時間不計。

(6) 所有機器正常運行，不會出現(xiàn)故障。

(7) 所有工件同時到達，到達時間設為0。

2.2 符號說明

模型中各符號代表的含義如下：n表示工件數(shù)；m表示機器數(shù)；T表示3×6的加工時間矩陣；tij表示第j個工件在第i臺機器上的加工時間；cti表示第i個工件的完工時間；ctmax表示最長完工時間，ctmax=maxi=1，2，…，n(cti)；Fmax表示最長流程。

2.3 問題分析

求最短完工時間，陳蓉秋曾研究了這個問題的解法[2]。假設所有工件同時到達，且到達時間為0。最長完工時間最短，則ctmax達到最小。即，最后加工工件的停留時間及最長流程最短。在車間調(diào)度的專業(yè)術(shù)語中，最長完工時間為Makespan指標。建立以最長完工時間為函數(shù)值、工件加工順序為自變量的模型，再根據(jù)適當?shù)乃惴ㄇ蟪黾庸ろ樞?，兩者結(jié)合可以得到最優(yōu)順序，最后求解得到最短的完工時間。

針對多階段排序問題，可以建立快速求解的貪婪算法，但該算法僅在解決計算量小的問題時操作才比較簡單。我們必須尋求一種可信度較高，且能夠簡單求解較復雜問題的算法。在解決流水作業(yè)排序問題時，可應用啟發(fā)式算法、遺傳算法、模擬退火算法和粒子群優(yōu)化算法，各算法單獨或融合應用。遺傳算法、模擬退火算法和禁忌搜索算法效果較好，迭代計算量較大，且需算法操作、參數(shù)結(jié)構(gòu)選取得當。神經(jīng)網(wǎng)絡算法是一種效果良好的調(diào)度求解法，但是應用中需對網(wǎng)絡參數(shù)和能量函數(shù)進行精心設計。啟發(fā)式算法因其計算量較小的優(yōu)點，更適用于比較簡單的流水線調(diào)度問題。當求解要求較高時，可采用遺傳算法。

3 算法及ctmax計算

3.1 Johnson算法

根據(jù)張鵬等人的Johnson算法研究可知[4]，Johnson算法主要用于n/2/P/ctmax這種情況，為m臺機器的啟發(fā)式算法提供了理論基礎。當m為2、3時，流水作業(yè)排列與排序問題具有相同的最優(yōu)解，所以這里是P或F是一樣的，與原問題保持一致，所以用P表示。

若T表示2×n的加工時間矩陣，Johnson最優(yōu)調(diào)度法則為：如果min{t1i,t2j}≤min{t1j,t2i}，則工件i排在工件j之前加工。按Johnson法則，則時間復雜度為O(2n)。對Johnson算法作如下改進：

Step1：U1={i/t1i≤t2i}，U2={i/t1i>t2i}

Step2：對U1中的工件按t1i非減順序調(diào)度得到A

Step3：對U2中的工件按t2i非增順序調(diào)度得到B

Step4：將A放在B之前，得到最優(yōu)加工順序

3.2 啟發(fā)式算法

Johnson算法的優(yōu)點是，操作簡單，計算量小。但是，對于m>3的情況，無法用Johnson算法來解決，且Johnson算法只能作為解決問題的一個充分條件。在實際生產(chǎn)當中，大量的多機器生產(chǎn)問題亟待解決，因此人們開始研究啟發(fā)式算法。應用啟發(fā)式算法可得到多機器生產(chǎn)的近似最優(yōu)解，而計算量較小，非常實用。

(2) Palmer啟發(fā)式算法。1965年，Palmer提出了基于工件的加工時間按斜度順序指標排列工件的啟發(fā)式算法。聶艷芳曾在VRP的數(shù)學模型及其算法中應用了這種算法[6]。該算法的基本思想是，給每個工件賦優(yōu)先權(quán)數(shù)，按機器的順序，機器加工時間趨于增加的工件得到較大的優(yōu)先數(shù)。工件的斜度指標λj為：

(1)

按照斜度不增的順序排列作業(yè)順序，可以得到1個較優(yōu)解。另外，Gupta提出了另一種類似于Palmer方法的啟發(fā)式算法，基于3臺機器的Johnson規(guī)則最優(yōu)性，定義工件j的斜度指標λj，然后以與Palmer相同的原則排列工件順序。

(2)

其中

3.3 ctmax的計算

基于以上算法，得到最優(yōu)排序的完工時間。假設當前加工順序為O={o1，o2，…，on}，oi表示排在第i位的工件代號。對于o1，在機器k上的完工時間為其在機器k之前的累計工序時間；對于oi，在機器k上的完工時間取決于前一個工件在機器k上的完工時間，以及oi在前一臺機器上的最大完工時間。ci，oj表示工件oj在機器i上的完工時間。于是有(3)(4)(5)遞推公式：

c1,o2=t1,o2,ck,o2=ck-1,o2+tk,o1,k=2,…,m

(3)

c1,o1=c1,o1-i+t1,o1，i=2，…，n

(4)

(5)

s1,o1=c1,oi-1=s1,oi-1+t1,oi-1,i=2，…，n

(7)

sk,o1=max(ck,oi-1,ck-1,o1)

(8)

=max(sk,oi-1+tk,oi-1,sk-1,o1)

i=2，…，n，k=2，…，m

根據(jù)以上公式，可以排列出最優(yōu)排序，并通過算法編程計算出最短時間。

4 啟發(fā)式算法的實現(xiàn)及分析

4.1 CDS算法計算

首先完成CDS算法編程，輸入加工時間矩陣，T=[3 6 3 5 5 7；5 4 2 4 4 5；5 24 6 3 6]；接著，調(diào)用Matlab程序，由[makespan,sort]=CDS(T)得到計算結(jié)果：

makespan= 35

sort=[1 3 4 6 5 2]

sort=[3 1 4 6 5 2]

其中，makespan返回值就是makespan指標的值，sort返回值是近似最優(yōu)排序。此時這2個sort返回值均為最優(yōu)解，其makespan指標都為35 min。

為了繪制甘特圖，我們對程序稍作改進，得到每個工件在每道工序上的起止時間。為了方便起見，在此只給出程序結(jié)果。兩種最優(yōu)解的加工時間如表2、表3所示。表中數(shù)據(jù)含義，以第二行第4列的(11,15)為例，表示第3個工件從第11 min開始進入第二道第15 min 加工完成。

表2 最優(yōu)解sort=[1 3 4 6 5 2]下的加工時間安排 min

表3 最優(yōu)解sort=[3 1 4 6 5 2] 下的加工時間安排 min

4.2 Palmer算法和Gupta算法

調(diào)用Palmer算法的程序palmer.m，得到如下結(jié)果：

λ=[4 -8 2 2 -4 -2]

sort = [1 3 4 6 5 2]

由此得到了與CDS同樣的最優(yōu)順序，最長完工時間同樣為35 min。同時，工件3和工件4的斜度指標均為2。設想一下，如果將這兩個任務顛倒，也許結(jié)果更優(yōu)。

然后，將sort = [1 4 3 6 5 2]代入程序Fmax=zxct(T,s)，得到最長完工時間為35 min，從而得到新的最優(yōu)解。

根據(jù)上述Gupta算法的不同斜度指標，編寫程序gupta.m，得到最優(yōu)排序為

sort =[3 1 4 6 5 2]

此最優(yōu)解與應用CDS算法得到的順序相同，其中λ=[1.250 0E-001 -1.666 7E-001 2.000 0E-001 1.111 1E-001 -1.428 6E-001 -9.090 9E-002 ]，最長完工時間也為35 min，并且所有的λ都不一樣。

4.3 關(guān)鍵工件法

運行程序keygj.m，得到結(jié)果：

sort =[1 3 4 6 5 2]

與應用CDS算法所得到的sort 相同，所有其他元素和加工時間矩陣等也都相同。

4.4 討論分析

根據(jù)以上幾種啟發(fā)式算法，得到3個近似最優(yōu)解(見表4)。

表4 3個近似最優(yōu)解

在表中，每個sort 出現(xiàn)的次數(shù)均不相同，這與算法的設計有關(guān)。如排序為小于等于，等于號也可以放在大于之列，而變成大于等于；如排序相等，也可以調(diào)換順序得到不同的調(diào)度結(jié)果。也就是說，只要對上述算法程序稍加改變，就可以求出達到最優(yōu)的另一個解。

應用啟發(fā)式算法，可以一次求出1個全局最優(yōu)解。由于存在N-P問題，它的全局最優(yōu)性無法保證，往往只能得到1個近似最優(yōu)解。選擇不同的啟發(fā)式算法，通過更多的實踐檢驗，才能發(fā)現(xiàn)其優(yōu)缺點。我們可以加大m和n的值，從而進一步了解這些算法的優(yōu)缺點。

通過對相關(guān)文獻的梳理，發(fā)現(xiàn)關(guān)于知識優(yōu)勢的研究主要集中在微觀層面(如企業(yè))，而中觀層面的研究(如知識鏈、企業(yè)聯(lián)盟)剛剛起步，至于宏觀層面(如國家知識優(yōu)勢)更鮮有研究。鑒于此，本文擬通過引入VRIO模型，從價值性、稀缺性、難以模仿性和組織四個維度探討知識鏈知識優(yōu)勢的來源，并分析這四者對知識優(yōu)勢形成的不同作用，以期為知識鏈知識優(yōu)勢的評價和測量提供一個基本框架。

這里給出一個結(jié)論：CDS 算法和關(guān)鍵工件法的解為較優(yōu)解，Palmer 算法與Gupta 算法適用于只需求解1個快速近似解的問題，當要求較高時可以采用CDS 算法和關(guān)鍵工件法。當然，解決這類問題時除了采用啟發(fā)式算法，還可以采用其他算法，如遺傳算法等。

當m=3,n=6時，這是一個比較簡單的問題，可用計算機枚舉法求出所有達到最優(yōu)的加工順序。根據(jù)龔純等人研究的Matlab最優(yōu)化算法[7]，運行Matlab程序meiju.m，得到表5所示結(jié)果。

表5 meiju.m程序運行結(jié)果

最后,對比啟發(fā)式算法與枚舉法在此問題上的運算時間(見表6)。

表6 啟發(fā)式算法與枚舉法的運算時間比較

枚舉法比啟發(fā)式算法的運行時間會長很多，但是就所求解的質(zhì)量而言，枚舉法所得解為最優(yōu)。為了與遺傳算法進行對比，我們列出了這些算法的運算時間，也可以通過理論方法計算這些算法的時間復雜度。

5 遺傳算法

5.1 遺傳算法設計

遺傳算法(GA)是Holland于1975年受生物進化論的啟發(fā)而提出。遺傳算法是一種基于自然選擇原理和自然遺傳機制的搜索算法，其自組織、自適應、自學習和群體進化等能力較強，適用于求解大規(guī)模復雜優(yōu)化問題。運用該算法，可將問題的求解表示成“染色體”適者生存的過程。遺傳算法的實現(xiàn)流程包括編碼/解碼部分和遺傳操作部分。其中，遺傳操作部分又包括選擇、復制、交叉和變異等步驟。受車間調(diào)度及其遺傳算法的啟發(fā)[8]，我們運用遺傳算法完成以下求解過程。

設定種群大小為M，分別取50、60、80。因為解的結(jié)果不唯一，所以用不同的M運行多次，得到全部的全局最優(yōu)解。迭代代數(shù)為N，取1 000。為了使得群體充分進化，設交叉率為1，變異率P為0.1，變異發(fā)生的可能性比較小。初始種群隨機生成。算法流程分解如下：

(1) 編碼與解碼。用數(shù)字1 — 6分別代表6個任務。

(2) 交叉。在此采用以下交叉方式：

Step 2：從前到后選擇父代個體f1中屬于S1的基因，以及父代個體f2中屬于S2的基因，構(gòu)成子代個體。

Step 3：類似Step 2，得到子代個體B2,從而得到子代B。

(3) 變異。 按照給定的變異率，對選定的變異個體，隨機選擇3個整數(shù)，1≤u1

(4) 選擇。在[f：B：C]中選擇適應度最大的M個體作為下一代的父代，可以保證父代的優(yōu)良基因被保存下來。

(5) 適應度函數(shù)。因為目標函數(shù)是使得ctmax達到最大，因此，選擇上限值為79-ctmax。建立適應度函數(shù)，F(xiàn)ITNESS=79-ctmax，將使得目標函數(shù)最小的M個體作為下一代。

遺傳算法步驟如下：隨機產(chǎn)生初始種群f；隨機兩兩交叉染色體產(chǎn)生子代B；根據(jù)變異概率在子代B中隨機選擇變異個體，進行變異得到子代C；計算父代與子代的適應度函數(shù)，選擇最大的前M個體作為下一代父代。為方便起見，直接計算個體在目標函數(shù)中的值，選擇最小的前M個體作為下一個父代。

5.2 遺傳算法計算機模擬結(jié)果

對不同取值的M進行迭代，并且針對每個M值運行程序[f,mm,OPT]= ycsf(T,P)，得到表7所示結(jié)果。

表7 程序運行結(jié)果

種群個體越大，運行時間也越長。我們也可以使得N增大而M不變。但計算機模擬結(jié)果表明，當N=10 000，M=50時，可以得到解的個數(shù)為12，而運行時間已經(jīng)達到了72 s。這顯然沒有使M變化后的計算復雜度變小，且其解也不是最優(yōu)。

遺傳算法中，選用的參數(shù)及結(jié)構(gòu)一定要適宜，不同的結(jié)構(gòu)會導致不同的結(jié)果。

6 結(jié) 語

啟發(fā)式算法是一種構(gòu)造方法，3臺機器以上即形成N-P問題。目前尚沒有出現(xiàn)解決多項式復雜性全局問題的最優(yōu)化算法，而采用啟發(fā)式算法可以快速得到次優(yōu)解。若我們需要快速得到近似解時，Palmer 算法和Gupta 是很好的選擇。若需要得到更好的解時，CDS算法和關(guān)鍵工件法是很好的選擇。啟發(fā)式算法以其特別方便，操作簡單贏得人們的關(guān)注。啟發(fā)式算法中，還有幾種較優(yōu)算法，限于篇幅未能逐一介紹。如NEH 算法以及在其基礎上改進的Rajendran算法，都是優(yōu)秀算法。遺傳算法給出了全部的最優(yōu)解，并且GA 解的質(zhì)量往往比啟發(fā)式算法更好。對于較復雜的車間調(diào)度問題，用GA 算法是一個好的選擇。車間調(diào)度問題限制較多，目標函數(shù)也極為明確，所得目標函數(shù)相對固定。采用啟發(fā)式算法找到最優(yōu)解，且通過枚舉給出了所有的解，使該車間調(diào)度問題得以完美解決。

本模型及其算法的不足之處是，一般的啟發(fā)式算法是一種構(gòu)造性方法，只能給出充分條件。同時，在大數(shù)據(jù)問題上啟發(fā)式算法只能給出近似解，而不能達到全局最優(yōu)解，若對解的要求不高，也可以采用。運用遺傳算法雖然可以得到較優(yōu)的解，但是算法操作和參數(shù)結(jié)構(gòu)設定應合適，且需要大量的迭代運算，時間復雜度和空間復雜度都相當高。