基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度研究

代招 李郝林

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

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

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

中圖分類號：TP301文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2020）005-0083-05

0 引言

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

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

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

1 FJSP調(diào)度模型

1.1 FJSP問題描述

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

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

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

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

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

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

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

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

2 改進(jìn)的遺傳算法求解FJSP

2.1 編碼與解碼

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

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

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

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

2.3 初始化種群

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

2.4 選擇

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

2.5 交叉與變異

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

2.5.1 交叉算子

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

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

2.5.2 變異算子

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

2.6 停止條件

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

3 實(shí)驗(yàn)結(jié)果

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

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

4 結(jié)語

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

參考文獻(xiàn)：

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

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

[3] 王明. 基于改進(jìn)遺傳算法的作業(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] 王春，張明，紀(jì)志成， 等. 基于遺傳算法的多目標(biāo)動(dòng)態(tài)柔性作業(yè)車間調(diào)度[J]. 系統(tǒng)仿真學(xué)報(bào)，2017， 29（8）： 1647-1657.

[10] 劉勝， 于海強(qiáng). 基于改進(jìn)遺傳算法的多目標(biāo)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] 何斌， 張接信， 張富強(qiáng). 一種求解作業(yè)車間調(diào)度問題的改進(jìn)遺傳算法[J]. 制造業(yè)自動(dòng)化， 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é)任編輯：杜能鋼）