基于改進和聲搜索算法的柔性作業車間調度研究

向雙玲 安友軍 劉秀鳳

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

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.

關鍵詞：柔性作業車間調度；和聲搜索算法；精英保留策略；變鄰域搜索

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

中圖分類號：TP181 文獻標識碼：A 文章編號：1006-4311（2018）31-0274-04

0 引言

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

與其他算法相比，和聲搜索算法的結構設計簡單、靈活通用，易與其他算法混合使用。針對FJSP的特點，借鑒變鄰域較強的局部搜索能力，提出一種改進和聲變鄰域搜索算法。首先對新和聲的產生方式進行改進，確保新調度解的有效性，然后對新解進行變鄰域操作，最后利用仿真實驗檢驗改進算法的有效性及最優解的質量。

1 柔性作業車間調度問題

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

2 基本和聲搜索算法

2.1 初始化和聲記憶庫

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

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

2.2 新和聲的產生

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

其傳統的和聲算法的新和聲產生策略為：當變量在和聲庫中無法獲得目標變量時，變量將從當前最優和聲解中隨機取得變量值，表達式如下。

3 改進和聲搜索算法

3.1 新和聲庫的產生

基于原始新和聲的產生都是隨機的，無法在短時間內獲得更優的解，本文將借鑒遺傳算法中的精英保留策略，根據適應度的大小來決定新和聲信息的構成。同時，將傳統的從全部初始解中隨機選擇信息變為從種群中部分較好的個體中選擇信息。同時，每次產生多個和聲來更新和聲庫。表達式如下：

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

①所選信息在新和聲中對應位置無信息，則直接復制給新和聲。

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

新和聲產生的具體執行步驟如下：

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

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

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

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

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

3.2 變鄰域搜索算法

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

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

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

3.3 更新和聲記憶庫

在和聲庫的更新操作中，解碼變鄰域后新和聲，如果新和聲優于和聲庫的最劣解，用新和聲替換最劣和聲，否則算法進入下一次循環操作。

改進和聲搜索算法的步驟如下：

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

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

Step3：產生一組新和聲集合，包括工序碼的新和聲和機器碼的新和聲。

Step4：進行變異操作。產生一個區間（0，1）內的隨機數rand，若randPAR，保持新和聲不變。

Step5：對產生的新和聲進行變領域操作。

Step6：計算新和聲集合的目標函數值，用新和聲替換和聲記憶庫中目標值差的和聲。

Step7：判斷算法是否終止。當創作次數達到設定的最大次數NI時跳出循環，并輸出最優結果。否則，轉至Step3。

改進和聲搜索算法的流程圖如圖4所示。

4 實驗驗證與分析

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

表1給出了該算法與Chen[7]和Pezzella[8]以及和標準HS算法（未改進的HS算法）對比結果，在表1中第一欄是問題，第二欄中n為工件數，m為機器數，T0為工件的總工序數，Flex.表示工序可選擇的加工機器的平均數，LB和UB分別為目前為止文獻中求得的最優上限和最優下限。

從表1可以看出，對于15個測試結果，改進和聲算法取得了較好的測試結果。改進和聲算法與Chen的GA相比有10個問題取得了更優或相同的最優結果，與文獻[8]相比有9個相同的最優結果，與標準和聲算法相比有12個問題取得了更優解。從改進和聲算法與其它算法比較，顯示了改進的和聲算法求解FJSP的有效性。

在測試實例中，改進和聲算法對于總工序數較小的小規模的FJSP上，都能取得較優解，而在較大規模的FJSP上，所求最優解效果差一點，主要原因在于當規模變大時，優良信息難以穩定的保存下去，構造優良和聲的能力變差。（圖5）

5 總結與展望

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

參考文獻：

[1]張國輝，高亮，李培根，張超勇.改進遺傳算法求解柔性作業車間調度問題[J].機械工程學報，2009，45（07）：145-151.

[2]孔飛，吳定會，紀志成.基于雙層粒子群優化算法的柔性作業車間調度優化[J].計算機應用，2015，35（2）：476-480.

[3]張于賢，丁修坤，薛殿春，王曉婷，程書瑞.基于記憶曲線模型的蟻群算法在柔性作業車間的調度優化[J].現代制造工程，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].華南理工大學學報（自然科學版），2016，44（01）：131-138.

[6]劉樂.單機最大延遲重調度的和聲變鄰域搜索算法[J].計算機集成制造系統，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.