作業(yè)車間調(diào)度問題的雜草優(yōu)化算法求解

黃　霞　葉春明　包曉曉

1(上海理工大學(xué)管理學(xué)院　上海 200093)2(江蘇科技大學(xué)　江蘇 張家港 215600)

?

作業(yè)車間調(diào)度問題的雜草優(yōu)化算法求解

黃霞1,2葉春明1包曉曉1

1(上海理工大學(xué)管理學(xué)院上海 200093)2(江蘇科技大學(xué)江蘇 張家港 215600)

摘要針對作業(yè)車間調(diào)度問題JSP(Job-shop scheduling problem)，提出一種入侵式雜草優(yōu)化算法。該算法中，子代以正態(tài)分布方式在父代個體周圍擴散，兼顧全局搜索和局部搜索，并根據(jù)迭代次數(shù)不同對二者強度進行調(diào)節(jié)。通過典型算例進行仿真試驗，并在反復(fù)實驗中對算法參數(shù)進行修正。測試結(jié)果表明雜草算法求解作業(yè)車間調(diào)度問題的可行性和有效性，優(yōu)于螢火蟲算法和基本粒子群算法，是解決生產(chǎn)調(diào)度問題的一種有效方法。

關(guān)鍵詞雜草優(yōu)化算法作業(yè)車間調(diào)度問題最大完工時間

0引言

作業(yè)車間調(diào)度問題JSP是許多生產(chǎn)調(diào)度問題的簡化模型，具有很多實際應(yīng)用背景。作為一類滿足任務(wù)配置和順序約束要求的資源分配問題，JSP已被證明是最困難的約束組合優(yōu)化問題和典型的NP-hard問題[1]。由于作業(yè)調(diào)度問題的復(fù)雜性，即使在規(guī)模較小時，當(dāng)前要獲得最優(yōu)解仍是非常困難。它的求解難度遠大于流水線調(diào)度問題，針對其算法的研究一直是學(xué)術(shù)界和工程界共同關(guān)注的重要課題。如何利用有限的資源，滿足被加工任務(wù)的各種約束，并確定工件在相關(guān)設(shè)備上的加工順序和時間，以保證所選擇的性能指標(biāo)最優(yōu)，即研究如何有效地求解JSP，有著非常重要的理論意義和實用價值。

用于作業(yè)車間調(diào)度問題的技術(shù)與方法主要分為兩類：一類是最優(yōu)化方法；一類是近似方法。用最優(yōu)化方法只能求解小規(guī)模的作業(yè)車間調(diào)度問題，而且速度很慢。對于大部分規(guī)模較大問題都不能用多項式算法求最優(yōu)解，只能使用近似方法求近似解[2]。其中仿生智能群優(yōu)化算法(如蟻群算法、粒子群算法、螢火蟲算法、布谷鳥算法、雜草算法等以及各種混合智能算法)作為一種有效的近似求解方法，能在較短時間內(nèi)可以獲得較高質(zhì)量的解，成為復(fù)雜優(yōu)化問題的有效求解途徑和國內(nèi)外研究熱點。

雜草算法IWO(invasiveweedoptimization)是由伊朗德黑蘭大學(xué)的Mehrabian等為解決數(shù)值優(yōu)化問題而首次提出[3]。雜草算法啟發(fā)于自然界雜草叢生現(xiàn)象，它是模擬雜草殖民擴張過程而形成的一種仿生智能群優(yōu)化算法。與經(jīng)典的優(yōu)化方法相比，IWO算法具有結(jié)構(gòu)簡單，魯棒性強，易于理解和編程等特點。IWO算法作為一種數(shù)值優(yōu)化算法，主要針對連續(xù)空間的浮點數(shù)問題而設(shè)計，適合求解具有連續(xù)變量的函數(shù)優(yōu)化問題。目前，IWO算法已經(jīng)成功應(yīng)用于DNA編碼順序計算問題[4]、壓電激勵器的優(yōu)化放置問題[5]、優(yōu)化組合問題[6],天線陣列設(shè)計問題[7]等多個領(lǐng)域。

雜草算法在生產(chǎn)調(diào)度中的應(yīng)用相對較少，在國內(nèi)外有關(guān)此方面的文獻目前只有少數(shù)幾篇。文獻[8]提出基于雜草搜索的方法解決中間buffers的流水車間調(diào)度問題，其目標(biāo)函數(shù)是最小化最大完工時間。文獻[9]將雜草算法應(yīng)用于流水線車間調(diào)度，求解置換流水車調(diào)度問題和無等待流水車間調(diào)度問題。目前還未見到采用IWO算法求解作業(yè)調(diào)度方面的研究。因此，本文嘗試運用IWO算法求解作業(yè)車間調(diào)度問題。首先從分析雜草算法的優(yōu)化機理著手，設(shè)計一種基于升序排列(ROV)的操作編碼，實現(xiàn)雜草連續(xù)位置到所有工序排列的轉(zhuǎn)換。在此基礎(chǔ)上應(yīng)用雜草優(yōu)化算法求解作業(yè)車間調(diào)度問題，經(jīng)過反復(fù)實驗和不斷修正，設(shè)置出性能較好的參數(shù)值，并將求得的結(jié)果與其他兩種算法相比較。算例測試結(jié)果證明IWO算法有較強的尋優(yōu)性能和良好的魯棒性。

1作業(yè)車間調(diào)度問題的數(shù)學(xué)描述

作業(yè)車間調(diào)度問題是具有特殊工藝特性和加工環(huán)境的最典型和最重要的調(diào)度問題。作業(yè)車間調(diào)度問題可描述為：n個工件在m臺機器上加工，第i個工件在第j臺機器上的操作時間Pij為已知，要求確定與工藝約束條件相容的各機器上所有工件的加工次序，使加工性能指標(biāo)達到最優(yōu)。除工藝約束外，通常還假定每一時刻每臺機器只能加工一個工件，且每個工件只能被一臺機器所加工，同時加工過程為不間斷，機器間緩沖區(qū)容量為無限，不考慮工件加工的優(yōu)先權(quán)。

關(guān)于JSP的求解往往要考慮生產(chǎn)調(diào)度實際期望達到的優(yōu)化指標(biāo)，問題的目標(biāo)函數(shù)是這些優(yōu)化指標(biāo)的抽象表示。通常JSP所考慮的優(yōu)化目標(biāo)有三種：任務(wù)的最大完工時間最短、任務(wù)總的拖期最短和任務(wù)的提前/拖期懲罰代價最小。本文所考慮的優(yōu)化目標(biāo)是任務(wù)的最大完工時間最短，即完成所有任務(wù)所需的時間最短，對該指標(biāo)的優(yōu)化有利于提高單位時間內(nèi)設(shè)備的利用率，從而提高生產(chǎn)的實際效率。常見的作業(yè)車間調(diào)度問題基本數(shù)學(xué)模型有三種：整數(shù)規(guī)劃模型、線性規(guī)劃模型和析取圖模型。本文采用Baker[10]給出的JSP整數(shù)規(guī)劃模型，下面是調(diào)度問題n/m/G/Cmax的一個整數(shù)規(guī)劃模型描述：

(1)

Subjectto:

cik-pik+M(1-aihk)≥cih

(2)

cjk-pjk+M(1-xijk)≥cik

(3)

cik≥0

(4)

(5)

(6)

上述公式中所涉及的符號含義如下：i=1,2,…,n；h,k=1,2,…,m；cik和pik分別為第i個工件在機器k上的完成時間和加工時間；M是一個足夠大的正數(shù)；aihk和xijk分別為指示系數(shù)和指示變量。式(1)表示目標(biāo)函數(shù)，即最小化最大完成時間Makespan；式(2)表示工藝約束條件決定的每個工件的各個操作的加工先后順序；式(3)表示加工各個工件的各機器的先后順序，同是也保證在同一時刻一個工件不會分配給兩臺機器，以及兩臺機器不會同時加工一個工件；式(4)表示完工時間變量約束條件；式(5)和式(6)分別表示指示系數(shù)和指示變量可能的取值大小。

2雜草算法的優(yōu)化機理

2.1雜草算法的基本原理

雜草專指那些生命力極其旺盛，具有入侵式的殖民化特點，可以生長于地球上的任何一塊地方的植物。即使有除草劑的出現(xiàn)，雜草仍以其旺盛的生命力和頑強的意志力遍布地球的每一個角落。雜草入侵的一般過程是適應(yīng)環(huán)境、乘機居留、占據(jù)地盤、結(jié)籽繁殖、扶養(yǎng)種群、隨機應(yīng)變、逐漸密集、適者生存、競爭消亡適應(yīng)性好的個體獲得更多的生存機會。雜草算法是一種基于模擬雜草入侵過程的數(shù)值優(yōu)化計算方法。

2.2雜草算法的數(shù)學(xué)描述與分析

在基本IWO中，雜草表示所求問題的可行解，種群是所有雜草的集合。進化過程中，雜草通過繁殖產(chǎn)生種子，種子通過空間擴散，生長成雜草，如此反復(fù)。當(dāng)種群中雜草數(shù)量達到預(yù)先設(shè)定的最大種群規(guī)模時，不是簡單的從父代中篩選優(yōu)秀個體進行繁殖，而是先讓所有個體都自由繁殖和擴散后，再將父代和子代一起按適應(yīng)度值排列并進行優(yōu)選。通過以適應(yīng)度為基準(zhǔn)的繁殖機制，雜草算法使其產(chǎn)生的解在不可行和可行之間不斷轉(zhuǎn)化。這種機制給予那些適應(yīng)度值差的個體繁殖機會，如果它們后代的適應(yīng)度值好，這些后代仍有機會生存下來，這樣能在最大限度上保留有用信息，也可以避免早熟和陷入局部最優(yōu)。

雜草繁殖種子的數(shù)目與雜草的適應(yīng)性成正比，通常適應(yīng)度高的雜草產(chǎn)生種子較多，而適應(yīng)度低的雜草產(chǎn)生種子較少。雜草產(chǎn)生種子的公式為：

(7)

其中，f為當(dāng)前雜草的適應(yīng)度值，fmax和fmin分別為當(dāng)前種群中所生長的雜草的最大和最小適應(yīng)度值；smax和smin分別表示一個雜草能產(chǎn)生種子的最大值和最小值。雜草產(chǎn)生的種子按平均值為0，標(biāo)準(zhǔn)差為σ的正態(tài)分布，擴散在父代雜草周圍。種子生長位置與父代雜草的距離稱為隨機步長D∈[-σ，σ]，具體σ的計算公式如下：

(8)

式中iter為當(dāng)前進化代數(shù)，itermax為最大進化代數(shù)，σ為當(dāng)前標(biāo)準(zhǔn)差，σinit和σfinal分別為標(biāo)準(zhǔn)差的最初值和最終值，n為非線性調(diào)和因子。

雜草算法中，子代是以正態(tài)分布方式在父代個體周圍擴散。在迭代初期σ較大，通過大的標(biāo)準(zhǔn)差值，使種子能以正態(tài)分布的方式擴散到距離父代雜草很遠的地方，此時種群勘探能力較強(r選擇)，對應(yīng)于雜草算法的全局探索。隨著迭代次數(shù)增加，當(dāng)?shù)M行到后期時，標(biāo)準(zhǔn)差σ逐漸變小，種子分布在距離父代雜草較近的地方，種子的擴散范圍縮小，原先的優(yōu)勢群體較容易得到興盛發(fā)展。此時開采能力較強(k選擇)，對應(yīng)于雜草算法的局部搜索。雜草算法兼顧全局搜索和局部搜索，并根據(jù)迭代次數(shù)不同對二者強度進行自適應(yīng)性調(diào)節(jié)。

IWO的主要步驟如下:

1) 雜草種群初始化，隨機初始化N顆雜草；

2) 雜草按式(7)產(chǎn)生相應(yīng)個數(shù)的種子；

3) 雜草的種子按式(8)以隨機步長進行空間擴散并生長為雜草，進入雜草種群；

4) 判斷種群是否達到預(yù)設(shè)的最大種群規(guī)模，如滿足則進行優(yōu)先排序，并選擇出適應(yīng)度好的最大種群規(guī)模數(shù)個體，否則直接轉(zhuǎn)到2)；

5) 判斷是否達到最大迭代次數(shù)，若滿足則輸出最優(yōu)解，并終止，否則轉(zhuǎn)到2)。

3雜草算法求解作業(yè)車間調(diào)度問題

3.1編碼方式

雜草優(yōu)化算法主要適用于求解連續(xù)空間域的優(yōu)化問題，而調(diào)度問題是離散空間的非數(shù)值優(yōu)化問題。因此，應(yīng)用雜草優(yōu)化算法求解調(diào)度問題需在連續(xù)空間的染色體與離散空間的調(diào)度解之間建立一種對應(yīng)關(guān)系。本算法采用一種基于工件升序排序ROV(rankedordervalue)的隨機鍵編碼方式[12]，用于實現(xiàn)從染色體連續(xù)位置矢量到工件排序的轉(zhuǎn)換。對于n個工件m個機器的作業(yè)車間調(diào)度問題，基于工序的編碼方法將每個染色體用n×m個代表工件基因組成，來表示一個工序排列，在這種工序排列中每個工件號均出現(xiàn)m次，可以隱式地保證工件的技術(shù)約束。

一條染色體位置矢量可以表示為Xi={xi,1,xi,2,…,xi,n×m}，則其對應(yīng)工序初始排列為1,…1,…,j,…,j,…,n,…,n,其中j(0

3.2算法流程

上述編碼規(guī)則中的染色體對應(yīng)為算法中的雜草個體。根據(jù)上述ROV編碼規(guī)則，雜草個體位置可以轉(zhuǎn)換為一個工序排列，每個工序排列的Makespan作為雜草個體的適應(yīng)度值。求解作業(yè)車間調(diào)度問題的雜草優(yōu)化算法流程如下：

1) 初始化算法基本參數(shù)：設(shè)置初始雜草個數(shù)、最大雜草個數(shù)、問題的維數(shù)、擴張區(qū)間大小、最大最小種子數(shù)、初始標(biāo)準(zhǔn)差和最終標(biāo)準(zhǔn)差，以及最大迭代次數(shù)。

2) 隨機產(chǎn)生初始化雜草種群，按照3.1節(jié)所述基于工序的編碼規(guī)則，將種群中每一顆雜草位置轉(zhuǎn)換為工序排列，計算對應(yīng)工序排列的Makespan，作為適應(yīng)度值。

3) 開始迭代，按式(7)對雜草種群的每一顆雜草，產(chǎn)生相應(yīng)數(shù)目的種子；雜草的種子按式(8)以隨機步長在一定范圍內(nèi)進行空間擴散并生長為新的雜草，對每一顆新雜草計算相應(yīng)工序排列的Makespan，作為其適應(yīng)度值，并將新雜草加入到雜草種群中。

4) 判斷雜草種群是否達到預(yù)設(shè)的最大種群規(guī)模，如滿足則按競爭性生存法則進行優(yōu)先排序，選擇出適應(yīng)度值排在前面的最大種群規(guī)模數(shù)個體，并保存當(dāng)前最優(yōu)適應(yīng)度值；否則直接轉(zhuǎn)到3)。

5) 判斷是否達到最大迭代次數(shù)，若滿足則輸出所有保存的適應(yīng)度值中的最優(yōu)解，并終止；否則轉(zhuǎn)到3)。

4仿真實驗

為了驗證IWO算法求解作業(yè)車間調(diào)度問題的有效性及其性能，選擇Taillard[13]提出的作業(yè)車間調(diào)度基準(zhǔn)測試數(shù)據(jù)來進行驗證。隨機選取LA類的11個基準(zhǔn)問題作為算例來進行仿真測試，并與基本粒子群算法BPSO[14](Basicparticleswarmoptimization)和螢火蟲算法FA[15](FireflyAlgorithm)的實驗結(jié)果進行比較驗證算法的有效性。測試環(huán)境：操作系統(tǒng)Win8，處理器3.20GHz，CPUIntel(R)Core(TM)i5，內(nèi)存4GB，采用MATLABR2010a實現(xiàn)算法編程。經(jīng)過反復(fù)實驗將雜草算法中參數(shù)設(shè)置如下性能較佳，初始雜草個數(shù)10，最大雜草個數(shù)45，初始標(biāo)準(zhǔn)差2，最終標(biāo)準(zhǔn)差0.001，最大種子個數(shù)20，最小種子個數(shù)1，非線性因子n=4。其他兩種算法參數(shù)設(shè)置分別參照文獻[14]和文獻[15]，基本粒子群算法中，粒子數(shù)n=30，學(xué)習(xí)因子c1=0.8，c2=1.2，慣性權(quán)重w=0.5；螢火蟲算法中，螢火蟲數(shù)n=30，光強吸收系數(shù)γ=1.0，最大吸引度β0=1.0，步長因子α=0.2。每一種算法都是迭代100次，各自獨立運行20次。測試結(jié)果如表1所示。

表1　三種算法優(yōu)化結(jié)果對比分析

表1中，C*為問題已知最優(yōu)值；Δmin為最小完工時間；Δmax為最大完工時間；Δavg為平均完工時間；Δstd為完工時間標(biāo)準(zhǔn)方差(其中Δavg、Δstd為四舍五入后所得結(jié)果)；加粗的數(shù)字代表最優(yōu)值。為比較各算法性能，本文對測試問題的上面4項指標(biāo)進行衡量。從測試數(shù)據(jù)可以看出，IWO算法的測試結(jié)果整體性能優(yōu)于BPSO和FA算法。表中顯示IWO算法有8個問題找到最優(yōu)值，BPSO算法有7個問題找到最優(yōu)值，F(xiàn)A算法僅有4個問題找到最優(yōu)值。在獨立運行20次中，IWO算法對LA01、LA05、LA06、LA10、LA11、LA12和LA14都能達到100%的尋優(yōu)率，其他兩種算法均未能達到100%尋優(yōu)率。而對于未能找到最優(yōu)值的LA03、LA08、LA17和LA20，IWO的4項指標(biāo)均比BPSO和FA要小，反映出IWO算法具有良好的魯棒性。

為了對比顯示IWO算法求解作業(yè)車間調(diào)度問題的尋優(yōu)效果，選取LA06問題對于這三種算法BPSO、FA和IWO各獨立運行30次的最優(yōu)結(jié)果進行演示。算法參數(shù)設(shè)置如前所述，最優(yōu)結(jié)果顯示如圖1所示。每種算法均獨立運行30次中，就尋優(yōu)能力而言，IWO算法30次全部擊中已知最優(yōu)值，BPSO算法有20次擊中最優(yōu)值，F(xiàn)A算法只有2次擊中最優(yōu)值。從FA和BPSO運行結(jié)果的波動曲線來看，F(xiàn)A的波動曲線起伏最大，BPSO的起伏較平穩(wěn)，但表現(xiàn)出一定的間斷性。從圖1對比尋優(yōu)結(jié)果來看，無論從尋優(yōu)次數(shù)還是尋優(yōu)率來看，IWO算法均表現(xiàn)出較卓越的尋優(yōu)性能。

為了進一步驗證IWO算法的收斂性能，分別基于LA10和LA14問題，IWO算法獨立運行10次，每次迭代100次的尋優(yōu)曲線如圖2和圖3所示。從圖2和圖3的尋優(yōu)曲線顯示，對于LA10問題和LA14問題，IWO獨立運行10次中，每次運行在迭代30次內(nèi)均一致收斂到最優(yōu)解，反映出IWO具有較強的收斂性能，在解空間能以較強的探索能力和較快的速度收斂到最優(yōu)值。

圖2　LA10問題運行10次尋優(yōu)曲線圖

圖3　LA14問題運行10次尋優(yōu)曲線圖

5結(jié)語

本文采用一種新型的仿生智能群優(yōu)化算法——雜草算法求解最小化最大完工時間的作業(yè)車間調(diào)度問題。仿真實驗表明：雜草算法具有收斂速度快、魯棒性強等優(yōu)點。雖然對于較大規(guī)模的Job-shop生產(chǎn)調(diào)度問題，雜草算法沒能搜索到已知最優(yōu)值，但是相比其他智能算法，更接近最優(yōu)值。鑒于雜草算法在解決生產(chǎn)調(diào)度問題中表現(xiàn)出的良好性能，本文意在拋磚引玉，期待雜草算法能在生產(chǎn)調(diào)度問題上有著更廣泛的應(yīng)用前景。下一步研究工作將著重于對IWO算法進行改進，并嘗試將改進算法用于研究具有不同約束條件的車間調(diào)度問題。

參考文獻

[1]GareyMR,JohnsonDS,SethiRavi.Thecomplexityofflowshopandjobshopscheduling[J].MathematicsofOperationsResearch,1976,1(2):117-129.

[2] 王永明,尹紅麗,秦開大.作業(yè)車間調(diào)度理論及其優(yōu)化方法研究[M].科學(xué)出版社,2013.

[3]MehrabianAR,LucasC.Anovelnumericaloptimizationalgorithminspiredfromweedcolonization[J].EcologicalInformatics,2006,1(4):355-366.

[4]ZhangX,WangY,CuiG,etal.ApplicationofanovelIWOtothedesignofencodingsequencesforDNAcomputiong[J].ComputersandMathematicswithApplications,2009,57(11/12):2001-2008.

[5]MehrabianAR,Yousefi-KomaA.Anoveltechniqueforoptimalplacementofpiezoelectricactuatorsonsmartstructures[J].JournaloftheFranklinInstitute,2011,348(1):12-23.

[6]SaravananB,VasudevanER,KothariDP.ASolutiontoUnitCommitmentProblemusingInvasiveWeedOptimizationAlgorithm[C]//InternationalConferenceonPower,EnergyandControl(ICPEC),2013:386-393.

[7]YanYingBai,ShaoqiuXiao,ChangrongLiu,etal.AHybridIWO/PSOAlgorithmforPatternSynthesisofConformalPhasedArrays[J].IEEETransactionsonAntennasandPropagation,2012,61(4):2328-2332.

[8]HongyanSang,QuankePan.Aneffectiveinvasiveweedoptimizationalgorithmfortheflowshopschedulingwithintermediatebuffers[C]//ChinesecontrolandDecisionconference,2013,25:861-864.

[9] 陳歡,周永權(quán).入侵雜草優(yōu)化算法的改進分析及應(yīng)用研究[D].廣西,廣西民族大學(xué),2013.

[10]BakerK.InroductiontoSequencingandScheduling[M].NewYork:JohnWiley&Sons,1974.

[11]KunduD,SureshK,GhoshS,etal.Multi-objectiveoptimizationwithartificialweedcolonies[J].InformationSciences,2010,181(12):2441-2454.

[12]BeanJC.Geneticalgorithmandrandomkeysforsequencingandoptimization[J].ORSAJournalofComputing,1994,6(2):154-159.

[13]TaillardE.Benchmarksforbasicschedulingproblems[J].EuropeanJournalofOperationalResearch,1993,64(2):278-285.

[14] 吳啟迪,汪鐳.智能微粒群算法研究及應(yīng)用[M].南京:江蘇教育出版社,2005.

[15] 劉長平,葉春明.一種新穎的仿生群智能優(yōu)化算法:螢火蟲算法[J].計算機應(yīng)用研究,2011,28(9):3295-3297.

INVASIVE WEED OPTIMISATION ALGORITHM FOR JOB SHOP SCHEDULING

Huang Xia1,2Ye Chunming1Bao Xiaoxiao1

1(School of Business,University of Shanghai for Science and Technology,Shanghai 200093,China)2(Jiangsu University of Science and Technology,Zhangjiagang 215600,Jiangsu,China)

AbstractThis paper introduces an invasive weed optimisation algorithm aimed at solving job shop scheduling problem. In this algorithm, the offspring diffuses around the parent individuals in the way of normal distribution, combining the global search and local search and adjusting different strength of both according to the number of iterations. Simulation tests are carried out through typical examples, and in repeated experiments the parameters of the algorithm are corrected. Test results demonstrate the feasibility and effectiveness of IWO in solving job shop scheduling problem, it is superior to the firefly algorithm and basic particle swarm optimisation, and is an effective approach for solving production scheduling problem.

KeywordsInvasive weed optimisation (IWO) algorithmJob shop scheduling problemMakespan

收稿日期：2014-10-25。國家自然科學(xué)基金項目(71271138)；上海市一流學(xué)科建設(shè)項目(S1201YLXK)；滬江基金項目(A14006)；上海理工大學(xué)人文社科攀登計劃項目(14XPB01)。黃霞，講師，主研領(lǐng)域：智能算法，生產(chǎn)調(diào)度。葉春明，教授。包曉曉，碩士生。

中圖分類號TH18TP301.6

文獻標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.056