混合差分進(jìn)化算法求解柔性作業(yè)車間調(diào)度問題①

寧桂英, 曹敦虔

(1.柳州工學(xué)院數(shù)理教學(xué)部,廣西 柳州 545616;2.廣西民族大學(xué)理學(xué)院,廣西 南寧 530006)

0 引 言

柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem,FJSP)是由Brucker[1]在1990年首次提出的，該問題是傳統(tǒng)作業(yè)車間調(diào)度問題(Job-shop Scheduling Problem,FSP)的延伸和拓展。與傳統(tǒng)作業(yè)車間調(diào)度問題不同的是，在柔性作業(yè)車間調(diào)度問題中，每個(gè)工件有多道工序，每道工序可以選擇加工的機(jī)床有多臺(tái)，不同機(jī)床加工工序所需要的時(shí)間不同，所以柔性作業(yè)車間調(diào)度問題可以看成是多工件多工序排列在多機(jī)器上加工的高維規(guī)劃問題，是一種復(fù)雜的NP-hard問題[2]。該問題更符合企業(yè)生產(chǎn)中的實(shí)際問題調(diào)度的需要，因此，對(duì)該問題的研究具有重要的理論意義和應(yīng)用價(jià)值。FJSP問題自提出以來，一直是國內(nèi)外學(xué)者們所關(guān)注的熱點(diǎn)問題，迄今為止，對(duì)該問題已有大量的研究，在眾多的研究中，經(jīng)典的具有代表性的算法有分支界定算法，但該方法的復(fù)雜度會(huì)隨著問題規(guī)模的增大而成指數(shù)級(jí)增長，因此不能滿足實(shí)際問題的需要。近年來，隨著智能算法的興起，越來越多的學(xué)者開始關(guān)注用智能算法解決此類問題，并取得了一定的成果，如張超勇等提出了柔性作業(yè)車間調(diào)度問題的兩級(jí)遺傳算法[3]；戴月明等提出了骨干雙粒子群算法求解柔性作業(yè)車間調(diào)度問題[4]；呂聰?shù)忍岢鋈嵝攒囬g調(diào)度問題的協(xié)作混合帝國算法[5]；李帆等提出改進(jìn)蝙蝠算法柔性作業(yè)車間調(diào)度問題研究[6]；王芳等提出求解柔性流水車間調(diào)度問題的高效分布估算算法[7]。在以上的研究中可以發(fā)現(xiàn)，學(xué)者們開始將用于研究連續(xù)性問題的智能算法設(shè)計(jì)為研究離散型的調(diào)度問題，主要考慮對(duì)算法的改進(jìn)和與其他算法的混合以提高算法的局部搜索能力，防止算法限于局部極優(yōu)。

針對(duì)柔性車間調(diào)度問題的特點(diǎn)，提出了混合差分進(jìn)化算法(Hybrid Differential Evolution Algorithm，簡(jiǎn)稱HDEA)求解柔性作業(yè)車間調(diào)度問題。首先對(duì)差分進(jìn)化算法進(jìn)行特殊的編碼和解碼，以適合求解離散型問題；然后在變異的過程中，采用雙向變異策略，利用概率值，將遺傳算法的變異和差分進(jìn)化算法的變異有機(jī)結(jié)合，增強(qiáng)了種群的多樣性，防止限于局部極值，利用差分進(jìn)化算法的變異策略，將全局搜索能力和局部搜索能力進(jìn)行有效平衡，提高了收斂速度和精度，同時(shí)根據(jù)問題的特點(diǎn)，采用遺傳算法的改進(jìn)交叉方式，即采用隨機(jī)變位交叉的方式，在保證生成的新個(gè)體是有效解的同時(shí)也增加了種群的多樣性。對(duì)14個(gè)經(jīng)典測(cè)試算例和2個(gè)實(shí)際案例進(jìn)行了仿真，仿真結(jié)果表明，提出的算法在求解柔性車間調(diào)度問題時(shí)具有良好的性能和較好的計(jì)算精度和收斂速度。

1 柔性作業(yè)車間調(diào)度問題模型

1.1 符號(hào)定義

為描述問題的方便，對(duì)使用的符號(hào)含義作如下說明：

M為可供加工的機(jī)器總數(shù)目；N為待加工的工件總數(shù)目；pi為工件i的工序數(shù)；Oij為工件i中的第j道工序；Tijk為第i個(gè)工件的第j道工序在機(jī)器k上加工時(shí)間；Sijk為第i個(gè)工件的第j道工序在機(jī)器k上開始加工時(shí)間；Cijk為第i個(gè)工件的第j道工序在機(jī)器k上加工結(jié)束時(shí)間；Ci為每個(gè)工件的完工時(shí)間；

1.2 柔性作業(yè)車間調(diào)度問題描述：

所研究的FJSP問題描述為：

N個(gè)不同的工件在M臺(tái)機(jī)器上加工，每個(gè)工件有pi道工序，每道工序可選擇在不同的機(jī)器上加工，同一道工序在不同的機(jī)器上加工對(duì)應(yīng)時(shí)間可以不同，該問題研究的目的是尋找一種合適的調(diào)度方案，使最大完工時(shí)間(makespan)達(dá)到最小，即為每個(gè)工件的每道工序選擇可加工的機(jī)器，同時(shí)為每臺(tái)機(jī)器合理安排加工順序。

對(duì)以上問題基于以下假設(shè)建立數(shù)學(xué)模型：

(1)初始時(shí)刻所有待加工工件都可被加工，所有機(jī)器均可用；

(2)不同工件之間沒有加工順序約束，同一工件中有工序順序約束；

(3)一道工序只能在可加工的機(jī)器中選擇一臺(tái)機(jī)器加工，且只能被加工一次；

(4)一臺(tái)機(jī)器在同一時(shí)刻只能加工一道工序；

(5)不考慮工序加工過程中被中斷情況，不考慮在加工以外的其他耗時(shí)。

基于以上假設(shè)，建立的數(shù)學(xué)模型為：

(1)

(2)

Ci=Ci,pi

(3)

Si,(j+1)≥Ci,j

(4)

(5)

Sijk≥Crlk

(6)

其中，式(1)為目標(biāo)函數(shù)，表示使所有工件完工時(shí)間的最大值達(dá)到最?。皇?2)表示工件的最后完工時(shí)間是該工件的開始加工時(shí)間與實(shí)際加工時(shí)間之和；式(3)表示工件的最大完工時(shí)間是該工件最后一道工序的完成時(shí)間；式(4)表示同一工件的工序有順序要求；式(5)表示一道工序只能在一臺(tái)機(jī)器加工，且只能被加工一次；式(6)表示一臺(tái)機(jī)器在同一時(shí)刻只能加工一道工序，其中Crlk表示在機(jī)器k上前一工作的完工時(shí)間。

2 差分進(jìn)化混合遺傳算法

差分進(jìn)化算法采用實(shí)數(shù)編碼，操作簡(jiǎn)單，魯棒性強(qiáng)，比現(xiàn)存的許多智能算法在收斂速度方面更具競(jìng)爭(zhēng)力，且已被證明具有很好的全局搜索能力。遺傳算法作為一種成熟的智能算法，目前在許多方面已得到廣泛應(yīng)用，而且已取得很好的效果，但在收斂速度上遺傳算法不具優(yōu)勢(shì)。在遺傳算法中，變異算子是遺傳算法的主要操作，能增加算法局部搜索能力和種群多樣性，因此考慮將遺傳算法的變異操作引入差分進(jìn)化算法中，結(jié)合這兩種算法的優(yōu)勢(shì)，以解決柔性車間調(diào)度問題。

2.1 雙向變異策略

對(duì)基本差分進(jìn)化算法的變異策略，結(jié)合DE/rand/1/bin變異方式和DE/best/1/bin變異方式的特點(diǎn)，提出一種新的變異方式，變異公式為：

vij(t+1)=λxij(t)+(1-λ)xbest,j(t)+

F(xp1,j(t)-xp2,j(t))

(7)

采用這種變異策略，第一：能保證在進(jìn)化過程中λ由1逐漸線性變化到0，當(dāng)λ=1時(shí)，上式變成DE/rand/1/bin，此時(shí)算法具有良好的全局搜索能力；當(dāng)λ=0時(shí)，上式變成DE/best/1/bin，此時(shí)算法具有良好的局部搜索能力；第二：標(biāo)準(zhǔn)差分進(jìn)化算法的變異算子選取[0,1]之間的具體數(shù)值，而變異因子F的設(shè)置，在進(jìn)化前期具有較大的變異因子，增加種群多樣性，隨著進(jìn)化代數(shù)的增加，在進(jìn)化后期，保留最好解的條件下進(jìn)行局部搜索，這種自適應(yīng)的設(shè)置大大提高收斂速度和精度。

在提出的算法中，采用雙向變異策略，隨機(jī)確定選擇何種變異：首先隨機(jī)生成一個(gè)隨機(jī)數(shù)，當(dāng)該隨機(jī)數(shù)大于變異概率Pm時(shí)，采用(7)式的差分進(jìn)化變異，否則，采用遺傳算法的隨機(jī)交換兩個(gè)基因位的變異。

2.2 交叉方式的改進(jìn)

針對(duì)離散型調(diào)度問題的特點(diǎn)，借鑒遺傳算法交叉的理念，用新的交叉方式，將個(gè)體采用隨機(jī)位交叉的交叉方式，此時(shí)對(duì)變異后的新群體分成兩組進(jìn)行兩兩配對(duì)，對(duì)每一對(duì)個(gè)體A和B，隨機(jī)選擇一個(gè)交叉位r(1≤r≤M), 將兩個(gè)個(gè)體的前r個(gè)基因交換。交換過程為了保證個(gè)體的有效性，采用下面方法進(jìn)行：比如要交換A(j)和B(j)，則在A中尋找B(j)在A中的位置k，將A(j)和A(k)交換，這實(shí)際上是個(gè)體內(nèi)部基因位交換，即工件各工序之間的一個(gè)重新排列，保證了個(gè)體的有效性。例如：以3工件9工序?yàn)槔珹和B為交叉前的編碼個(gè)體，若隨機(jī)產(chǎn)生的r=3，則交換A和B的前三個(gè)元素，因?yàn)锽的第一個(gè)元素是3，對(duì)應(yīng)著A中的第一個(gè)3的位置，所以實(shí)際交換的是A的第一個(gè)和第三個(gè)元素，同樣的方法交換剩余兩個(gè)元素，交換后得到新的個(gè)體A1如下圖所示：

可以看出，對(duì)編碼A實(shí)施交叉，實(shí)際上是A內(nèi)部個(gè)體位之間的交換，保證了生成個(gè)體的有效性。對(duì)B也實(shí)施同樣的交叉，交換后得到新的個(gè)體B1如上圖所示。

2.3 編碼和解碼

根據(jù)求解FJSP問題的需要，設(shè)置了特殊的編碼和解碼方式。首先對(duì)FJSP的編碼分為三個(gè)部分：工序編碼向量，機(jī)器編碼向量和時(shí)間編碼向量。其中工序的編碼向量為所有工件工序的總長度之和，由于每道工序所能選擇的機(jī)器和每臺(tái)機(jī)器對(duì)應(yīng)加工的時(shí)間是已知的，所以一旦工序編碼確定，根據(jù)編碼去選擇可加工的機(jī)器編碼，此時(shí)對(duì)應(yīng)的時(shí)間編碼就確定了。在進(jìn)化過程中，只有工序編碼參入變異、交叉操作，機(jī)器編碼和時(shí)間編碼不參入進(jìn)化操作，而是采用貪婪的搜索方式，根據(jù)工序編碼尋找對(duì)應(yīng)的每個(gè)工序可使用的機(jī)器編號(hào)，而且在選擇機(jī)器時(shí)，總是在可選擇機(jī)器中選擇加工該工序結(jié)束時(shí)刻最早的，如果有多臺(tái)可選擇機(jī)器同時(shí)結(jié)束加工時(shí)間，則選擇加工時(shí)間最少的機(jī)器進(jìn)行加工，這樣減少解碼時(shí)間，提高了效率?，F(xiàn)以3工件3機(jī)器為例給出具體的編碼和解碼方法，每個(gè)工件的工序數(shù)，加工時(shí)間和可加工機(jī)器如下表1：

表1 3工件3機(jī)器對(duì)應(yīng)加工時(shí)間

上表中3工件總共有7道工序。

對(duì)應(yīng)工序編碼方式為：

1112233

當(dāng)工序?qū)?yīng)編碼選擇(7)式進(jìn)行變異操作后，生成新的個(gè)體為

0.150.961.3720.481.671.85

解碼方法：

將新生成的個(gè)體編碼進(jìn)行升序排列，記錄排序后的各分量在原來個(gè)體中的位置，再將變異前的個(gè)體相應(yīng)位置上的分量放在排序后的位置上，升序后的個(gè)體和對(duì)應(yīng)位置如下表：

0.150.480.961.371.671.8521523674

解碼后的個(gè)體為：

1211332

這種解碼方式保證變異操作之后個(gè)體的有效性。

3 差分進(jìn)化混合遺傳算法求解柔性車間調(diào)度問題步驟

step1: 設(shè)置種群規(guī)模M，最大進(jìn)化代數(shù)T,變異概率Pm，選擇式(1)為適應(yīng)度函數(shù)，隨機(jī)生成工序初始編碼；

step2: 按照2.1雙向變異策略進(jìn)行變異操作，對(duì)依概率選擇了(7)式變異后的個(gè)體，需要按照2. 3進(jìn)行解碼，解碼后與參入遺傳算法的隨機(jī)交換兩個(gè)基因位變異后的個(gè)體一起構(gòu)成新的種群；

step3: 將step2中新的個(gè)體按照2.2進(jìn)行交叉操作；

step4: 選擇：比較交叉后的新個(gè)體和原來舊個(gè)體的適應(yīng)度值，選擇適應(yīng)度值較優(yōu)的進(jìn)入下一代；

step5: 判斷是否達(dá)到最大進(jìn)化代數(shù)，若是，則進(jìn)化終止，輸出最優(yōu)解，否則，轉(zhuǎn)到step2。

4 實(shí)例仿真及結(jié)果分析

為了測(cè)試算法在柔性作業(yè)車間調(diào)度問題求解中的性能，首先選取 Kacem問題[9]提出的4個(gè)基準(zhǔn)測(cè)試算例，這些算例通常被用來測(cè)試算法的性能。規(guī)模分別為4×6，8×8，10×10和15×10，其中4×6和8×8是部分柔性問題，4×6有12道工序，8×8有27道工序， 10×10和15×10是全柔性問題，10×10有30道工序，15×10有56道工序。設(shè)置種群規(guī)模為50，最大進(jìn)化代數(shù)50代，通過實(shí)驗(yàn)測(cè)試觀察：變異概率Pm∈[0.1,0.3]之間的隨機(jī)數(shù)時(shí)，算法運(yùn)行最佳。與比較的文獻(xiàn)一致，每個(gè)算例獨(dú)立運(yùn)行10次，表2給出了10次中算法得到的最優(yōu)解，并與文獻(xiàn)算法所得結(jié)果進(jìn)行了比較。

表2 Kacem問題計(jì)算結(jié)果與文獻(xiàn)結(jié)果的比較

從表2可以看出，對(duì)被測(cè)試的四個(gè)問題，前三個(gè)算例本文算法都能很快找到最優(yōu)解，文獻(xiàn)[10]，[11]最差，對(duì)于較大規(guī)模的算例四，算法找到結(jié)果僅次于文獻(xiàn)[5]，但收斂速度勝于文獻(xiàn)[5]，文獻(xiàn)[5]進(jìn)化300代，由于文獻(xiàn)[5]未給出更大規(guī)模的算例結(jié)論，所以也無法再與該算法比較。文獻(xiàn)[13]的HGWO算法是目前看來比較好的算法，除了4×6 問題文獻(xiàn)[13]沒給出結(jié)果外，其它兩個(gè)算例運(yùn)行結(jié)果與本文一樣，對(duì)于規(guī)模較大的問題四，進(jìn)化50代的結(jié)果較文獻(xiàn)[13]進(jìn)化800代的結(jié)果優(yōu)，說明改進(jìn)后的算法不僅提高了解的質(zhì)量，還提高了收斂速度。從整體上來看，提出算法在求解中小規(guī)模柔性作業(yè)車間調(diào)度問題上具有一定的優(yōu)勢(shì)。圖1-圖4給出了算法得到的調(diào)度甘特圖。

圖1 4*6問題的調(diào)度甘特圖

圖2 8*8問題的調(diào)度甘特圖

圖3 10*10問題的調(diào)度甘特圖

圖4 15*10問題的調(diào)度甘特圖

為了進(jìn)一步測(cè)試算法的性能，下面選取了經(jīng)典的Brandimarte問題[14]測(cè)試算例中的MK01-MK10的10個(gè)測(cè)試數(shù)據(jù)，這10個(gè)算例有全柔性的，也有部分柔性的，現(xiàn)將每個(gè)算例獨(dú)立運(yùn)行20次，表3給出了算法在20次中找到的最好解，并與遺傳算法GA，文獻(xiàn)[12]的混合算法，文獻(xiàn)[13]的HGWO算法，文獻(xiàn)[17]的混合化學(xué)反應(yīng)算法，文獻(xiàn)[11]的啟發(fā)式算法及文獻(xiàn)[14]的算法進(jìn)行了比較，并給出了這10個(gè)算例的上、下界[LB，UB]，UB參看文獻(xiàn)[14]。

表3 Brandimarte問題算例計(jì)算結(jié)果比較

在表3中：首先，從解的有效性上看，對(duì)10個(gè)算例，算法找到的最優(yōu)解都在[LB,UB]內(nèi)，說明解是有效的；其次，從解的精度上分析，MK06，MK10這兩個(gè)算例在所有算法中看起來都很難找到理想的解，目前文獻(xiàn)[17]的算法在求這兩個(gè)的解上占優(yōu)勢(shì)，與理想最優(yōu)解偏差分別為24和32，而算法除了在這兩個(gè)解上略遜于文獻(xiàn)[17]和文獻(xiàn)[12]外，其余解都優(yōu)于所有比較的文獻(xiàn)解，說明算法求解精度高，魯棒性強(qiáng)；對(duì)于所比較的算法都能找到最優(yōu)解的MK03和MK08，在進(jìn)化代數(shù)較少的條件下就找到了最優(yōu)解，說明算法收斂速度快。另外，對(duì)于普遍較難優(yōu)化的MK01，MK02，MK04，MK07，MK09，本文算法都給出了全新的解，是迄今為止找到的最好解，而且MK01， MK04，MK07都找到了文獻(xiàn)[14]給出的理論最優(yōu)解，這進(jìn)一步說明了算法的有效性和優(yōu)越性。

為了進(jìn)一步測(cè)試提出算法在解決實(shí)際問題中的性能，選取了實(shí)際生產(chǎn)中的2個(gè)典型案例模型進(jìn)行計(jì)算，其中案例2是一個(gè)規(guī)模較大的案例，數(shù)據(jù)也較大。

案例1：假設(shè)某汽車發(fā)動(dòng)機(jī)廠要對(duì)金進(jìn)行加工，在加工過程中需要加工12個(gè)工件，每個(gè)工件有三道工序，分別為車、刨和磨，共36道工序，該車間有車床3臺(tái)、刨床2臺(tái)，磨床4臺(tái)，不同機(jī)床加工時(shí)間參考文獻(xiàn)[15]。

案例2：選取具有較大規(guī)模的鋼鐵生產(chǎn)的過程，有12個(gè)工件，每個(gè)工件有四道工序：煉鋼—精煉—連鑄—軋制，共要完成48道工序，現(xiàn)有3臺(tái)煉鋼爐、3臺(tái)精煉爐、2臺(tái)鑄機(jī)和2臺(tái)軋機(jī)，各機(jī)器的加工時(shí)間參考文獻(xiàn)[15]。

對(duì)這兩個(gè)實(shí)際應(yīng)用案例，參數(shù)設(shè)置與前面設(shè)置相同，每個(gè)案例與所比較文獻(xiàn)一樣，獨(dú)立運(yùn)行10次。表4給出了算法運(yùn)行10次得到的最好結(jié)果及平均值，并與文獻(xiàn)中相應(yīng)的結(jié)果進(jìn)行了比較，圖5-圖6分別給出了案例1調(diào)度甘特圖和案例2的進(jìn)化曲線。

表4 實(shí)例1--實(shí)例2的計(jì)算結(jié)果的比較

圖5 案例1的甘特圖

圖6 案例2的進(jìn)化曲線圖

從表4可以看出：對(duì)于解決所提的兩個(gè)實(shí)際問題，從解的質(zhì)量上分析，算法能找到問題的最優(yōu)解，文獻(xiàn)[15]的GA算法對(duì)兩個(gè)問題都沒找到最優(yōu)解，文獻(xiàn)[16]對(duì)案例1沒能找到最優(yōu)解；從穩(wěn)定性上分析，在運(yùn)行10次的平均解上，算法略勝于文獻(xiàn)[16] ，對(duì)案例2，文獻(xiàn)[15]只給出運(yùn)行一次的解；從收斂速度上分析，文獻(xiàn)[15]和[16]找到這兩個(gè)最優(yōu)解的進(jìn)化代數(shù)均為10000次代，而算法為50代。因此，在解決實(shí)際問題中，所提算法同樣具有很好的穩(wěn)定性和魯棒性，能夠在較少的時(shí)間內(nèi)快速找到問題的最優(yōu)解。

5 結(jié) 語

針對(duì)柔性作業(yè)車間調(diào)度問題的求解特點(diǎn)，從特殊的編碼、解碼，從變異策略、交叉策略等方面對(duì)基本差分進(jìn)化算法進(jìn)行了改進(jìn)，提出了求解柔性作業(yè)車間調(diào)度問題的差分進(jìn)化混合遺傳算法，用改進(jìn)后的算法對(duì)14個(gè)經(jīng)典測(cè)試算例和2個(gè)實(shí)際應(yīng)用案例進(jìn)行了仿真計(jì)算，仿真結(jié)果表明，提出算法具有很好的穩(wěn)定性和魯棒性，在計(jì)算性能上也有大大提高，對(duì)部分較難優(yōu)化的經(jīng)典測(cè)試算例給出了新的最優(yōu)解，說明算法對(duì)求解柔性作業(yè)車間調(diào)度問題具有一定的指導(dǎo)作用，后續(xù)工作是進(jìn)一步提高算法的性能以解決更大規(guī)模及多目標(biāo)生產(chǎn)調(diào)度問題。