貓群優化算法求解柔性作業車間調度問題

姜天華

魯東大學 交通學院，山東 煙臺 264025

1 引言

柔性作業車間調度問題（Flexible Job Shop scheduling Problem，FJSP）是在經典作業車間調度問題的基礎上發展而來的，它進一步考慮了工件柔性加工路徑的特性，增加了車間調度的靈活性，但同時也給問題的求解帶來了更大的難度[1]。對于該類問題的求解，目前智能優化算法已成為最受歡迎的方法之一，引起了國內外學者們廣泛關注。

張超勇等[1]提出了一種具有雙層子代產生模式的改進遺傳算法，求解不同生產指標下的柔性作業車間調度問題。李修琳等[2]將蜂群算法和模擬退火算法相結合，提出了一種混合蜂群算法，求解柔性作業車間調度問題。仲于江等[3]將小生境技術引入到粒子群算法中，提出了一種小生境粒子群算法，求解多目標柔性作業車間調度問題。Ho和Tay[4]以工件最大完工時間為優化目標，提出了一種文化算法，求解柔性作業車間調度問題。Ennigrou和Ghédira[5]基于禁忌搜索算法提出了基于多智能體的方法求解柔性作業車間調度問題。Ziaee[6]提出了一種啟發式方法優化柔性作業車間工件最大完工時間。隨著各學科間的相互交叉和快速發展，不斷涌現出更多新型的智能優化算法，但目前還沒有一種算法能夠獲得所有問題的全局最優解，因此新型算法在生產調度問題的應用研究仍然是制造領域研究的熱點。

基本貓群優化算法（Cat Swarm Optimization，CSO）是通過觀察貓的行為習性而提出的一種群智能優化算法。它的主要特點體現在算法每次迭代時將貓群按比例劃分為兩個子群，并分別在搜尋模式和跟蹤模式下進行個體位置更新，使算法能夠同時進行全局和局部搜索[7]。目前該算法雖已被應用于多種復雜優化問題的求解，但在車間調度中的應用仍然較少[8-9]。因此，本文對基本貓群優化算法進行一系列設計和改進，提出了一種改進型貓群優化算法（Improved Cat Swarm Optimization，ICSO）求解柔性作業車間調度問題，以獲得最優的工件最大完工時間。最后，通過基準算例驗證了所提算法在求解FJSP問題方面的可行性和有效性。

2 柔性作業車間調度問題

車間內m臺機器需要n個待加工工件，各工件相互獨立，且每個工件i的加工由Ji(Ji≥1)道工序組成，各道工序可在多于一臺的機器上加工，加工時間是由其所在機器的能力決定的。本文需要解決的FJSP問題是為工序分配合適機器，并確定機器上工序間的加工順序，最終使工件最大完工時間最小。

對于該問題，考慮以下假設條件：

（1）工件和機器零時刻均為可用狀態。

（2）同一時刻同臺機器只可加工一道工序。

（3）工序加工時不可被中斷。

（4）各工件加工優先級相同。

（5）不考慮機器故障和機器加工前的準備時間。

令Cmax表示工件最大完工時間，CiJi表示工件i的完工時間，則目標函數可表示為：

3 基本貓群優化算法

貓群優化算法的搜索模式可分為搜尋模式和跟蹤模式兩種，分別對應于全局搜索和局部搜索[7]。每次迭代過程時，首先按照一定比例對貓群個體劃分成兩個子群，然后對子群個體進行不同模式下的位置更新，直至算法結束。

在搜尋模式下，貓群個體需預先設定改變維數的個數和維數的改變范圍，然后對原個體位置進行一定擾動，并填滿搜尋記憶池，評價記憶池中新個體位置后，選擇其中最優位置替代原個體位置[9]。在跟蹤模式下，基本貓群優化算法與粒子群算法相似，采用速度-位移更新公式，并根據全局最優解的位置來更新貓群個體位置，如式（2）和（3）所示。

其中，t表示當前迭代次數；xk表示第k只貓的位置向量，x*表示貓群目前搜索到的最佳位置，vk表示第k只貓的速度向量，c1為加速度常數，rand表示[0，1]間的隨機數。由于篇幅限制，基本貓群優化算法的步驟可詳見文獻[7]。

4 改進貓群優化算法

4.1 編碼方法

個體位置采用前后等長的兩段式編碼，分別對應于機器分配和工序排序。個體位置中各元素均在[a,b]內任意取值，b＞a≥0，并根據一定的順序存儲。假設車間內包含3個待加工工件，每個工件具有2道工序，則個體位置向量總長度為12。若個體位置元素在[0，1]內任意取值，則編碼方案如圖1所示。

圖1 個體位置編碼

4.2 轉換方法

基本CSO算法個體位置元素為連續值，然而調度解為離散值。因此，本文采用文獻[10]中的轉換方法，用于解決解空間與問題空間之間的相互轉換。

（1）位置向量轉換為調度方案

①機器分配段：根據式（4）將位置向量的元素轉換成其所對應工序可選機器集合中機器的編號。其中，2 l為個體位置向量的總長度，s(k)為元素k所對應的工序的可選機器的數量，u(k)為已選機器在工序可選機器集合中的編號，即工序可選機器集合中第u(k)個元素為工序所分配的機器。

②工序排序段：首先對個體位置向量中的元素進行依次編號，然后采用升序排列規則，為每個元素賦予唯一一個的順序值π(k)，將順序值與位置編號進行對比，找到各順序值對應的工序編號，從而確定工序加工順序，如圖2所示。

圖2 位置向量轉換成工序排序

（2）調度方案向位置向量轉換

①機器分配段：按照文獻[10]的轉換方式，將工序所分配的機器編號轉換成[0，1]中的個體位置元素，如式（5）所示。

②工序排序段：首先為排序方案中的元素進行依次編號，然后將工序編號和排序方案進行對比，從而獲得順序值π(k)，按照式（6）即可確定個體位置向量中各元素的值，如圖3所示。

圖3 工序排序轉換成位置向量

4.3 種群初始化

分別針對調度解前后兩段進行種群初始化，并按照4.2節中的方法將其轉換為個體位置向量。

（1）前半段采用文獻[11]中的啟發式算法，即全局搜索、局部搜索與隨機生成三種方式相結合來獲得初始機器分配方案。

①全局搜索[11]：根據機器數建立一個等長的數組，各元素值為對應機器的負載。任選一個未分配機器的工件，并從被選工件第一道工序開始，將工序可選機器的加工時間與相應數組元素值相加，選擇累加時間最短的機器作為工序的加工機器，然后更新數組元素值，將被選機器的加工時間加到數組對應元素上，依次類推直到當前工件的所有工序的加工機器均已選擇完畢，然后再隨機選擇下一個未分配機器的工件，重復上述操作，直到所有工件分配完畢。

②局部搜索[11]：與全局搜索相比，主要區別在于該方法每次對工件進行機器選擇后，數組元素值需要重新置零，且在執行過程中不存在隨機選擇工件。

③隨機生成：在各工序可選機器集合任選一臺機器加入初始調度解。

（2）后半段針對每一個已生成的機器分配方案，隨機生成法獲得若干個排序方案，評估每一個排序方案與機器分配方案的組合的適應度值，然后選擇最優的組合作為一個初始調度解，重復上述過程，直到生成初始種群為止。

4.4 自適應行為模式選擇方法

由基本貓群優化算法可知，貓群個體被以固定比例劃分為兩個子群，并分別在搜尋模式和跟蹤模式下進行個體位置更新，即該算法在進化過程中執行全局搜索和局部搜索的個體數量的比例是固定的。然而，一個優秀的算法應該能夠在進化過程中有效地協調全局搜索和局部搜索的能力，即算法在運行初期側重于全局搜索，并在運行后期側重于局部搜索。對此，本文采用自適應貓群行為模式選擇方法，如式（7）所示，其中MR表示兩種行為模式的混合比率，MRmax和MRmin分別表示混合比率的最大值和最小值，t表示算法當前迭代次數，tmax表示最大迭代次數。

4.5 搜尋模式

在基本貓群優化算法中，搜尋模式下參數的設置對算法性能具有較大影響，若參數設定過大，則解的變化范圍較大，致使算法類似于隨機搜索，不利于算法收斂；若參數設定過小，則解的變化范圍較小，降低了算法的搜索能力，使其易于陷入局部最優解[9]。對此，采用文獻[9]針對混流裝配線排序問題，提出了一種基于多樣化搜尋算子的改進搜尋模式。本文在此基礎上根據柔性作業車間的特點重新設計三種不同類型的搜尋算子，各個體隨機執行以下操作形成新個體位置來填滿記憶池，選擇其中最優個體位置替代原個體位置。

（1）N1：在工序排序部分中任選兩個元素，并對所選元素進行交換操作，如圖4所示。

圖4 第一種鄰域結構

（2）N2：在工序排序部分中任選兩個元素，并將后一元素插入到前一元素之前的位置，如圖5所示。

圖5 第二種鄰域結構

（3）N3：在機器分配部分任選一個元素（對應工序的可選機器應多于一臺），然后將該工序分配至不同的機器上，并根據式（5）生成新的元素值。若圖6中第4個元素被選中，其對應工序O22可選機器數s(4)為4，重新選擇的機器在工序O22可選機器集合中的編號u(k)為2，則按式（5）生成的新元素值為0.33。

圖6 第三種鄰域結構

4.6 跟蹤模式

在跟蹤模式下，貓群優化算法與粒子群算法類似，二者均通過速度-位移公式更新個體位置，且同樣易于陷入局部最優解。對此，本文在跟蹤模式中引入萊維飛行策略，用于增強算法跳出局部最優位置的能力。萊維飛行是一種服從萊維分布的隨機搜索路徑，該搜索策略下短距離搜索與偶爾長距離行走同時存在，其中前者可使動物覓食時在自身附近小范圍內進行精細搜索，后者則可使動物進入另一個搜索區域進行更廣范圍的搜索[12]。因此，萊維飛行策略已被許多學者引入到進化算法中，并且取得了較好的效果。文獻[12]對萊維飛行和隨機行走進行了仿真對比，即相同步數下，隨機行走的搜索范圍相對集中，而萊維飛行則具有更大的搜索范圍和更強的搜索能力。文獻[13]將萊維飛行嵌入粒子群算法的個體位置更新公式，使算法性能得到明顯改善。因此，本文對貓群優化算法跟蹤模式下個體位置更新方法進行了改進，利用服從萊維分布的隨機數代替式（2）中服從均勻分布的隨機數，從而使個體位置更新具有萊維飛行的特點，如式（8）所示。

4.7 跳躍機制

為了進一步改善算法的計算結果，在算法中引入跳躍機制，即為最優個體位置設置一個“解齡”，其初始值為零，若算法迭代一次后計算結果未發生變化，則解齡加1，否則置0。當解齡超過預設上限（文中取為10），則對當前最優個體位置執行變鄰域搜索，迫使其跳出局部最優位置。變鄰域搜索可直接利用本文第4.4節中三種搜尋算子作為鄰域結構進行設計，具體步驟如下：

步驟1將當前最優個體位置作為變鄰域搜索的初始解x，令ηmax←3，λ←1，并設置最大迭代次數λmax。

步驟2設置η←1。

步驟3 若η=1，則x′←N1(x)；若η=2，x′←N2(x)；若η=3，x′←N3(x)。

步驟4將x′作為初始解進行局部搜索，獲取局部最優解x″。

步驟5 若 x″優于 x，則 x←x″，并令η←1；否則令η←η+1。

步驟6判斷是否滿足η＞ηmax。若是，令λ←λ+1，轉到步驟7；否則，轉到步驟3。

步驟7判斷是否滿足λ＞λmax。若是，轉到步驟8；否則，轉到步驟2。

步驟8變鄰域搜索結束。

變鄰域搜索中局部搜索則采用閾值接受法，具體步驟如下：

步驟1獲取初始解 x′，并令閾值θ＞0，q←1，?←1，設置最大迭代次數qmax。

步驟2 若 ?=1，則 x″←N1(x′)?N3(x′)；若 ?=0 ，x″←N2(x′)?N3(x′)。

步驟3 判斷是否滿足 Cmax(x″)-Cmax(x′)≤θ。若是，則 x′←x″；否則令

步驟4設置q←q+1，并判斷是否滿足q＞qmax。若是，x″←x′，轉到步驟5；否則，轉到步驟2。

步驟5局部搜索結束。

5 算例分析

本章對FJSP問題的基準Brandimarte算例[14]（MK01～MK10）和Kacem算例[15]（Kacem01～Kacem05）進行仿真并測試算法的計算性能。采用Fortran程序設計語言進行編程，并在WinXP系統下內存2 GB的Pentium CPU G2030@3.00 GHz，2.99 GHz計算機上運行。算法參數設置為：種群大小為200，最大迭代次數為500，記憶池大小為20，MRmax和MRmin分別為1.0和0.0，變鄰域搜索和局部搜索最大迭代次數λmax和qmax均為10。

首先對引入萊維飛行策略和跳躍機制的有效性進行對比分析，將各算法在MK01～MK10算例下獨立運行十次的結果進行比較，如表1所示，其中BEST表示十次運行獲得最優值，AVG表示十次運行的平均值。CSO-1算法和CSO-2算法表示在ICSO算法中去除跳躍機制，其中CSO-1算法中跟蹤模式個體位置更新按式（2）和式（3）進行，CSO-2算法跟蹤模式個體位置更新按式（8）和式（3）進行，即引入萊維飛行策略。從表1中數據可以看出，ICSO算法的計算結果優于其他兩種算法，驗證了跳躍機制的有效性。此外，大多數情況下CSO-2算法的性能優于CSO-1算法，由此說明萊維飛行策略的引入能夠改善算法的計算結果。

表1 三種算法的對比結果

為了進一步驗證ICSO算法求解FJSP問題的有效性，將其與現有文獻中的不同算法進行比較，對比結果如表2和表3所示。其中，粗體表示同一算例下各算法間的最優值，“—”表示對比文獻中沒有給出相應的計算結果。從表2和表3中的數據可以明顯看出，ICSO算法在大多數情況下均能獲得最優值。因此，ICSO算法求解本文FJSP問題具有一定的可行性和有效性。圖7和圖8分別為算例Kacem05和MK10的甘特圖。

表2 Kacem算例對比結果

表3 Brandimarte算例對比結果

圖7 算例Kacem05甘特圖

6 結束語

本文以工件最大完工時間為優化目標求解柔性作業車間生產調度問題，提出了一種改進型貓群優化算法。

圖8 算例MK10甘特圖

（1）針對問題的特點，設計了兩段式編碼和基于啟發式算法的種群初始化方法；采用自適應行為模式選擇方法，使貓群個體執行不同模式下的個體位置更新；采用基于多樣化搜尋算子的搜尋模式，并設計了三種不同搜尋算子；提出了基于萊維飛行的跟蹤模式，增強了算法的局部搜索能力。此外，在算法中引入了跳躍機制，使算法性能得到了進一步改善。

（2）針對15個FJSP問題的基準算例進行算法測試，驗證了算法萊維飛行和跳躍機制的有效性，并進一步驗證了算法解決本文FJSP問題的有效性。

（3）下一步將把貓群優化算法擴展至更復雜的車間調度問題中，并結合問題的特點，設計出更加有效的算法。