面向作業(yè)車間調(diào)度問題的遺傳算法改進(jìn)

鄭先鵬 王雷

摘 要：為了獲得遺傳算法在作業(yè)車間調(diào)度問題上的最優(yōu)化解，提高算法的迭代速度，研究了遺傳算法的改進(jìn)方法，以工件的加工時間最短為目標(biāo)建立調(diào)度模型。在算法上提出了基于概率改進(jìn)的具有自適應(yīng)能力的交叉與變異算子，以求作業(yè)車間調(diào)度問題的最優(yōu)解。在遺傳算法上采用精英保留策略方法，并結(jié)合改進(jìn)的自適應(yīng)算子對問題進(jìn)行求解。以基準(zhǔn)案例LA01和FT06作為實驗仿真對象，獲得了相應(yīng)的甘特圖以及搜索過程曲線。仿真結(jié)果表明，與未改進(jìn)的算法相比，該算法能夠更加快速地獲得最優(yōu)解。改進(jìn)后的算法在搜索上更加快速有效，在求解作業(yè)車間調(diào)度問題上具有一定的可行性，更加適合工業(yè)加工生產(chǎn)。

關(guān)鍵詞：最優(yōu)化;機(jī)械車間;作業(yè)車間調(diào)度;自適應(yīng)算子;精英策略;改進(jìn)的遺傳算法

中圖分類號：TP278 ? 文獻(xiàn)標(biāo)志碼：A ? doi：10.7535/hbkd.2019yx06006

Abstract： In order to obtain the optimal solution of genetic algorithm for job shop scheduling problem and improve the iteration speed of the algorithm， the improved method of genetic algorithm is studied. The scheduling model is established with the shortest processing time of the workpiece as the target. An adaptive crossover and mutation operator based on probability improvement is proposed to get the optimal solution of the job shop scheduling problem. The elitist retention strategy and the improved adaptive operator are used in the genetic algorithm， to solve solve job shop scheduling problem. The benchmark cases LA01 and FT06 are used as simulation objects. The corresponding Gantt chart and the search process curve are obtained. The simulation results show that the improved algorithm can get the optimal solution more quickly with the unmodified algorithm. The improved algorithm is more efficient and faster. It is feasible to solve job shop scheduling problem， and is more suitable for industrial production.

Keywords：optimization; machinery workshop; job shop scheduling; adaptive operator; elitist strategy; improved genetic algorithm

作業(yè)車間調(diào)度問題（ job shop scheduling problem，JSP）主要是確定各工件的加工次序和機(jī)器，是典型的NP-hard 問題[1]。隨著市場經(jīng)濟(jì)的發(fā)展， 企業(yè)間的競爭越來越激烈，如何合理安排作業(yè)車間調(diào)度顯得至關(guān)重要[2]。隨著科學(xué)技術(shù)的蓬勃發(fā)展，工業(yè)工程中車間生產(chǎn)規(guī)模逐漸擴(kuò)大，作業(yè)車間調(diào)度越來越復(fù)雜，作業(yè)車間調(diào)度的組合優(yōu)化問題已成為當(dāng)今工業(yè)工程領(lǐng)域發(fā)展研究的熱點(diǎn)問題之一[3]。對于該問題，研究者們主要是通過各種啟發(fā)式研究方法進(jìn)行求解，常用于主流求解的方法有粒子群優(yōu)化算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、禁忌搜索算法等[4-10]。 其中，遺傳算法因簡單通用、高效、容易取得較好的結(jié)果，已經(jīng)廣泛應(yīng)用在優(yōu)化調(diào)度問題、組合問題優(yōu)化等方面[11]。在求解實際的工業(yè)工程生產(chǎn)調(diào)度問題上，遺傳算法被普遍關(guān)注和使用，遺傳算法的運(yùn)算反映了優(yōu)勝劣汰操作的基本原則[12]。當(dāng)今雖然有許多國內(nèi)外學(xué)者應(yīng)用遺傳算法對作業(yè)車間調(diào)度問題的求解進(jìn)行了大量研究，然而在遺傳算法求解車間調(diào)度問題上依然有很多未知的改進(jìn)方法未被人們發(fā)掘。由于作業(yè)車間調(diào)度問題在實際工業(yè)生產(chǎn)環(huán)境中存在復(fù)雜性，如何求得滿足要求的準(zhǔn)最優(yōu)解是一個亟待解決的問題，因此對它的研究具有非常重要的現(xiàn)實意義[13-14]。

本文提出了一種改進(jìn)的自適應(yīng)遺傳算法，并利用其對作業(yè)車間調(diào)度問題進(jìn)行目標(biāo)求解。改進(jìn)的算法在交叉和變異概率選擇操作上能夠?qū)崿F(xiàn)自適應(yīng)改變，可應(yīng)用于作業(yè)車間調(diào)度問題的求解。

1 作業(yè)車間調(diào)度建模

作業(yè)車間調(diào)度可描述為，有一批待生產(chǎn)加工工件，這一批工件總共有n個，每個工件有m道工序需要加工[15]，并且加工這批工件的設(shè)備總共有m臺。加工這批工件的要求是：

1）在剛開始加工的時候，每一個工件都有被選中加工的可能;

2）車間中的任何一臺加工設(shè)備在任一時刻只能加工一個工件;

3）如果加工工作開始，就不能中斷;

4）在車間中進(jìn)行加工的同一時刻，要求每一個被加工工件只能由一臺加工設(shè)備加工;

5）每一個工件在開始加工之前沒有先后順序的約束，然而同一工件的加工工序在加工時有先后順序的約束;

6）每一個工件必須按照加工的工藝路線加工;

7）不考慮加工工件時在運(yùn)輸、裝夾等輔助工序上產(chǎn)生的運(yùn)輸時間。

本文以加工工件的最短時間為目標(biāo)進(jìn)行研究。其目標(biāo)函數(shù)如式（1）所示：f（x）=min1≤k≤m{max1≤i≤n{Cik}}，（1）式中：Cik表示工件i在機(jī)器k上的完工時間。式（1）的倒數(shù)為適應(yīng)度函數(shù)。

2 遺傳算法的改進(jìn)設(shè)計

2.1 染色體編碼和解碼

目前遺傳算法的編碼方式有很多種，如浮點(diǎn)數(shù)編碼、二進(jìn)制編碼、整數(shù)編碼、符號編碼、矩陣編碼等[16]。對于遺傳算法而言，基因編碼在算法中起著至關(guān)重要的作用，編碼的方式直接影響遺傳算法的運(yùn)行速度以及能否找到全局最優(yōu)解[17]。本文針對作業(yè)調(diào)度問題，采用了比較受青睞的基于工序的編碼方式。

在基于工序的編碼方式上，染色體上的基因表示確定的工序在機(jī)器上的加工順序，因此可以得到調(diào)度問題的解。染色體上的基因表示如下：染色體上每一個位置上的基因用于表示對于加工工序的選擇，每個基因位置上的數(shù)字用來表示對應(yīng)序號的相應(yīng)加工工件，染色體上出現(xiàn)相同的數(shù)字出現(xiàn)第幾次就用來表示該工件被加工的工序號。同一數(shù)字在該段的染色體上出現(xiàn)的次數(shù)就表示該工件的總工序數(shù)。在染色體上不同的位置，若出現(xiàn)不同的序號則表示不同的工件加工順序。編碼示例見表1。

染色體解碼是在染色的基因部分所包含的基因信息轉(zhuǎn)化為工件加工流程信息[18]。根據(jù)加工工序開始依次加工，然后得到機(jī)器加工工件從開始加工到結(jié)束加工所用的時間，從而得出整個加工系統(tǒng)的調(diào)度甘特圖。

2.2 選擇和交叉操作

2.2.1 選擇操作

選擇操作的目的就是為了挑選出種群中的較優(yōu)個體，使較優(yōu)個體在種群中逐漸增加，在迭代的過程中使種群往更好的方向發(fā)展。對種群中的個體進(jìn)行選擇操作時，依據(jù)個體適應(yīng)度值的大小來決定在進(jìn)化下一代時它是被淘汰還是其他操作。在遺傳算法的選擇操作中個體會被選中的概率與它的適應(yīng)度函數(shù)值呈現(xiàn)一種正比例關(guān)系。

2.5 終止準(zhǔn)則

設(shè)置算法的最大迭代次數(shù)，如果迭代次數(shù)過少則會影響算法的有效性，在有限的迭代次數(shù)內(nèi)得不到近似最優(yōu)解[20]。在本文中，當(dāng)搜索次數(shù)達(dá)到最大次數(shù)時，算法停止運(yùn)行，并輸出最優(yōu)解。

2.6 改進(jìn)的遺傳算法流程圖

改進(jìn)的遺傳算法運(yùn)行流程圖如圖2所示。

3 仿真實驗

3.1 算法實例

為了驗證改進(jìn)算法的可行性，首先對LA01基準(zhǔn)案例進(jìn)行仿真。

利用Matlab對改進(jìn)的自適應(yīng)遺傳算法進(jìn)行編程求解。算法的基本參數(shù)如下：種群規(guī)模Z=100，k1=k2=0.9，k3=k4=0.1，進(jìn)化代數(shù)G=200。利用改進(jìn)算法對案例LA01求解的甘特圖如圖3所示，算法進(jìn)化過程如圖4所示。由圖3可知，使用改進(jìn)的遺傳算法獲得的最少加工時間為666 s，實驗仿真結(jié)果與目前已知該案例的最優(yōu)解完全相同。仿真實驗結(jié)果有力證明了改進(jìn)的遺傳算法是可行和有效的。

另外，針對基準(zhǔn)案例FT06進(jìn)行仿真實驗，得到該案例的實驗甘特圖如圖5所示，搜索進(jìn)化過程如圖6所示。改進(jìn)的遺傳算法運(yùn)用于該基準(zhǔn)案例獲得的實驗仿真結(jié)果為55 s，與目前已知該案例的最優(yōu)解完全相同，進(jìn)一步說明了改進(jìn)算法是可行的。

3.2 算法對比

為了進(jìn)一步驗證改進(jìn)算法的有效性，針對FT06基準(zhǔn)案例，將改進(jìn)的遺傳算法與基本遺傳算法進(jìn)行比較，結(jié)果如圖7所示。改進(jìn)算法僅需9代便可以獲得實驗的最優(yōu)解，未改進(jìn)算法在第73代才獲得最優(yōu)解，因此改進(jìn)的遺傳算法具有非常高的搜索能力，從而證明了改進(jìn)的遺傳算法是有效和可行的。

4 結(jié) 語

針對求解作業(yè)車間調(diào)度問題，將最大完工時間最短作為調(diào)度的最終求解目標(biāo)，應(yīng)用改進(jìn)的遺傳算法對該目標(biāo)問題進(jìn)行求解，設(shè)計了自適應(yīng)交叉和變異概率算子，在選擇操作上加入了精英保留策略，以保留最優(yōu)個體不會遭受破壞。對基準(zhǔn)案例LA01和FT06的實驗仿真結(jié)果表明，在進(jìn)化過程中，改進(jìn)的遺傳算法不僅具有十分優(yōu)良的搜索能力，還具有更快的收斂能力，因此，其在求解作業(yè)車間調(diào)度問題上是有效和可行的。

本研究的不足之處在于該改進(jìn)的遺傳算法僅適用于傳統(tǒng)的作業(yè)車間調(diào)度問題，未來還需對多目標(biāo)、環(huán)境多變、復(fù)雜的柔性作業(yè)車間調(diào)度問題進(jìn)行研究。

參考文獻(xiàn)/References：

[1] 徐華， 程冰. 混合遺傳蝙蝠算法求解單目標(biāo)柔性作業(yè)車間調(diào)度問題[J]. 小型微型計算機(jī)系統(tǒng)，2018， 39（5）： 1010-1015.

XU Hua， CHENG Bing. Hybrid genetic bat algorithm for single-objective flexible job shop scheduling problem[J]. Journal of Chinese Computer Systems， 2018，39 （5）： 1010-1015.

[2] 吳再新. 基于粒子群算法的動態(tài)車間調(diào)度問題研究[D]. 上海：東華大學(xué)，2016.

WU Zaixin.Research on Dynamic Job Shop Scheduling Problem Based on Particle Swarm Optimization[D]. Shanghai： Donghua Univer-sity，2016.

[3] 曹磊， 葉春明， 黃霞. 變鄰域雜草算法在多目標(biāo)柔性作業(yè)車間調(diào)度中的應(yīng)用[J]. 計算機(jī)應(yīng)用研究， 2018，35（1）： 150-154.

CAO Lei， YE Chunming， HUANG Xia. Application of variable neighborhood weed algorithms in multi-objective flexible job-shop scheduling[J]. Application Research of Computers， 2018，35（1）： 150-154.

[4] 王雷， 蔡勁草， 唐敦兵， 等. 基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度[J]. 南京航空航天大學(xué)學(xué)報， 2017，49（6）： 779-785.

WANG Lei， CAI Jincao， TANG Dunbing， et al.Flexible job shop scheduling based on improved genetic algorithms[J]. Journal of Nanjing University of Aeronautics & Astronautics， 2017， 49（6）： 779-785.

[5] ARIYASINGHA I D I D， FERNANDO T G I. A performance study for the multi-objective ant colony optimization algorithms on the job shop scheduling problem[J]. International Journal of Computer Applications， 2015， 132（14）：907638.

[6] FLOREZ E， GOMEZ W， LOLA B. An ant colony optimization algorithm for job shop scheduling problem[J]. International Journal of Artificial Intelligence & Applications， 2013， 4（4）： 53-66.

[7] PENG B， LU Zhipeng， CHENG T C E. A tabu search/path relinking algorithm to solve the job shop scheduling problem[J]. Computers & Operations Research， 2015， 53： 154-164.

[8] SPANOS A C， PONIS S T， TATSIOPOULOS I P， et al. A new hybrid parallel genetic algorithm for the job-shop scheduling problem[J]. International Transactions in Operational Research， 2014， 21（3）： 479-499.

[9] NASIRI M M. A modified ABC algorithm for the stage shop scheduling problem[J]. Applied Soft Computing， 2015， 28： 81-89.

[10] KARIMI-NASAB M， MODARRES M， SEYEDHOSEINI S M. A self-adaptive PSO for joint lot sizing and job shop scheduling with compressible process times[J]. Applied Soft Computing， 2015， 27： 137-147.

[11] 周明， 孫樹棟. 遺傳算法原理及應(yīng)用[M]. 北京：國防工業(yè)出版社，1999.

[12] 王進(jìn)業(yè)， 宋宇博. 旁通式自動化立體倉庫揀選作業(yè)和出口選擇的組合優(yōu)化[J]. 河北科技大學(xué)學(xué)報， 2015， 36（1）： 36-44.

WANG Jinye， SONG Yubo.Combination optimization of picking operation and export selection in bypass automated three-dimensional warehouse [J]. Journal of Hebei University of Science and Technology， 2015， 36（1）： 36-44.

[13] 薛宏全， 魏生民， 張鵬， 等. 基于多種群蟻群算法的柔性作業(yè)車間調(diào)度研究[J]. 計算機(jī)工程與應(yīng)用，2013，49（24）： 243-248.

XUE Hongquan， WEI Shengmin， ZHANG Peng， et al.Research on flexible job shop scheduling based on multi-population ant colony algorithms[J]. Computer Engineering and Applications， 2013， 49（24）： 243-248.

[14] 王凌， 鄧瑾， 王圣堯. 分布式車間調(diào)度優(yōu)化算法研究綜述[J]. 控制與決策，2016，31（1）： 1-11.

WANG Ling， DENG Jin， WANG Shengyao.A review of distributed job shop scheduling optimization algorithms [J]. Control and Decision， 2016， 31（1）： 1-11.

[15] 劉洪銘， 曾鴻雁， 周偉， 等. 基于改進(jìn)粒子群算法作業(yè)車間調(diào)度問題的優(yōu)化[J]. 山東大學(xué)學(xué)報，2019，49（1）： 75-82.

LIU Hongming， ZENG Hongyan， ZHOU Wei， et al.Job shop scheduling problem optimization based on improved particle swarm optimization [J]. Journal of Shandong University， 2019，49（1）： 75-82.