趙 芮，顧幸生

(華東理工大學(xué) 化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237)

0 引 言

零空閑置換流水車間調(diào)度問題(No-idle Permutation Flow Shop Scheduling Problem, NPFSP)廣泛存在于陶瓷熔塊生產(chǎn)、玻璃纖維加工、鑄造、集成電路生產(chǎn)和煉鋼等現(xiàn)代工業(yè)中。關(guān)于調(diào)度問題中零空閑概念的提出者在學(xué)術(shù)界存在爭議[1-2]，一部分學(xué)者認(rèn)為是Adiri和Pohoryles于1982年考慮了求解總流水時(shí)間的帶零空閑約束的流水車間調(diào)度問題；另一部分學(xué)者認(rèn)為是Babushkin等人早在1975年就嘗試以最小化makespan為目標(biāo)，對具有零空閑約束的類似流水車間的調(diào)度問題進(jìn)行了研究。但毋庸置疑的是，自此NPFSP的研究受到了廣泛的關(guān)注，并在近年取得了很大的進(jìn)展。

然而，這種假設(shè)所有機(jī)器都是零空閑的情況較為少見，實(shí)際生產(chǎn)過程中更多的是混合零空閑調(diào)度問題，即只有部分機(jī)器受到零空閑狀態(tài)的約束。目前國內(nèi)外已經(jīng)有學(xué)者對混合零空閑置換流水車間調(diào)度問題(Mixed No-idle Permutation Flow Shop Scheduling Problem, MNPFSP)進(jìn)行了研究。PAN等[3]首先對混合零空閑流水車間進(jìn)行研究，提出了一種有效的迭代貪婪(Iterative Greedy, IG)算法來最小化makespan；CHENG等[4]將分布式調(diào)度運(yùn)用到混合零空閑流水車間中，并提出一種新的基于云理論的IG算法，用于最小化makespan；ROSSI等[5]針對存在序列相關(guān)準(zhǔn)備時(shí)間的混合零空閑流水車間，開發(fā)了一種新的有效的啟發(fā)式算法。

雖然對MNPFSP的研究已經(jīng)取得了一些進(jìn)展，但在算法求解方面還可以有更深入的研究。對于MNPFSP的計(jì)算復(fù)雜性，已被證明是NP完全問題[1,3]。因此，只有小規(guī)模的問題能通過精確算法在合理的計(jì)算時(shí)間內(nèi)找到最優(yōu)解，隨著問題規(guī)模的逐漸增大，其復(fù)雜性呈現(xiàn)指數(shù)爆炸效應(yīng)。構(gòu)造性啟發(fā)式方法雖然能在較短時(shí)間內(nèi)構(gòu)造出近似最優(yōu)解，但難以保證解的質(zhì)量。因此，近年來的研究趨勢是將啟發(fā)式規(guī)則與智能優(yōu)化算法相結(jié)合求解調(diào)度問題，從而大大提高了智能優(yōu)化算法的性能[6]。

如上所述，MNPFSP是NPFSP一個(gè)比較新的變體，成功應(yīng)用于MNPFSP的智能優(yōu)化算法還很少。引力搜索算法(Gravitational Search Algorithm, GSA)[7]是一種模擬自然界中粒子相互吸引的智能優(yōu)化算法，已在一些生產(chǎn)調(diào)度問題上取得了一定成果，但目前還沒有用于MNPFSP和NPFSP的求解。BARZEGAR等[8]利用GSA和有色Petri網(wǎng)求解最小化makespan的柔性作業(yè)車間調(diào)度問題；針對作業(yè)車間調(diào)度，吳瓊等[9]提出一種協(xié)同粒子群和GSA混合算法最小化makespan，結(jié)果表明該算法較粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法和遺傳算法(Genetic Algorithm, GA)等在求解作業(yè)車間調(diào)度問題上更具優(yōu)越性。GSA作為一種隨機(jī)優(yōu)化算法，其原理簡單，具有較強(qiáng)的全局搜索能力，收斂性也被證明優(yōu)于粒子群優(yōu)化算法、遺傳算法等智能優(yōu)化算法[10-12]。然而，隨著種群的進(jìn)化，個(gè)體受最優(yōu)解吸引逐漸群聚在一起，導(dǎo)致GSA在進(jìn)化后期收斂速度過快，無法完全覆蓋所有解，尋優(yōu)精度不高。因此，對GSA進(jìn)行改進(jìn)，并將其應(yīng)用于MNPFSP中，具有重要的研究意義。

針對混合零空閑置換流水車間問題的特點(diǎn)，本文采用GSA解決以最小化總流水時(shí)間為目標(biāo)的MNPFSP，提出一種基于可變迭代貪婪(variable Iterative Greedy, vIG)的引力搜索算法，利用vIG對解空間較強(qiáng)的局部開發(fā)能力來改善GSA的精度。為了將GSA算法用于離散的調(diào)度問題，使用ROV規(guī)則進(jìn)行編碼。算法的初始化階段，融入NEH(Nawaz-Enscore-Ham)啟發(fā)式規(guī)則，以獲得較好的初始解，提高算法的搜索效率；針對傳統(tǒng)GSA隨著種群的進(jìn)化，個(gè)體受最優(yōu)解吸引逐漸群聚在一起導(dǎo)致尋優(yōu)精度不高的問題，將具有較強(qiáng)局部搜索能力的vIG算法[13-14]與GSA相結(jié)合，提高了求解質(zhì)量；為了加快vIG算法的收斂速度、提高其求解精度，加入?yún)⒄詹迦敕桨?Referenced Insertion Scheme, RIS)[15-16]；而針對vIG算法容易陷入局部最優(yōu)的缺陷，引入模擬退火思想[2,15]，以一定概率接受劣解，以增加算法多樣性。實(shí)驗(yàn)表明，采用本文提出的基于可變迭代貪婪的引力搜索算法解決MNPFSP是可行且有效的。

1 混合零空閑置換流水車間調(diào)度問題

MNPFSP描述如下：n個(gè)工件J={1,2,…,n}按照相同的順序在m臺機(jī)器M={1,2,…,m}上進(jìn)行加工。在任意時(shí)刻，每臺機(jī)器最多加工一個(gè)工件，每個(gè)工件最多只能被一臺機(jī)器加工[17]。為了遵循零空閑的約束，機(jī)器i加工第j個(gè)工件的開始時(shí)間必須等于第j-1個(gè)工件的加工完成時(shí)間。換句話說，每臺機(jī)器加工任意兩相鄰工件時(shí)沒有空閑時(shí)間。

MNPFSP是NPFSP和置換流水車間調(diào)度問題(Permutation Flow Shop Scheduling Problem, PFSP)的混合，是指在加工過程中，有的機(jī)器處于零空閑狀態(tài)，有的機(jī)器不處于零空閑狀態(tài)。用π={π1,π2,…,πl(wèi),…,πn}來表示一個(gè)工件排序，用[l]來表示排序中處于位置l的工件，即πl(wèi);用pi,[l]來表示工件πl(wèi)在機(jī)器i上的加工時(shí)間;Si,[l]和Ci,[l]分別表示工件πl(wèi)在機(jī)器i上加工的開始時(shí)間和完成時(shí)間;ai表示工件πl(wèi)在機(jī)器i上開始加工前的總延遲時(shí)間。將具有零空閑狀態(tài)的機(jī)器集合記為M′，則MNPFSP的公式如下[3]：

(1)

(2)

(3)

(4)

(5)

調(diào)度問題的目標(biāo)是求得一個(gè)工件加工序列π，使各工件按照該序列加工時(shí)總流水時(shí)間(Total Flow Time, TFT)最小，目標(biāo)函數(shù)TFT可表達(dá)為：

(6)

2 引力搜索算法

GSA是伊朗的克曼大學(xué)教授RASHEDI等[7]于2009年提出的一種新型智能優(yōu)化算法，算法靈感來源于粒子受萬有引力的作用。它可以理解為眾多的粒子向具有最大慣性質(zhì)量的粒子不斷靠近的過程。算法中，種群由慣性質(zhì)量各不相同的粒子組成，每個(gè)粒子的位置對應(yīng)問題的一個(gè)解，指引算法進(jìn)行迭代優(yōu)化的引力和慣性質(zhì)量是由適應(yīng)度函數(shù)值確定的。當(dāng)種群中出現(xiàn)慣性質(zhì)量大的粒子時(shí)，其他粒子都朝著慣性質(zhì)量大的粒子運(yùn)動(dòng)，從而使算法收斂到最優(yōu)解。

假設(shè)在n維搜索空間中有NP個(gè)粒子，則第i個(gè)粒子的位置表示為：

(7)

在第t次迭代時(shí)，種群中第j個(gè)粒子作用在第i個(gè)粒子上的引力表示為：

(8)

式中：Mi(t)和Mj(t)分別表示被作用粒子i和作用粒子j的慣性質(zhì)量;Rij(t)為兩個(gè)粒子i和j之間的歐氏距離;ε為一個(gè)很小的常量;G(t)為第t次迭代時(shí)的引力系數(shù)，它隨時(shí)間逐漸減小以控制搜索精度，是初始值G0和迭代次數(shù)t的函數(shù)：

(9)

式中：α為控制G(t)衰減速率的常數(shù);T為迭代總次數(shù)。一般G0=100，α=20。

(10)

(11)

式中randj是范圍在[0,1]之間的隨機(jī)數(shù)。

粒子的慣性質(zhì)量可根據(jù)種群的適應(yīng)度值fit來計(jì)算：

(12)

(13)

worst(t)和best(t)分別表示當(dāng)前種群中適應(yīng)度的最差值和最好值，由于本文求解的是最小值問題，定義worst(t)和best(t)為種群中適應(yīng)度最大值和最小值。

GSA算法中，每一次迭代種群的速度和位置更新公式為：

(14)

(15)

式中randi是區(qū)間[0,1]中的均勻隨機(jī)變量。

3 求解MNPFSP的貪婪引力搜索算法

3.1 編碼方案與ROV轉(zhuǎn)換

由于標(biāo)準(zhǔn)的GSA是處理連續(xù)問題的優(yōu)化算法，其連續(xù)編碼方案不能直接用于求解離散的MNPFSP，而IG算法是基于工件排序直接進(jìn)行編碼的，需要將兩者的解空間進(jìn)行轉(zhuǎn)換。本文基于升序排列(Ranked-Order-Value, ROV)規(guī)則將多維空間的連續(xù)粒子位置與工件排序進(jìn)行一一對應(yīng)映射，其原理如表1所示。將粒子的位置分量按從小到大的順序排列，最小的位置分量賦值為1，次小的位置分量賦值為2，以此類推，從而形成完整的工件排序。如果分量值相同，則粒子維度較小的賦予分量值較小，粒子維度較大的賦予分量值較大。表1中粒子Xi的工件排序?yàn)棣衖=(4,3,2,6,1,5)。

表1 粒子Xi的ROV轉(zhuǎn)換

3.2 種群初始化

好的初始種群可以有效加快收斂速度并提高解的質(zhì)量。為了提高搜索效率，使解既有較高的質(zhì)量又有較大的發(fā)散度，在初始化中引入NEH啟發(fā)式規(guī)則[18]產(chǎn)生第一個(gè)解，其余解隨機(jī)生成。

NEH啟發(fā)式規(guī)則由排序和插入兩個(gè)階段組成，其基本操作如下：

步驟2按總加工時(shí)間Pj的降序，對工件進(jìn)行排序。

步驟3取k=1和k=2兩個(gè)工件進(jìn)行排序，并選擇總流水時(shí)間小的那個(gè)排序作為當(dāng)前部分序列。

步驟4k:=k+1，將第k個(gè)工件插入當(dāng)前部分序列(包含k-1個(gè)工件)所有可能的k個(gè)位置中，得到k種不同的工件排序，然后在其中選出使總流水時(shí)間最小的排序作為當(dāng)前部分序列(包含k個(gè)工件)。

步驟5如果k=n，則停止，否則轉(zhuǎn)步驟4。

3.3 貪婪引力搜索算法

GSA算法具有較強(qiáng)的全局搜索能力，種群多樣性也很好，但其收斂速度過快，不能完全覆蓋所有解，算法精度不高。本文提出的貪婪引力搜索算法(Greedy Gravitational Search Algorithm, GGSA)以GSA為主框架，在進(jìn)化后期(即最優(yōu)解連續(xù)L代不再變化時(shí))，加入局部搜索能力強(qiáng)的帶RIS的可變迭代貪婪算法(vIG_RIS)，能夠很大程度上提高GSA算法的尋優(yōu)精度，從而改善收斂效果。

vIG_RIS算法由vIG算法[13]和RIS[16]局部搜索兩部分組成，偽代碼如圖1所示。vIG_RIS實(shí)質(zhì)上是迭代貪婪(IG)算法的一種改進(jìn)。RUIZ等[19]研究表明，IG算法對于求解離散的調(diào)度問題十分有效。并且，該算法的破壞重構(gòu)(destruct construct)機(jī)制直接基于工件排序進(jìn)行，無需編碼、解碼，更適合離散的調(diào)度問題。由此可以看出，引入vIG_RIS算法是十分有效的。

IG中毀壞工件數(shù)d是一個(gè)比較關(guān)鍵的參數(shù)，若d太小，則算法搜索范圍較小、收斂較慢;若d太大,則會影響算法效率。因此，一般選取固定的單一值[20]。vIG算法在此基礎(chǔ)上引入了變鄰域的概念，使得在構(gòu)造新解的過程中原本固定的參數(shù)d可變，從而增加了解的多樣性。當(dāng)解沒有被改進(jìn)時(shí)，d從1逐次遞增到n-1；一旦解有所改進(jìn)，則將d再次固定為d=1，從頭開始搜索。

圖1中，Destruction和Construction兩個(gè)階段用來生成新的解π1。在Destruction階段，首先從π中移除隨機(jī)選擇的d個(gè)工件，產(chǎn)生πR和πD兩個(gè)排序，其中πR包含d個(gè)移除工件，πD包含剩余的n-d個(gè)工件;在Construction階段，將πR的第一個(gè)工件插入πD中，產(chǎn)生n-d+1個(gè)部分解，選擇其中最優(yōu)解用于下一次迭代,接下來將第2個(gè)工件插入πD中，……，直至πD中包含n個(gè)工件，形成完整的調(diào)度解。

vIG_RIS算法在vIG算法的基礎(chǔ)上對解π1進(jìn)行了基于插入和交換的隨機(jī)局部搜索RIS，由此產(chǎn)生了一個(gè)新的解π2。當(dāng)π2是一個(gè)劣解時(shí)，使用OSMAN等[21]提出的模擬退火的收斂判據(jù)以概率exp{-(f(π2)-f(π))/Temp}接受它。通過該方式，當(dāng)前解在搜索過程中獲得了一些劣解而得以多樣化，以此來期望逃離局部最優(yōu)。

(16)

式中：Temp為恒定的溫度；τ為調(diào)整溫度Temp的冷卻系數(shù)。

如圖2所示為RIS的程序偽代碼。在RIS中，πref為參照排序，它是迄今為止得到的最優(yōu)解。舉例來說，假設(shè)πref=(3,1,5,2,4)且當(dāng)前解π=(4,2,5,1,3)，RIS首先在π中找到工件3，從π中移除工件3并將其插入π的所有可能位置。接下來，在π中找到工件1，從π中移除工件1并將其插入π的所有可能位置。重復(fù)該過程，直至πref的所有工件均被參考過?？梢钥闯?，RIS的主要概念是：工件移除由參照排序引導(dǎo)而不是隨機(jī)選擇。

vIG_RIS算法在IG的基礎(chǔ)上，增加了可變的鄰域結(jié)構(gòu)，使得算法在搜索過程中能更多地探索解空間，有更大可能找到更優(yōu)解，使解的多樣性得到了改善。而且該算法以一定概率接受劣解，能在一定程度上避免陷入局部最優(yōu)，還通過RIS增強(qiáng)了局部搜索能力，但是其尋找解的過程較為緩慢。本文提出的GGSA算法在GSA算法迭代的后期引入vIG_RIS算法進(jìn)行局部搜索，vIG_RIS的尋優(yōu)開始于當(dāng)前的最優(yōu)解，利用vIG_RIS優(yōu)秀的局部開發(fā)能力幫助其提高尋優(yōu)精度，然后再回到GSA算法的主體中繼續(xù)迭代。這樣既可以平衡算法的收斂速度，又可以提高尋優(yōu)精度，從而提高解的質(zhì)量，取得好的收斂效果。

GGSA算法的總體流程如圖3所示。其中L為最優(yōu)值不變的最大代數(shù)，F(xiàn)best為當(dāng)前最優(yōu)適應(yīng)度值，當(dāng)Fbest經(jīng)過L代都沒有發(fā)生變化時(shí)，算法轉(zhuǎn)入vIG_RIS搜索。若vIG_RIS搜索得到的解的適應(yīng)度值小于Fbest，則將其替換為種群X中隨機(jī)的一個(gè)粒子。

4 仿真實(shí)驗(yàn)

算法基于MATLAB 2015實(shí)現(xiàn)，在處理器為2.40 GHz、內(nèi)存為64.0 GB的PC機(jī)下運(yùn)行。為了檢驗(yàn)GGSA算法求解MNPFSP的有效性，本章在正交實(shí)驗(yàn)確定了參數(shù)的基礎(chǔ)上，采用Taillard Benchmark問題[22]中的9種不同規(guī)模的共90個(gè)典型算例進(jìn)行測試，并將仿真結(jié)果與DFWA-LS算法[23]、vIG算法[13]以及IGeDC算法[3]進(jìn)行比較。

由MNPFSP的實(shí)際生產(chǎn)過程可知，第一臺機(jī)器一般處于零空閑狀態(tài)，最后一臺機(jī)器一般不處于零空閑狀態(tài)，而大多數(shù)工廠生產(chǎn)中需要零空閑約束的機(jī)器占比較少。因此，在仿真測試中設(shè)置兩臺機(jī)器處于零空閑狀態(tài)：第一臺機(jī)器和隨機(jī)選擇的除第一臺和最后一臺機(jī)器外的中間一臺機(jī)器(用符號Mset來表示)。實(shí)驗(yàn)中每個(gè)算例對應(yīng)的Mset分別進(jìn)行如下設(shè)置：m=5時(shí)，每種規(guī)模下的算例按從小到大的序號排列，其Mset依次為[4 2 2 4 3 4 3 3 2 4]；同樣地，m=10時(shí)，Mset依次為[3 5 8 4 7 5 6 9 4 6]；m=20時(shí)，Mset依次為[11 15 4 7 10 5 13 17 6 18]。不同算法對比時(shí)，每個(gè)算例中處于零空閑狀態(tài)的機(jī)器編號是相同的。

為確定算法中最大迭代次數(shù)T、種群規(guī)模NP以及參數(shù)G0、α、τ、L和tmax的取值，利用正交設(shè)計(jì)方法，將每個(gè)參數(shù)都設(shè)為3個(gè)因子，每個(gè)因子設(shè)置3個(gè)不同水平，選擇L18(37)正交表進(jìn)行正交實(shí)驗(yàn)，如表2所示。正交實(shí)驗(yàn)在算例Ta043上進(jìn)行，每種參數(shù)組合各進(jìn)行20次仿真，正交實(shí)驗(yàn)結(jié)果如表3所示。以相對百分比偏差(Relative Percentage Deviation, RPD)的平均值作為響應(yīng)變量(Response Variable, RV)：RPD=(TFTi-TFT*)/TFT*×100%，其中TFTi為第i組參數(shù)組合下得到的總流水時(shí)間值，TFT*為所有參數(shù)組合下算法運(yùn)行得到的總流水時(shí)間最優(yōu)值。

表2 正交設(shè)計(jì)因子水平表

由正交實(shí)驗(yàn)結(jié)果可見，參數(shù)對算法性能的影響程度從大到小依次為：tmax，T，L，α，G0，τ，NP。由圖4可見，參數(shù)tmax和T對算法性能影響的水平趨勢相同：較大的迭代次數(shù)有利于算法進(jìn)行更深入的搜索。參數(shù)L的變化趨勢表明適當(dāng)減小參數(shù)L有利于算法避免早熟收斂或收斂緩慢。參數(shù)G0和α對算法性能的影響趨勢也大致相同，它們對平衡算法的全局搜索和局部搜索有著重要意義，既不能太大也不能太小。參數(shù)τ和NP的極差較小，但也不能說對算法性能完全沒有影響：參數(shù)τ的值要取的較小一些，如果τ的值太大，算法接受差解的概率太大，會導(dǎo)致算法在結(jié)束前不能找到足夠好的解；而適當(dāng)大的種群規(guī)模則對算法的多樣性有利。基于以上分析，采用如下參數(shù)設(shè)置進(jìn)行后續(xù)實(shí)驗(yàn)：tmax=10，T=2 000，L=10，NP=50，G0=100，α=20，τ=0.2。

表3 算例Ta041的正交實(shí)驗(yàn)結(jié)果

目前研究MNPFSP的文獻(xiàn)還非常少，尚無已知的最優(yōu)解。參考文獻(xiàn)[24]中分析比較Fm/prmu,no-idle/∑Cj問題的方法，將DFWA-LS算法、vIG算法、IGeDC算法以及GGSA算法產(chǎn)生的解與NEH規(guī)則產(chǎn)生的解進(jìn)行對比分析(如表4)。為了避免測試的隨機(jī)性帶來的誤差，每次不同的仿真都獨(dú)立運(yùn)行10次。結(jié)果以平均相對百分比偏差(Δavg)和標(biāo)準(zhǔn)偏差(Δstd)給出，其公式如下：

(17)

(18)

其中：N為規(guī)模相同的算例的數(shù)量;TFTi(H)表示H算法求解算例i的10次運(yùn)行結(jié)果的平均值;NEHi

為NEH規(guī)則下算例i的解。

表4 GGSA算法與其他各算法的比較結(jié)果

從表4中可以看出，對比4種算法，它們的標(biāo)準(zhǔn)偏差沒有統(tǒng)計(jì)學(xué)上的顯著差異，而GGSA算法的平均相對百分比偏差的絕對值更大，所求得的總流水時(shí)間更小，即GGSA算法可較好地應(yīng)用于MNPFSP，能在保證算法穩(wěn)定性的情況下找到比DFWA-LS算法、vIG算法和IGeDC算法更優(yōu)的解。

表5 平均相對誤差的比較結(jié)果

續(xù)表5

綜合表4和表5可以得出：對于Taillard Benchmark算例，GGSA算法的求解要優(yōu)于DFWA-LS算法、vIG算法和IGeDC算法，且一般而言(排除極個(gè)別算例)，隨著算例規(guī)模的增大，GGSA算法的求解效果也越來越好，這充分說明了GGSA算法在求解MNPFSP上的有效性和優(yōu)越性。

DFWA-LS、vIG、IGeDC和GGSA四種算法對Ta043算例的迭代收斂曲線如圖6所示，由比較結(jié)果可知，DFWA-LS和vIG算法的求解效果較差、精度較低，而IGeDC算法雖然收斂較快，但容易陷入局部最優(yōu)，GGSA算法由于在進(jìn)化的后期引入vIG_RIS，能夠在GSA找不到更優(yōu)解時(shí)加大對極值點(diǎn)鄰域的開發(fā)，提高其搜索精度，得到令人滿意的解。

5 結(jié)束語

本文將引力搜索算法應(yīng)用于求解以最小化總流水時(shí)間為目的的混合零空閑置換流水車間調(diào)度問題。在引力搜索算法的基礎(chǔ)上，引入具有較強(qiáng)局部開發(fā)能力的vIG算法,并對原引力搜索算法初始解的產(chǎn)生方式、vIG算法的局部搜索進(jìn)行了改進(jìn)，提出一種貪婪引力搜索算法(GGSA)，使其求解調(diào)度問題的精度更高，能夠得到更高質(zhì)量的解。針對零空閑機(jī)器數(shù)量較少的MNPFSP，在Taillard Benchmark算例上測試了本文提出的GGSA算法，并通過與DFWA-LS、vIG和IGeDC算法的對比，驗(yàn)證了GGSA算法在求解MNPFSP上的有效性和優(yōu)越性。下一步研究包括以下幾個(gè)方面：考慮將算法應(yīng)用于更廣泛的調(diào)度問題以及其他的優(yōu)化目標(biāo)；考慮MNPFSP中零空閑機(jī)器的其他情況。