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

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

0 引言

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

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

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

1 問題描述

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

表1 完全柔性作業(yè)車間調(diào)度問題實例

表2 部分柔性作業(yè)車間調(diào)度問題實例

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

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

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

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

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

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

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

n：工件總數(shù)。

m：機器總數(shù)。

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

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

ei：第i個工件的工序數(shù)。

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：一個特別大的正數(shù)。

Ci：工件Ji的完工時間。

Cmax：最大完成時間。

目標函數(shù)及約束條件如下：

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

2 改進的ABC算法

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

圖1 雇傭蜂、觀察蜂和偵查蜂轉(zhuǎn)換關(guān)系圖

2.1 編碼與解碼

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

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

圖2 工序串編碼示意圖

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

圖3 機器串編碼示意圖

2.2 種群初始化

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

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

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

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

2.3 雇傭蜂操作

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

(1)IPOX交叉

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

步驟1：從種群中選擇一條工序串作為父代X1，生成一個0～1之間的隨機數(shù)，若隨機數(shù)小于0.5，選擇全局最優(yōu)解為X2；若隨機數(shù)在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)多點交叉操作

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

步驟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]的選擇方式，根據(jù)蜜源的適應度值選擇蜜源的位置，蜜源的適應度值越高，選擇該蜜源位置的概率越大。依據(jù)式(10)計算選擇概率，fitw是第w個解對應的適應度值，D為蜜源的數(shù)量，等于種群NP的一半，如式(11)：

(10)

(11)

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

fitw=1/(1+objw)

(12)

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

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

2.5 偵查蜂操作

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

2.6 算法流程

根據(jù)上述改進策略，結(jié)合柔性作業(yè)車間調(diào)度問題，提出改進的ABC算法，如圖4所示。

主要包括以下步驟：

步驟1：建立柔性作業(yè)車間調(diào)度模型；

步驟2：確定調(diào)度的約束條件；

步驟3：初始化種群以及設(shè)置參數(shù)；

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

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

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

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

步驟8：判斷算法是否達到最大迭代次數(shù)，如果是則算法結(jié)束；如果未達到最大迭代次數(shù)，則跳轉(zhuǎn)到步驟4。

圖4 改進的ABC算法流程圖

3 實驗分析

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

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

表3 四種算法結(jié)果比較

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

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

圖5 8×8最優(yōu)解甘特圖

圖6 10×10最優(yōu)解甘特圖

圖7 兩個算例的進化曲線

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

4 結(jié)論

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