求解多目標柔性作業車間調度問題的離散人工蜂群算法

田野，徐洪華

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

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

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

1 問題描述

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

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

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

2 DABC算法

2.1 食物源的表示

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

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

圖1 編碼

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

2.2 交叉操作

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

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

圖2 RMC交叉示意圖

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

2.3 變異操作

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

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

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

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

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

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

圖3 三種變異方式

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

2.4 算法描述

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

3 實驗

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

3.1 實驗環境及參數設置

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

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

3.2 實驗結果與分析

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

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

表1 Kacem4X5問題結果

表2 Kacem8X8問題結果

表3 Kacem10X7問題結果

表4 Kacem10X10問題結果

表5 Kacem15X10問題結果

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

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

表6 最優解均值對比

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

4 結論

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

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

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