寧桂英, 曹敦虔

(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)度問題中，每個工件有多道工序，每道工序可以選擇加工的機(jī)床有多臺，不同機(jī)床加工工序所需要的時間不同，所以柔性作業(yè)車間調(diào)度問題可以看成是多工件多工序排列在多機(jī)器上加工的高維規(guī)劃問題，是一種復(fù)雜的NP-hard問題[2]。該問題更符合企業(yè)生產(chǎn)中的實(shí)際問題調(diào)度的需要，因此，對該問題的研究具有重要的理論意義和應(yīng)用價值。FJSP問題自提出以來，一直是國內(nèi)外學(xué)者們所關(guān)注的熱點(diǎn)問題，迄今為止，對該問題已有大量的研究，在眾多的研究中，經(jīng)典的具有代表性的算法有分支界定算法，但該方法的復(fù)雜度會隨著問題規(guī)模的增大而成指數(shù)級增長，因此不能滿足實(shí)際問題的需要。近年來，隨著智能算法的興起，越來越多的學(xué)者開始關(guān)注用智能算法解決此類問題，并取得了一定的成果，如張超勇等提出了柔性作業(yè)車間調(diào)度問題的兩級遺傳算法[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)度問題，主要考慮對算法的改進(jìn)和與其他算法的混合以提高算法的局部搜索能力，防止算法限于局部極優(yōu)。

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

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

1.1 符號定義

為描述問題的方便，對使用的符號含義作如下說明：

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

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

所研究的FJSP問題描述為：

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

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

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

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

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

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

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

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

(1)

(2)

Ci=Ci,pi

(3)

Si,(j+1)≥Ci,j

(4)

(5)

Sijk≥Crlk

(6)

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

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

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

2.1 雙向變異策略

對基本差分進(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時，上式變成DE/rand/1/bin，此時算法具有良好的全局搜索能力；當(dāng)λ=0時，上式變成DE/best/1/bin，此時算法具有良好的局部搜索能力；第二：標(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ī)生成一個隨機(jī)數(shù)，當(dāng)該隨機(jī)數(shù)大于變異概率Pm時，采用(7)式的差分進(jìn)化變異，否則，采用遺傳算法的隨機(jī)交換兩個基因位的變異。

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

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

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

2.3 編碼和解碼

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

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

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

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

1112233

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

0.150.961.3720.481.671.85

解碼方法：

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

0.150.480.961.371.671.8521523674

解碼后的個體為：

1211332

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

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

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

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

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

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

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

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

為了測試算法在柔性作業(yè)車間調(diào)度問題求解中的性能，首先選取 Kacem問題[9]提出的4個基準(zhǔn)測試算例，這些算例通常被用來測試算法的性能。規(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)測試觀察：變異概率Pm∈[0.1,0.3]之間的隨機(jī)數(shù)時，算法運(yùn)行最佳。與比較的文獻(xiàn)一致，每個算例獨(dú)立運(yùn)行10次，表2給出了10次中算法得到的最優(yōu)解，并與文獻(xiàn)算法所得結(jié)果進(jìn)行了比較。

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

從表2可以看出，對被測試的四個問題，前三個算例本文算法都能很快找到最優(yōu)解，文獻(xiàn)[10]，[11]最差，對于較大規(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é)果外，其它兩個算例運(yùn)行結(jié)果與本文一樣，對于規(guī)模較大的問題四，進(jìn)化50代的結(jié)果較文獻(xiàn)[13]進(jìn)化800代的結(jié)果優(yōu)，說明改進(jìn)后的算法不僅提高了解的質(zhì)量，還提高了收斂速度。從整體上來看，提出算法在求解中小規(guī)模柔性作業(yè)車間調(diào)度問題上具有一定的優(yōu)勢。圖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)一步測試算法的性能，下面選取了經(jīng)典的Brandimarte問題[14]測試算例中的MK01-MK10的10個測試數(shù)據(jù)，這10個算例有全柔性的，也有部分柔性的，現(xiàn)將每個算例獨(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個算例的上、下界[LB，UB]，UB參看文獻(xiàn)[14]。

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

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

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

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

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

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

5 結(jié) 語

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