考慮多時間約束和機器效率的柔性作業(yè)車間調(diào)度問題建模及優(yōu)化 *

梁曉磊 馬千慧 李章洪 劉星雨 張孟鏑

(武漢科技大學(xué)汽車與交通工程學(xué)院，湖北 武漢 430065)

柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem, FJSP)是作業(yè)車間調(diào)度問題(job-shop scheduling problem, JSP)的一個重要分支，多機器選擇和工序排序問題是比確定加工路徑的調(diào)度問題更為復(fù)雜的NP-hard問題[1]，也是制造業(yè)中亟需解決的一類問題。針對這一問題，許多學(xué)者研究了不同條件下的柔性作業(yè)車間調(diào)度問題。如在模型構(gòu)建方面，有考慮加工時間不確定性并利用時間Petri網(wǎng)建立模型[2]、基于設(shè)備狀態(tài)-能量分布的綠色低碳調(diào)度模型[3]、考慮工件安裝和定位調(diào)整時間的模型[4]、具有運輸時間和以總拖期最短為目標[5]以及具有增強信息素關(guān)系的蟻群序列和運輸時間的模型[6]。此外，大多數(shù)考慮時間因素的FJSP研究也都是以最小完工時間為目標[7-9]。在求解方法的研究中，主要采用智能算法，如結(jié)合仿生雜交細菌覓食優(yōu)化算法和模擬退火算法求解FJSP[10]、粒子群算法和人類學(xué)習優(yōu)化算法混合[11]、社會蜘蛛優(yōu)化與遺傳算法混合求解FJSP[12]等，這些研究表明，智能算法在求解FJSP方面具有較好的效果，成為研究的主流?？梢?，目前的研究主要集中在獨立時間因素或以最小完工時間為目標的柔性作業(yè)車間調(diào)度，較少綜合考慮多時間和多目標因素，特別是對工序間運輸時間和機器效率的影響研究不足。在實際制造過程中，包括運輸時間在內(nèi)的多時間因素以及使機器負載均衡化是不可忽略的重要因素[13-15]。

因此，本文提出同時考慮工件運輸時間、到達時刻和交貨期，構(gòu)建以最小化完工時間和最大化機器效率為目標的柔性作業(yè)車間調(diào)度模型，任務(wù)調(diào)度會受到工件的緊前工序、機器上的前置工序、機器可用時間段的影響?；谶z傳算法，在變異操作過程中考慮機器的利用率對機器重新選擇，并設(shè)計了一種分段交叉和局部種群擴張策略對模型進行求解。

1 考慮工件運輸時間和機器效率的FJSP問題及模型描述

1.1 問題描述

在傳統(tǒng)的JSP中，工件選擇的機器和加工時間都是固定的，調(diào)度目標只需確定工序的加工順序。在FJSP中，每道工序可以選擇可加工機器集中的一臺機器加工，且加工時間不同。與生產(chǎn)實際相一致，本文研究最大化機器效率下具有工序無關(guān)的運輸時間和部分柔性作業(yè)特點的車間調(diào)度問題。問題描述如下：一個生產(chǎn)調(diào)度包含n個工件和m臺機器，每個工件的操作工序不同，每道工序有不同的可選機器，在不同機器上的加工時間和運輸時間也不相同，每個工件的到達時刻和交貨期是確定的。調(diào)度目標是為每道工序選擇最合適的機器、確定每臺機器上各工件工序的最佳加工順序，使工件的完工時間和機器效率綜合最優(yōu)。

1.2 模型假設(shè)

對于構(gòu)建的模型，根據(jù)作業(yè)要求，做如下假設(shè)：

(1)所有機器在加工前準備就緒，所有工件嚴格按照到達時刻加工。

(2)在給定時間內(nèi)，每個工件加工一旦開始不可中斷，即加工過程為非搶占式。

(3)任意機器同一時刻只能加工一個工件，任意工件同一時刻只能被一臺機器加工。

(4)不同工件間沒有加工順序約束；同一工件的工序需按照工藝順序加工。

(5)任意工序一旦加工完成，就立即運輸?shù)较乱还ば蚣庸C器，不考慮成批運輸。

(6)工件交付受交貨期限制，即每個工件最后一道工序的最大完工時間不大于交貨期。

(7)不考慮機器故障和運輸資源。

1.3 符號和變量定義

模型符號的定義如下：

Ji：表示第i個工件(i∈[1,n])。

Mk：表示第k臺機器(k∈[1,m])。

Oi,j：表示第i個工件的第j道工序(j∈[1,h])。

Ut,i,j,k：表示t時刻機器Mk可加工工序數(shù)量。

Pi,j,k：表示工序Oi,j在機器Mk上的加工時間。

Ti,l,k：表示工件Ji在兩個不同機器Ml和Mk之間的運輸時間(l∈[1,m])。

FTk：表示機器Mk從開始加工到結(jié)束加工之間的空閑時間。

MSk,MEk：表示機器可用時間段的開始時間和結(jié)束時間。

Ei,j,k：表示工序Oi,j在機器Mk上的完工時間。

定義Oi,(j-1)表示Oi,j的緊前工序，Oi′,j′表示Oi,j當前所在機器的前置工序。則，

Ei′,j′,k：表示工序Oi′,j′所對應(yīng)的完工時間。

每個工件的到達時刻和交貨期是給定的：

Ri：表示工件Ji的到達時刻。

Di：表示工件Ji的交貨期。

L：表示一個極大的正數(shù)。

決策變量的解釋如下：

Xi,j,k：如果工序Oi,j選擇機器Mk進行加工，則Xi,j,k=1，否則Xi,j,k=0。

Yv,g,i,j,k：如果工序Ov,g在機器Mk上比工序Oi,j先加工，則Yv,g,i,j,k=1，否則Yv,g,i,j,k=0(v∈[1,h],g∈[1,h])。

Z(Mk)：如果當前機器正在使用，則Z(Mk)=1，否則Z(Mk)=0。

1.4 模型建立

(1)

其中：k∈[1,m]

f2=min(maxEi,j,k)

(2)

其中：l∈[1,n],j∈[1,h]

Z(Mk)=0

(3)

Z(Mk)=1

(4)

(5)

(6)

其中：v∈[1,n],g∈[1,h]

Ut,i,j,k=1

(7)

(8)

(9)

(10)

(11)

當j=h時，Ei,j,k≤Di

(12)

(13)

式(1)表示第一個目標函數(shù)，最大化機器效率；式(2)表示第二個目標函數(shù)，最小化工件最大完工時間；式(3)、(4)表示考慮了運輸時間約束和機器可用時間段的工件完工時間的計算；式(5)、(6)表示每臺加工機器的能力約束；式(7)表示每個工件同一時刻只能被分配給一個加工機器；式(8)表示同一工件中兩個操作工序之間的優(yōu)先約束；式(9)表示同一臺機器上兩個操作工序之間的優(yōu)先約束；式(10)表示只有在當前機器可用時才能加工工件；式(11)表示運輸時間約束；式(12)表示工件的交付受交貨期限制；式(13)表示工件的任意一道工序的可選機器至少有一種，每一臺機器上可以存在循環(huán)操作。

根據(jù)以上約束模型，考慮設(shè)備使用情況和加工機器的沖突，避免每次工件選擇加工時間短的機器進行加工，造成單一機器使用頻率過多，其余機器大量空閑，以致機器利用不均衡，現(xiàn)設(shè)置第一個目標最大化機器效率；考慮到車間效率，設(shè)置第二個目標最小化最大完工時間，目標函數(shù)構(gòu)建如下：

(1)最大化機器效率

(14)

在此定義機器效率用每臺機器開始加工到結(jié)束加工之間的空閑時間和計算。

(2)最小化最大完工時間

f2=min(maxEi,j,k),l∈[1,n],j∈[1,h]

(15)

2 求解柔性作業(yè)車間調(diào)度問題的改進遺傳算法設(shè)計

2.1 算法編碼及解碼策略設(shè)計

(1)分段式編碼策略

本文FJSP在傳統(tǒng)JSP基于工序編碼的基礎(chǔ)上設(shè)計了分段編碼策略，將兩個子問題編碼到一條染色體上，每個基因位用整數(shù)表示，該染色體由兩部分組成，第一部分采用基于工序的編碼，用來確定工序的加工先后順序，工件號出現(xiàn)的次數(shù)就表示該工件的工序數(shù)；第二部分為基于機器分配的編碼，用于選擇工序的可加工機器，基因位上的數(shù)值表示工序可選機器集中從左往右的第幾臺機器，并不是表示實際的加工機器編號。這兩部分染色體長度均為總工序數(shù)。為解釋算法的編碼和解碼過程，本文構(gòu)建了小規(guī)模部分柔性作業(yè)車間調(diào)度問題案例進行說明。表1、2是一個3×5(3個工件、5臺機器)規(guī)模問題實例和運輸時間表，其中“-”表示某一工序不能在該機器上加工。下文以該3×5規(guī)模問題為例說明編碼過程，結(jié)合兩種編碼的染色體結(jié)構(gòu)如圖1所示。

表1 3×5規(guī)模問題實例

表2 實例運輸時間

圖1工序排序部分所示一個工序編碼為[2 1 1 3 2 1 3 3 2]，染色體長度為9。第一個基因位上的數(shù)值2表示加工工件J2的第一道工序O21；第二個基因位上的數(shù)值1表示加工工件J1的第一道工序O11，以此類推。同樣，圖1機器選擇部分所示一個機器編碼為[2 1 3 1 2 3 2 2 4]，染色體長度亦為9。第一個基因位上的數(shù)值2表示工序O21選擇第二臺可以選擇的機器M3，第二個基因位上的數(shù)值1表示工序O11選擇第一臺可以選擇的機器M1，以此類推。

(2)插入式解碼策略

①機器選擇解碼

對于機器選擇部分，從左到右依次解碼機器染色體，轉(zhuǎn)換成機器矩陣JM和時間矩陣T。以表1、2實例為例，如圖1所示的一個染色體編碼，機器選擇部分[2 1 3 1 2 3 2 2 4]轉(zhuǎn)換成機器矩陣JM=[3 1 4 1 3 2 4 3 5]和時間矩陣T=[8 9 16 15 11 7 6 9 19]，其中JM中的基因位表示工序，基因位上的數(shù)值表示機器編號，如第一個基因位上的數(shù)值3表示工序O21選擇機器M3，同樣地，T中的基因位表示工序，基因位上的數(shù)值表示該工序在相應(yīng)機器上的加工時間，如第一個基因位上的數(shù)值8表示工序O21在機器M3上的加工時間為8。

②工序排序解碼

對于工序排序部分，從左到右依次解碼工序染色體，得到最佳加工工藝順序，再通過JM和T得到每一道工序的相應(yīng)加工機器Mk、加工時間Pi,j,k和運輸時間Ti,l,k；根據(jù)式(3)、(4)計算工件的最早開始加工時間和完工時間。如果該工序是機器上的第一個操作，只需考慮其緊前工序的完工時間；如果該工序是工件的第一道工序，則需要比較該工件的到達時刻和加工機器前置工序的完工時間的大?。环駝t，需要考慮機器的可用時間段是否滿足工件的插入，當某一工件滿足式(10)時，部分工序插入式解碼過程如圖2a所示，不滿足時如圖2b所示。

2.2 遺傳操作策略改進

(1)混合初始化設(shè)計

初始解的質(zhì)量影響算法的收斂速度和搜索性能。當前此類問題通常采用隨機初始化的方法，但這種方法沒有考慮時間約束，降低了生成初始可行解的效率。為了充分考慮多時間因素，在初始化階段加入加工時間和運輸時間約束，設(shè)計了一種混合策略初始化種群，工序排序部分采用隨機初始化，機器選擇部分采用混合初始化，即對80%染色體的工序選擇加工時間和運輸時間最短的機器，20%染色體的工序在其可選機器集中隨機選擇一臺機器加工，使種群在保持多樣性的前提下盡量選擇優(yōu)化結(jié)果好的個體。根據(jù)3×5規(guī)模問題實例，得到采用隨機初始化和混合初始化兩種方法下的初始解對比圖如圖3所示，從圖中可以明顯看出改進后的初始解更優(yōu)。

(2)適應(yīng)度值計算

本文模型以機器效率最高和完工時間最短為目標，為簡化計算，在此采用加權(quán)方式對兩個目標綜合，構(gòu)建適應(yīng)度函數(shù)。適應(yīng)度值計算如下：

F=ω1f1+ω2f2

(16)

式中：ω1、ω2取值在[0,1]且ω1+ω2=1。根據(jù)實際決策偏好(時間和效率)可調(diào)整ω1、ω2的大小，以滿足不同決策者對兩個子目標的要求?；谏鲜龇绞竭M行染色體適應(yīng)度計算，作為遺傳選擇操作基礎(chǔ)。

輪盤賭是遺傳算法中一種常用的隨機選擇方法，這種比例選擇操作能夠使種群快速地逼近最優(yōu)解。本文選擇操作采用最優(yōu)個體保存和輪盤賭結(jié)合的選擇策略，最優(yōu)個體保存是將種群中的最優(yōu)個體直接復(fù)制到下一代，然后采用輪盤賭依據(jù)個體的適應(yīng)度值計算每個個體在后代中出現(xiàn)的概率，以隨機選擇個體構(gòu)成子代種群。

(3)交叉變異操作設(shè)計

①交叉操作設(shè)計

固定的交叉概率會使得個體在產(chǎn)生新子代的過程中缺乏適應(yīng)性，無法根據(jù)種群需求進行調(diào)整。本文基于S-自適應(yīng)交叉概率[16]設(shè)計了個體分段交叉策略，工序排序部分采用IPOX交叉方式，將所有工件隨機分成兩組，僅交叉父代染色體中工件的工序序列，直接復(fù)制工件中工序選擇的機器到子代，而機器選擇部分采用隨機交叉方式。以3×5規(guī)模問題為例的交叉操作過程如下圖4所示，復(fù)制父代1中包含在J1同一位置的工序到子代1，復(fù)制父代2中包含在J2同一位置的工序到子代2；父代1中包含在J1中的工序按順序復(fù)制到子代2剩余位置，父代2中包含在J2中的工序按順序復(fù)制到子代1剩余位置。

②變異操作設(shè)計

為了保持種群多樣性，變異操作采用分段變異方式。對于工序排序部分，實施基于工序變異的單點變異操作；對于機器選擇部分，基于機器利用率的機器選擇策略在原有變異策略的基礎(chǔ)上，計算每個父代個體每臺機器的使用頻次，在工序順序不變的前提下，以一定概率對機器進行輪盤賭選擇，重新選擇時，以機器的使用頻次為依據(jù)，使用頻次越小，被選擇的概率越大。以3×5實例問題為例，某一個體[1 1 2 3 2 1 3 3 2 2 1 3 1 2 3 1 3 1]機器選擇部分對應(yīng)的實際機器號為[2 2 4 1 3 5 3 5 1]，其中機器1被選擇2次，機器2被選擇2次，機器3被選擇2次，機器4被選擇1次，機器5被選擇2次，機器4使用頻次最小，使用輪盤賭操作使其被選擇的概率最大，從而縮短機器的最大完工時間，實現(xiàn)機器效率最大化。

(4)局部種群擴張策略

針對傳統(tǒng)的遺傳算法采用交叉變異后的個體擴充種群，可能造成部分解信息丟失。在此常規(guī)種群構(gòu)建基礎(chǔ)上，本文采用一種局部種群擴張策略，從父代和子代混合個體中進行選擇，這樣父代個體和交叉變異得到的個體具有同等的選擇機會，既能將最優(yōu)個體保留到下一代，又便于保持子代的多樣性。

2.3 算法流程

基于改進遺傳算法求解考慮運輸時間的柔性作業(yè)車間調(diào)度問題的步驟如下：

步驟1設(shè)置參數(shù)。確定種群大小P、最大遺傳代數(shù)M、選擇概率Pa、變異概率Pm；

步驟2 種群初始化?？紤]調(diào)度問題的時間因素，基于分段式編碼和插入式解碼以及混合策略進行種群初始化；

步驟3 采用最優(yōu)個體保存和輪盤賭結(jié)合的復(fù)合選擇策略進行選擇，選出交叉?zhèn)€體；

步驟4 采用S-自適應(yīng)交叉概率對種群個體分段交叉；

步驟5 對工序排序部分進行單點變異，機器選擇部分按照一定概率選擇加工時間和運輸時間短的機器；

步驟6 保持工序順序不變，機器選擇部分根據(jù)一定概率基于機器利用率進行輪盤賭選擇；

步驟7 更新目標適應(yīng)度值比較大小，若滿足輸出條件結(jié)束運行，否則，采用局部種群擴張策略重新插入新種群，執(zhí)行步驟3。

3 案例求解與結(jié)果分析

3.1 案例及算法參數(shù)設(shè)置

為了驗證模型和算法的有效性，以10×8算例[17]和12×10算例[5]數(shù)據(jù)進行測試，兩個算例運輸時間參考文獻5中數(shù)據(jù)。

為了進一步比較算法的性能，采用傳統(tǒng)遺傳算法(genetic algorithm，GA)、粒子群算法(particle swarm optimization，PSO)、模擬退火算法(simulated annealing，SA)和本文改進遺傳算法(improved GA，IGA)分別進行測試。采用Matlab R2018b對算法進行編程實現(xiàn)并對實例問題進行求解驗證，實驗在平臺(Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz 3.19 GHz，內(nèi)存8.00 GB)上進行。算法參數(shù)設(shè)置如下：種群規(guī)模和迭代次數(shù)統(tǒng)一設(shè)置為P=200、M=200；其中PSO參數(shù)設(shè)置參考文獻18，學(xué)習因子c1、c2取值2.05，慣性權(quán)重ωmax=0.9，ωmin=0.4；SA參數(shù)設(shè)置參考文獻[19]，退火起始Tb=1 000，終止溫度Te=0.001，降溫速度r=0.98，迭代步長L=200；本文算法IGA設(shè)置選擇概率Pa=0.8，變異概率Pm=0.1；為方便做對比，GA中設(shè)置和IGA相同的參數(shù)。設(shè)置算法IGA、GA、PSO達到設(shè)定迭代次數(shù)就終止算法，算法SA達到設(shè)定終止溫度Te就終止算法。

表3 12×10規(guī)模問題實例

表4 實例運輸時間

3.2 案例求解

以12 × 10 規(guī)模問題為例 。 求解中假設(shè)取時間和機器效率的目標權(quán)重分別為 0.8 和 0.2 ，得到考慮運輸時間的最優(yōu)調(diào)度甘特圖如圖 5 所示。基于優(yōu)化結(jié)果(圖 5 可知， 求解獲得的最好適應(yīng)度值調(diào)度解的工序編碼為 [201 901 1001 301 401 701 501 902 601 702 1002 402 101 202 801 602 1101 903 1201 802 302 502 603 203 1202 102 904 303 403 1003 905 803 1102 103 1004 1203 304 906 804 ]，機器編碼為 [4 7 9 3 8 4 5 7 9 8 6 4 7 9 3 10 5 4 7 3 8 6 10 4 7 1 2 8 6 4 2 1 0 7 4 10 1 2 4 10 ]。 解釋如下:其中，201 在縱坐標對應(yīng)值為4，表示第2個工件的第一道工序在機器4 上加工， 距離坐標原點的這段時間對應(yīng)于工件2的到達時刻8,因此201的最早開始加工時間為8，再經(jīng)過10個單位的加 工時間，它的完工時間為18；工件2的第2道工序 202 在機器9上加工，機器4到機器9的運輸時間為5，此時機器9上有前置工序1001和601，工序1001的最早開始加工時間為到達時刻15，再經(jīng)過7個單位的加工時間，其完工時間為22，工序601的到達時刻為19 ,其最早開始加工時間為 max (19,22 )=22,再經(jīng)過 11 個單位的加工時間，其完工時間為33，因此工序202的最早開始加工時間為 max( 33 ,18+5 )=33。同理，10 × 8 規(guī)模問題類似。

圖6 為不采用基于機器利用率的變異策略的調(diào)度甘特圖，和圖 5 相比較，將機器利用率作為影響因素考慮進調(diào)度方案可以明顯縮短工件的完工時間，并且有效降低各機器的空閑時間，增大機器使用率，從而提高機器效率。

3.3 算法性能測試

為測試算法性能，用上述兩組問題實例對GA、PSO、SA和本文算法IGA分別進行測試，優(yōu)化目標為最小化最大完工時間和最大化機器效率。運算取時間和機器效率的目標權(quán)重分別為0.8和0.2，針對每個不同的實例分別連續(xù)運行20次，并分別記錄其最優(yōu)值和平均值，測試結(jié)果見表5?；谶\行時間和最優(yōu)解，本文提出的IGA 算法明顯優(yōu)于PSO、SA 算法，雖然與GA相比，運行時間更長，但是獲得的最優(yōu)解比GA 更好，可以證明改進的遺傳算法在解決實例問題中能找到更好的結(jié)果，具有更好的優(yōu)化能力。

上述4種算法求解兩組問題實例的最優(yōu)解對比和最優(yōu)解變化趨勢箱線圖如圖7和圖8所示，從圖7中可以看出，在求解柔性作業(yè)車間調(diào)度問題實例時，與其他3種算法相比，本文提出的改進遺傳算法明顯降低了適應(yīng)度值，克服了遺傳算法的早熟收斂，并加快了遺傳算法的收斂速度；從圖8中可以看出，絕大多數(shù)最優(yōu)解集中在中位值和平均值下方，證明本文改進算法有一定的優(yōu)越性且提高了解的穩(wěn)定性。

表5 不同算法測試結(jié)果對比

3.4 權(quán)重系數(shù)分析

ω為目標函數(shù)的權(quán)重系數(shù)，權(quán)重的分配可根據(jù)決策者的要求進行設(shè)置。在更加關(guān)注設(shè)備使用的情況下，即機器效率，則設(shè)計ω1>ω2；在更多關(guān)注車間效率的情況下，即最大完工時間，則設(shè)計ω1<ω2；當兩者同等考慮時，則設(shè)計ω1=ω2。

以12×10案例為例，設(shè)置不同權(quán)重系數(shù)取值，用本文改進遺傳算法求解模型中機器效率和完工時間目標，實驗結(jié)果如表6所示，同時給出不同權(quán)重系數(shù)下目標值的分布情況如圖9所示。可以看出，調(diào)度過程中降低機器效率的同時會相應(yīng)增大完工時間，說明目標權(quán)重取值大小會影響車間調(diào)度效率，決策者可以通過對目標的重視程度調(diào)整ω取值從而獲得最優(yōu)調(diào)度結(jié)果。

4 結(jié)語

本文在傳統(tǒng)FJSP模型上，綜合考慮了加工時間和運輸時間等影響因素，增加了工件的到達時刻、交貨期約束及機器利用率約束，建立了以最大化機器效率和最小化完工時間為目標的FJSP模型。針對該模型，設(shè)計了一種改進遺傳算法對其進行求解。算法中采用了混合初始化、復(fù)合選擇和局部種群擴張等策略，提升遺傳算法求解此類FJSP問題能力，避免陷入局部最優(yōu)。實例測試結(jié)果也驗證了模型和算法的有效性。在下一步研究工作中，將重點研究考慮加工和運輸中隨機因素對柔性車間調(diào)度問題目標的影響及應(yīng)用多目標優(yōu)化方法的求解設(shè)計。