一種融合模擬退火的遺傳算法在柔性作業車間調度中的應用

王家海　呂程

摘要：針對理論上屬于NP完全問題的車間離散調度問題，在傳統的遺傳算法搜索中融入模擬退火算法，同時按照一定的規則生成初始種群。采用機器碼和工序碼相結合的編碼方式，以全局選擇、局部選擇以及隨機生成的方式產生初始種群，同時針對遺傳算法局部搜索能力較差、易出現早熟現象的缺點，考慮模擬退火算法提高全局優化概率搜索。仿真結果表明融合了模擬退火算法遺傳算法性能具有更快的收斂性和尋優效果。

關鍵詞：車間離散調度；遺傳算法；模擬退火

中圖分類號：TP301 文獻標識碼：A 文章編號：1007-9416（2019）01-0133-04

1 概述

FJSP問題是作業車間調度問題（JSP）的擴展[1]，其突出特點是同一個加工任務有多臺加工設備可供調度選擇。FJSP是典型的組合優化問題，更加接近實際的生產調度環境，但同時問題復雜度相對于JSP也更高，對于此類問題，傳統的數學優化方法無法在相對有限的時間內求解，因此采用近年來興起的智能優化算法成為了一個可行的解決方法。作為智能算法之一的遺傳算法在此問題上得到了廣泛的應用，Ho等[2]采將啟發式算法與遺傳算法結合，提出一種混合算法， Teekeng等[3]設計了一種模糊輪盤賭的種群選擇操作廖珊[4]采用一種改進的GA算法，設計了自適應的選擇、變異、交叉算子，李鐵克[5]提出文化GA求解FJSP。

遺傳算法雖然具有較強的全局搜索能力，但同時也存在著過早收斂、容易陷入局部最優、適應性較差等缺點。模擬退火算法具有較強的局部搜索能力，其不僅接受使目標函數變好的解，還能以一定的概率接受使目標函數變差的解，因此該算法具有跳出局部最優解的能力。可以發現，將模擬退火算法和遺傳算法緊密結合起來，可以克服各自不足，提高算法尋優性能，從而取得更優解。

基于以上觀點，本文在遺傳算法的基礎上將模擬退火算法融合，提出一種改進版的GA算法。

2 問題描述及數學模型

2.1 問題描述

柔性作業車間調度問題（FJSP）的描述如下：n個工件（J1，J2，…，Jn）要在m臺機器（M1，M2，…，Mm）上加工；每一個工件包含一道或者多道工序；工序順序是預先確定的；每道工序可以在多臺不同的加工機器上進行加工；每道工序的加工時間隨著加工機器的不同而不同；調度的目標是為每道工序選擇出合適的機器，確定每臺機器上各道工序的最佳加工順序以及開工時間，使整個系統的某些性能指標達到最優。因此FJSP問題包含兩個子問題：確定各工序的加工機器（機器選擇子問題）以及確定各個機器上的加工先后順序（工序排序問題）。

本文建立的調度問題模型包含了以下約束：（1）同一臺機器在某一時刻只能加工一個工件；（2）同一工件的同一道工序在同一時刻只能被一臺機器加工；（3）每個工件的每道工序一旦開始，加工便不能中斷；（4）不同工件的工序之間沒有先后約束，同一工件的工序之間有先后約束；（5）所有機器在t = 0時刻都可用，所有工件在t=0時刻都可加工；（6）同一工件不同工序的加工順序和在不同機器上的加工時間都是固定的。

2.2 數學模型

定義以下符號：

n：工件總數；

m：機器總數；

i，e：機器序號，i，e=1，2，3，…，m；

j，k：工件序號，j，k=1，2，3，…，n；

hj：第j個工件的工序總數；

l：工序序號，l=1，2，3，…，hj；

Ojh：第j個工件的第h道工序；

Oijh：第j個工件的第h道工序在機器i上加工；

pijh：第j個工件的第h道工序在機器i上的加工時間；

sjh：第j個工件的第h道工序加工開始時間；

cjh：第j個工件的第h道工序加工完成時間；

L：一個足夠大的正數；

Cj：每個工件的完成時間；

Cmax：最大完工時間；

Xijh：若工序Ojh選擇機器i上加工，則Xijh=1，否則Xijh=0；

Yijhkl：若Oijh先于Oikl加工，則Yijhkl=1，否則Yijhkl=0。

優化模型：

minCmax=min（maxCj）# （1）

s. t.

sjh+xijh×pijh≤cjh# （2）

cjh≤sj（h+1）# （3）

sjh+pijh≤skl+L（1-Yijhkl）# （4）

cjh≤sj（h+1）+L（1-Yiklj（h+1））# （5）

=1# （6）

=Xikl# （7）

=Xijh# （8）

sjh≥0，cjh≥0# （9）

其中，式（1）表示目標函數，式（2）和式（3）表示每一個工件的工序順序約束，式（4）和式（5）表示同一臺機器在同一時刻只能加工一道工序，式（6）表示機器約束，同一時刻同一道工序有且僅能被一臺機器加工，式（7）和式（8）表示機器存在循環操作，式（9）表示參數必須是正數。

3 算法設計

3.1 染色體編碼

編碼擬采用文獻所提出的兩段式編碼方法，在編碼時，將染色體基因分成機器碼與工序碼，解釋如下：

工序碼：工序碼部分的總長度等于所有待排工件的所有工序之和，每個基因位用工件號表示，該工件號在工序碼部分中第n次出現，則表示該工件的第n道工序，工件號出現的次數為該工件包含的工序數量。

機器碼：機器碼部分的總長度為所有待排工件的所有工序之和，每個基因位的編碼表示對應于工序碼部分相同位點的基因所表示的工序選擇的機器編號。

3.2 種群初始化

初始化種群的質量因其往往影響著遺傳算法的收斂速度與求解結果的質量所以十分重要，本文對工序碼部分和機器碼部分采用不同的初始化方法。

工序碼：采用隨機初始化的方法產生各個位點基因。

對于機器碼部分的初始化，我們擬采用三種初始化方法：選取加工時間最小的機器的初始化方法（全局選擇），平衡機器負荷（局部選擇）的初始化方法以及隨機選擇機器的初始化方法。隨機選擇機器的初始化方法同工序碼部分類似。針對前兩種初始化方法的解釋如下：

（1）選取加工時間最小的機器的初始化方法：即針對每一道工序在其可加工機器集合中選取加工時間最短的機器；

（2）平衡機器負荷的初始化方法：將機器所占用的時間累加，選取時間最短的機器作為該道工序的加工機器。

3.3 選擇

本文采用最大完工時間最小作為評價指標，即公式（1）作為適應度函數，適應度小的個體即為優良個體，在對每一個個體進行適應度評價后，采用輪盤賭策略與精英保留策略對種群個體進行選擇。

3.4 染色體交叉

采用改進的POX（基于工件優先順序的交叉）方式進行工序碼部分交叉操作，具體過程如下：

Step1 產生兩個工件集JP1與JP2，JP1與JP2均為工件集合J的子集，兩個子集中所含工件的個數小于或等于總工件個數的1/2，并且JP1∩JP2=。

Step2 將父代染色體P1中與JP1相關的工序基因按照與父代P1相同的位置填入子代染色體C1中，在選取父代P2中與JP1無關的工序基因按照原有順序依次填入C1的空位基因處。

Step3 將父代染色體P2中與JP2相關的工序基因按照與父代P2相同的位置填入子代染色體C2中，在選取父代P1中與JP2無關的工序基因按照原有順序依次填入C2的空位基因處。

對于機器碼部分的交叉操作描述如下：

Step1 產生兩個隨機數r1與r2，（0

Step2 將父代染色體P1中基因位點為[r1，r2]之間的所有基因復制給子代C1，同時保證基因的位置順序均不發生改變。將父代染色體P2中基因位點為[1，r1）與（r2，n]的所有基因復制給子代C1，同時保證基因的位置順序均不發生改變。

Step3 將父代染色體P2中基因位點為[r1，r2]之間的所有基因復制給子代C2，同時保證基因的位置順序均不發生改變。將父代染色體P1中基因位點為[1，r1）與（r2，n]的所有基因復制給子代C2，同時保證基因的位置順序均不發生改變。

3.5 染色體變異

對于機器碼部分，在對應工序的可用機器集合中選取另一臺可加工設備替換當前選擇的加工機器。

工序碼部分采用互換變異，隨機選取工序碼中的兩個基因，將其互換。基于工序的編碼方式使得通過互換變異得到的仍為可行解。

3.6 模擬退火操作

由于遺傳算法易陷入早熟，導致無法獲得最優解，同時考慮到模擬退火算法具有較強的局部搜索能力，因此將遺傳算法與模擬退火算法融合。對當前溫度T與閾值溫度Tmin進行對比，若Tmin>T，則對種群個體進行如下變換：選取種群中另一個個體，將該個體與將要變換的個體的機器碼進行互換，得到新的個體，并參照Metropolis準則得到個體接收概率，接收概率如下：

P=# （10）

式中，Fb（T）為個體變換前的個體適應度，Fa（T）則為變換后的個體適應度。通過公式（10）計算出新個體的接收概率，與此同時產生一個隨機數r∈[0，1]，若r

T=α×T# （11）

式中，α為控制參數，一般取值范圍為0.5～0.99之間。

3.7 算法執行過程

Step1 算法的參數設置。包括種群大小、最大迭代次數、機器染色體三種初始化方法所占的種群比例、精英個體的數量、交叉與變異概率、模擬退火初始溫度、閾值溫度、溫度衰減參數。

Step2 按照設置的參數進行種群初始化，生成第一代種群個體。

Step3 對種群中每一個個體進行解碼操作，同時評價種群適應度大小。

Step4 判斷迭代次數是否達到最大迭代次數或種群最優解連續幾代均為發生改變，若滿足，輸出種群最優解，否則執行Step5。

Step5 執行染色體選擇操作操作，結合精英主義選取下一代種群。

Step6 執行染色體交叉、染色體變異、模擬退火操作，得到新一代種群。同時返回Step3。

該算法的執行流程圖如圖1所示。

4 實驗計算結果

為了驗證本文所設計的改進的遺傳算法（Improved Genetic Algorithm，IGA）的性能，采用文獻[6]提出的8 ×8 的柔性作業車間算例進行測試，算法運行環境64bit Visual Studio 2017，處理器為Intel（R） Core（TM） i7-6700HQ CPU @ 2.60GHz 2.59GHz，程序采用C#編程語言編寫。算法參數設置為：種群規模為100，最大迭代次數200，交叉概率0.8，變異概率為0.05，初始溫度3000，閾值溫度為1000，溫度衰減參數為0.9。圖2為本文提出的算法所求得最優解的甘特圖，圖3為基本遺傳算法求得的解，表1對比了本文提出的算法與其他算法求解結果的對比。

通過圖2、圖3以及表1中的數據結果對比可知：在融合了模擬退火算法后，改進后的遺傳算法尋優能力更強，得到的結果也更優。

5 結語

本文對柔性作業車間問題進行研究，并提出了一種改進的遺傳算法，在種群初始化時考慮各臺機器保持負荷相平衡，提出了機器碼生成的三種初始化方式，同時對于遺傳算法本身易早熟的特點，將模擬退火操作融入遺傳算法當中， 提高全局搜索能力，增加了搜索精度，從而達到全局最優。通過實例計算表明改進后的遺傳算法尋優效果好，搜索精度高，對柔性作業車間問題具有一定的指導作用。

參考文獻

[1] Ham A.Flexible job shop scheduling problem with parallel batch processing machine[C]// Winter Simulation Conference.IEEE，2017.

[2] Ho N B，Tay J C，Lai E M K.An effective architecture for learning and evolving flexible job-shop schedules[J].European J of Operational Research，2007，179（2）：316-333.

[3] Teekeng W，Thammano A.Modified Genetic Algorithm for Flexible Job-Shop Scheduling Problems[J].Procedia Computer Science，2012，12（Complete）：122-128.

[4] 廖珊，翟所霞，魯玉軍.基于改進遺傳算法的柔性作業車間調度方法研究[J].機電工程，2014，31（6）：729-733.

[5] 李鐵克，王偉玲，張文學.基于文化遺傳算法求解柔性作業車間調度問題[J].計算機集成制造系統，2010，16（4）：861-866.

[6] Kacem I，Hammadi S，Borne P.Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J].IEEE Transactions on Systems， Man and Cybernetics， Part C （Applications and Reviews），2002，32（1）：1-13.

Abstract：Aiming at the discrete scheduling problem of the workshop which belongs to the NP-complete problem in theory， the simulated annealing algorithm is incorporated into the traditional genetic algorithm search， and the initial population is generated according to certain rules. Using the combination of machine code and process code， the initial population is generated by global generation， local generation and random generation. At the same time， the local search ability of genetic algorithm is poor and prone to premature phenomenon. Using the simulated annealing algorithm to improve the global search ability. The simulation results show that the performance of genetic algorithm combined with simulated annealing algorithm has faster convergence and optimization effect.

Key words：workshop scheduling；genetic algorithm；simulated annealing algorithm