作業車間調度問題的雜草優化算法求解

黃　霞　葉春明　包曉曉

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

?

作業車間調度問題的雜草優化算法求解

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

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

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

關鍵詞雜草優化算法作業車間調度問題最大完工時間

0引言

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

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

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

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

1作業車間調度問題的數學描述

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

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

(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是一個足夠大的正數；aihk和xijk分別為指示系數和指示變量。式(1)表示目標函數，即最小化最大完成時間Makespan；式(2)表示工藝約束條件決定的每個工件的各個操作的加工先后順序；式(3)表示加工各個工件的各機器的先后順序，同是也保證在同一時刻一個工件不會分配給兩臺機器，以及兩臺機器不會同時加工一個工件；式(4)表示完工時間變量約束條件；式(5)和式(6)分別表示指示系數和指示變量可能的取值大小。

2雜草算法的優化機理

2.1雜草算法的基本原理

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

2.2雜草算法的數學描述與分析

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

雜草繁殖種子的數目與雜草的適應性成正比，通常適應度高的雜草產生種子較多，而適應度低的雜草產生種子較少。雜草產生種子的公式為：

(7)

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

(8)

式中iter為當前進化代數，itermax為最大進化代數，σ為當前標準差，σinit和σfinal分別為標準差的最初值和最終值，n為非線性調和因子。

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

IWO的主要步驟如下:

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

2) 雜草按式(7)產生相應個數的種子；

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

4) 判斷種群是否達到預設的最大種群規模，如滿足則進行優先排序，并選擇出適應度好的最大種群規模數個體，否則直接轉到2)；

5) 判斷是否達到最大迭代次數，若滿足則輸出最優解，并終止，否則轉到2)。

3雜草算法求解作業車間調度問題

3.1編碼方式

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

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

3.2算法流程

上述編碼規則中的染色體對應為算法中的雜草個體。根據上述ROV編碼規則，雜草個體位置可以轉換為一個工序排列，每個工序排列的Makespan作為雜草個體的適應度值。求解作業車間調度問題的雜草優化算法流程如下：

1) 初始化算法基本參數：設置初始雜草個數、最大雜草個數、問題的維數、擴張區間大小、最大最小種子數、初始標準差和最終標準差，以及最大迭代次數。

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

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

4) 判斷雜草種群是否達到預設的最大種群規模，如滿足則按競爭性生存法則進行優先排序，選擇出適應度值排在前面的最大種群規模數個體，并保存當前最優適應度值；否則直接轉到3)。

5) 判斷是否達到最大迭代次數，若滿足則輸出所有保存的適應度值中的最優解，并終止；否則轉到3)。

4仿真實驗

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

表1　三種算法優化結果對比分析

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

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

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

圖2　LA10問題運行10次尋優曲線圖

圖3　LA14問題運行10次尋優曲線圖

5結語

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

參考文獻

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

[2] 王永明,尹紅麗,秦開大.作業車間調度理論及其優化方法研究[M].科學出版社,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] 陳歡,周永權.入侵雜草優化算法的改進分析及應用研究[D].廣西,廣西民族大學,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] 吳啟迪,汪鐳.智能微粒群算法研究及應用[M].南京:江蘇教育出版社,2005.

[15] 劉長平,葉春明.一種新穎的仿生群智能優化算法:螢火蟲算法[J].計算機應用研究,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。國家自然科學基金項目(71271138)；上海市一流學科建設項目(S1201YLXK)；滬江基金項目(A14006)；上海理工大學人文社科攀登計劃項目(14XPB01)。黃霞，講師，主研領域：智能算法，生產調度。葉春明，教授。包曉曉，碩士生。

中圖分類號TH18TP301.6

文獻標識碼A

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