基于改進(jìn)和聲搜索算法的柔性作業(yè)車間調(diào)度研究

向雙玲 安友軍 劉秀鳳

摘要：結(jié)合柔性作業(yè)車間調(diào)度問題，對和聲搜索算法中新和聲的產(chǎn)生方式及變異操作進(jìn)行改進(jìn)，提出了改進(jìn)和聲搜索算法。在改進(jìn)算法中，對新和聲的合成方式采用精英保留策略，保證新和聲的較優(yōu)性能；在迭代過程中引入變領(lǐng)域搜索算法，以提高算法的全局搜索能力。最后通過仿真實驗對改進(jìn)算法的求解性能進(jìn)行檢驗，驗證了改進(jìn)算法在求解柔性作業(yè)車間問題上的可行性及有效性。

Abstract： Combined with the flexible job shop scheduling problem， the new harmony mode and the mutation operation in the harmony algorithm are improved， and an improved harmony search algorithm is proposed. In the improved algorithm， the elite harmony strategy is adopted for the synthesis of the new harmony to ensure the superior performance of the new harmony. The variable domain search operator is introduced in the iterative process to further improve the global search ability of the algorithm. Finally， the performance of the improved algorithm is tested by experimental simulation， and the feasibility and effectiveness of the algorithm in solving the flexible work shop problem are verified.

關(guān)鍵詞：柔性作業(yè)車間調(diào)度；和聲搜索算法；精英保留策略；變鄰域搜索

Key words： flexible job shop scheduling；harmony algorithm；elite retention strategy；variable neighborhood search

中圖分類號：TP181 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2018）31-0274-04

0 引言

柔性作業(yè)車間調(diào)度問題（Flexible Job-Shop Scheduling Problem，F(xiàn)JSP）是一個經(jīng)典且復(fù)雜的組合優(yōu)化問題，其中，求解該問題最常用的方法為元啟發(fā)式算法，例如：遺傳算法[1]，粒子群算法[2]，蟻群算法[3]等。和聲搜索（Harmony Research，HS）算法是由韓國學(xué)者Geem Z W[4]等人在受到音樂創(chuàng)作的啟發(fā)后，提出的一種全局搜索算法。王勇臻等[5]用和聲搜索算法求解了旅行商問題；劉樂等[6]針對單機(jī)最大延遲重調(diào)度問題，設(shè)計了一種和聲變鄰域搜索算法。

與其他算法相比，和聲搜索算法的結(jié)構(gòu)設(shè)計簡單、靈活通用，易與其他算法混合使用。針對FJSP的特點，借鑒變鄰域較強(qiáng)的局部搜索能力，提出一種改進(jìn)和聲變鄰域搜索算法。首先對新和聲的產(chǎn)生方式進(jìn)行改進(jìn)，確保新調(diào)度解的有效性，然后對新解進(jìn)行變鄰域操作，最后利用仿真實驗檢驗改進(jìn)算法的有效性及最優(yōu)解的質(zhì)量。

1 柔性作業(yè)車間調(diào)度問題

柔性作業(yè)車間調(diào)度問題較傳統(tǒng)作業(yè)車間調(diào)度問題更加復(fù)雜，其可用數(shù)學(xué)模型描述為：n個工件在m臺機(jī)器上加工，工件集為J={J1，J2，…，Jn}，機(jī)器集為M={M1，M2，…，Mn}，每個工件包含一道或多道工序，工件i的工序集合為Oi={Oi1，Oi2，…，Oij}，工件i的第j道工序可供選擇的機(jī)器的集合為Mij={Mij1，Mij2，…，Mijk}，工件i的第j道工序在機(jī)器k上的加工時間集合為pij={pij1，pij2，…，pijk}，所有集合中的數(shù)據(jù)均已知，結(jié)合生產(chǎn)要求，將所有待加工的工件安排在機(jī)器上加工，保證生產(chǎn)的穩(wěn)定性和有序性。基于上述思路，以最大完工時間為優(yōu)化目標(biāo)，建立FJSP的調(diào)度模型如下：

2 基本和聲搜索算法

2.1 初始化和聲記憶庫

選擇用隨機(jī)生成的方式產(chǎn)生和聲記憶庫HM，調(diào)度問題在初始化時，加工每道工序可供選擇的機(jī)器有多臺，因此每組和聲解用雙層編碼方式產(chǎn)生。第一層為基于工件工序的編碼，工件號在工序碼中出現(xiàn)的次數(shù)表示該工件的工序數(shù)；第二層為機(jī)器編碼，每個工序在可供選擇的機(jī)器集內(nèi)選擇任意一臺機(jī)器，機(jī)器序號作為該工序的機(jī)器編碼。任一雙層編碼的和聲解都能解碼成一個初始調(diào)度方案，并能直觀看出各工件選擇加工的機(jī)器和各工序加工的先后次序。圖1為一個工序和機(jī)器各有12個編碼的雙層初始和聲。

圖1中Oij表示工件代號，i表示工件號，j為工件i的第j道工序；機(jī)器鏈中的編碼為對應(yīng)工件工序的加工機(jī)器在機(jī)器集中的順序號。例如：工序編碼中的第八個數(shù)字“1”表示工件1的第二道工序，對應(yīng)的機(jī)器碼“2”表示選擇該道工件工序在當(dāng)前可選的機(jī)器集合中的第二臺機(jī)器。

2.2 新和聲的產(chǎn)生

新和聲的產(chǎn)生包括兩個部分，第一個部分為工序的新和聲，第二部分為機(jī)器的新和聲。根據(jù)HS算法產(chǎn)生新和聲的過程，當(dāng)新和聲來自于記憶庫，直接從記憶庫中分別獲得工序碼和機(jī)器碼的新和聲。用和聲算法求解車間調(diào)度問題，產(chǎn)生工序碼的新和聲會遇到這樣的問題：若HMS較小，當(dāng)某一變量從對應(yīng)列中隨機(jī)取值時，所在列的值為[2 2 3 2 1 2 2 1 2 1 1 2 2 4 4 1 4 2 1 2]，變量取值為1，2，4，對應(yīng)的工件的工序數(shù)都將超過該工件的最大工序數(shù)，只有取值為3時才能滿足條件，因此變量無法取得滿足要求的解或取得目標(biāo)值的概率很低，且在迭代后期，較小的和聲庫將降慢最優(yōu)解的更新速度。若HMS較大，和聲庫包含較多的大小不等的目標(biāo)解，得到滿意解的概率較大，但運(yùn)算量大。

其傳統(tǒng)的和聲算法的新和聲產(chǎn)生策略為：當(dāng)變量在和聲庫中無法獲得目標(biāo)變量時，變量將從當(dāng)前最優(yōu)和聲解中隨機(jī)取得變量值，表達(dá)式如下。

3 改進(jìn)和聲搜索算法

3.1 新和聲庫的產(chǎn)生

基于原始新和聲的產(chǎn)生都是隨機(jī)的，無法在短時間內(nèi)獲得更優(yōu)的解，本文將借鑒遺傳算法中的精英保留策略，根據(jù)適應(yīng)度的大小來決定新和聲信息的構(gòu)成。同時，將傳統(tǒng)的從全部初始解中隨機(jī)選擇信息變?yōu)閺姆N群中部分較好的個體中選擇信息。同時，每次產(chǎn)生多個和聲來更新和聲庫。表達(dá)式如下：

由于目標(biāo)函數(shù)，即最短完工時間越短，解越優(yōu)，則適應(yīng)度fitness取每個個體完工時間ObjV的倒數(shù)。按照適應(yīng)度從大到小的原則依次選取目標(biāo)個體，該個體的信息保留比率rate取適應(yīng)度與該目標(biāo)個體完工時間在種群中的排序值order（按從小到大的順序）的乘積。該目標(biāo)個體的信息保留長度SLi取工件總長度tota ln umber與信息保留比率rate的乘積。保留策略分兩種：

①所選信息在新和聲中對應(yīng)位置無信息，則直接復(fù)制給新和聲。

②所選信息在新和聲中對應(yīng)位置有信息，則復(fù)制給新和聲中無信息的其它位置上。（圖2）

新和聲產(chǎn)生的具體執(zhí)行步驟如下：

Step1：計算每個個體的適應(yīng)度值及信息保留比例rate。

Step2：找出初始解中的最優(yōu)個體，計算該個體保留信息的長度SLi。隨機(jī)選擇信息復(fù)制給新和聲new。

Step3：尋找下一個適應(yīng)度值排序僅次于上一個被選個體的較優(yōu)個體，若該個體的SLi和新和聲已有信息長度SL大于等于小于工件總數(shù)，則更新SLi，其公式如下：

找出該目標(biāo)個體中新和聲中沒有的其它信息，從中隨機(jī)選擇SLi個信息，根據(jù)上述保留策略將信息復(fù)制給新和聲。

Step4：若新和聲的長度SL小于tota ln umber，則返回Step3；否則，將新和聲放進(jìn)新和聲集合中。

3.2 變鄰域搜索算法

在車間調(diào)度問題中，工件的加工滿足工序約束和機(jī)器約束，目標(biāo)值的好壞在很大程度上取決于關(guān)鍵路徑的好壞，優(yōu)化關(guān)鍵路徑實質(zhì)是盡可能找到問題的最優(yōu)解。交換記憶庫和新和聲中相鄰工序的次序能保證后續(xù)解的有效性和質(zhì)量；即當(dāng)產(chǎn)生一組新和聲向量后，對工序碼進(jìn)行變鄰域搜索，提高算法的局部搜索能力，兩道工序順序交換的過程如圖3所示。具體步驟為：

Step1：交換除第一個和最后一個關(guān)鍵塊外的其它關(guān)鍵塊的塊首和塊尾。

Step2：若第一個人關(guān)鍵塊包含兩道以上關(guān)鍵工序，則只交換快首快尾相連的兩道工序；如果最后一個關(guān)鍵快包含兩道以上關(guān)鍵工序，則只交換快首；如果它們只包含兩道關(guān)鍵工序，那么只交換此兩道工序。

3.3 更新和聲記憶庫

在和聲庫的更新操作中，解碼變鄰域后新和聲，如果新和聲優(yōu)于和聲庫的最劣解，用新和聲替換最劣和聲，否則算法進(jìn)入下一次循環(huán)操作。

改進(jìn)和聲搜索算法的步驟如下：

Step1：設(shè)置算法參數(shù)和聲記憶庫大小HMS、記憶庫選擇概率HMCR、微調(diào)概率的最大值PARmax、最小值PARmin、創(chuàng)作次數(shù)NI；個體長度tota ln umber。

Step2：初始化和聲記憶庫HM，采用雙層編碼的方式分別產(chǎn)生工序和機(jī)器的初始和聲庫。

Step3：產(chǎn)生一組新和聲集合，包括工序碼的新和聲和機(jī)器碼的新和聲。

Step4：進(jìn)行變異操作。產(chǎn)生一個區(qū)間（0，1）內(nèi)的隨機(jī)數(shù)rand，若randPAR，保持新和聲不變。

Step5：對產(chǎn)生的新和聲進(jìn)行變領(lǐng)域操作。

Step6：計算新和聲集合的目標(biāo)函數(shù)值，用新和聲替換和聲記憶庫中目標(biāo)值差的和聲。

Step7：判斷算法是否終止。當(dāng)創(chuàng)作次數(shù)達(dá)到設(shè)定的最大次數(shù)NI時跳出循環(huán)，并輸出最優(yōu)結(jié)果。否則，轉(zhuǎn)至Step3。

改進(jìn)和聲搜索算法的流程圖如圖4所示。

4 實驗驗證與分析

為了驗證本文提出的改進(jìn)和聲變鄰域搜索算法對問題求解的有效性，選取的算法測試對象分別為，4×6，8×8，10×10，和Brandimarte提出的10個實例。改進(jìn)和聲算法采用MATLAB R2016編程，程序在環(huán)境為Interl（R） Core（TM）i-5200U CPU@2.20，主頻2.20GHz，內(nèi)存為4GB個人電腦上運(yùn)行。設(shè)置和聲記憶庫大小HMS=100，和聲記憶庫微調(diào)概率PAR為0.3，迭代次數(shù)為200，連續(xù)運(yùn)行10次。

表1給出了該算法與Chen[7]和Pezzella[8]以及和標(biāo)準(zhǔn)HS算法（未改進(jìn)的HS算法）對比結(jié)果，在表1中第一欄是問題，第二欄中n為工件數(shù)，m為機(jī)器數(shù)，T0為工件的總工序數(shù)，F(xiàn)lex.表示工序可選擇的加工機(jī)器的平均數(shù)，LB和UB分別為目前為止文獻(xiàn)中求得的最優(yōu)上限和最優(yōu)下限。

從表1可以看出，對于15個測試結(jié)果，改進(jìn)和聲算法取得了較好的測試結(jié)果。改進(jìn)和聲算法與Chen的GA相比有10個問題取得了更優(yōu)或相同的最優(yōu)結(jié)果，與文獻(xiàn)[8]相比有9個相同的最優(yōu)結(jié)果，與標(biāo)準(zhǔn)和聲算法相比有12個問題取得了更優(yōu)解。從改進(jìn)和聲算法與其它算法比較，顯示了改進(jìn)的和聲算法求解FJSP的有效性。

在測試實例中，改進(jìn)和聲算法對于總工序數(shù)較小的小規(guī)模的FJSP上，都能取得較優(yōu)解，而在較大規(guī)模的FJSP上，所求最優(yōu)解效果差一點，主要原因在于當(dāng)規(guī)模變大時，優(yōu)良信息難以穩(wěn)定的保存下去，構(gòu)造優(yōu)良和聲的能力變差。（圖5）

5 總結(jié)與展望

本文對新和聲的產(chǎn)生方式進(jìn)行了改進(jìn)，同時為了提高算法的局部搜索性能，對產(chǎn)生的新和聲進(jìn)行變鄰域操作，提出了一種改進(jìn)和聲變鄰域搜索算法來求解柔性作業(yè)車間調(diào)度問題。最后用不同規(guī)模的實驗對改進(jìn)算法進(jìn)行了對比和驗證，結(jié)果表明相比于標(biāo)準(zhǔn)和聲搜索算法，改進(jìn)算法的局部搜索效果得到了提升，且結(jié)果的整體性能優(yōu)于對比算法的結(jié)果。將改進(jìn)和聲算法的結(jié)果與其他算法的結(jié)果相比可看出該改進(jìn)算法在解決柔性作業(yè)車間調(diào)度問題方面具有可操作性。今后將進(jìn)一步探究本文提出的改進(jìn)和聲變鄰域搜索算法的求解效果，并將其運(yùn)用于求解組合優(yōu)化問題。

參考文獻(xiàn)：

[1]張國輝，高亮，李培根，張超勇.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機(jī)械工程學(xué)報，2009，45（07）：145-151.

[2]孔飛，吳定會，紀(jì)志成.基于雙層粒子群優(yōu)化算法的柔性作業(yè)車間調(diào)度優(yōu)化[J].計算機(jī)應(yīng)用，2015，35（2）：476-480.

[3]張于賢，丁修坤，薛殿春，王曉婷，程書瑞.基于記憶曲線模型的蟻群算法在柔性作業(yè)車間的調(diào)度優(yōu)化[J].現(xiàn)代制造工程，2017（11）：105-109.

[4]Geem ZW，Kim JH，Loganathan GV.A new heuristic optimization algorithm： harmony search.Simulation[J].2001，76（2）： 60-68.

[5]王勇臻，陳燕，張金松.用于求解旅行商問題的多策略離散型和聲搜索算法[J].華南理工大學(xué)學(xué)報（自然科學(xué)版），2016，44（01）：131-138.

[6]劉樂.單機(jī)最大延遲重調(diào)度的和聲變鄰域搜索算法[J].計算機(jī)集成制造系統(tǒng)，2016，22（08）：1977-1991.

[7]Chen H ， Ihlow J ， Lehmann C .A Genetic Algorithm for Flexible Job-Shop Scheduling[R].IEEE International Conference on Robotics and Automation .Detr-oit ， 1999 ：1120-1125.

[8]Pezzella F，Morganti G，Ciaschetti G.A Hybrid Genetic and Variable Neighborhood Descent Algorithm for Flexible Job Shop Scheduling Problems[J].Computers & Operations Reseach，2008，35（9）：2892-2907.