基于改進遺傳進化算法的復雜作業流程調度

張春燕

（無錫科技職業學院，江蘇 無錫 214028）

基于改進遺傳進化算法的復雜作業流程調度

張春燕

（無錫科技職業學院，江蘇 無錫 214028）

為了提高車間或者工業生產速度和質量，需要對生產中復雜作業流程調度進行研究。當前算法利用調度靜態求解法和動態優化法實現復雜作業流程的調度。該算法沒有相關策略的制定，也沒有高效的理論作為支撐，導致該算法存在調度效率低，資源的利用率和環境適應能力較差等問題。為此，提出基于改進遺傳進化算法的復雜作業流程調度。該算法先對復雜作業流程調度問題進行描述，針對調度問題描述，利用改進遺傳進化算法對車間作業調度問題進行解決，將問題描述中的數學規劃模型建立在規定的定義上。然后構建合適的編碼實現改進遺傳進化算法正常運行，過程中按一定要求對JSSP染色體進行編碼，選擇初始種群，并對適應度函數進行計算，引入交叉算子和變異算子擴大尋優范圍。最后利用無延遲作業計劃解決死鎖狀況，并通過調度過程流程圖和作業調度整體結構流程圖實現調度。實驗結果表明，本文所提算法充分利用了現有資源實現了復雜作業流程的高效調度，同時也具有比較好的適應能力和靈活性。

遺傳進化算法；復雜作業流程；調度

0 引言

車間復雜作業流程的調度，是完成車間資源優化配置比較有效的手段[1]。制造業作為國家實體經濟重要的組成部分，當前面臨著市場的殘酷競爭，制造型企業發展中出現了嚴峻考驗，比如資源瀕臨枯竭、勞動力成本的不斷增加、客戶對產品質量的要求陸續提升等[2]。如何考慮產品質量、服務、時間以及成本等因素，提高品牌聲譽，得到客戶的青睞，成為了制造型企業著重考慮的方面[3]。近些年來，中國的制造業平均水平有了很大的提高，不過在生產的效率以及生產現代化的水平上，與發達國家相比還有一定差距。由于復雜作業的調度是提升產品加工效率和實現制造型企業現代化發展的前提與基礎，怎樣實現實用又高效的復雜作業調度，成為了先進生產模式的首要問題之一[4]。車間作業的流程調度是目前調度領域中最繁瑣和最困難的問題之一，所以采用當前的復雜作業流程調度算法，無法實現物料、機器和時間等相關資源的正確調度[5]。為了解決上述問題，本文提出了一種基于改進遺傳進化算法的復雜作業流程調度，可完善當前復雜作業流程的正確調度，提高了調度的速度，提升了產品生產效率[6]。生產車間的復雜作業流程調度在一定程度上決定了制造型企業的生存，這樣的重要性引起了人們的討論，和有關專家學者的廣泛關注與研究，以下介紹了幾種比較優秀的調度算法[7]。

文獻[8]算法中提出了工作流程調度的效率，是評價工作整體表現重要指標之一。工作流程調度問題是 NP-hard問題，異構式計算環境將該問題變得更為棘手，分層基因算法把啟發式算法和GA算法結合，根據GA算法優化通過正向分層后的作業調度隊列，很顯著地減少了作業流程運行時間，該算法利用作業分層的優先級生成作業隊列，將隊列內的同層作業在整體上當作一位基因進行處理，可有效規劃作業流程，但是耗時較長。文獻[9]算法提出調度規則是實際生產中車間作業調度有關問題重要解決方式，不過它通常只在指定調度條件下性能較好，條件發生變化時，需要實時進行選擇和評價。實現調度規則實時選擇與評價方法的綜述，用來研究實際生產中車間實時調度問題。概述了調度規則發展、特點以及分類，對調度規則選擇與評價方法做出總結，全面介紹調度規則選擇方法，其中包含使用比較多的人工智能方法，給出了實驗方法，實驗證明該法對調度的選擇和評估進行了深度研究，但是存在實際應用效果較差的問題。文獻[10]算法中，在傳統的優先級調度算法基礎上，提出利用動態優先級驅動調度算法。該算法把復雜作業流程區分為四個等級，依次分配至已經設置好的等待隊列中，等待隊列內設置了不同優先級閾值，對優先級進行動態調整，達到閾值之后提升至就緒隊列中，并通過實驗證明該算法縮短了高優先級的作業流程響應時間，但是調度正確性較差。

針對上述產生的問題，提出一種基于改進遺傳進化算法的復雜作業流程調度，并利用實驗證明，該算法可對復雜作業流程進行高速穩定地調度。

1 復雜作業流程調度問題描述

假設大規模復雜作業車間內有n個工件，要在m臺設備上進行加工，工件i內包含道工序，i = 1… n 。各個工序間有工藝先后順序的約束，每臺設備j最多進行一次加工，j=1…m，代表工件i于 j上的加工工序，,ijp 代表工序,ijO 加工時間，,ikt 代表工序,ijO 開工時間，其中調度任務為：在m臺設備上對n個工件進行加工，對各個設備上的各工序加工順序和相關開工時間進行確定，用來對各個工件拖期時間進行最小化操作，并滿足以下約束條件：

全部工件工藝路線以及工序加工的時間保持不變，其中工序一旦開始，加工就不允許中斷，在同一時間各設備最多可加工一個工件，在同一時間各工件最多可在一臺設備進行加工。根據上述參數和描述，得到復雜作業調度問題所對應的數學規劃模型，也就是目標函數：

式（1）是復雜作業流程調度問題目標，也就是最小化的拖期時間之和。式（2）代表相同工件在不同工序間加工順序的約束，各工件在任意時間僅可在一臺設備上加工。式（3）與式（4）為相同設備上的不同工件間加工的順序約束，進而保障各設備在任意時刻最多加工一個工件。式（5）保障各個工件須到車間之后才能開工。復雜作業流程調度問題大概為上述內容，下面利用改進遺傳進化算法解決復雜作業流程調度問題。

2 基于改進遺傳進化算法的復雜作業流程調度

2.1 關于作業調度的定義

針對調度問題描述，利用改進遺傳進化算法對車間作業調度問題（JSSP）進行解決。車間作業調度的基本約束條件為進行調度理論分析主要約束條件，可否解決JSSP基本的約束條件，滿足作業調度問題是作業調度問題研究的關鍵。為了更好地解決調度問題，將上述的數學規劃模型建立在以下定義上。

定義一：假設P表示n個工件集合，那么P能夠表達為式（6）：

定義二：假設M表示m臺設備的集合，那么M可表達為式（7）：

定義三：假設iP的工序數量為ik，iJP表示iP工件工序集合，那么iJP可表達為式（8）：

定義四：假設 Pi中的工序到 Ji中的元素，在設備M中的加工次序是記為i（1）,i（2）,… i（ k），其中，那么設備加工的次序Q可表達為下式：

定義五：假設iM上加工工序的排列為iJM，其中0im＜＜，那么iJM可表達為式（10）：

式中，il代表在設備iM上的加工工序總數，代表設備M第i個加工零件工序的代號。

式中，iJM 表示第i臺設備上加工工序的排列陣。

定義七：有了設備加工的次序陣Q以及設備加工的工序排列陣JM，則可描述一個加工，不過缺少一個描述加工的時間矩陣，由此將加工時間矩陣定義為：

上述矩陣中每個元素均和矩陣JM內的元素對應。根據上述七個定義，和1中的數學規劃模型以及基本約束條件，對車間作業調度遺傳編碼進行研究。

2.2 改進遺傳進化算法編碼

依據作業調度的定義，對改進遺傳進化算法編碼進行分析，構建合適的編碼是實現改進遺傳進化算法正常運行的重要前提，根據JSSP數學規劃模型可知，JSSP的解可表示為所有設備的工序排列矩陣JM，因此JSSP染色體的編碼可否表達JSSP的一個有效解，其關鍵就在于可否直接或者間接表示為設備工序的排列矩陣JSSP。綜上，JSSP染色體的編碼需做到以下幾點：

1. JSSP的染色體編碼應是有序編碼串。只有有序，才能將JSSP染色體的編碼，唯一地映象成一個設備工序排列矩陣JM；

2. JSSP染色體的編碼串應包括零件加工時的所有特征，也就是哪一個工件第幾個工序，在哪一臺設備上加工。只有這樣JSSP染色體的編碼串才可以唯一地映象成一個設備工序的排列矩陣JM；

3. JSSP染色體的編碼應盡可能地精簡，只有精簡才有利于改進遺傳進化算法操作的效率。

根據上述 JSSP染色體的編碼需做到的 3點要求，給出了JSSP染色體編碼的方式。就是單一編碼方式，將所有工件工序進行統一的編號，則文中的調度問題利用如下方式進行表示：

在研究JSSP染色體之后，接下來開始選取初始的種群，隨機生成A個位數，成為nk的染色體串初始的種群，每個染色體串利用以上方式表示，盡量保持各個基因間相互獨立。

為了使改進遺傳進化算法對適應度比較高的個體，有更多生存機會，利用對目標函數標度，獲得適應度函數其中α和β為常數。

由于遺傳進化一般為雙親繁殖，所以利用這一特點，引入交叉算子，各代的各個體按照一定交叉概率，交換部分基因，生產新基因組合，用來使各解可以有機會對其優秀基因進行交流，能夠得到比父代更佳的解結構，也就是最優解。

為了使改進遺傳進化算法，并很好地應用于作業流程調度中，在交叉算子的基礎上引入了變異算子。變異算子對各個體每一位按照一定概率生成新的變化，生成新的基因型，可以進一步擴大尋優范圍，進而利于保障算法全局的最優性。

2.3 復雜作業流程調度的實現

以2.1和2.2中內容為基礎，在實現調度之前，先對死鎖的概念進行介紹。死鎖是在安排某工序加工時，這個工序前一道工序還沒有被安排進行加工，進而造成調度沒辦法繼續進行的情況。死鎖的問題得以解決，則復雜作業流程的調度問題可以獲得最大優化。

圖1 調度過程流程圖Fig.1 Flow chart of scheduling process

圖2 作業調度整體結構流程圖Fig.2 The whole structure flow chart of job scheduling

由此采用無延遲作業計劃解決死鎖情況，使每代的個體代表的解均是近優解，進而加快迭代的過程收斂速度。這里只簡單介紹死鎖的解決方法，并不作詳細的探討。得到死鎖的解決辦法后，利用調度過程流程圖和作業調度整體結構流程圖完成對調度的研究。

以上就是基于改進遺傳進化算法的復雜作業流程調度全解[11][12]，根據流程圖實現調度的準確高效操作。

3 實驗結果與分析

為了證明基于改進遺傳進化算法的復雜作業流程調度的有效性，需要進行一次相關的實驗與分析。在MATLAB R2015b環境下搭建復雜作業流程調度實驗平臺，實驗數據取自于JSP。

隨機生成10個大規模JSP算例，其中工件數集合是[100 150 200]，設備數量集合是[20 30 50]，各個工件操作過程中有5個工序，各個工序加工的時間服從[1 100]均勻分布。隨機在設備集合中選取設備進行加工，各工序在加工設備上只加工一次。

選取100個工件，和20臺設備，利用不同的調度算法，測試不同算法的調度性能。表1為不同算法下100*20算例調度結果。

分析表1可知，本文算法的拖期時間和運行時間均少于文獻所提算法。文獻[8]算法的拖期時間最長，該算法利用作業分層的優先級生成作業隊列，將隊列內的同層作業在整體上當作一位基因進行處理，在流程規劃的同時沒有指定最小拖期指標，導致拖期時間長。文獻[9]算法調度運行的時間最長，該算法概述了調度規則發展、特點以及分類，對調度規則選擇與評價方法做出總結，全面介紹調度規則選擇方法，沒有明確的約束條件，因此調度的運行時間相比其它調度算法較長。本文算法對調度的基本約束條件和最小拖期函數進行了研究和分析，建立了數學規劃模型，減少了調度運行時間，同時也減少了拖期時間。上述實驗證明了本文所提算法具有一定的可行性。圖3為不同算法加工時間（s）對比。

表1 不同算法調度性能對比（100*20）Table 1 Comparison of scheduling performance of different algorithms (100*20)

圖3 不同算法加工時間對比Fig.3 Comparison of processing time of different algorithms

由圖3可知，本文調度算法加工時間，明顯少于文獻算法加工時間。因為在利用本文算法實現調度過程中，構建了合適的編碼，并對JSSP染色體的編碼提出了要求，利用雙親繁殖的特點引入交叉算子，在交叉算子基礎上，加入變異算子，優化了本文算法調度精度，由于調度精度的增加，提高了設備加工的速度，減少了加工時間。下面是調度規模分別為100*50，150*30，150*20時，不同算法調度的負載均衡度[13]（%）對比。

通過對不同算法在不同規模下的負載均衡度對比結果可知[14]，負載均衡度越高代表調度的穩定性越好，而表中本文算法的負載均衡度相比文獻算法的負載均衡度較高。進一步說明了本文算法具有高度可實踐性和可擴展性。

表2 不同算法調度的負載均衡度對比（100*50）Table 2 Comparison of load balancing of different algorithms scheduling (100*50)

表3 不同算法調度的負載均衡度對比（150*30）Table 3 Comparison of load balancing of different algorithms scheduling (150*30)

表4 不同算法調度的負載均衡度對比（150*20）Table 4 Comparison of load balancing of different algorithms scheduling (150*20)

4 結束語

文中的交叉算子和變異算子使調度程序可視化程度受到了影響，因此需要與生產企業的調度部門所制定的生產流程調度計劃進行連接，從而可以直接應用到生產中。

采用當前算法對復雜作業流程進行調度時，無法對作業流程進行穩定，高效地調度。而基于改進遺傳進化算法的復雜作業流程調度可以實現作業流程的可靠調度，并利用實驗證明，本文所提算法具有實際意義。

[1] 郭晴, 楊海霞, 劉永泰. 云計算環境下的復雜數據庫并行調度模型仿真[J]. 計算機仿真, 2015, 32(6): 360-363.

[2] 翟穎妮, 王軍強, 褚崴, 等. 基于TOC理論的大規模作業車間調度問題研究[J]. 機械科學與技術, 2015, 34(8):1222-1228.

[3] 閆俊剛, 邢立寧, 張忠山, 等. 具有雙重時間窗約束的作業車間調度算法[J]. 科學技術與工程, 2016, 16(26): 85-92.

[4] 劉迷, LiuMi. 云計算下虛擬信息資源大數據特征集成調度[J]. 科技通報, 2015, 31(10): 199-201.

[5] 孫瓊瓊, 蔡琪. 文化框架下多群智能優化算法的云作業調度[J]. 計算機測量與控制, 2015, 23(1): 273-276.

[6] 劉?？? 李集林, 張華健. 一種改進的M-LWDF動態業務調度方法[J]. 電子設計工程, 2016, 24(22): 26-29.

[7] 李斌. 面向計算思維的集裝箱碼頭裝卸作業調度[J]. 交通運輸系統工程與信息, 2016, 16(3): 161-167.

[8] 謝濤, 董滔. 基于混合GA算法的工作流作業調度隊列優化[J]. 計算機工程與應用, 2016, 52(24): 85-90.

[9] 范華麗, 熊禾根, 蔣國璋,等. 動態車間作業調度問題中調度規則算法研究綜述[J]. 計算機應用研究, 2016, 33(3):648-653.

[10] 李薛劍, 李凱. 一種基于動態優先級的RQ作業調度算法[J]. 小型微型計算機系統, 2017, 38(1): 124-128.

[11] 吳瓊, 紀志成, 吳定會. 協同混合粒子群算法求解車間作業調度問題[J]. 計算機工程與應用, 2016, 52(5): 266-270.

[12] 馬莉, 唐善成, 王靜, 趙安新. 云計算環境下的動態反饋作業調度算法[J]. 西安交通大學學報, 2014, 48(7): 77-82.

[13] 王鵬, 黃焱, 李坤, 郭又銘. 云計算集群相空間負載均衡度優先調度算法研究[J]. 計算機研究與發展, 2014, 51(5):1095-1107.

[14] 翟穎妮, 王軍強, 褚崴, 劉昌軍. 基于TOC理論的大規模作業車間調度問題研究[J]. 機械科學與技術, 2015, 34(8):1222-1228.

Complex Job Scheduling Based on Improved Genetic Evolution Algorithm

ZHANG Chun-yan
(Wuxi Professional College of Science and Technology, Wuxi 214028)

In order to improve the production speed and quality of the workshop or industry, it is necessary to study the complicated operation process in production. The current algorithm USES the scheduling static solution method and the dynamic optimization method to implement the scheduling of complex job processes. The algorithm is not related to strategy formulation and no effective theory as the support, leading to low efficiency of the algorithm exists scheduling, resource utilization and environmental adaptation ability is poor. In this paper, the complex operation process scheduling based on improving genetic evolutionary algorithm is proposed. The algorithm for complex process scheduling problem is described first, in view of the scheduling problem description, using the improved genetic algorithm for solving job shop scheduling problem, described the problem of mathematical programming model based on the definition of the rules. And then build a suitable encoding to achieve improved genetic evolutionary algorithm run normally, process according to certain requirements for JSSP chromosome coding,choose the initial population, and the fitness function calculation, the introduction of crossover operator and mutation operator for expanding the scope of the optimization. Finally, the problem of deadlock condition was solved by using the non-delayed operation plan, and the scheduling of the whole structure flowchart was implemented by scheduling process flowchart and operation scheduling. The experimental results show that the proposed algorithm made full use of existing resources to achieve the efficient scheduling of complex process, at the same time also has a good adaptability and flexibility.

Genetic evolutionary algorithm; Complex operation process; Scheduling

國家自然科學基金(61300149)，江蘇高校品牌專業建設工程資助項目(Top-notch Academic Programs Project of Jiangsu Higher Education Institutions，TAPP)，江蘇省教育廳高校哲學社會科學研究指導項目(2016SJD880064)

張春燕(1982-)，女，江蘇南通人，講師，碩士，主要研究方向為人工智能算法與模式識別，計算機控制系統等方面。

TP18

A

10.3969/j.issn.1003-6970.2017.12.019

本文著錄格式：張春燕. 基于改進遺傳進化算法的復雜作業流程調度[J]. 軟件，2017，38（12）：98-103