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

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

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

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

1 考慮工件運(yùn)輸時(shí)間和機(jī)器效率的FJSP問題及模型描述

1.1 問題描述

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

1.2 模型假設(shè)

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

(1)所有機(jī)器在加工前準(zhǔn)備就緒，所有工件嚴(yán)格按照到達(dá)時(shí)刻加工。

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

(3)任意機(jī)器同一時(shí)刻只能加工一個(gè)工件，任意工件同一時(shí)刻只能被一臺(tái)機(jī)器加工。

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

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

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

(7)不考慮機(jī)器故障和運(yùn)輸資源。

1.3 符號(hào)和變量定義

模型符號(hào)的定義如下：

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

Mk：表示第k臺(tái)機(jī)器(k∈[1,m])。

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

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

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

Ti,l,k：表示工件Ji在兩個(gè)不同機(jī)器Ml和Mk之間的運(yùn)輸時(shí)間(l∈[1,m])。

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

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

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

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

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

每個(gè)工件的到達(dá)時(shí)刻和交貨期是給定的：

Ri：表示工件Ji的到達(dá)時(shí)刻。

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

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

決策變量的解釋如下：

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

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

Z(Mk)：如果當(dāng)前機(jī)器正在使用，則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)

當(dāng)j=h時(shí)，Ei,j,k≤Di

(12)

(13)

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

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

(1)最大化機(jī)器效率

(14)

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

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

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

(15)

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

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

(1)分段式編碼策略

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

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

表2 實(shí)例運(yùn)輸時(shí)間

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

(2)插入式解碼策略

①機(jī)器選擇解碼

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

②工序排序解碼

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

2.2 遺傳操作策略改進(jìn)

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

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

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

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

F=ω1f1+ω2f2

(16)

式中：ω1、ω2取值在[0,1]且ω1+ω2=1。根據(jù)實(shí)際決策偏好(時(shí)間和效率)可調(diào)整ω1、ω2的大小，以滿足不同決策者對(duì)兩個(gè)子目標(biāo)的要求。基于上述方式進(jìn)行染色體適應(yīng)度計(jì)算，作為遺傳選擇操作基礎(chǔ)。

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

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

①交叉操作設(shè)計(jì)

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

②變異操作設(shè)計(jì)

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

(4)局部種群擴(kuò)張策略

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

2.3 算法流程

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

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

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

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

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

步驟5 對(duì)工序排序部分進(jìn)行單點(diǎn)變異，機(jī)器選擇部分按照一定概率選擇加工時(shí)間和運(yùn)輸時(shí)間短的機(jī)器；

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

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

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

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

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

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

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

表4 實(shí)例運(yùn)輸時(shí)間

3.2 案例求解

以12 × 10 規(guī)模問題為例 。 求解中假設(shè)取時(shí)間和機(jī)器效率的目標(biāo)權(quán)重分別為 0.8 和 0.2 ，得到考慮運(yùn)輸時(shí)間的最優(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 ]，機(jī)器編碼為 [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 在縱坐標(biāo)對(duì)應(yīng)值為4，表示第2個(gè)工件的第一道工序在機(jī)器4 上加工， 距離坐標(biāo)原點(diǎn)的這段時(shí)間對(duì)應(yīng)于工件2的到達(dá)時(shí)刻8,因此201的最早開始加工時(shí)間為8，再經(jīng)過10個(gè)單位的加 工時(shí)間，它的完工時(shí)間為18；工件2的第2道工序 202 在機(jī)器9上加工，機(jī)器4到機(jī)器9的運(yùn)輸時(shí)間為5，此時(shí)機(jī)器9上有前置工序1001和601，工序1001的最早開始加工時(shí)間為到達(dá)時(shí)刻15，再經(jīng)過7個(gè)單位的加工時(shí)間，其完工時(shí)間為22，工序601的到達(dá)時(shí)刻為19 ,其最早開始加工時(shí)間為 max (19,22 )=22,再經(jīng)過 11 個(gè)單位的加工時(shí)間，其完工時(shí)間為33，因此工序202的最早開始加工時(shí)間為 max( 33 ,18+5 )=33。同理，10 × 8 規(guī)模問題類似。

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

3.3 算法性能測試

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

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

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

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

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

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

4 結(jié)語

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