蜜蜂交配優(yōu)化算法在車間作業(yè)調度中的應用

李小霞，劉峰，劉建曉

華中農業(yè)大學 理學院，武漢 430070

蜜蜂交配優(yōu)化算法在車間作業(yè)調度中的應用

李小霞，劉峰，劉建曉

華中農業(yè)大學 理學院，武漢 430070

1 引言

車間作業(yè)調度問題（JSP）所要解決的是如何找出多個工件在多臺機器上的最優(yōu)加工過程。JSP是許多企業(yè)在實際生產過程中都會面臨的問題，也是一類典型的組合優(yōu)化問題和NP難題[1-3]。目前，已經出現(xiàn)了多種用于求解該問題的方法，主要以啟發(fā)式算法為主[4]，例如：遺傳算法[5-6]、模擬退火算法[7-9]、蟻群算法[10-11]等。盡管這些方法的應用已經取得了一定的效果，但由于仍然存在計算復雜度高，前期收斂速度快而后期收斂速度慢等問題，使得它們只適用于求解較小規(guī)模的車間作業(yè)調度問題，而且求解過程易陷入局部最優(yōu)解。

蜜蜂交配優(yōu)化算法（Honey-Bee Mating Optimization Algorithm，HBMOA）是近年來涌現(xiàn)出的一種新的群智能算法，其搜索最優(yōu)解的方法受到真實蜜蜂交配過程的啟示。蜂王是一個蜂群中最優(yōu)秀、最健壯的個體，她的壽命長達3～5年，而工蜂和雄蜂的壽命最多只有5～6個月。蜂王飛出蜂巢與多個雄蜂在空中完成交配，交配后，雄蜂立即死亡，蜂王將飛回蜂巢產下幼蜂。幼蜂經工蜂精心培養(yǎng)，喂食蜂王漿，將成長為新一代蜂王。可見，蜜蜂交配繁衍過程是蜂王不斷更新的過程，這一過程類似進化計算中的優(yōu)化過程。模擬蜜蜂交配過程的算法——蜜蜂交配算法已經應用于解決多種組合優(yōu)化問題[12-14]，例如：水庫優(yōu)化問題、旅行商問題、車輛路徑問題等，并得到了很好的優(yōu)化結果。但是，至今尚未見到對于如何將蜜蜂交配優(yōu)化算法應用于解決車間作業(yè)調度問題的具體實現(xiàn)方法的詳細探討。因此，本文在對車間作業(yè)調度問題進行詳細描述的前提下，給出了將蜜蜂交配優(yōu)化算法應用于車間作業(yè)調度問題的具體實現(xiàn)方法，并通過應用實例驗證了該方法的可行性和有效性。

2 車間作業(yè)調度問題描述

假設有m臺機器M={M1，M2，…，Mm}，n個待加工工件P={P1，P2，…，Pn}，工件Pi對應多道工序Oi={Oi1，Oi2，…，Oik}，k≥1，矩陣JM中存放每道工序可選用的加工設備，即JM中任一元素JMij，1≤i≤n，1≤j≤k，表示第i個工件的第j道工序可選用的設備，矩陣T中存放每道工序在相應設備上的加工時間，即T中任一元素Tij，1≤i≤n，1≤j≤k，表示第i個工件的第j道工序在相應設備上加工所需的時間，則可將n/m車間作業(yè)調度問題的求解目標描述如下：

在滿足加工約束條件的基礎上，確定m臺機器上n個工件的加工順序，并使調度目標達到最優(yōu)。

這里的加工約束條件一般包括：

（1）各工件之間無優(yōu)先級；

（2）每個工件的各工序之間存在先后關系，即按照加工工藝規(guī)定，每道工序必須等到它前面的工序加工完畢后才能加工；

（3）在任一時刻，每臺機器只能執(zhí)行一道工序，且每道工序只能在一臺機器上執(zhí)行；

（4）每臺機器在加工工序的過程中不會發(fā)生故障，加工不會中斷。

本文采用最小化最大完工時間Cmax作為調度目標，滿足公式（1）：

其中Cij是工序Oij的加工結束時間。

3 車間作業(yè)調度問題的蜜蜂交配優(yōu)化算法實現(xiàn)

蜜蜂交配優(yōu)化算法是通過模擬蜜蜂交配過程實現(xiàn)全局尋優(yōu)的。在蜜蜂交配過程中，蜂王飛出蜂巢，選擇健壯的雄蜂進行飛行交配，每交配一次，蜂王就會將與之交配的雄蜂的基因存放在儲精囊中，同時飛行速度也將減少一定的量。當蜂王的儲精囊充滿后，蜂王回到蜂巢，蜂王基因與儲存在儲精囊中的雄蜂基因進行交叉產下幼蜂，并將幼蜂交給工蜂撫養(yǎng)。若經工蜂撫養(yǎng)后的幼蜂比當前的蜂王更健壯，則它將替代當前蜂王成為新一代的蜂王，并開始它的交配飛行。由此可見，新蜂王的產生就是一個優(yōu)化過程，而在蜜蜂交配過程結束后，所得到的蜂王即為待尋求的最優(yōu)解。因此，可將蜜蜂交配過程應用于組合優(yōu)化問題中尋求最優(yōu)解。

通過蜜蜂交配尋求最優(yōu)解的過程可以看出，蜜蜂交配算法應包括以下幾個關鍵步驟：

（1）產生一個初始種群，并選擇其中最健壯的個體作為蜂王，其他個體均作為雄蜂；

（2）選擇能與蜂王交配的雄蜂；

（3）通過將蜂王的基因與雄蜂的基因進行交叉產生新的幼蜂；

（4）選擇工蜂撫養(yǎng)幼蜂使其發(fā)生變異，并用變異得到的比當前蜂王更健壯的幼蜂替代當前蜂王；

（5）判斷交配飛行次數(shù)是否達到最大值，若是則終止交配飛行，否則重復執(zhí)行（2）、（3）、（4）。

基于以上分析，下面給出蜜蜂交配算法求解JSP的具體實現(xiàn)。

3.1 個體編碼

一個車間作業(yè)調度方案對應一個個體編碼串，該編碼串包括三段內容：第一段對應的是全部工件的加工工序，第二段和第三段分別是執(zhí)行第一段中各工序所選用的機器的序號和刀具的序號。

對于n/m車間作業(yè)調度問題，設n個工件中每個工件對應的工序數(shù)為ki（i為工件的序號），所有工件對應的工序之和S=k1+k2+…+kn，則編碼的長度為3×S。編碼的第一段為1..S部分，存放的是待加工的工件的序號，工件序號第j次出現(xiàn)即是工件的第j道工序，編碼的第二段為S+1..2×S部分，存放的是第一段中各工序選用的機器在矩陣JM1中的序號，編碼中第j(j＜S)個位置的工序選用的機器號存放在編碼的第j+S位置上，編碼的第三段為2×S+1..3×S部分，存放的是第一段中各工序選用的刀具在矩陣JM2中的序號，編碼中第j(j＜S)個位置的工序選用的刀具號存放在編碼的第j+2×S位置上。需要說明的是，矩陣JM2中存放每道工序可選用的刀具的序號，即JM2中任一元素JM2ij，1≤i≤n，1≤j≤k，表示第i個工件的第j道工序可選用的刀具。

3.2 初始種群的生成

通過上面的分析發(fā)現(xiàn)，蜂王是當前種群中最健壯的個體，而雄蜂也必須足夠的健壯才能追上蜂王與之交配。因此，實現(xiàn)蜜蜂交配優(yōu)化算法需要解決兩個方面的問題：（1）如何生成一個健壯的初始種群；（2）如何從種群中選出最優(yōu)的個體作為蜂王。

為了生成一個健壯的初始種群，選用遺傳算法實現(xiàn)對隨機生成的種群進行優(yōu)化，優(yōu)化所得的種群即為初始種群。通過遺傳算法得到的初始種群是由多個健壯的個體組成的調度方案集，其中每一個個體分別對應為一個調度方案。為了從初始種群中選出最優(yōu)的個體作為蜂王，采用公式（2）計算出個體的適應度并利用所計算出的適應度判斷個體的優(yōu)劣：

可見，調度方案所需時間越少，其適應度越高，方案越好。故而，可通過公式（2）計算出初始種群中各方案的適應度值，從中找出其中適應度最大的方案作為蜂王，其余方案作為雄蜂。

3.3 雄蜂選擇的設計

蜂王以一定的速度飛出蜂巢，開始她的交配飛行。然而，由于蜂王的飛行速度較快，只有那些健壯的雄蜂才能追上她與之交配，也就是說，適應度越接近蜂王適應度的雄蜂與蜂王交配的概率越大，故而，可采用公式（3）計算雄蜂與蜂王交配的概率：

式中，f(Queen)-f(Drone)是蜂王與雄蜂的適應度之差，Speed(t)是蜂王在時刻t的速度，其初始值在蜂王開始交配飛行之前隨機產生，并將隨著時間的推移而不斷降低，本文假設蜂王的速度以α為系數(shù)降低，即Speed(t+1)=α×Speed(t)，α是隨機產生的一個0到1之間的隨機數(shù)。于是，根據公式（3）可計算出雄蜂與蜂王的交配概率，若交配概率滿足條件Probility(Drone)＞r，則雄蜂可與蜂王交配并將雄蜂的基因存放在蜂王的儲精囊中。需要說明的是，條件中的r是一個隨機產生的0到1之間的數(shù)。

3.4 交叉算子的設計

由于車間作業(yè)調度問題編碼方式的特殊性，不能直接采用一般的交叉算子實現(xiàn)蜂王基因與雄蜂基因的交叉操作，而是將交叉算子具體設計為以下三個關鍵步驟：

（1）蜂王基因的第一段中的部分染色體與雄蜂對應的子染色體進行交叉；

（2）由于上一步驟中執(zhí)行的交叉操作可能造成所得新染色體的前半段中出現(xiàn)缺失和多余的基因，因此要找出缺失和多余的基因，并用缺失的基因替換多余的基因，從而得到新染色體的第一段；

（3）根據新染色體前半段基因與蜂王和雄蜂的對應關系，得到新染色體的后兩段基因。

3.5 變異算子的設計

由于不同工蜂會對幼蜂進行不同的撫養(yǎng)，因此，將不同工蜂對應為不同的變異方法，不同工蜂對幼蜂的撫養(yǎng)過程對應為不同的局部尋優(yōu)過程。

假設工蜂數(shù)量為Domen(Domen≥1)，則可通過生成一個的隨機數(shù)m(m≤Domen)來選擇相應的變異方法。這里將隨機數(shù)m設置為變異的次數(shù)，根據存放在JM1和JM2中的各工件工序可選用的機器序號和刀具序號，對編碼后兩段的機器序號和刀具序號進行不同次數(shù)的變異。

4 實驗與分析

為了驗證本文提出的應用于車間作業(yè)調度的蜜蜂交配算法的可行性和有效性，采用文獻[8]提供的實例作為測試用例，進行車間作業(yè)調度的蜜蜂交配算法的實驗。其中所用的車間作業(yè)資源包括5臺機器(M1,M2,…，M5)，12個刀具(C1,C2,…，C12)可供選擇使用，另有3個待加工的工件（編號為：1、2、3）以及它們對應的加工工序（工序個數(shù)為：20、16、14），可選用的機器和刀具，參見文獻[15]。

仿真實驗在Matlab中進行，在實驗過程中，蜜蜂交配算法采用的雄蜂個數(shù)為100，交配飛行次數(shù)為800次，用于計算雄蜂與蜂王交配概率的參數(shù)Speed(t)的初始值設置為1 000，每交配一次速度下降的系數(shù)α設置為0.9。采用蜜蜂交配算法實現(xiàn)的調度甘特圖如圖1所示，可以看出，蜜蜂交配算法能夠有效地求解車間作業(yè)調度問題。圖2同時給出了采用蜜蜂交配算法、模擬退火算法和遺傳算法實現(xiàn)測試用例中待加工工件所有工序的調度優(yōu)化過程。從圖2和表1的實驗結果可以發(fā)現(xiàn)，蜜蜂交配算法用于解決JSP，能夠得到比遺傳算法和模擬退火算法更好的優(yōu)化結果，是一種很有潛力的優(yōu)化算法。

表1 算法優(yōu)化結果

圖1 蜜蜂交配算法調度甘特圖

圖2 算法優(yōu)化過程

5 結束語

JSP是一類典型的組合優(yōu)化問題。本文在對JSP進行詳細分析的基礎上，提出了一種用于求解JSP的蜜蜂交配算法。通過實例驗證了蜜蜂交配算法求解JSP的可行性和有效性，同時將該算法與用于求解JSP的傳統(tǒng)優(yōu)化算法進行了實驗比較，結果表明蜜蜂交配算法能夠得到比傳統(tǒng)優(yōu)化算法更好的優(yōu)化結果。然而，如何更科學地設定算法中的一些參數(shù)，以及將算法進一步應用于解決多目標車間作業(yè)調度問題，還有待今后進行更深入的研究。

[1]BlazewiczJ，F(xiàn)inkeG，HaoptG.Newtrendsinmachine scheduling[J].European Journal of Operational Research，1988，37：303-317.

[2]Martin D，Bracken I.The integration and socioeconomic and physical resource data for applied land management information systems[J].Applied Geo Graphy，1993，2：45-53.

[3]王凌.車間調度及其遺傳算法[M].北京：清華大學出版社，2003：71-121.

[4]郭冬芬，李鐵克.基于約束滿足的車間調度算法綜述[J].計算機集成制造系統(tǒng)，2007，13（1）：117-125.

[5]Biegel J E，Davern J J.Genetic algorithms and job shop scheduling[J].Computers and Industrial Engineering，1990，19（4）：81-91.

[6]紀樹新.遺傳算法在車間作業(yè)調度中的應用[J].系統(tǒng)工程理論與實踐，1998，18（5）：34-39.

[7]Plamer G J.A simulated annealing approach to integrated production scheduling[J].Journal of Intelligent Manufacturing， 1996，7（3）：163-176.

[8]趙衛(wèi).模擬退火遺傳算法在車間作業(yè)調度中的應用[J].計算機仿真，2011，28（7）：361-364.

[9]Li W D，Ong S K，Nee A Y C.A hybrid genetic algorithm and simulated annealing approach for the optimization of process plan for prismatic parts[J].Int J Prod Res，2002，40：1899-1922.

[10]姬耀鋒，黨培，郭小波.基于蟻群算法的車間作業(yè)調度問題研究[J].計算機與數(shù)字工程，2011，39（1）：4-6.

[11]王進峰，陰國富，雷前召，等.蟻群算法在工藝規(guī)劃與車間調度集成優(yōu)化中的研究[J].東南大學學報：自然科學版，2012，42（S1）：173-177.

[12]Abbass H A.Marriage in honey-bee optimization（MBO）：a haplometrosis polygynous swarming approach[C]//Proceedings of the Congress on Evolutionary Computation（CEC2001），Seoul，Korea，2001：207-214.

[13]Afshar A，Bozog Haddad O，Marino M A，et al.Honey-Bee Mating Optimization（HBMO）algorithm for optimal reservoir operation[J].JournaloftheFranklinInstitute，2007，344：452-462.

[14]Marinakis Y，Marinaki M.A honey bees mating optimization algorithmfor the openvehicle routingproblem[C]// Proceedingsof the13th Annual ConferenceonGenetic andEvolutionaryComputation（GECCO11），NewYork，USA，2011：101-108.

[15]Li W D，Ong S K，Nee A Y C.Optimization of process planning using a constraint-based tabu search method[J]. Int J Prod Res，2004，42：1955-1985.

LI Xiaoxia,LIU Feng,LIU Jianxiao

College of Science,Huazhong Agricultural University,Wuhan 430070,China

To solve the Job-shop Scheduling Problem（JSP）,a solution method—honey-bee mating optimization algorithm is presented on the basis of the JSP’s description.The method takes a set of job scheduling schemes as the bee swarm,and minimizing the processing time as the optimization goal.The optimal scheduling scheme is obtained by simulating the procedure of honey-bee mating.The test is carried out by the JSP test cases on Matlab.The experimental results show that this method can not only solve JSP but also find a better optimal scheduling scheme than the traditional optimization methods.

honey-bee mating optimization algorithm;Job-shop Scheduling Problem（JSP）;combinatorial optimization

為了解決車間作業(yè)調度問題，在對其進行分析描述的基礎上，提出了采用蜜蜂交配優(yōu)化算法的求解方法。該方法把由多個作業(yè)調度方案組成的集合作為蜂群，以最小化加工時間作為算法的優(yōu)化目標，通過模擬蜂群交配繁衍培養(yǎng)蜂王的優(yōu)化過程來獲得最優(yōu)作業(yè)調度方案。采用車間作業(yè)調度測試案例在Matlab平臺上進行實驗，實驗結果表明，該方法不僅能夠有效地求解車間作業(yè)調度問題，而且能夠取得了比傳統(tǒng)優(yōu)化方法更好的優(yōu)化結果。

蜜蜂交配優(yōu)化算法；車間作業(yè)調度問題；組合優(yōu)化

A

TP391

10.3778/j.issn.1002-8331.1303-0193

LI Xiaoxia,LIU Feng,LIU Jianxiao.Application of honey-bee mating optimization algorithm to job-shop scheduling. Computer Engineering and Applications,2013,49（13）：262-265.

武漢大學軟件工程國家重點實驗室開放研究基金（No.SKLSE2012-09-24）；華中農業(yè)大學新進博士科研啟動專項（No.52902-0900206084，No.52902-0900206081）；高等學校博士學科點專項科研基金新教師類資助課題（No.20120146120002）；中央高校基本科研業(yè)務費專項資金資助項目（No.2013PY118）。

李小霞（1979—），女，博士，講師，研究領域為CAD，CIMS；劉峰（1981—），通訊作者，男，博士，講師，研究領域為CIMS，物聯(lián)網；劉建曉（1985—），男，博士，講師，研究領域為云制造。E-mail：lxx1818@126.com

2013-03-13

2013-06-08

1002-8331（2013）13-0262-04