田野，徐洪華

（長春理工大學 計算機科學技術學院，長春 130022）

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

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

1 問題描述

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

對于多目標柔性作業(yè)車間調度問題來說，需要確定兩個子問題，及機器指派問題和作業(yè)排序問題，使得預先確定的多個調度目標達到最優(yōu)。在本文中，有三個調度目標同時優(yōu)化（最小化），分別是最大完成時間CM、機器總的負載時間WT、以及最大機器負載時間WM。那么對于n個作業(yè)，m臺機器的FJSSP問題，三個調度目標可以通過下面的數(shù)學公式來表述：

其中ω1、ω2和ω3分別成為最大完成時間、機器總的負載時間和最大機器負載時間的權重，且ω1+ω2+ω3=1。

2 DABC算法

2.1 食物源的表示

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

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

圖1 編碼

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

2.2 交叉操作

在標準的人工蜂群算法中，食物源的搜索方式是通過兩個食物源位置的差分進行擾動來實現(xiàn)的。而對于求解離散問題時，標準的人工蜂群算法搜索策略無法直接應用于離散問題，但是可以借鑒遺傳算法的思想，通過交叉操作來產生新的解，其中雇傭蜂和跟隨蜂都采用交叉的方式來獲得新的食物源位置。

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

圖2 RMC交叉示意圖

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

2.3 變異操作

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

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

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

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

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

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

圖3 三種變異方式

從圖2中可以看出，交換變異的攪動是最小的，而插入變異和反轉變異都會對兩個隨機選擇的位置之間的作業(yè)產生影響，但是反轉變異同時也會改變原有的作業(yè)順序，因此對粒子的攪動更大一些。變異過程的偽代碼描述如下：

2.4 算法描述

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

3 實驗

為了測試DABC算法的性能，在本節(jié)中，將文中提出的DABC算法通過常用的Kacem測試集［6］進行了測試，并和文獻［7］中的算法（這里稱為ESM算法）進行了對比，驗證DABC算法的有效性。

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

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

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

3.2 實驗結果與分析

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

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

表1 Kacem4X5問題結果

表2 Kacem8X8問題結果

表3 Kacem10X7問題結果

表4 Kacem10X10問題結果

表5 Kacem15X10問題結果

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

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

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

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

4 結論

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

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

［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.