基于改進遺傳算法的柔性作業車間調度研究

代招 李郝林

摘 要：針對中小型企業生產車間柔性作業調度問題，采用改進的遺傳算法求解最優調度結果。將最大完工時間最小化作為調度目標，對經典遺傳算法進行相應的改進。首先利用粒子群算法獲取工序序列與粒子參數之間的映射關系，在初始種群中利用混沌映射和反向學習策略以提高初始種群質量;然后提出一種將機器編碼和工序編碼相結合的分段編碼方法，以解決某道工序有多臺可選機器加工的問題;最后利用自適應交叉和變異概率提高算法收斂速度。通過對Brandimarte設計的10組不同規格的基準案例進行仿真實驗，得到進化曲線和最優調度方案。實驗結果驗證了該方法的實用性和有效性。

關鍵詞：遺傳算法;作業車間調度;柔性;完工時間

DOI：10. 11907/rjdk.192572 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP301文獻標識碼：A 文章編號：1672-7800（2020）005-0083-05

0 引言

柔性作業調度問題（Flexible Job Shop Scheduling Problem，FJSP）作為生產管理和組合優化問題的重點研究對象 [1]，是傳統作業車間調度問題（Job-shop Scheduling Problem， JSP）的擴展，也被劃分為強NP-hard問題[2]。FJSP的含義是：工件的工序不但能夠在各個機器上進行處理，而且加工耗時也因機器而異，這要求為工件的每道工序分派最適合的機器，同時也要保證工件加工工藝的合理性[3]。所以FJSP更符合車間實際生產環境，是目前亟待解決的調度難題[4]。該問題一般有兩個難點：①如何將可選機器集中分派給指定工序;②如何安排工序在機器上的加工順序。

為解決這類問題，學者提出了遺傳算法[5]、蟻群算法[6]、模擬退火算法[7]、粒子群算法[8]等智能優化方法。現有研究結果表明，利用遺傳算法求解FJSP效果很好且有獨特優勢[9-10]。遺傳算法求解FJSP時，初始種群質量對最終求解結果和迭代速度有較大影響。目前，用遺傳算法求解FJSP時一般采用隨機生成初始種群方式，這樣在迭代初期會形成許多非法解，只有經過大量的復雜運算后才可能出現較優解，因而導致算法收斂速度低。Kacem等[11]提出了根據加工時間表進行分配的方法，Zhang等[12]提出了依據機器時間數組的分配方法，雖然這兩種方法取得了一定效果，但都是基于單步優化策略分配機器的方式，并不能保證最終整體分配質量。

為加快算法的收斂速度，提高機器分配質量，本文試圖采用改進的遺傳算法解決柔性作業調度問題，改進之處包括：利用粒子群算法得到粒子參數與工序序列的映射關系，在初始種群中采用混沌映射[13]和反向學習[14]策略，選取適應度值前50%作為初始種群，進而提高種群質量，同時不失去其多樣性，利用自適應交叉和變異概率提高算法的搜索效率，提高算法的收斂性能。提出將機器編碼和工序編碼相結合的分段編碼方法解決機器分配問題，利用粒子群算法得到優化的初始機器鏈，對機器分配序號，朝著加工耗時最短的目標方向變異以提高機器分配質量。最后利用不同規格的基準案例進行仿真實驗，實驗結果驗證了本改進算法的實用性和有效性。

1 FJSP調度模型

1.1 FJSP問題描述

通常將柔性作業調度描述為：某生產車間有[m]臺機器，[n]個工藝流程明確的工件，每個工件至少有一道工序需在這些機器上加工，每個工序能夠在不同機器上進行加工且耗時因機器而異。所以FJSP就是要在滿足一定約束條件的前提下，為工件的每道工序分派最適合的加工機器，同時還應對工件工序的加工順序進行合理編排，以達到最優的性能指標 [3]。FJSP一般由以下幾個要素組成：

（1）待加工工件集合。[J=J1，J2，？，Jn]是一個待加工工件數為[n]的集合，每個工件[Ji]都有其加工工藝，[Oij]表示工件[i]的第[j]道工序，在零時刻，所有的工件都能被加工。

（2）加工機器集合。[M=M1，M2，？，Mm]是一個機器數量為[m]的集合。每臺設備在同一時間只能對一個工件進行加工且工序一旦開始就不能中斷。在零時刻，所有機器都是可用的。

（3）柔性。某道工序能夠在可選機器集合中的任一機器進行加工。

（4）約束。主要約束包括：在同一時刻，任何工件的任一工序只能被一臺設備處理;每道工序一旦開始處理就不允許暫停;工件之間沒有嚴格的優先級;任一工件的后道工序只有等前道工序加工完成后才能進行。

（5）目標。本文把最大完工時間的最小值作為最優解。即把[n]個工件安排在[m]臺設備上加工，使所有加工任務的最大完工時間[Cmax]最小。

1.2 FJSP問題數學模型

本文用一個二維數組proMacArray[][]表示各個工序的可選加工設備及該工序在此設備上的加工耗時，proMacArray[][]中的每個一維數組對應一道工序，一維數組的個數等于所有工件的工序數量之和。任意工件的任一工序可用加工機器用一個一維數組描述，機器編號為該一維數組的索引;該機器加工該工序的耗時為該索引對應的一維數組中的元素值。如表1所示，以工件1的第2道工序（[O12]）為例，其可用加工設備的編號為2和4，對應的加工時間為5和3。

2 改進的遺傳算法求解FJSP

2.1 編碼與解碼

本文采用分段編碼技巧，即把染色體分為兩部分：①機器選擇部分（MS）為染色體的前半部分，由工件工序的可選加工設備編號組成，用來為工序提供加工機器;②工序選擇部分（OS）為染色體的后半部分，由工件的各個工序編號組成，用于編排各工序的處理次序。兩段長度分別為N，N為所有工件的工序總數。MS和OS通過間接編碼方法實現，如圖1所示。若[i]為工件編號，則該工件的第幾道工序就是[i]在OS段出現的次數值。第一個工件的第一道工序一直到最后一個工件的末道工序所選機器編號，就是MS段中從左至右依次出現的數字。采用這種方式，MS和OS一一對應。

解碼可視為編碼的逆流程，具體步驟為：首先對OS段進行從左至右的依次遍歷，那么工件和工序編號就可據此確定，再根據MS中的值確定加工機器號和加工時間。

2.2 適應度函數設計

車間作業調度順序是按OS段的編碼從左向右依次執行的。當OS編碼段中工序加工完成，那么就得到完成調度任務的最大完工時間。我們的目標是最大完工時間最小化，因此適應度值與最大完工時間成反比，計算方法如下：

2.3 初始化種群

經典的粒子群算法是由[n]個粒子組成的一個[D]維搜索空間。每次迭代時，第[i]個粒子會憑借此時整體最優值和歷次最優值實行種群間的相互交流，從而更新自身速度和位置，進而使整體種群不停地朝著全局最優解方向靠攏[15]，粒子更新公式為：

2.4 選擇

為盡可能讓適應度高的個體被保留，本文選擇后代個體的方式是以輪盤賭策略為基礎，輔以精英策略相結合。輪盤賭策略可有效防止問題的解步入局部最優化陷阱，精英策略則確保種群向更高質量的方向進化，兩者有效結合，加速了種群的迭代和求解速度。

2.5 交叉與變異

按照編碼方式本文選擇算子如下：針對MS利用隨機交叉和單點變異算子，針對OS采用順序交叉、單點交叉相結合的方法和逆轉變異算子，下面作簡單介紹。

2.5.1 交叉算子

針對MS段采用的是隨機交叉算子，其實現流程為：隨機將兩條染色體中MS部分中的某個局部區間的所有基因進行交換，其交叉過程如圖2所示。

OS的交叉過程為：在兩親代染色體[P1]和[P2]中，任意選其中一個基因的位置[i]，然后把[1～i]這一范圍內的基因段當成交叉區間，且用[A]和[B]標記交叉區間中的基因段;在[P1]中，把[B]中所有基因值按從左至右的次序進行遍歷，然后將[P1]中出現相對應位置的基因去掉，同理操作[P2];然后把[P1]、[P2]中余下的基因位置保持相對位置不變向右移;最后把[P1]交叉區間的基因更換為[B]的基因，把[P2]交叉區間的基因更換為[A]的基因，其交叉過程如圖3所示。

2.5.2 變異算子

MS段利用的是單點變異算子，實現流程為：把某個工序的可選加工機器集中耗時最短的機器編號更新為MS段中某一指定位置的值。用圖中[O12]進行說明，它對應的基因值是1，表明選擇機器集中的第一臺機器M2。據表1可知，該位置對應M2和M4這兩臺可選機器，其加工耗時分別是5和3。由于M4 耗時小于M2，因此這個位置的基因就變異為可選機器集中M4的編碼2，反之保留1不變。OS段利用的是逆轉變異算子，其實現過程十分簡易，就是將OS段中不同位置的值進行交換。

2.6 停止條件

當滿足收斂條件或迭代次數達到100次時，結束尋優搜索。

3 實驗結果

本文利用Brandimarte[17]設計的MK01-10系列標準案例對改進的遺傳算法進行驗證。該案例包括10個問題，其中工件數量從10～20個不等，機器數量從6～15臺不等。該算法收斂曲線如圖4所示，傳統遺傳算法收斂曲線如圖5所示。表2是本文所提出的改進遺傳算法和其它文獻所用算法進行求解FJSP問題的結果對比， [N]代表工件數，[M]代表設備數。文中改進算法仿真所用參數為：種群大小為[N]=100，迭代次數[T]=100，[k1]=1.0，[k2]=1.0，[k3]=0.5，[k4]=0.5。

對比表中數據得出如下結論：在求解中小規模的車間調度問題時，利用本文改進的遺傳算法得到的最大完工時間能夠達到目前已知的最優解，而且本文所用算法收斂速度較傳統遺傳算法有了較大的提升，能夠滿足車間實時調度要求。下面用規模10*6的仿真案例進行說明，將最終得出的調度方案用甘特圖展示，如圖6所示。圖中數字代表工件號，同一工件在橫軸方向上出現的不同次序表示工件的各個工序，矩形長短表示加工某工序的耗時多少。縱軸代表機器在某機器上進行加工的工序，該工序與機器編號在同一行出現。

4 結語

為解決中小型企業柔性作業車間調度問題，本文建立了相對應的數學模型，對遺傳算法進行改進，以尋求作業調度的最優解。通過改變初始種群的生產方式，利用自適應交叉和變異概率等改進措施，大幅提高了算法的收斂速度和求解質量，能夠滿足車間實時調度要求。通過一系列標準的實驗案例，驗證本文改進遺傳算法求解FJSP的正確性和有效性。未來將對基于事件的多目標動態調度進行研究。

參考文獻：

[1] 徐本柱， 費曉露， 章興玲. 柔性作業車間批量劃分與并行調度優化[J]. 計算機集成制造系統， 2016， 22（8）： 1953-1964.

[2] 張騰飛， 馬躍， 李力， 等. 柔性作業車間調度問題的改進遺傳算法[J]. 小型微型計算機系統， 2017， 38（1）： 129-132.

[3] 王明. 基于改進遺傳算法的作業車間調度問題研究[D]. 蕪湖：安徽工程大學，2019.

[4] ZHANG R， SONG S， WU C. A two-stage hybrid particle swarm optimization algorithm for the stochastic job shop scheduling problem[J]. Information & Control， 2012， 27（3）： 393-406.

[5] BHOSALE KC， PAWAR PJ. Material flow optimization of flexible manufacturing system using real coded genetic algorithm （RCGA）[J]. Materials Today Proceedings， 2018， 5（2）： 7160-7167.

[6] 喬東平，裴杰，肖艷秋，等. 蟻群算法及其應用綜述[J]. 軟件導刊， 2017， 16（12）： 217-221.

[7] CRUZCHAVEZ M A， MARTINEZRANGEL M G， CRUZROSALES M H. Accelerated simulated annealing algorithm applied to the flexible job shop scheduling problem[J]. International Transactions in operational Research， 2017， 24（5）： 1119-1137.

[8] HUANG S，TIAN N，WANG Y，et al. Multi-objective flexible job-shop scheduling problem using modified discrete particle swarm optimization[J]. SpringerPlus， 2016， 5（1）： 1432.

[9] 王春，張明，紀志成， 等. 基于遺傳算法的多目標動態柔性作業車間調度[J]. 系統仿真學報，2017， 29（8）： 1647-1657.

[10] 劉勝， 于海強. 基于改進遺傳算法的多目標FJSP問題研究[J]. 控制工程， 2016， 23（6）： 816-822.

[11] KACEM I， HAMMADI S， BORNE P. Approach by localization and multi-objective 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.

[12] ZHANG G H， GAO L， SHI Y. An effective genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications， 2011， 38（4）： 3563-3573.

[13] MAY B R. Simple mathematical models with very complicated dynamics[J]. Nature， 1976， 261（5560）： 459-467.

[14] WANG H， WU Z， RAHNAMAYAN S， et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences， 2011， 181（20）： 4699-4714.

[15] GHASEMI M ， AGHAEI J ， HADIPOUR M . New self-organizing hierarchical PSO with jumping time-varying acceleration coefficients[J]. Electronics Letters， 2017， 53（20）：1360-1362.

[16] 何斌， 張接信， 張富強. 一種求解作業車間調度問題的改進遺傳算法[J]. 制造業自動化， 2018， 40（8）， 113-117

[17] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search [J]. Annals of Operations Research， 1993（22）： 158-183.

（責任編輯：杜能鋼）