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

李小霞，劉峰，劉建曉

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

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

李小霞，劉峰，劉建曉

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

其中Cij是工序Oij的加工結(jié)束時間。

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

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

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

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

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

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

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

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

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

3.1 個體編碼

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

對于n/m車間作業(yè)調(diào)度問題，設(shè)n個工件中每個工件對應(yīng)的工序數(shù)為ki（i為工件的序號），所有工件對應(yīng)的工序之和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)化所得的種群即為初始種群。通過遺傳算法得到的初始種群是由多個健壯的個體組成的調(diào)度方案集，其中每一個個體分別對應(yīng)為一個調(diào)度方案。為了從初始種群中選出最優(yōu)的個體作為蜂王，采用公式（2）計算出個體的適應(yīng)度并利用所計算出的適應(yīng)度判斷個體的優(yōu)劣：

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

3.3 雄蜂選擇的設(shè)計

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

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

3.4 交叉算子的設(shè)計

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

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

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

（3）根據(jù)新染色體前半段基因與蜂王和雄蜂的對應(yīng)關(guān)系，得到新染色體的后兩段基因。

3.5 變異算子的設(shè)計

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

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

4 實驗與分析

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

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

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

圖1 蜜蜂交配算法調(diào)度甘特圖

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

5 結(jié)束語

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

[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]王凌.車間調(diào)度及其遺傳算法[M].北京：清華大學出版社，2003：71-121.

[4]郭冬芬，李鐵克.基于約束滿足的車間調(diào)度算法綜述[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è)調(diào)度中的應(yīng)用[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è)調(diào)度中的應(yīng)用[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è)調(diào)度問題研究[J].計算機與數(shù)字工程，2011，39（1）：4-6.

[11]王進峰，陰國富，雷前召，等.蟻群算法在工藝規(guī)劃與車間調(diào)度集成優(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è)調(diào)度問題，在對其進行分析描述的基礎(chǔ)上，提出了采用蜜蜂交配優(yōu)化算法的求解方法。該方法把由多個作業(yè)調(diào)度方案組成的集合作為蜂群，以最小化加工時間作為算法的優(yōu)化目標，通過模擬蜂群交配繁衍培養(yǎng)蜂王的優(yōu)化過程來獲得最優(yōu)作業(yè)調(diào)度方案。采用車間作業(yè)調(diào)度測試案例在Matlab平臺上進行實驗，實驗結(jié)果表明，該方法不僅能夠有效地求解車間作業(yè)調(diào)度問題，而且能夠取得了比傳統(tǒng)優(yōu)化方法更好的優(yōu)化結(jié)果。

蜜蜂交配優(yōu)化算法；車間作業(yè)調(diào)度問題；組合優(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）；華中農(nóng)業(yè)大學新進博士科研啟動專項（No.52902-0900206084，No.52902-0900206081）；高等學校博士學科點專項科研基金新教師類資助課題（No.20120146120002）；中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目（No.2013PY118）。

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

2013-03-13

2013-06-08

1002-8331（2013）13-0262-04