求解多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題的離散人工蜂群算法

田野，徐洪華

（長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022）

作業(yè)車(chē)間調(diào)度問(wèn)題（Job Shop Scheduling Problem，JSSP）是一類(lèi)典型的組合優(yōu)化問(wèn)題，描述為若干工件在一組機(jī)器上的加工過(guò)程，每個(gè)工件都包含一系列操作，要求任一時(shí)刻一臺(tái)機(jī)器最多可加工一個(gè)工件，并且這些操作必須按照規(guī)定的順序進(jìn)行加工，目的是要找出一個(gè)適當(dāng)?shù)恼{(diào)度方案，使特定的目標(biāo)（如最終加工時(shí)間）得以滿(mǎn)足［1］。相對(duì)于JSSP問(wèn)題，柔性作業(yè)車(chē)間調(diào)度問(wèn)題（Flexible Job Shop Scheduling Problem，F(xiàn)JSSP）允許每個(gè)操作可以從給定的機(jī)器集合中選擇任意機(jī)器進(jìn)行加工，因此柔性作業(yè)車(chē)間調(diào)度問(wèn)題是作業(yè)車(chē)間調(diào)度問(wèn)題的擴(kuò)展，并且更為復(fù)雜［2］。人工蜂群算法（Artificial Bee Colony Algorithm，ABC）是一種新的群智能算法，主要通過(guò)模擬蜜蜂的覓食行為來(lái)進(jìn)行問(wèn)題的求解［1］。該算法思想簡(jiǎn)單、參數(shù)少、易于實(shí)現(xiàn)，目前已在函數(shù)優(yōu)化、生產(chǎn)調(diào)度等領(lǐng)域得到了廣泛的應(yīng)用［3-5］。

本文提出了一種離散的人工蜂群方法（Discrete Artificial Bee Colony Algorithm，DABC）用于求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題。為了使得人工蜂群算法可應(yīng)用于組合優(yōu)化問(wèn)題的求解，算法通過(guò)交叉方式來(lái)搜索更好的蜜源，并引入食物源活性來(lái)進(jìn)行自適應(yīng)的變異，以降低早熟收斂的可能性，增加群體的多樣性。

1 問(wèn)題描述

柔性作業(yè)車(chē)間調(diào)度問(wèn)題假設(shè)有n個(gè)待加工的作業(yè)集合J={J1,J2,…,Jn}和m臺(tái)可用于作業(yè)加工的機(jī)器集M={M1,M2,…,Mm}，每個(gè)作業(yè)i包含ni個(gè)操作，Oi,j(j=1,2,…,ni)表示作業(yè)i的第 j個(gè)操作。Pi,j,k為作業(yè)i的第 j個(gè)操作在機(jī)器k上的加工處理時(shí)間（i=1，2，…，n ；j=1，2，…，ni；k=1，2，…，m）。每個(gè)作業(yè)的每個(gè)操作Oi,j可能有多臺(tái)可以加工的機(jī)器集合Mi,j?M，Ci表示作業(yè)Ji的完成時(shí)間。

對(duì)于多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題來(lái)說(shuō)，需要確定兩個(gè)子問(wèn)題，及機(jī)器指派問(wèn)題和作業(yè)排序問(wèn)題，使得預(yù)先確定的多個(gè)調(diào)度目標(biāo)達(dá)到最優(yōu)。在本文中，有三個(gè)調(diào)度目標(biāo)同時(shí)優(yōu)化（最小化），分別是最大完成時(shí)間CM、機(jī)器總的負(fù)載時(shí)間WT、以及最大機(jī)器負(fù)載時(shí)間WM。那么對(duì)于n個(gè)作業(yè)，m臺(tái)機(jī)器的FJSSP問(wèn)題，三個(gè)調(diào)度目標(biāo)可以通過(guò)下面的數(shù)學(xué)公式來(lái)表述：

其中ω1、ω2和ω3分別成為最大完成時(shí)間、機(jī)器總的負(fù)載時(shí)間和最大機(jī)器負(fù)載時(shí)間的權(quán)重，且ω1+ω2+ω3=1。

2 DABC算法

2.1 食物源的表示

標(biāo)準(zhǔn)的人工蜂群算法是在連續(xù)型空間中進(jìn)行求解的，因此無(wú)法直接用于本文中的問(wèn)題。因此需要先進(jìn)行一定的編碼，以滿(mǎn)足調(diào)度問(wèn)題的需要。文中采取機(jī)器指派和操作排序相結(jié)合的編碼方式，整個(gè)編碼分為兩部分，第一部分是機(jī)器指派，用于選擇作業(yè)所需的加工機(jī)器，第二部分是操作排序，用來(lái)確定操作的加工順序。

假設(shè)有三個(gè)作業(yè)，其中作業(yè)1和作業(yè)2有兩道工序，作業(yè)3有三道工序，具體編碼形式如圖1所示。

圖1 編碼

機(jī)器指派中的第一個(gè)數(shù)字2表示機(jī)器2被選定加工工序O1，1，第二個(gè)數(shù)字1表示機(jī)器1被選定加工工序O1，2，以此類(lèi)推。作業(yè)排序中的數(shù)字出現(xiàn)順序表示每個(gè)作業(yè)的工序加工順序，如第一個(gè)數(shù)字2表示作業(yè)2的第一道工序O2，1，第二個(gè)數(shù)字1表示作業(yè)1的第一道工序O1，1，第四個(gè)數(shù)字1表示作業(yè)1的第二道工序O1，2，以此類(lèi)推。

2.2 交叉操作

在標(biāo)準(zhǔn)的人工蜂群算法中，食物源的搜索方式是通過(guò)兩個(gè)食物源位置的差分進(jìn)行擾動(dòng)來(lái)實(shí)現(xiàn)的。而對(duì)于求解離散問(wèn)題時(shí)，標(biāo)準(zhǔn)的人工蜂群算法搜索策略無(wú)法直接應(yīng)用于離散問(wèn)題，但是可以借鑒遺傳算法的思想，通過(guò)交叉操作來(lái)產(chǎn)生新的解，其中雇傭蜂和跟隨蜂都采用交叉的方式來(lái)獲得新的食物源位置。

根據(jù)上面的公式可以看出，通過(guò)交叉操作后，解Xi(t)既受到了解Xk(t)的擾動(dòng)，同時(shí)也保留了自身的一部分信息。針對(duì)柔性作業(yè)車(chē)間調(diào)度問(wèn)題的特點(diǎn)，文中針對(duì)機(jī)器指派序列采用多點(diǎn)交叉（Multiple Point Crossover，MPC），該交叉操作能夠較好地繼承父代個(gè)體工序分配的機(jī)器特征性到子代。相對(duì)于作業(yè)排序的交叉操作，本文在兩點(diǎn)間作業(yè)段交叉的基礎(chǔ)上提出了一種兩點(diǎn)間作業(yè)段隨機(jī)移動(dòng)的交叉方法，稱(chēng)為 Randomly Movement Crossover（簡(jiǎn)稱(chēng)RMC），RMC交叉和兩點(diǎn)間作業(yè)段交叉的不同之處在于兩個(gè)切點(diǎn)之間的作業(yè)子排列可以放置在子代中的任何位置，只要保證子排列在兩個(gè)子代個(gè)體中的位置是互相對(duì)稱(chēng)的即可，因此可以保證即使交叉的父代個(gè)體相似或甚至相同，也能得到不同于父代特征的子代個(gè)體，如圖2所示。

圖2 RMC交叉示意圖

從圖2中可以看出，當(dāng)兩個(gè)父代個(gè)體差異性很小甚至相同時(shí)（右側(cè)），RMC交叉仍然可以得到不同的子代個(gè)體。

2.3 變異操作

在發(fā)現(xiàn)食物源的過(guò)程中，所有食物源的位置會(huì)逐漸向目前發(fā)現(xiàn)的最優(yōu)食物源靠攏，當(dāng)所有的食物源匯聚到一起時(shí)，由于差分?jǐn)_動(dòng)無(wú)法起作用，因此容易導(dǎo)致算法的早熟收斂，陷入局部極值。對(duì)于這種情況，本文采用變異操作來(lái)克服這個(gè)問(wèn)題，通過(guò)對(duì)當(dāng)前食物源進(jìn)行自適應(yīng)變異來(lái)增強(qiáng)群體的多樣性，避免陷入局部極值。具體而言，在食物源的發(fā)現(xiàn)過(guò)程中，考慮當(dāng)前食物源和目前發(fā)現(xiàn)的最優(yōu)食物源之間的差異性，根據(jù)這個(gè)差異性來(lái)確定食物源的變異概率，進(jìn)行自適應(yīng)變異。這個(gè)差異性文中稱(chēng)為食物源活性，首先給出食物源活性的概念。

食物源活性：對(duì)于一個(gè)食物源位置Xi，其活性Activity（Xi）定義為當(dāng)前食物源位置和當(dāng)前最優(yōu)食物源位置之間的差異度。

由于食物源的位置表示成作業(yè)的排序序列，因此很容易出現(xiàn)多個(gè)食物源對(duì)應(yīng)的作業(yè)排序不同，但是和當(dāng)前最優(yōu)食物源所對(duì)應(yīng)的作業(yè)排序序列的差異度相同，即多個(gè)食物源的活性是一樣的，從而導(dǎo)致無(wú)法體現(xiàn)不同食物源的變異差異。因此，再引入一個(gè)隨機(jī)食物源來(lái)計(jì)算食物源的活性，即：

則食物源的變異概率公式如下：

此時(shí)，如果食物源活性較好，則認(rèn)為群體多樣性較好，那么食物源可以以較大的概率進(jìn)行變異；而當(dāng)食物源活性較差時(shí)，則群體多樣性差，食物源可能比較密集，并且當(dāng)前食物源可能更接近最優(yōu)解，因此應(yīng)該施以較小的概率進(jìn)行變異。

在本文中，考慮三種變異方式：交換變異（M1）；插入變異（M2）和反轉(zhuǎn)變異（M3）。三種變異方式如圖3所示。

圖3 三種變異方式

從圖2中可以看出，交換變異的攪動(dòng)是最小的，而插入變異和反轉(zhuǎn)變異都會(huì)對(duì)兩個(gè)隨機(jī)選擇的位置之間的作業(yè)產(chǎn)生影響，但是反轉(zhuǎn)變異同時(shí)也會(huì)改變?cè)械淖鳂I(yè)順序，因此對(duì)粒子的攪動(dòng)更大一些。變異過(guò)程的偽代碼描述如下：

2.4 算法描述

基于前面幾部分的介紹，本文提出的DABC的偽代碼描述如下：

3 實(shí)驗(yàn)

為了測(cè)試DABC算法的性能，在本節(jié)中，將文中提出的DABC算法通過(guò)常用的Kacem測(cè)試集［6］進(jìn)行了測(cè)試，并和文獻(xiàn)［7］中的算法（這里稱(chēng)為ESM算法）進(jìn)行了對(duì)比，驗(yàn)證DABC算法的有效性。

3.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

DABC算法采用MATLAB語(yǔ)言實(shí)現(xiàn)，機(jī)器配置為Windows 7系統(tǒng)，處理器為Intel Core（TM）i3-2120，3.3GHz，內(nèi)存大小為4G。

對(duì)于DABC算法來(lái)說(shuō)，主要的參數(shù)有三個(gè)，分別是群體大小NP、食物源廢棄閾值limit以及迭代次數(shù)gen。群體大小我們固定為200，其中雇傭蜂和跟隨蜂的個(gè)數(shù)分別為100，偵察蜂的個(gè)數(shù)為1。而limit和gen與問(wèn)題規(guī)模有關(guān)，因此文中分別設(shè)置為2*n和4*n*m（n是作業(yè)個(gè)數(shù)，m是機(jī)器個(gè)數(shù)）。

3.2 實(shí)驗(yàn)結(jié)果與分析

在本小節(jié)實(shí)驗(yàn)中，將本文DABC算法與ESM算法進(jìn)行比較，遵循文獻(xiàn)［6］，權(quán)重系數(shù)共有9種組合，兩個(gè)算法的對(duì)比結(jié)果如表1至5所示。

對(duì)于Kacem4X5，ESM算法對(duì)于不同系數(shù)的組合共找到了三組最優(yōu)解，而DABC算法找到了兩組。而對(duì)于問(wèn)題Kacem8X8來(lái)說(shuō)，ESM算法共找到了四組不同的最優(yōu)解，而DABC算法只找到了三組，但是DABC算法找到的解的質(zhì)量要優(yōu)于ESM算法，如DABC的一組解（16，73，13）要優(yōu)于ESM算法找到的解（17，73，13）。兩個(gè)算法對(duì)于問(wèn)題Kacem10X7均找到了三組相同的最優(yōu)解。DABC算法再Kacem10X10問(wèn)題上，盡管找到的最優(yōu)解個(gè)數(shù)與ESM算法相等，但是其中解（8，42，5）要優(yōu)于ESM的解（8，42，6）的，而ESM算法僅僅在組合3的情況下發(fā)現(xiàn)了解（8，42，6）。對(duì)于問(wèn)題Kacem15X10，除了組合2的情況外，DABC算法找到的最優(yōu)解均不劣于ESM算法找到的最優(yōu)解。因此，通過(guò)實(shí)驗(yàn)可以說(shuō)明，盡管對(duì)于個(gè)別問(wèn)題，DABC算法找到的最優(yōu)解個(gè)數(shù)比ESM算法少，但是解的質(zhì)量不劣于或者優(yōu)于ESM算法，并且將所有組合獲得的最優(yōu)解作為整體來(lái)看，DABC算法的求解質(zhì)量是優(yōu)于ESM算法的。

表1 Kacem4X5問(wèn)題結(jié)果

表2 Kacem8X8問(wèn)題結(jié)果

表3 Kacem10X7問(wèn)題結(jié)果

表4 Kacem10X10問(wèn)題結(jié)果

表5 Kacem15X10問(wèn)題結(jié)果

為了更進(jìn)一步證明前面的結(jié)論，文中針對(duì)每個(gè)問(wèn)題，將每種組合所獲得的最優(yōu)解進(jìn)行取均值，即將三個(gè)目標(biāo)值進(jìn)行相加然后取均值，具體計(jì)算公式如下：

其中L表示系數(shù)組合的個(gè)數(shù)，Ki表示組合i找到的最優(yōu)解的個(gè)數(shù)，Sol表示取所有組合獲得的最優(yōu)解的均值，SolDABC和SolESM分別表示DABC算法和ESM算法求得的均值，均值越小，說(shuō)明獲得的三個(gè)目標(biāo)的時(shí)間相對(duì)越少，ratio表示兩種算法的均值相對(duì)偏離比。從公式（12）可以看出，如果ratio為負(fù)值，說(shuō)明SolDABC小于SolESM，也就是說(shuō)DABC算法求得的解的均值要優(yōu)于ESM算法。表6列出了計(jì)算后的均值、算法運(yùn)行時(shí)間以及均值的比較。

表6 最優(yōu)解均值對(duì)比

從表6中可以看出，對(duì)于所有測(cè)試問(wèn)題，DABC算法獲得的最優(yōu)解的均值都小于ESM算法獲得的最優(yōu)解均值，ratio的值均為負(fù)值，這說(shuō)明從獲得最優(yōu)解的整體性來(lái)看，DABC算法獲得的解的質(zhì)量要由于ESM算法。此外，DABC算法的執(zhí)行時(shí)間也小于ESM算法，因此，DABC算法是有效的，并且是高效的。

4 結(jié)論

本文針對(duì)柔性作業(yè)車(chē)間調(diào)度問(wèn)題進(jìn)行了研究，提出了一種離散的人工蜂群算法DABC用于求解最大完成時(shí)間、機(jī)器總負(fù)載時(shí)間和最大機(jī)器負(fù)載時(shí)間問(wèn)題。算法通過(guò)交叉策略來(lái)實(shí)現(xiàn)解的搜索，并提出了一種兩點(diǎn)間作業(yè)段隨機(jī)移動(dòng)的交叉策略（RMC），該交叉策略在兩個(gè)父代個(gè)體相似甚至相同的情況下，也可以得到不同的子代個(gè)體。此外，針對(duì)群智能算法容易發(fā)生早熟收斂的問(wèn)題，DABC算法引入了自適應(yīng)的變異策略，通過(guò)食物源的活性來(lái)自適應(yīng)地控制個(gè)體的變異，增加群體的多樣性。

為了驗(yàn)證算法的有效性，本文采用了不同規(guī)模的Kacem測(cè)試數(shù)據(jù)集，并和近年來(lái)提出的ESM算法進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果表明，本文算法在總的求解質(zhì)量上要優(yōu)于對(duì)比算法，并且算法執(zhí)行時(shí)間更短，是非常有效的。

［1］Garey，MR，Johnson DS，Sethi R.The complexity of flow shop and job shop scheduling［J］.Mathematics of Operations Research，1976（1）：117-129.

［2］BrukerP，Schlie R.Job-shop scheduling with multi-purpose machines［J］.Computing，1990（45）：369-375.

［3］Dervis Karaboga，Bahriye Basturk.A powerful and efficient algorithm for numerical function optimization：artificial bee colony（ABC）algorithm［J］.Journal of Global Optimization，2007，39（3）：459-471.

［4］Gao Weifeng，Liu Sanyang.Improved artificial bee colony algorithm for global optimization［J］.Information Processing Letters，2011（111）：871-882.

［5］Liu Yanfeng，Liu Sanyang.A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem［J］.Applied SoftComputing，2013（13）：1459-1463.

［6］Imed Kacem，Slim Hammadi，Pierre Borne.Pareto-optimality approach for flexible job-shop scheduling problems：hybridization ofevolutionary algorithms and fuzzy logic［J］.Mathematics and Computers in Simulation，2002（60）：245-276.

［7］Xing Lining，Chen Yingwu，Yang Kewei.An efficient search method for multi-objective flexible job shop scheduling problems［J］.J Intell Manuf，2009（20）：283-293.