貓群優(yōu)化算法求解柔性作業(yè)車間調(diào)度問題

姜天華

魯東大學(xué) 交通學(xué)院，山東 煙臺(tái) 264025

1 引言

柔性作業(yè)車間調(diào)度問題（Flexible Job Shop scheduling Problem，F(xiàn)JSP）是在經(jīng)典作業(yè)車間調(diào)度問題的基礎(chǔ)上發(fā)展而來(lái)的，它進(jìn)一步考慮了工件柔性加工路徑的特性，增加了車間調(diào)度的靈活性，但同時(shí)也給問題的求解帶來(lái)了更大的難度[1]。對(duì)于該類問題的求解，目前智能優(yōu)化算法已成為最受歡迎的方法之一，引起了國(guó)內(nèi)外學(xué)者們廣泛關(guān)注。

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

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

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

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

對(duì)于該問題，考慮以下假設(shè)條件：

（1）工件和機(jī)器零時(shí)刻均為可用狀態(tài)。

（2）同一時(shí)刻同臺(tái)機(jī)器只可加工一道工序。

（3）工序加工時(shí)不可被中斷。

（4）各工件加工優(yōu)先級(jí)相同。

（5）不考慮機(jī)器故障和機(jī)器加工前的準(zhǔn)備時(shí)間。

令Cmax表示工件最大完工時(shí)間，CiJi表示工件i的完工時(shí)間，則目標(biāo)函數(shù)可表示為：

3 基本貓群優(yōu)化算法

貓群優(yōu)化算法的搜索模式可分為搜尋模式和跟蹤模式兩種，分別對(duì)應(yīng)于全局搜索和局部搜索[7]。每次迭代過(guò)程時(shí)，首先按照一定比例對(duì)貓群個(gè)體劃分成兩個(gè)子群，然后對(duì)子群個(gè)體進(jìn)行不同模式下的位置更新，直至算法結(jié)束。

在搜尋模式下，貓群個(gè)體需預(yù)先設(shè)定改變維數(shù)的個(gè)數(shù)和維數(shù)的改變范圍，然后對(duì)原個(gè)體位置進(jìn)行一定擾動(dòng)，并填滿搜尋記憶池，評(píng)價(jià)記憶池中新個(gè)體位置后，選擇其中最優(yōu)位置替代原個(gè)體位置[9]。在跟蹤模式下，基本貓群優(yōu)化算法與粒子群算法相似，采用速度-位移更新公式，并根據(jù)全局最優(yōu)解的位置來(lái)更新貓群個(gè)體位置，如式（2）和（3）所示。

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

4 改進(jìn)貓群優(yōu)化算法

4.1 編碼方法

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

圖1 個(gè)體位置編碼

4.2 轉(zhuǎn)換方法

基本CSO算法個(gè)體位置元素為連續(xù)值，然而調(diào)度解為離散值。因此，本文采用文獻(xiàn)[10]中的轉(zhuǎn)換方法，用于解決解空間與問題空間之間的相互轉(zhuǎn)換。

（1）位置向量轉(zhuǎn)換為調(diào)度方案

①機(jī)器分配段：根據(jù)式（4）將位置向量的元素轉(zhuǎn)換成其所對(duì)應(yīng)工序可選機(jī)器集合中機(jī)器的編號(hào)。其中，2 l為個(gè)體位置向量的總長(zhǎng)度，s(k)為元素k所對(duì)應(yīng)的工序的可選機(jī)器的數(shù)量，u(k)為已選機(jī)器在工序可選機(jī)器集合中的編號(hào)，即工序可選機(jī)器集合中第u(k)個(gè)元素為工序所分配的機(jī)器。

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

圖2 位置向量轉(zhuǎn)換成工序排序

（2）調(diào)度方案向位置向量轉(zhuǎn)換

①機(jī)器分配段：按照文獻(xiàn)[10]的轉(zhuǎn)換方式，將工序所分配的機(jī)器編號(hào)轉(zhuǎn)換成[0，1]中的個(gè)體位置元素，如式（5）所示。

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

圖3 工序排序轉(zhuǎn)換成位置向量

4.3 種群初始化

分別針對(duì)調(diào)度解前后兩段進(jìn)行種群初始化，并按照4.2節(jié)中的方法將其轉(zhuǎn)換為個(gè)體位置向量。

（1）前半段采用文獻(xiàn)[11]中的啟發(fā)式算法，即全局搜索、局部搜索與隨機(jī)生成三種方式相結(jié)合來(lái)獲得初始機(jī)器分配方案。

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

②局部搜索[11]：與全局搜索相比，主要區(qū)別在于該方法每次對(duì)工件進(jìn)行機(jī)器選擇后，數(shù)組元素值需要重新置零，且在執(zhí)行過(guò)程中不存在隨機(jī)選擇工件。

③隨機(jī)生成：在各工序可選機(jī)器集合任選一臺(tái)機(jī)器加入初始調(diào)度解。

（2）后半段針對(duì)每一個(gè)已生成的機(jī)器分配方案，隨機(jī)生成法獲得若干個(gè)排序方案，評(píng)估每一個(gè)排序方案與機(jī)器分配方案的組合的適應(yīng)度值，然后選擇最優(yōu)的組合作為一個(gè)初始調(diào)度解，重復(fù)上述過(guò)程，直到生成初始種群為止。

4.4 自適應(yīng)行為模式選擇方法

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

4.5 搜尋模式

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

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

圖4 第一種鄰域結(jié)構(gòu)

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

圖5 第二種鄰域結(jié)構(gòu)

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

圖6 第三種鄰域結(jié)構(gòu)

4.6 跟蹤模式

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

4.7 跳躍機(jī)制

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

步驟1將當(dāng)前最優(yōu)個(gè)體位置作為變鄰域搜索的初始解x，令ηmax←3，λ←1，并設(shè)置最大迭代次數(shù)λmax。

步驟2設(shè)置η←1。

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

步驟4將x′作為初始解進(jìn)行局部搜索，獲取局部最優(yōu)解x″。

步驟5 若 x″優(yōu)于 x，則 x←x″，并令η←1；否則令η←η+1。

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

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

步驟8變鄰域搜索結(jié)束。

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

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

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

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

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

步驟5局部搜索結(jié)束。

5 算例分析

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

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

表1 三種算法的對(duì)比結(jié)果

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

表2 Kacem算例對(duì)比結(jié)果

表3 Brandimarte算例對(duì)比結(jié)果

圖7 算例Kacem05甘特圖

6 結(jié)束語(yǔ)

本文以工件最大完工時(shí)間為優(yōu)化目標(biāo)求解柔性作業(yè)車間生產(chǎn)調(diào)度問題，提出了一種改進(jìn)型貓群優(yōu)化算法。

圖8 算例MK10甘特圖

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

（2）針對(duì)15個(gè)FJSP問題的基準(zhǔn)算例進(jìn)行算法測(cè)試，驗(yàn)證了算法萊維飛行和跳躍機(jī)制的有效性，并進(jìn)一步驗(yàn)證了算法解決本文FJSP問題的有效性。

（3）下一步將把貓群優(yōu)化算法擴(kuò)展至更復(fù)雜的車間調(diào)度問題中，并結(jié)合問題的特點(diǎn)，設(shè)計(jì)出更加有效的算法。