基于改進人工蜂群算法的柔性作業車間調度*

王玉芳，馬銘陽，葛嘉榮，繆 昇

(南京信息工程大學 a.江蘇省大氣環境與裝備技術協同創新中心；b.自動化學院;c.江蘇省大數據分析技術重點實驗室，南京 210044)

0 引言

上世紀90年代，Brucker P[1]首次提出柔性作業車間調度問題 (Flexible Job Shop Problem, FJSP) 的概念。柔性作業車間調度問題是傳統作業車間調度的擴展，突破了資源唯一性限制，每道工序可在多臺不同的機器上加工，從而使作業車間調度問題更加貼合實際生產，所以一直是國內外的研究熱點。

黃海松等[2]提出一種改進的模擬退火的方法解決柔性調度問題，采用個體調換和局部顛倒兩種不同的搜索方式，避免算法陷入“早熟”。靳彬鋒等[3]提出一種模擬退火結合遺傳算子的混合算法，采用拉普拉斯交叉算子和逆轉變異，結合模擬退火的局部搜索能力，提高問題的求解速度與質量。近年來，因具有搜索速度快，參數少，魯棒性強等特點[4-6]，人工蜂群(Artificial Bee Colony，ABC)算法也應用到調度問題求解中。陳少等[7]在ABC算法中引入了相似度概念對種群進行分類，采用不同的搜索策略，觀察蜂選擇操作用錦標賽代替輪盤賭改善算法過早收斂現象。田野等[8]提出一種離散的ABC算法，采用自適應變異策略降低早熟收斂的可能性。Leila Asadzadeh[9]提出的并行ABC采用動態遷移策略與其他種群進行交流，結果與其他算法相比，算法的收斂速度較快。Arit Thammano等[10]提出混合ABC算法，采用迭代搜索和分散搜索進行局部搜索，利用模擬退火算法跳出局部最優解，驗證結果表明該算法能夠找到最優解或近似最優解。針對ABC算法局部搜索能力弱，容易陷入局部最優的缺陷[11-13]，上述研究進行了改進，并取得了階段性成果。但是，算法跳出局部最優能力尚存較大改進空間。

本文提出一種改進ABC算法，通過改進初始解的生成方法及三種蜜蜂的操作，提高算法的尋優能力和魯棒性，改善算法陷入局部最優的問題。

1 問題描述

柔性作業車間調度問題描述如下：有m(M1,M2,...,Mm)臺機器處理n(J1,J2,...,Jn)個工件，每個工件有若干道工序，Oij表示工件i的第j道工序，每道工序可以在不同機器上進行加工，且在不同的機器上的加工時間是不相同的。根據資源選擇條件限制，柔性作業車間調度問題分為完全柔性作業車間調度問題和部分柔性作業車間調度問題，完全柔性作業車間調度問題中每一個工件的任意一道工序可以選擇車間中任意機器加工；而部分柔性作業車間調度問題至少存在一道工序只能選擇車間部分機器進行加工。兩種類型如表1和表2所示，這是一個包括3個工件、3臺機器的加工時間表，表中數據表示工序在機器上的加工時間，“—”表示工序不能在該機器上加工。

表1 完全柔性作業車間調度問題實例

表2 部分柔性作業車間調度問題實例

調度目標是通過為各工序選擇合適的機器進行加工以及調整各個機器上工序加工的先后順序來使最大完成時間最小。本文中的時間均為抽象的單位時間，此外，在加工過程中還需要滿足下列的約束條件：

(1) 任意工件都可以從零時刻開始被處理；

(2) 同一時間同一臺機器上只可以處理一個工件；

(3) 同一個工件的同一道工序在同一時間只能被一臺機器處理，直到該工序處理完成；

(4) 同一個工件的工序之間有先后順序約束，但是不同工件的工序沒有先后順序約束；

(5) 不同的工件之間沒有先后順序的約束。

定義如下數學符號用于問題的數學描述：

n：工件總數。

m：機器總數。

i：工件序號，i=1,2,3,...,n。

h：機器序號，h=1,2,3,...,m。

ei：第i個工件的工序數。

j：第i個工件的工序號，j=1,2,3,...,ei。

Oij：第i個工件的第j道工序。

Oijh：第i個工件的第j道工序在機器Mh上加工。

tijh： 第i個工件的第j道工序在機器Mh上加工所需時間。

sij：第i個工件的第j道工序加工開始時間。

cij：第i個工件的第j道工序加工完成時間。

K：一個特別大的正數。

Ci：工件Ji的完工時間。

Cmax：最大完成時間。

目標函數及約束條件如下：

f=min{maxCi}

(1)

s.t.

ci0=0

(2)

sij+xijh×tijh≤cij

(3)

ci(j-1)≤sij

(4)

cij≤Cmax

(5)

sij+tijh≤skl+K(1-yijhkl)

(6)

ci(j-1)≤sij+K(1-yijhkj)

(7)

(8)

sij≥0,cij≥0

(9)

其中，式(1)表示本文所求的目標函數：最小化最短完成時間；式(2)表示虛擬的第零道工序完工時間為零；式(3)和式(4)表示同一個工件包含的工序必須按照先后順序處理；式(5)表示任意工序的完成時間不超過總的完成時間；式(6)和式(7)表示在某一時刻的一臺機器上只允許處理一道工序；式(8)表示在某一時刻同一道工序只能在一臺機器上處理；式(9)表示任意工序的開始時間和完成時間都是非負的，且任意工件都可以從0時刻開始加工。

2 改進的ABC算法

2005年，Karaboga D[14]在總結了前人的研究成果之后，提出了ABC算法。該算法模型主要包含蜜源和蜜蜂兩大要素。蜜源相當于需解決優化問題的可行解；蜜蜂分為雇傭蜂、觀察蜂和偵查蜂三種類別。雇傭蜂與蜜源的位置相對應，所有雇傭蜂的數量與蜜源相等，且具有記憶功能，能夠把搜索到的蜜源信息存儲起來，根據蜜源的好壞，按一定的概率分享給觀察蜂。觀察蜂得到雇傭蜂分享的信息之后，選擇滿意的蜜源信息進行跟隨，觀察蜂的數量等同于雇傭蜂。偵查蜂則按一定規則搜索新的蜜源位置。三種蜜蜂之間可以互相轉換，這是蜂群算法特有的機制，其轉換關系如圖1所示。

圖1 雇傭蜂、觀察蜂和偵查蜂轉換關系圖

2.1 編碼與解碼

標準ABC算法是處理連續解空間的啟發式算法，無法直接應用于柔性作業車間調度這種離散問題，因此針對該問題需進行合適的編碼。考慮此問題存在兩個相應的子問題，即作業在機器上的加工順序和加工工序選擇機器問題，所以采用雙層編碼的形式。第一層是工序層，用來確定工序的加工順序；第二層是機器層，用來表示各工序選擇的機器。每一層的長度和工序的總數相同。

工序串編碼如圖2所示，假設工序串為[3 1 2 1 2 2]，則第一個3表示工件3的第一道工序，同理，第一個1表示工件1的第一道工序，而在第四個位置上的1則表示工件1的第二道工序；每個數字出現的次數等于對應的該道工件的工序數。所以圖2中工序串的加工順序O31→O11→O21→O12→O22→O23。

圖2 工序串編碼示意圖

機器串編碼如圖3所示，機器串編碼是從左到右按工件序號以及各工件中工序的順序來排序。第一個位置上的數字2表示該工序選擇其可選機器集中的第二個機器M2進行加工，同理第五個位置上的數字1表示該位置的工序選擇其可選機器加工集的第一個機器M3進行加工；與圖2的工序串對應起來即工序O11在機器M2上加工，工序O23在機器M3上加工。

圖3 機器串編碼示意圖

2.2 種群初始化

種群初始化方法對算法的求解質量和求解速度有很大的影響，若完全使用隨機方法生成初始種群，則初始解優劣不一，隨機性過強，初始解的質量很難得到保障，這勢必會影響搜索最優解的速度，導致需要以增加迭代次數和種群大小為代價來獲得最優解，進而增加優化時間。為了避免上述問題，本文采用隨機選擇和按規則選擇相結合的方法實現種群初始化。

在機器串編碼中，采用三種初始解生成規則，全局選擇(global selection, GS)、局部選擇(local selection, LS)和隨機選擇(random selection, RS)[15]。GS和LS能夠盡可能地平衡每臺機器上的負荷，提高機器的利用率，在一定程度上減小初始解的最大完工時間；而具有強隨機性的隨機選擇可以取到解空間中的任意解，保證初始解的多樣性。

在工序串編碼中，本文采用剩余負荷最大規則(maximum residual load, MRL)、加工時間最短優先(shortest process time, SPT)規則和隨機選擇(random selection, RS)三種規則。MRL把各個工件的剩余加工時間統計排序，優先加工剩余加工時間最長的工件；SPT優先處理剩余加工時間短的工件；RS把各個工序進行隨機排序選擇。

機器串生成規則GS/LS/RS的選擇概率分別為30%、30%和40%，工序串的生成規則MRL/SPT/RS的選擇概率分別為30%、30%和40%。

2.3 雇傭蜂操作

針對柔性作業車間調度問題，對傳統的雇傭蜂操作進行改進，采用兩種交叉方法，第一種是在工序串上進行IPOX交叉[16]，第二種在機器串上進行多點交叉的操作。這兩種方法不會產生非法解，同時還能把父代個體中的優良基因傳遞到下一代。

(1)IPOX交叉

首先通過初始解求得目標函數值，然后計算適應度值，選取適應度值最大的工序串為全局最優解。具體操作過程如下：

步驟1：從種群中選擇一條工序串作為父代X1，生成一個0～1之間的隨機數，若隨機數小于0.5，選擇全局最優解為X2；若隨機數在0.5～1之間，則種群中選出另一條工序串作為X2(即X2不能與X1相同)；

步驟2：把n個工件J1,J2,...,Jn分為兩個互補的工件集R1和R2；

步驟3：把父代X1中包含在R1工件集中的工序號按照在X1中的位置復制到子代C1中，把X2中包含在R2工件集中的工序按照原順序插入到子代C1的空缺處；

步驟4：把父代X2中包含在R2工件集中的工序號按照在X2中的位置復制到子代C2中，把X1中包含在R1工件集中的工序按照原順序插入到子代C2的空缺處；

步驟5：計算子代C1和C2的適應度值，選擇適應度值較大的子代作為交叉后的子代；

步驟6：計算子代染色體適應度值，若其大于父代X1的適應度值則替換，否則不改變。

(2)多點交叉操作

多點交叉作用于機器串的交叉操作，因為交叉的是同一工序的可用機器，所以不會產生非法解，具體步驟如下：

步驟1：選則與父代X1工序串對應的機器串作為機器串父代P1，選則與父代X2工序串對應的機器串作為機器串父代P2；

步驟2：隨機生成一個由0和1組成的長度與機器串相等的二進制串；

步驟3：把父代P1中與二進制串中與1位置相同的機器號復制到子代S1的相同位置；把父代P2中與二進制串中與0位置相同的機器號復制到子代S1的相同位置；

步驟4：把父代P2中與二進制串中與1位置相同的機器號復制到子代S2的相同位置；把父代P1中與二進制串中與0位置相同的機器號復制到子代S2的相同位置；

步驟5：計算子代S1和S2的適應度值，選擇適應度值大的作為機器串多點交叉后的子代；

步驟6：計算子代染色體適應度值，若其大于父代P1的染色體的適應度值則替換，否則不改變。

2.4 觀察蜂操作

觀察蜂采用輪盤賭[17]的選擇方式，根據蜜源的適應度值選擇蜜源的位置，蜜源的適應度值越高，選擇該蜜源位置的概率越大。依據式(10)計算選擇概率，fitw是第w個解對應的適應度值，D為蜜源的數量，等于種群NP的一半，如式(11)：

(10)

(11)

蜜源的適應度值按式(12)計算，objw是蜜源w的目標值：

fitw=1/(1+objw)

(12)

工序串采用變換步長策略對選擇的蜜源位置附近進行搜索，大步長交換可行解中多對工序的順序，易產生顯著變化，增強全局搜索能力，避免陷入局部最優；而小步長交換可行解中一對工序的順序，這種變化很小，適合在當前解空間進行更深一步地搜索，加快算法向最優解靠近。對于變步長策略來說，需要設定一個閾值，使大步長與小步長有機結合，當搜索次數小于閾值時進行小步長搜索，反之進行大步長搜索，同時把搜索次數變量清零；計算適應度值，用貪婪策略選擇適應度高的個體，以保證種群能夠保留精英個體。

對工序串進行插入變異，從工序串中選擇任意一道工序插入到工序串中任意位置，其他工序按原有順序排序，計算適應度值，用貪婪策略保留最優解；對機器串進行變異操作，任意選取一道工序，在其可選機器集中隨機選擇一臺機器進行變異，同時計算適應度值，用貪婪策略選擇適應度高的染色體保留到下一代種群中。

2.5 偵查蜂操作

在標準ABC算法中，若雇傭蜂在同一個蜜源的適應度值超過limit次(最大搜索次數)沒有改進，雇傭蜂轉換為偵查蜂，隨機產生一個新的解，但是每次只有一只雇傭蜂轉換為偵查蜂，隨機生成的一個新解對于種群的影響較小，不利于算法跳出局部最優解。因此，本文對偵查蜂進行改進，若Y個蜜源經過limit次而沒有改進，則采用本文2.2節的種群初始化方法生成Y個新蜜源，通過增加偵查蜂的數量來保持種群的多樣性，利于提高算法的全局搜索能力。

2.6 算法流程

根據上述改進策略，結合柔性作業車間調度問題，提出改進的ABC算法，如圖4所示。

主要包括以下步驟：

步驟1：建立柔性作業車間調度模型；

步驟2：確定調度的約束條件；

步驟3：初始化種群以及設置參數；

步驟4：計算適應度值，雇傭蜂進行IPOX交叉和多點交叉操作；

步驟5：計算各蜜源適應度值，并且計算觀察蜂選擇跟隨各雇傭蜂的概率；

步驟6：觀察蜂采用變步長搜索策略，并且進行變異操作；

步驟7：判斷蜜源是否達到最大搜索次數，若滿足條件則雇傭蜂轉換為偵查蜂，搜索新的蜜源，否則到步驟8；

步驟8：判斷算法是否達到最大迭代次數，如果是則算法結束；如果未達到最大迭代次數，則跳轉到步驟4。

圖4 改進的ABC算法流程圖

3 實驗分析

為了驗證所提算法在求解柔性作業車間調度問題的有效性，本文與文獻[18-19]和文獻[7]提出的算法性能進行比較，均采用Kacem標準測試集[18]中的8×8和10×10兩個算例來測試算法的性能。8×8是8個工件在8臺機器上加工的部分柔性作業車間調度問題算例，10×10是10個工件在10臺機器上加工的完全柔性作業車間調度問題算例。

本文改進的ABC算法采用Matlab編程實現，程序在Windows 10系統，主頻為3.4 GHz，內存為8 G的個人電腦上運行。對于上述兩個算例，算法參數設置如下：種群NP=200；最大迭代次數maxCycle=100；最大搜索次數limit=20； 搜索閾值threshold=5；將算法運行10次，并與文獻[18]中Kacem所得到的結果、文獻[19]所提的IGA算法和文獻[7]中的改進ABC算法的運行結果相比較，比較結果如表3所示(Cmax表示10次運行中所得的最優值，Aver表示10 次運行的平均值)。

表3 四種算法結果比較

從表1中可以看出本文算法在8×8和10×10算例中均能找到最優解，說明改進ABC算法具有較好的尋優能力。值得說明的是，算法10次運行找到最優解的平均值更小，可以看出算法中的改進策略是有效的，變步長策略既保證了局部搜索的能力，又增強了算法全局搜索能力，有效避免啟發式算法易陷入局部最優的局限性，算法收斂性和魯棒性好。

8×8問題和10×10問題的最優解甘特圖如圖5、圖6所示，橫坐標為完工時間，是抽象時間單位，縱坐標為機器號；圖7為改進ABC算法的進化曲線，橫坐標為迭代次數，縱坐標為完成時間。

圖5 8×8最優解甘特圖

圖6 10×10最優解甘特圖

圖7 兩個算例的進化曲線

從算例的進化曲線中可以看出種群均值時而會產生退化，這是由于偵查蜂數量增多，產生新的初始解導致種群均值增大，但是在種群均值退化的同時，全局最優解曲線也會向下降，找到更好的全局最優解，而且從算法收斂曲線可以看到退化只是暫時的，總體趨勢還是向最優解靠近，說明增加偵查蜂數量可以有效地使算法跳出局部最優。

4 結論

針對柔性作業車間調度問題，以最大完工時間最小為目標，提出了改進的ABC算法，種群的初始化采用隨機選擇與按規則選擇相結合的方法，減少了生成過差初始解的可能，同時避免了因依賴按規則選擇產生初始解導致的算法早熟。算法在雇傭蜂操作中通過IPOX交叉策略來對蜜源進行搜索，并提出全局最優解或者任意解與當前蜜源進行交叉操作，提高了算法的收斂速度；在觀察蜂階段采用變步長策略提高算法的全局搜索能力，提升算法跳出局部最優的可能性；為了保持種群的多樣性，增加了偵查蜂的數量。通過實驗算例驗證了改進算法突出的尋優能力和收斂性。后續將研究綠色柔性作業車間調度問題，響應國家提出的綠色制造號召。