基于遺傳算法的流動車間作業(yè)調度

劉明，索良澤

（貴州大學電氣工程學院，貴州 貴陽 550025）

0 引言

一直以來，調度問題都是一個極其重要的課題。在各種工業(yè)活動中，制訂一個高效的調度計劃是不可或缺的組成部分。這就要求計劃制訂者要做出滿足任務要求的調度安排，并根據任務確定最晚完工時間。此問題最具挑戰(zhàn)性的地方在于如何找到理想的調度計劃，既滿足任務要求又是問題的最優(yōu)解[1-3]。在數學上，通常將此類問題歸結為組合優(yōu)化問題，同時也屬于NP完全問題，其特點是還沒有找到一種算法可以在多項式時間內求出其最優(yōu)解。由于啟發(fā)式算法對解決此類問題有著很明顯的優(yōu)點，如算法簡單易于設計，計算效率高等，所以一直以來人們使用啟發(fā)式算法來對調度問題進行求解。在本文中，研究調度問題中的一種典型問題，車間調度問題[4-8]。

車間作業(yè)調度問題是生產管理中必須要面臨的問題。調度計劃的好壞對生產成本和生產時間有直接的影響。通過科學的調度方法，車間內的資源可以得到更合理高效的利用，同時還能以最快的速度將要加工的零件送入車間，加工完成的零件運到下一車間[9]。車間調度涉及到每一批加工的零件在時間、空間及設備等各種資源上的協調和分配，這屬于運籌學中的動態(tài)調度問題。

我們常常需要考慮實際的約束條件，根據現有的資源去完成各種加工任務，給出不同工件在相關機器上的加工時間和順序，使得相關的性能指標達到最優(yōu)，這不僅能有效的提高企業(yè)的作業(yè)效率，還能為企業(yè)帶來巨大的經濟效益。車間作業(yè)調度問題解決的關鍵在于算法，因此，研究出精確而高效的調度算法不僅是該領域重要的課題，還是實際生產中的迫切需求。本文應用遺傳算法對車間調度問題進行求解，目的在于熟悉遺傳算法，并能將其應用于實際問題中[10]。

1 車間作業(yè)調度問題模型

車間作業(yè)調度是一類有順序約束的資源配置問題，也屬于組合優(yōu)化類問題。隨著工業(yè)水平的快速發(fā)展，車間作業(yè)調度的研究越來越重要。在生產工程中若能優(yōu)化流程，提高加工效率，縮短產品的加工時間，無疑對于工業(yè)生產來說是獲取更大利潤的一個措施。雖然研究車間作業(yè)調度能帶來巨大的利益，而且這方面的研究也有了近50年的歷史，但是由于車間作業(yè)調度問題種類繁多，所含約束非常多，并且大多是非線性約束，所以在實際應用中還未有一整套完整的理論和方法[11-13]。

一般來說，為了理論研究，車間作業(yè)調度問題都會做一些簡化假設，以便于建立數學模型。經典的車間作業(yè)調度問題可以簡單描述為：有一個待加工的工件集合和一個用來加工工件設備的集合，每一個工件有多道工序，而每一道工序需要特定的加工設備，工件需要在某一段時間內在該設備上進行加工。調度問題就是將工件在某一段時間內放在某臺機器上進行加工。在理論上研究車間調度問題時，常?；谝韵潞喕僭O：

1）同時刻，一個工件只能在一臺設備上加工；

2）每臺設備在同一時刻只能加工一個工件；

3）一個工件的不同工序需要在不同設備上加工。也就是說，一個工件的一道工序只在一臺設備上完成，一臺設備只加工一個工件的一道工序；

4）只有同一個工件的工序有前后順序約束，工件之間不影響加工順序；

5）在加工過程中，不考慮兩道工序之間的轉運時間，即上一道工序完成立即就開始下一道工序；

6）每一道工序作為一個完整體，不可分割，即是說工序開始之后，除了加工結束，否則不能將工件拿開；

7）工件的集合，機器的集合，加工的順序和每一道工序需要的時間都是已知的。一些在過程中花費的時間統(tǒng)統(tǒng)算入加工時間內，保持兩道工序間是連續(xù)進行加工的。

以上假設基本解析了車間作業(yè)調度問題的約束條件。這些約束可以總結為兩個方面，一個是加工的順序約束，另一個方面為加工的資源約束。也即工件的加工要按照一定的先后順序依次進行加工，另外，機器數量有限，在一個時間段只能加工一個工件，而其余工件就可能發(fā)生排隊等待的情況。那么，車間作業(yè)調度問題就可以看做是資源約束和順序約束下的組合優(yōu)化問題，問題的核心就是如何在這兩個約束條件下將工件的工序分配到加工機器上使得某個指標性能達到最優(yōu)，例如使整個加工任務總時間最小[14-16]。

2 算法簡述

遺傳算法又被稱為GA（Genetic Algorithms），它是在20世紀60年代初由美國Michigan大學的Holland教授提出的，根據自然界的遺傳機制和生物進化論而成的一種并行隨機搜索最優(yōu)化方法[17]。由于遺傳算法搜索的高效性，又適用于解決搜索空間巨大的復雜組合優(yōu)化問題，并在生產調度中已有廣泛成功的應用先例，所以本文采用遺傳算法來對車間調度問題進行求解。

遺傳算法搜索過程中的基本操作為：復制、交叉、變異。正是由于這幾種操作的存在才使得遺傳算法具有不斷向目標搜索前進的能力，而這些操作又都是具有概率性的，所以在搜索進程中具有很大的靈活性和高速度性，隨著搜索進程的發(fā)展越來越多的優(yōu)良個體會產生，逐漸逼近問題的最優(yōu)解[18-20]。

遺傳算法的5個要素是編碼、適應度函數、初始種群、遺傳算子和參數設置。本文按照遺傳算法在流動車間作業(yè)調度問題應用上的設計步驟對問題進行求解。具體步驟如下：

（1）編碼

本文采用M行N列的二維數組對問題進行編碼，M是工件數量，N是加工所需工序數量。數組中第i行第j列的元素代表第i個工件在第j個工序上加工的設備編號。這種編碼是根據工件在對應工序上加工設備編號的排列組合生成的，十分直觀、便于計算。如表1所示：

表1 工件信息表Table 1 Workpiece information sheet

（2）適應度函數

對于M個工件，N個工序，第 j道工序有Ki臺機器（1≤j≤N）的問題來說。設第i個工件在第j個工序上加工的時間為

那么對于第一個工序，按機器編號順序來依次確定各工件的加工時間。都選擇1號機器的工件之間進行排序，發(fā)生等待。依次按此規(guī)則進行到Ki號機器。依上例就是先進行1號工件的加工然后2號工件等待，而3號工件沒有約束和1號工件一起開始加工，3和5號工件也有同樣約束。以此規(guī)則便能定下5個工件在第一個加工工序上的先后順序和確定加工時間。即1號工件在t11時刻結束第一個工序的加工而2號工件在 t11+t21時刻結束，以此類推。

對于第二個工序到第N個工序，則需考慮兩個約束。一是工件要在前一個工序結束后才能開始，二是工件要在機器上的前一個工件加工完成后才能進行加工。在沒有違反這些約束的條件下工件的加工先后順序對結果沒有影響，所以按照編號順序來確定工件加工的先后順序（編號小的先進行加工）。最終，整個加工任務的結束時間就為最后一個工序結束時5個工件中加工時間的最大值。到此自適應函數建立完畢，并將此作為遺傳個體優(yōu)良好壞的評價標準。計算出每個個體的適應度函數，選擇函數值較小的作為優(yōu)良個體，淘汰不良個體，以優(yōu)良個體作為父代繼續(xù)遺傳下去。

（3）對種群進行初始化

遺傳算法的執(zhí)行效率和運行結果受種群大小的影響，種群太大會增加計算的復雜度，延長收斂時間，太小則不能提供足夠的采樣點。因此，我們通常將種群的個體設置為20～100之間。本次實驗采用的種群規(guī)模為100，種群個體皆為隨機產生，即上述表格中的機器編號都是隨機產生的。

（4）遺傳算子

一般而言，遺傳算子包括變異算子、交叉和選擇。此次實驗中的選擇方式為先進行交叉產生新的個體，即將新產生的個體和原來的個體組成一個200個個體的種群然后進行兩兩隨機配對競爭，將適應度函數值大的個體淘汰，留下較小的那個又形成100個個體的種群。

交叉，將初始種群中的個體隨機進行兩兩配對交叉，隨機選擇交叉點進行單點交叉。行交叉是將一個個體在交叉點以上的行與另一個個體在交叉點以上的行進行交換，從而產生新的個體。列交叉是將個體在交叉點以前的列與另一個個體交叉點以前的列進行交換產生新的個體；變異，選取變異概率為0.1，隨機選擇一個變異點，將其改變?yōu)橐粋€不違反規(guī)則的隨機數。

（5）參數設置

即確定好初始種群大小，交叉概率，變異概率，終止迭代次數等參數。本例中采用的初始種群大小為100，交叉概率為1，變異概率為0.1，終止迭代次數為100。

3 算例分析

在本例中求解5個工件經過4個工序的車間調度問題。為簡單起見，以平均加工時間作為每個工件在相應工序上的加工時間。如下表：

表2 車間加工信息表Table 2 Workshop Processing Information table

圖1 調度結果圖Fig. 1 Scheduling results graph

矩形塊中的數字代表工件選擇的機器編號，矩形長度代表時間，寬度表示工件編號。從該甘特圖中（圖1）可以看出此方案即是調度的最優(yōu)方案，實現了加工時間最小的目標。

從圖2中可以看出每經過一代個體的遺傳變異，種群中平均適應度函數值的總體趨勢是在變小的，經過約35代的遺傳基本穩(wěn)定在最優(yōu)解68處，也即說明經過上述遺傳算法處理過后的群體的適應度是在不斷增強的。

圖2 各代種群平均適應度函數值Fig. 2 Average fitness function value of each generation population

4 結論

通過算例可知，針對此類車間調度問題，本文設計的遺傳算法可以很好的求解得到調度結果。本文提出了一種直接的編碼方式，便捷易處理。文中所述的適應度函數相較于其他遺傳算法具有直觀、便于計算等優(yōu)點。文中設計的遺傳算子采用全隨機的方式，可以最大限度的擴充搜索空間。有兩種選擇復制的方式可供隨機挑選，保證了新種群中個體的多樣性同樣擴大了搜索空間。兩兩隨機配對競爭的策略使得種群具有保留最優(yōu)個體的能力，保證了基因的優(yōu)良性。

[1] 張長水, 閻平凡. 解Job-Shop調度問題的神經網絡方法[J]. 自動化學報, 1995, 21(6): 706-712.ZHANG Chang-shui, YAN Ping-fan. Neural Network Method for Solving Job-shop Scheduling Problem [J]. Acta Automatica Sinica, 1995,21(6): 706-712.

[2] 黃彥曌, 王科社, 黃喜淦, 等. 基于遺傳算法的滾珠絲杠副控制器設計與仿真[J]. 新型工業(yè)化, 2017, 7(11): 5-10.HUANG Yan-zhao, WANG Ke-she, HUANG Xi-gan, et al. Ball Screw Pair Controller Design & Simulation Based on Genetic Algorithm[J].The Journal of New Industrialization, 2017, 7 (11): 5-10.

[3] 王書鋒, 鄒益仁. 車間作業(yè)調度(JSSP)技術問題簡明綜述[J]. 系統(tǒng)工程理論與實踐, 2003, 23(1): 49-55.WANG Shu-feng, ZOU Yi-ren. Techniques for the Job Shop Scheduling Problem: a Survey[J]. Systems Engineering-Theory & Practice,2003, 23(1): 49-55.

[4] 王永辰, 肖伸平, 劉先亮. 基于改進自適應遺傳算法的配電網重構[J]. 新型工業(yè)化, 2015, 5(8): 6-10.WANG Yong-chen, XIAO Shen-ping, LIU Xian-liang. Distribution System Reconfiguration Based on Improved Genetic Algorithm[J]. The Journal of New Industrialization, 2015, 5(8): 6-10.

[5] 沈斌, 周瑩君, 王家海. 基于自適應遺傳算法的流水車間作業(yè)調度[J]. 計算機工程, 2010, 36(14): 201-203.SHEN Bin, ZHOU Ying-jun, WANG Jia-hai. Flow Job Shop Scheduling Based on Self-adaptive Genetic Algorithm[J]. Computer Engineering,2010, 36(14): 201-203.

[6] 曲媛, 楊曉偉. 關于流水車間調度問題的綜述[J]. 經營管理, 2007(8): 24-25.QU Yuan, YANG Xiao-wei. A summary of flow shop scheduling problem[J]. Sci-Tech & Development of Enterprise, 2007(8): 24-25.

[7] SIM S T, YEO K T, LEE W H. An expert neural network system for dynamic job shop scheduling[J]. Engineering Library, 1994, 32(8): 1759-1773.

[8] Ding Y R, Cai Y J, Sun P D. The Use of Combined Neural Networks and Genetic Algorithms for Prediction of River Water Quality[J]. Journal of Applied Research and Technology, 2014, 12(3): 493-499.

[9] KHAN A, BAIG A R. Multi-Objective Feature Subset Selection using Non-dominated Sorting Genetic Algorithm[J]. Journal of Applied Research and Technology, 2015, 13(1): 145-159.

[10] Kumar M, Guria C. The elitist non-dominated sorting genetic algorithm with inheritance (i-NSGA-II) and its jumping gene adaptations for multi-objective optimization[J]. Information Sciences, 2017(s382-383): 15-37.

[11] 劉民, 吳澄, 蔣新松. 用遺傳算法解決并行多機調度問題[J]. 系統(tǒng)工程理論與實踐, 1998, 18(1): 14-17.LIU Min, WU Cheng, JIANG Xin-song. Genetic Algorithm Method for Identical Parallel Machine Scheduling Problem[J]. Systems Engineering-Theory & Practice, 1998, 18(1): 14-17.

[12] 鄭文秀, 房瑞東, 王璞, 等. 基于混合遺傳算法的線路板AOI運動控制系統(tǒng)設計[J]. 新型工業(yè)化, 2017, 7(2): 60-66.ZHENG Xiu-wen, FANG Rui-dong, WANG Pu, et al. Hybrid Genetic Algorithm for the AOI Motion Control System of PCB[J]. The Journal of New Industrialization, 2017,7(2): 60-66.

[13] 葛繼科, 邱玉輝, 吳春明, 等. 遺傳算法研究綜述[J]. 計算機應用研究, 2008, 25(10): 2911-2916.GE Ji-ke, QIU Yu-hui, WU Chun-ming, et al. Summary of genetic algorithm sresearch[J]. Application Research of Computers, 2008,25(10): 2911-2916.

[14] 邊霞, 米良. 遺傳算法理論及其應用研究進展[J]. 計算機應用研究, 2010, 27(7): 2425-2429.BIAN Xia, MI Liang. Development on genetic algorithm theory and its applications[J]. Application Research of Computers, 2010, 27(7):2425-2429.

[15] 孔玲爽, 潘曉楠, 肖伸平, 等. 基于改進擬態(tài)物理學算法的配電網故障區(qū)段定位[J]. 新型工業(yè)化, 2015, 5(5): 9-14.KONG Ling-shuang, PAN Xiao-nan, XIAO Shen-ping, et al. Fault Location in Distribution Network Based on Improved APO[J]. The Journal of New Industrialization, 2015, 5(5): 9-14.

[16] 馬永杰,云文霞. 遺傳算法研究進展[J]. 計算機應用研究, 2012, 29(4): 1201-1206.MA Yong-jie, YUN Wen-xia. Research progress of genetic algorithm[J]. Application Research of Computers, 2012, 29(4): 1201-1206.

[17] ?？×? 張春慨, 邵惠鶴. 求解一類并行多機調度問題的混合啟發(fā)式算法[J]. 計算機仿真, 2004, 21(3): 121-123.CHANG Jun-lin, ZHANG Chun-kai, SHAO Hui-he. A hybrid heuristic algorithm for solving a class of parallel multi-machine scheduling problems[J]. Computer Simulation, 2004, 21(3): 121-123.

[18] 徐加利, 管章玉. 協作無線網絡中基于遺傳算法的聯合中繼選擇與認知頻譜接入機制[J]. 新型工業(yè)化, 2014, 4(5): 41-47.XU Jia-li, GUANG Zhang-yu. Joint relay selection and cognitive spectrum access based on Genetic Algorithm in cooperative wireless networks[J]. The Journal of New Industrialization, 2014, 4(5): 41-47.

[19] 于瑩瑩, 陳燕, 李桃迎. 改進的遺傳算法求解旅行商問題[J]. 控制與決策, 2014, 29(8): 1483-1488.YU Ying-ying, CHEN Yan, LI Tao-ying. Improved genetic algorithm for solving TSP[J]. Control and Decision, 2014, 29(8): 1483-1488.

[20] 韓鋮, 張彥軍. 基于遺傳算法的四旋翼飛行器最優(yōu)控制[J]. 電光與控制, 2018, 25(1): 28-33.HAN Cheng, ZHANG Yan-jun. Optimal Control for Quad-rotor Aircrafts Based on Genetic Algorithm[J]. Electronics Optics ＆ Control,2018, 25(1): 28-33.