基于改進SCE算法的Job Shop調(diào)度方法研究

趙付青, 張建林, 王俊彪, Jonrinaldi Jonrinaldi

調(diào)度是影響和制約制造行業(yè)中生產(chǎn)效率的一個重要因素,有效的調(diào)度策略能夠減少完成任務(wù)的時間,提高生產(chǎn)效率,從而給企業(yè)和社會帶來較高的經(jīng)濟效益。Job Shop調(diào)度是一種典型的生產(chǎn)調(diào)度問題,且已有研究已經(jīng)證明其屬于典型NP-hard問題[1],對Job Shop調(diào)度問題的研究也成為企業(yè)和研究者的熱門課題。

近年來,基于生物進化思想的智能優(yōu)化方法被大量用于求解各種Job Shop調(diào)度問題,并取得了較好的效果,主要有模擬退火[2]、遺傳算法[3]、蛙跳算法[4]和粒子群優(yōu)化算法[5]。但對于Job Shop調(diào)度問題而言,其存在較多的局部最優(yōu)解,很多智能算法在求解時容易陷入局部最優(yōu)值,往往產(chǎn)生不了預(yù)期的效果。SCE算法是一種較新的智能群體算法,該算法結(jié)合了混洗方法,使得空間中每個個體的信息能夠得到全局共享,因此具有較強的全局解搜索能力,避免陷入局部最優(yōu)。目前該算法已被廣泛應(yīng)用于各個領(lǐng)域[6-7]。

Job Shop調(diào)度問題是一類典型的組合優(yōu)化問題,目前,SCE算法用于求解生產(chǎn)調(diào)度方面的研究很少,所以本文提出將SCE算法用于Job Shop調(diào)度問題中,對工件的加工完成時間進行求解。由于基本SCE算法在獲取最優(yōu)解時存在求解速度慢和求解質(zhì)量差等缺點,本文對基本的SCE算法進行改進,通過改進基本SCE算法中個體的進化策略,使得每一代個體的進化方向趨向于當前群體中的最優(yōu)個體,從而提高了求解速度以及最終解的質(zhì)量。

1 SCE算法

1.1 SCE算法描述

SCE算法是Duan等人[8]在解決概念性降雨模型的參數(shù)評估時提出來的,其結(jié)合了單純形算法、生物進化和復(fù)合混洗等方法的優(yōu)點,使得SCE算法不僅具有有效性和健壯性,同時也具有高效性和靈活性。確定性的搜索策略能夠更有效地引導最優(yōu)解的收斂。已有研究表明,SCE算法在求解非線性復(fù)雜、非凸等高維問題時表現(xiàn)出更好的優(yōu)化效果。

SCE算法的原理是通過單純形法在待解問題的合法空間中的一個局部區(qū)域產(chǎn)生一個新的解,然后通過復(fù)合體混洗的方法使得該新解的信息在整個合法空間中得到共享,從而避免產(chǎn)生局部最優(yōu)解的概率。

1.2 SCE算法的步驟

Step 1 確定復(fù)合體的個數(shù)p和每個復(fù)合體中的個數(shù)m。計算初始樣本的大小s=p*m。

Step 2 在可行域中隨意生成s個樣本點數(shù)x{x1,x2,…,xs},并計算每個點xi的函數(shù)值fi。

Step 3 將生成的s個樣本點按照函數(shù)值升序進行排列,并將它們存儲在數(shù)組D中,即D={(xi,fi),i=1,2,…,s},其中i=1表示最小的函數(shù)值。

Step 5 對每個復(fù)合體Ak分別使用復(fù)合體進化算法(CCE)進行計算。

Step 6 將新產(chǎn)生的每個復(fù)合體按照函數(shù)值升序重新進行排序,并將排序后的結(jié)果存儲到數(shù)組D中,即D={Ak,k=1,…,p}。

Step 7 如果結(jié)果滿足收斂條件,則停止,否則返回Step 4。

1.3 復(fù)合進化算法(CCE)

Step 1 給定q、α、β的初始值。其中q表示子復(fù)合體的個數(shù),α表示子代迭代的次數(shù),β表示每個復(fù)合體進化的次數(shù),各參數(shù)值須滿足約束條件2≤q≤m,α≥1,β≥1。

Step 3 利用三角形概率分布從復(fù)合體Ak中隨機選取q個點ui,…,uq構(gòu)成子復(fù)合體。然后將q個頂點和它們的相對位置存儲在數(shù)組B={(ui,vi),i=1,…,q}和L中,其中vi是點ui的函數(shù)值。

Step 4 對q個點構(gòu)成的子復(fù)合體進化:

2) 計算新頂點r=2g-uq,其中r為頂點Uq對中心位置g的對稱映射點,即為Uq對應(yīng)的反射點。

3) 若頂點r在可行域解空間H中,計算函數(shù)值fz,并轉(zhuǎn)到4);否則計算含有Ak的最小超正方體H∈Rn,在該正方體中隨機地產(chǎn)生一個點z,計算其函數(shù)值fz,使得r=z,并設(shè)fr=fz。

4) 若fr

5) 若fc

6) 重復(fù)1)～5)α次。

Step 5 用產(chǎn)生的子代替換掉數(shù)組B中對應(yīng)的父代。重新按照函數(shù)值升序進行排列。

Step 6 重復(fù)執(zhí)行Step 2到Step 6β次。

2 Job Shop調(diào)度問題

2.1 問題描述及數(shù)學模型

Job Shop調(diào)度問題可描述為:在m臺機器上加工n個工件,每個工件都有自己的加工工序且在各個機器上的加工時間已知。其目標就是確定每臺機器上各工件的加工順序,從而使得某種特定性能指標達到最優(yōu)。以最小化工件的最大完成時間為目標的Job Shop調(diào)度問題的數(shù)學模型如(1)式所示:

(1)

(2)

(3)

式中:cik表示第i個工件在第k臺機器上的完成時間,pik表示工件i在機器k上的加工時間,M表示一個足夠大的正數(shù),aihk表示機器h先于機器k加工工件i,xijk表示工件i先于工件j在機器k上加工。

3 基于改進SCE算法的Job Shop調(diào)度問題

3.1 編碼機制

本文采用基于工序編碼的方式進行編碼。對于一個m×n的Job Shop調(diào)度,編碼后的序列由工件的編號組成,長度為m×n,同一工件的所有工序都采用其編號表示,并根據(jù)它們在序列中出現(xiàn)的順序確定它們的加工順序。例如序列[2 1 1 1 3 2 2 3 3],其中1、2、3分別代表工件J1、J2、J3的編號,在序列中的順序代表工件依次進行的加工操作。

為了使SCE算法能夠合理地求解組合優(yōu)化問題,本文采用序列映射方式將連續(xù)解空間的變量映射到離散空間中。以3×3的Job Shop調(diào)度為例,具體過程如圖1所示,首先在[0,1]區(qū)間隨機產(chǎn)生一長度為3×3的實數(shù)序列1,然后按從大到小的順序進行排序,并依次記錄其所在的相應(yīng)位置,便可產(chǎn)生序列2。將序列2中的每個數(shù)字除以待解問題中的設(shè)備數(shù)目m,可產(chǎn)生序列3,此序列即為SCE算法在求解Job Shop調(diào)度問題時的編碼序列,其代表待解問題的一個候選解。

圖1 實數(shù)空間到離散空間的映射

3.2 解碼機制

采用順序插入解碼機制。其過程為:①將已有序列轉(zhuǎn)化成一個有序操作表;②利用產(chǎn)生的操作表以及對應(yīng)的工藝約束對各操作以最早允許加工時間逐一進行加工;③產(chǎn)生對應(yīng)的調(diào)度方案。

表1 工件的加工時間

對于一個3×3的Job Shop調(diào)度,其加工時間和順序如表1。假設(shè)有一序列 [2 1 1 1 2 2 3 3 3],由解碼機制可產(chǎn)生有序操作表[O211,O111,O122,O133,O223,O232,O312,O321,O333],其中Oijk表示工件i的第j次操作在機器k上。對照機器和工件的工藝約束條件,可產(chǎn)生相應(yīng)的調(diào)度如圖2所示。

圖2 序列 [2 1 1 1 3 2 2 3 3] 的調(diào)度圖

3.3 適應(yīng)度函數(shù)

根據(jù)2.1建立的Job Shop調(diào)度數(shù)學模型,以最小化工件的最大完成時間為目標,確定目標函數(shù)為fitness,如公式(4)所示:其中C為工件的完成時間。

fitness=min {maxC}

(4)

3.4 基于改進SCE算法的Job Shop調(diào)度

基本SCE算法在求解比較復(fù)雜的問題時,存在求解速度慢以及求解質(zhì)量差等缺點。從基本SCE算法的求解過程看出,其新一代個體解的產(chǎn)生是通過復(fù)合體中全部個體的中心點進行反射和收縮的,這種進化方式并沒有很好地沿著當前復(fù)合體中最優(yōu)個體的方向進行。因此本文對基本SCE算法進行改進,通過改變個體的進化策略,使下一代個體的進化方向更加趨向于當前群體中的最優(yōu)個體。基本SCE算法和改進SCE算法中個體的進化方式分別如公式(5)～(8)所示。

基本SCE算法:

反射點:

Xref=2*Ce-Xw

(5)

收縮點：

(6)

改進SCE算法:

反射點：

St=t*Ce+(1-t)*Xb0

Xref=2*St-Xw

(7)

收縮點:

St=t*Ce+(1-t)*Xb0

(8)

式中：Xw為復(fù)合體中適應(yīng)度最低的個體；Ce為復(fù)合體中個體的中心位置；Xb為復(fù)合體中適應(yīng)度最高的個體；Xref為產(chǎn)生的反射點,Xcon為收縮點。

可以看出,改進的SCE算法中,中心點的產(chǎn)生策略更多地借鑒了最優(yōu)個體Xb的信息,使得產(chǎn)生的新解更趨近于Xb的區(qū)域。

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

假設(shè)待解調(diào)度問題中工件數(shù)目為N,機器數(shù)目為M。結(jié)合改進SCE算法的流程可得,該算法主要由4個部分組成:①計算目標函數(shù)值,其復(fù)雜度為O(pmMN);②對整個群體中個體排序,最壞情況下其復(fù)雜度為O(pm*pm);③為復(fù)合體進化部分,即CCE算法,主要包括2個部分:a)對q個個體排序,最壞情況下其復(fù)雜度為O(q2)；b)對m個個體進行排序,最壞情況下其復(fù)雜度為O(m2),在CCE迭代β次的情況下,其復(fù)雜度為O(β)*(O(q2)+O(m2)),約為O(m2);④為進化后的整個個體混洗排序,最壞情況下其復(fù)雜度為O(pm*pm)。

利用文獻[7]中提出的SCE算法參數(shù)關(guān)系式,在整個SCE算法迭代k次的情況下,用于求解Job Shop調(diào)度問題的改進SCE算法復(fù)雜度為:

4 實驗仿真與結(jié)果分析

為驗證本文算法的有效性,選取了11個經(jīng)典調(diào)度問題進行求解。算法采用MATLAB編寫,運行環(huán)境為Windows XP Professional,1.73 GHz CPU,1G的內(nèi)存,每次實驗運行20次。算法終止的條件是:計算目標函數(shù)值的最大次數(shù)maxn>10 000時。實驗結(jié)果如表2所示:

表2 改進SCE算法的計算結(jié)果

可以看出,改進的SCE算法在該11個經(jīng)典調(diào)度問題上都取得了很好的效果,在參數(shù)一定的情況下都能夠獲得理論最優(yōu)解。

圖3～圖8分別是FT06、LA09和LA12的甘特圖和收斂曲線圖,可以看出,改進的SCE算法在一定的迭代次數(shù)下都可以有效地收斂到最優(yōu)值。

圖3 FT 06問題的一個最優(yōu)解的甘特圖 圖4 FT06的求解過程 圖5 LA 09問題的一個最優(yōu)解的甘特圖

圖6 LA09的求解過程 圖7 LA 12問題的一個最優(yōu)解的甘特圖 圖8 LA12的求解過程

表3 改進SCE算法和基本SCE算法的比較

圖9 改進SCE算法和基本SCE算法求解性能比較

表3對基本SCE算法和改進的SCE算法在求解經(jīng)典調(diào)度問題時的情況進行了對比,可以看出:基本SCE算法只有在求解LA01、LA05、LA10和LA14問題時獲得了理論最優(yōu)解,圖9為2個算法所求最優(yōu)解分別與理論最優(yōu)解之差的對比圖,從表3中可以得出,在兩者都求出最優(yōu)解的情況下,除了在LA01問題中改進SCE算法所用的時間稍大于基本的SCE算法之外,另外3個問題中改進的SCE算法所用時間都要少于基本SCE算法。可以看出,改進的SCE在求解Job Shop調(diào)度問題上相比基本SCE算法更加有效。

5 結(jié) 論

本文以求解Job Shop調(diào)度中工件的最小完成時間為目標,研究了改進的SCE算法在Job Shop調(diào)度中的應(yīng)用。同時也對改進SCE算法和基本SCE算法在Job Shop調(diào)度問題中的性能進行了對比分析。結(jié)果表明,改進的SCE算法在求解Job Shop調(diào)度問題上是有效的,從而為解決該類問題提供了一種新的途徑。

參考文獻：

[1] Cook S A. The Complexity of Theorem-Proving Procedures[C]∥Proc of the 3rdAnnual ACM Symp on Theory of Computing. New York: ACM Press, 1971, 151-158

[2] Atabak E, Maghsud S, Seyda T, Afshin E. A Simulated Annealing Algorithm for the Job Shop Cell Scheduling Problem with Intercellular Moves and Reentrant Parts[J]. Computers & Industrial Engineering, 2011, 61(1): 171-178

[3] 王凌. 車間調(diào)度及其遺傳算法[M]. 北京:清華大學出版社,2002

Wang Ling. Shop Scheduling with Genetic Algorithms[M]. Beijing: Tsinghua University Press, 2002 (in Chinese)

[4] Wannaporn T, Arit T. A Combination of Shuffled Frog Leaping and Fuzzy Logic for Flexible Job Shop Scheduling Problems[J]. Procedia Computer Science, 2011, 6: 69-75

[5] Gary G Y, Brian I. Job Shop Scheduling Optimization through Multiple Independent Particle Swarms[J]. International Journal of Intelligent Computing and Cybernetics, 2009, 2(1): 5-33

[6] Samer A, Barakat, Salah Altoubat. Application of Evolutionary Global Optimization Techniques in the Design of RC Water Tanks[J]. Engineering Structures, 2009, 31: 332-344

[7] Charles N M, Donath M. Shuffled Complex Evolution Algorithms in Infrastructure Works Programming[J]. Journal of Computing in Civil Engineering. 2004, 18(3): 257-266

[8] Duan Q Y, Gupta V K, Sorooshian S. Shuffled Complex Evolution Approach for Effective and Efficient Global Minimization[J]. Journal of Optimization Theory and Application, 1993, 76(3): 501-521