代招 李郝林

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

關(guān)鍵詞：遺傳算法;作業(yè)車間調(diào)度;柔性;完工時間

DOI：10. 11907/rjdk.192572 開放科學(xué)（資源服務(wù)）標識碼（OSID）：

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

0 引言

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

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

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

1 FJSP調(diào)度模型

1.1 FJSP問題描述

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

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

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

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

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

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

1.2 FJSP問題數(shù)學(xué)模型

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

2 改進的遺傳算法求解FJSP

2.1 編碼與解碼

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

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

2.2 適應(yīng)度函數(shù)設(shè)計

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

2.3 初始化種群

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

2.4 選擇

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

2.5 交叉與變異

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

2.5.1 交叉算子

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

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

2.5.2 變異算子

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

2.6 停止條件

當(dāng)滿足收斂條件或迭代次數(shù)達到100次時，結(jié)束尋優(yōu)搜索。

3 實驗結(jié)果

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

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

4 結(jié)語

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

參考文獻：

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

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

[3] 王明. 基于改進遺傳算法的作業(yè)車間調(diào)度問題研究[D]. 蕪湖：安徽工程大學(xué)，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] 喬東平，裴杰，肖艷秋，等. 蟻群算法及其應(yīng)用綜述[J]. 軟件導(dǎo)刊， 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] 王春，張明，紀志成， 等. 基于遺傳算法的多目標動態(tài)柔性作業(yè)車間調(diào)度[J]. 系統(tǒng)仿真學(xué)報，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] 何斌， 張接信， 張富強. 一種求解作業(yè)車間調(diào)度問題的改進遺傳算法[J]. 制造業(yè)自動化， 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.

（責(zé)任編輯：杜能鋼）