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

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

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

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

1 SCE算法

1.1 SCE算法描述

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

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

1.2 SCE算法的步驟

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

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

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

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

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

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

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

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

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

Step 4 對q個(gè)點(diǎn)構(gòu)成的子復(fù)合體進(jìn)化:

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

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

4) 若fr

5) 若fc

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

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

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

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

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

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

(1)

(2)

(3)

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

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

3.1 編碼機(jī)制

本文采用基于工序編碼的方式進(jìn)行編碼。對于一個(gè)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的編號,在序列中的順序代表工件依次進(jìn)行的加工操作。

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

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

3.2 解碼機(jī)制

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

表1 工件的加工時(shí)間

對于一個(gè)3×3的Job Shop調(diào)度,其加工時(shí)間和順序如表1。假設(shè)有一序列 [2 1 1 1 2 2 3 3 3],由解碼機(jī)制可產(chǎn)生有序操作表[O211,O111,O122,O133,O223,O232,O312,O321,O333],其中Oijk表示工件i的第j次操作在機(jī)器k上。對照機(jī)器和工件的工藝約束條件,可產(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ù)學(xué)模型,以最小化工件的最大完成時(shí)間為目標(biāo),確定目標(biāo)函數(shù)為fitness,如公式(4)所示:其中C為工件的完成時(shí)間。

fitness=min {maxC}

(4)

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

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

基本SCE算法:

反射點(diǎn):

Xref=2*Ce-Xw

(5)

收縮點(diǎn)：

(6)

改進(jìn)SCE算法:

反射點(diǎn)：

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

Xref=2*St-Xw

(7)

收縮點(diǎn):

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

(8)

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

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

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

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

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

4 實(shí)驗(yàn)仿真與結(jié)果分析

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

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

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

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

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

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

表3 改進(jìn)SCE算法和基本SCE算法的比較

圖9 改進(jìn)SCE算法和基本SCE算法求解性能比較

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

5 結(jié) 論

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

參考文獻(xiàn)：

[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]. 北京:清華大學(xué)出版社,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