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

鄭先鵬 王雷

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

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

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

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

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

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

1）在剛開(kāi)始加工的時(shí)候，每一個(gè)工件都有被選中加工的可能;

2）車(chē)間中的任何一臺(tái)加工設(shè)備在任一時(shí)刻只能加工一個(gè)工件;

3）如果加工工作開(kāi)始，就不能中斷;

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

5）每一個(gè)工件在開(kāi)始加工之前沒(méi)有先后順序的約束，然而同一工件的加工工序在加工時(shí)有先后順序的約束;

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

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

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

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

2.1 染色體編碼和解碼

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

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

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

2.2 選擇和交叉操作

2.2.1 選擇操作

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

2.5 終止準(zhǔn)則

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

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

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

3 仿真實(shí)驗(yàn)

3.1 算法實(shí)例

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

利用Matlab對(duì)改進(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)算法對(duì)案例LA01求解的甘特圖如圖3所示，算法進(jìn)化過(guò)程如圖4所示。由圖3可知，使用改進(jìn)的遺傳算法獲得的最少加工時(shí)間為666 s，實(shí)驗(yàn)仿真結(jié)果與目前已知該案例的最優(yōu)解完全相同。仿真實(shí)驗(yàn)結(jié)果有力證明了改進(jìn)的遺傳算法是可行和有效的。

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

3.2 算法對(duì)比

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

4 結(jié) 語(yǔ)

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

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

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

[1] 徐華， 程冰. 混合遺傳蝙蝠算法求解單目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題[J]. 小型微型計(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] 吳再新. 基于粒子群算法的動(dòng)態(tài)車(chē)間調(diào)度問(wèn)題研究[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è)車(chē)間調(diào)度中的應(yīng)用[J]. 計(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è)車(chē)間調(diào)度[J]. 南京航空航天大學(xué)學(xué)報(bào)， 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] 周明， 孫樹(shù)棟. 遺傳算法原理及應(yīng)用[M]. 北京：國(guó)防工業(yè)出版社，1999.

[12] 王進(jìn)業(yè)， 宋宇博. 旁通式自動(dòng)化立體倉(cāng)庫(kù)揀選作業(yè)和出口選擇的組合優(yōu)化[J]. 河北科技大學(xué)學(xué)報(bào)， 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è)車(chē)間調(diào)度研究[J]. 計(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] 王凌， 鄧瑾， 王圣堯. 分布式車(chē)間調(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è)車(chē)間調(diào)度問(wèn)題的優(yōu)化[J]. 山東大學(xué)學(xué)報(bào)，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.