黃　霞　葉春明　包曉曉

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

?

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

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

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

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

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

0引言

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

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

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

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

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

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

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

(1)

Subjectto:

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

(2)

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

(3)

cik≥0

(4)

(5)

(6)

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

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

2.1雜草算法的基本原理

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

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

在基本IWO中，雜草表示所求問(wèn)題的可行解，種群是所有雜草的集合。進(jìn)化過(guò)程中，雜草通過(guò)繁殖產(chǎn)生種子，種子通過(guò)空間擴(kuò)散，生長(zhǎng)成雜草，如此反復(fù)。當(dāng)種群中雜草數(shù)量達(dá)到預(yù)先設(shè)定的最大種群規(guī)模時(shí)，不是簡(jiǎn)單的從父代中篩選優(yōu)秀個(gè)體進(jìn)行繁殖，而是先讓所有個(gè)體都自由繁殖和擴(kuò)散后，再將父代和子代一起按適應(yīng)度值排列并進(jìn)行優(yōu)選。通過(guò)以適應(yīng)度為基準(zhǔn)的繁殖機(jī)制，雜草算法使其產(chǎn)生的解在不可行和可行之間不斷轉(zhuǎn)化。這種機(jī)制給予那些適應(yīng)度值差的個(gè)體繁殖機(jī)會(huì)，如果它們后代的適應(yīng)度值好，這些后代仍有機(jī)會(huì)生存下來(lái)，這樣能在最大限度上保留有用信息，也可以避免早熟和陷入局部最優(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)前種群中所生長(zhǎng)的雜草的最大和最小適應(yīng)度值；smax和smin分別表示一個(gè)雜草能產(chǎn)生種子的最大值和最小值。雜草產(chǎn)生的種子按平均值為0，標(biāo)準(zhǔn)差為σ的正態(tài)分布，擴(kuò)散在父代雜草周?chē)?。種子生長(zhǎng)位置與父代雜草的距離稱(chēng)為隨機(jī)步長(zhǎng)D∈[-σ，σ]，具體σ的計(jì)算公式如下：

(8)

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

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

IWO的主要步驟如下:

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

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

3) 雜草的種子按式(8)以隨機(jī)步長(zhǎng)進(jìn)行空間擴(kuò)散并生長(zhǎng)為雜草，進(jìn)入雜草種群；

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

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

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

3.1編碼方式

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

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

3.2算法流程

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

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

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

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

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

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

4仿真實(shí)驗(yàn)

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

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

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

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

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

圖2　LA10問(wèn)題運(yùn)行10次尋優(yōu)曲線(xiàn)圖

圖3　LA14問(wèn)題運(yùn)行10次尋優(yōu)曲線(xiàn)圖

5結(jié)語(yǔ)

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

參考文獻(xiàn)

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

[2] 王永明,尹紅麗,秦開(kāi)大.作業(yè)車(chē)間調(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)化算法的改進(jìn)分析及應(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] 劉長(zhǎng)平,葉春明.一種新穎的仿生群智能優(yōu)化算法:螢火蟲(chóng)算法[J].計(jì)算機(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。國(guó)家自然科學(xué)基金項(xiàng)目(71271138)；上海市一流學(xué)科建設(shè)項(xiàng)目(S1201YLXK)；滬江基金項(xiàng)目(A14006)；上海理工大學(xué)人文社科攀登計(jì)劃項(xiàng)目(14XPB01)。黃霞，講師，主研領(lǐng)域：智能算法，生產(chǎn)調(diào)度。葉春明，教授。包曉曉，碩士生。

中圖分類(lèi)號(hào)TH18TP301.6

文獻(xiàn)標(biāo)識(shí)碼A

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