一種融合模擬退火的遺傳算法在柔性作業(yè)車間調(diào)度中的應(yīng)用

王家?！纬?/p>

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

關(guān)鍵詞：車間離散調(diào)度；遺傳算法；模擬退火

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2019）01-0133-04

1 概述

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

遺傳算法雖然具有較強(qiáng)的全局搜索能力，但同時(shí)也存在著過早收斂、容易陷入局部最優(yōu)、適應(yīng)性較差等缺點(diǎn)。模擬退火算法具有較強(qiáng)的局部搜索能力，其不僅接受使目標(biāo)函數(shù)變好的解，還能以一定的概率接受使目標(biāo)函數(shù)變差的解，因此該算法具有跳出局部最優(yōu)解的能力?？梢园l(fā)現(xiàn)，將模擬退火算法和遺傳算法緊密結(jié)合起來，可以克服各自不足，提高算法尋優(yōu)性能，從而取得更優(yōu)解。

基于以上觀點(diǎn)，本文在遺傳算法的基礎(chǔ)上將模擬退火算法融合，提出一種改進(jìn)版的GA算法。

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

2.1 問題描述

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

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

2.2 數(shù)學(xué)模型

定義以下符號：

n：工件總數(shù)；

m：機(jī)器總數(shù)；

i，e：機(jī)器序號，i，e=1，2，3，…，m；

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

hj：第j個(gè)工件的工序總數(shù)；

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

Ojh：第j個(gè)工件的第h道工序；

Oijh：第j個(gè)工件的第h道工序在機(jī)器i上加工；

pijh：第j個(gè)工件的第h道工序在機(jī)器i上的加工時(shí)間；

sjh：第j個(gè)工件的第h道工序加工開始時(shí)間；

cjh：第j個(gè)工件的第h道工序加工完成時(shí)間；

L：一個(gè)足夠大的正數(shù)；

Cj：每個(gè)工件的完成時(shí)間；

Cmax：最大完工時(shí)間；

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

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

優(yōu)化模型：

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）表示目標(biāo)函數(shù)，式（2）和式（3）表示每一個(gè)工件的工序順序約束，式（4）和式（5）表示同一臺機(jī)器在同一時(shí)刻只能加工一道工序，式（6）表示機(jī)器約束，同一時(shí)刻同一道工序有且僅能被一臺機(jī)器加工，式（7）和式（8）表示機(jī)器存在循環(huán)操作，式（9）表示參數(shù)必須是正數(shù)。

3 算法設(shè)計(jì)

3.1 染色體編碼

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

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

機(jī)器碼：機(jī)器碼部分的總長度為所有待排工件的所有工序之和，每個(gè)基因位的編碼表示對應(yīng)于工序碼部分相同位點(diǎn)的基因所表示的工序選擇的機(jī)器編號。

3.2 種群初始化

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

工序碼：采用隨機(jī)初始化的方法產(chǎn)生各個(gè)位點(diǎn)基因。

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

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

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

3.3 選擇

本文采用最大完工時(shí)間最小作為評價(jià)指標(biāo)，即公式（1）作為適應(yīng)度函數(shù)，適應(yīng)度小的個(gè)體即為優(yōu)良個(gè)體，在對每一個(gè)個(gè)體進(jìn)行適應(yīng)度評價(jià)后，采用輪盤賭策略與精英保留策略對種群個(gè)體進(jìn)行選擇。

3.4 染色體交叉

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

Step1 產(chǎn)生兩個(gè)工件集JP1與JP2，JP1與JP2均為工件集合J的子集，兩個(gè)子集中所含工件的個(gè)數(shù)小于或等于總工件個(gè)數(shù)的1/2，并且JP1∩JP2=。

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

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

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

Step1 產(chǎn)生兩個(gè)隨機(jī)數(shù)r1與r2，（0

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

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

3.5 染色體變異

對于機(jī)器碼部分，在對應(yīng)工序的可用機(jī)器集合中選取另一臺可加工設(shè)備替換當(dāng)前選擇的加工機(jī)器。

工序碼部分采用互換變異，隨機(jī)選取工序碼中的兩個(gè)基因，將其互換?；诠ば虻木幋a方式使得通過互換變異得到的仍為可行解。

3.6 模擬退火操作

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

P=# （10）

式中，F(xiàn)b（T）為個(gè)體變換前的個(gè)體適應(yīng)度，F(xiàn)a（T）則為變換后的個(gè)體適應(yīng)度。通過公式（10）計(jì)算出新個(gè)體的接收概率，與此同時(shí)產(chǎn)生一個(gè)隨機(jī)數(shù)r∈[0，1]，若r

T=α×T# （11）

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

3.7 算法執(zhí)行過程

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

Step2 按照設(shè)置的參數(shù)進(jìn)行種群初始化，生成第一代種群個(gè)體。

Step3 對種群中每一個(gè)個(gè)體進(jìn)行解碼操作，同時(shí)評價(jià)種群適應(yīng)度大小。

Step4 判斷迭代次數(shù)是否達(dá)到最大迭代次數(shù)或種群最優(yōu)解連續(xù)幾代均為發(fā)生改變，若滿足，輸出種群最優(yōu)解，否則執(zhí)行Step5。

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

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

該算法的執(zhí)行流程圖如圖1所示。

4 實(shí)驗(yàn)計(jì)算結(jié)果

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

通過圖2、圖3以及表1中的數(shù)據(jù)結(jié)果對比可知：在融合了模擬退火算法后，改進(jìn)后的遺傳算法尋優(yōu)能力更強(qiáng)，得到的結(jié)果也更優(yōu)。

5 結(jié)語

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

參考文獻(xiàn)

[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ìn)遺傳算法的柔性作業(yè)車間調(diào)度方法研究[J].機(jī)電工程，2014，31（6）：729-733.

[5] 李鐵克，王偉玲，張文學(xué).基于文化遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].計(jì)算機(jī)集成制造系統(tǒng)，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