張?jiān)?齊雪

(安徽科技學(xué)院信息與網(wǎng)絡(luò)工程學(xué)院， 安徽 鳳陽(yáng) 233100)

1 問(wèn)題重述

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

表1 各工序下每種加工件所需耗時(shí) min

假定，在等待進(jìn)入下一臺(tái)機(jī)器處理的過(guò)程中，不允許排在后面的加工件“插隊(duì)”。通常，總加工時(shí)間越短，成本越低，因此，需要設(shè)計(jì)合理的加工順序使總加工時(shí)間最短。

2 模型的假設(shè)、符號(hào)說(shuō)明與問(wèn)題分析

2.1 假設(shè)

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

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

(3) 每臺(tái)機(jī)器每次只能處理1個(gè)加工件，特定機(jī)器處理特定的工序。

(4) 等待下一臺(tái)機(jī)器處理時(shí)，不允許排在后面的加工件插隊(duì)。

(5) 所有機(jī)器同時(shí)運(yùn)轉(zhuǎn)，工件在機(jī)器之間的轉(zhuǎn)移時(shí)間不計(jì)，即機(jī)器的準(zhǔn)備時(shí)間不計(jì)。

(6) 所有機(jī)器正常運(yùn)行，不會(huì)出現(xiàn)故障。

(7) 所有工件同時(shí)到達(dá)，到達(dá)時(shí)間設(shè)為0。

2.2 符號(hào)說(shuō)明

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

2.3 問(wèn)題分析

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

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

3 算法及ctmax計(jì)算

3.1 Johnson算法

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

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

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

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

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

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

3.2 啟發(fā)式算法

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

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

(1)

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

(2)

其中

3.3 ctmax的計(jì)算

基于以上算法，得到最優(yōu)排序的完工時(shí)間。假設(shè)當(dāng)前加工順序?yàn)镺={o1，o2，…，on}，oi表示排在第i位的工件代號(hào)。對(duì)于o1，在機(jī)器k上的完工時(shí)間為其在機(jī)器k之前的累計(jì)工序時(shí)間；對(duì)于oi，在機(jī)器k上的完工時(shí)間取決于前一個(gè)工件在機(jī)器k上的完工時(shí)間，以及oi在前一臺(tái)機(jī)器上的最大完工時(shí)間。ci，oj表示工件oj在機(jī)器i上的完工時(shí)間。于是有(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)排序，并通過(guò)算法編程計(jì)算出最短時(shí)間。

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

4.1 CDS算法計(jì)算

首先完成CDS算法編程，輸入加工時(shí)間矩陣，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)得到計(jì)算結(jié)果：

makespan= 35

sort=[1 3 4 6 5 2]

sort=[3 1 4 6 5 2]

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

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

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

表3 最優(yōu)解sort=[3 1 4 6 5 2] 下的加工時(shí)間安排 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)順序，最長(zhǎng)完工時(shí)間同樣為35 min。同時(shí)，工件3和工件4的斜度指標(biāo)均為2。設(shè)想一下，如果將這兩個(gè)任務(wù)顛倒，也許結(jié)果更優(yōu)。

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

根據(jù)上述Gupta算法的不同斜度指標(biāo)，編寫(xiě)程序gupta.m，得到最優(yōu)排序?yàn)?/p>

sort =[3 1 4 6 5 2]

此最優(yōu)解與應(yīng)用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 ]，最長(zhǎng)完工時(shí)間也為35 min，并且所有的λ都不一樣。

4.3 關(guān)鍵工件法

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

sort =[1 3 4 6 5 2]

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

4.4 討論分析

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

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

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

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

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

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

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

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

最后,對(duì)比啟發(fā)式算法與枚舉法在此問(wèn)題上的運(yùn)算時(shí)間(見(jiàn)表6)。

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

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

5 遺傳算法

5.1 遺傳算法設(shè)計(jì)

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

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

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

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

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

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

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

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

(5) 適應(yīng)度函數(shù)。因?yàn)槟繕?biāo)函數(shù)是使得ctmax達(dá)到最大，因此，選擇上限值為79-ctmax。建立適應(yīng)度函數(shù)，F(xiàn)ITNESS=79-ctmax，將使得目標(biāo)函數(shù)最小的M個(gè)體作為下一代。

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

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

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

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

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

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

6 結(jié) 語(yǔ)

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

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