求解作業(yè)車間調(diào)度問題的離散海洋捕食者算法

姚 雄，張永平

(1.鹽城工學(xué)院機(jī)械工程學(xué)院，江蘇 鹽城 224051；2.鹽城工學(xué)院信息工程學(xué)院，江蘇 鹽城 224051)

0 引言

調(diào)度是工業(yè)，尤其是制造業(yè)的基本活動之一。它對于計(jì)劃工作、流程時間以及如何處理資源非常重要，它規(guī)劃了任務(wù)的完成時間和工作活動之間的關(guān)系。作業(yè)車間調(diào)度問題(job-shop scheduling problem，JSP)是離散制造系統(tǒng)中最經(jīng)典的調(diào)度問題。JSP作為最困難的組合優(yōu)化問題之一，是一個著名的NP-hard問題，即沒有一種算法能在多項(xiàng)式時間內(nèi)收斂到問題的最優(yōu)解。許多學(xué)者提出了一些啟發(fā)式和基于優(yōu)化的調(diào)度算法，以提高制造效率和降低其成本為目標(biāo)來解決JSP[1-3]。

由于作業(yè)車間調(diào)度問題的規(guī)模和約束，當(dāng)前大多數(shù)研究都集中在啟發(fā)式和元啟發(fā)式算法的使用上，廣為人知的有遺傳算法(genetic algorithm，GA)、粒子群算法(particle swarm optimization，PSO)[4]和蟻群算法(ant colony algorithm，ACO)[5]等。遺傳算法是一種基于達(dá)爾文進(jìn)化論和孟德爾遺傳學(xué)說的隨機(jī)自適應(yīng)搜索算法。該算法的主要操作包括相似物種在進(jìn)化過程中的遺傳選擇、交叉和變異。粒子群算法模仿了簡單的社會系統(tǒng)，最初是用于模擬鳥類搜索食物的過程，但后來被發(fā)現(xiàn)是一種很好的優(yōu)化算法。蟻群算法模擬了螞蟻的覓食行為，已成功地應(yīng)用于許多離散優(yōu)化問題。近年來，新提出的鯨魚優(yōu)化算法(whale optimization algorithm，WOA)也獲得了許多學(xué)者的關(guān)注和研究[6]。

為了獲得更優(yōu)良的作業(yè)車間調(diào)度結(jié)果，本文提出了一種海洋捕食者算法(marine predators algorithm，MPA)的離散變體，稱為離散海洋捕食者算法 (discrete marine predators algorithm，DMPA)，并從對立學(xué)習(xí)、混沌映射及自適應(yīng)步長策略等優(yōu)化方向入手，實(shí)現(xiàn)作業(yè)車間高效合理的調(diào)度。

1 JSP描述及數(shù)學(xué)模型

1.1 問題描述

JSP一般描述為在給定加工工藝、機(jī)床順序和每個工件的加工時間下，通過合理安排n個工件在m臺機(jī)器上的加工順序來優(yōu)化性能指標(biāo)。求解作業(yè)車間調(diào)度問題時的基本約束條件如下：

a.每個工件都有若干要完成的工序。

b.每個工件不能同時在多個機(jī)器上加工。

c.每道工序的加工時間在每臺機(jī)器上是確定的。

d.所有工件都在0時刻可用。

e.每臺機(jī)器在同一時段內(nèi)最多可處理1道工序。

f.所有工序必須在1組機(jī)器上完成。

1.2 數(shù)學(xué)模型

本文將JSP用整數(shù)規(guī)劃模型描述為

min max1≤j≤mcij

(1)

1≤i≤n

約束于：

cij-tij+M(1-aihj)≥cih

(2)

ckj-cij+M(1-xikj)≥tkj

(3)

cij≥0

(4)

aihj、xikj=0,1

(5)

i、k=1,2,…,n

(6)

j、h=1,2,…,m

(7)

tij為工件i在機(jī)器j上的加工時間；cij為工件i在機(jī)器j上的完成時間；aihj為指示系數(shù)，aihj= 1表示在加工工件i時機(jī)器h早于機(jī)器j，aihj= 0表示在加工工件i時機(jī)器j早于機(jī)器h；xikj為指示變量，xikj= 1表示在機(jī)器j上，工件i早于工件k加工，xikj= 0表示在機(jī)器k上，工件i早于工件j加工；M為足夠大的正數(shù)。

式(1)確定了JSP的目標(biāo)：使最大完工時間最小化。

2 海洋捕食者算法

海洋捕食者算法是Faramarzi等[7]在2020年提出的一種新型元啟發(fā)式算法，是利用布朗運(yùn)動和萊維飛行模擬海洋捕食者覓食獵物的物理行為。該算法通過E矩陣和Y矩陣的迭代更新來完成目標(biāo)(最佳解)的獲取。E是頂級捕食者(最佳解)，捕食者根據(jù)獵物Y的位置更新自己的位置。與其他基于種群的算法不同，在MPA中捕食者并不總是搜索者，有時獵物也是搜索者。MPA的數(shù)學(xué)模型表示為

(8)

XI為頂級捕食者；Xi,j為第i個獵物的第j個維度；n為種群數(shù)量；d為維度。

根據(jù)捕食者和獵物的壽命,MPA的迭代優(yōu)化過程分為3個階段。在第1個階段，獵物是搜索者，捕食者是目標(biāo)；在第2個階段，捕食者和獵物可以同時是搜索者和目標(biāo)；在最后階段，捕食者是搜索者。這3個階段的數(shù)學(xué)模型如下：

Si=RB?(Ei-RB?Yi)i=1,2,…,n

(9)

Yi=Yi+(P·R?Si)i=1,2,…,n

(10)

S為運(yùn)動步長；RB為布朗運(yùn)動，它是一個正態(tài)分布的隨機(jī)矢量；R為[0,1] 中的均勻隨機(jī)向量；P為常數(shù) 0.5；It為當(dāng)前迭代次數(shù)；Mt為最大迭代次數(shù)。

(11)

(12)

RLYi是用來模擬獵物的運(yùn)動；RL為基于萊維運(yùn)動的隨機(jī)向量。

(13)

(14)

RB?Ei是用來模擬捕食者的運(yùn)動；CF為步長控制參數(shù)，其更新方式為

(15)

Si=RL?(RL?Ei-Yi)i=1,2,…,n

(16)

Yi=Ei+P·CF?Sii=1,2,…,n

(17)

然而，捕食過程中可能會受到渦流形成或魚類聚集裝置(FA)影響而陷入局部最優(yōu)，因此采用較長的步長跳躍來避免局部收斂。跳躍方式為：

Yi=

(18)

FA= 0.2；r為[0,1]中的隨機(jī)數(shù)；Xmax和Xmin為獵物位置的上下限；U為一個值為0和1的二進(jìn)制向量；Yr1和Yr2為隨機(jī)選擇的2個獵物位置。

最后，在每次迭代結(jié)束時，通過海洋記憶將當(dāng)前解與前一次迭代的解進(jìn)行比較，選擇適應(yīng)度更高的解來提高種群質(zhì)量。

MPA在理論上是成功的，有許多學(xué)者研究了它在連續(xù)數(shù)學(xué)函數(shù)領(lǐng)域的優(yōu)化及改進(jìn)[8-10]；但是其也存在求解精度低和收斂速度慢的不足，無法創(chuàng)造出高質(zhì)量初始種群，也沒有離散化的版本應(yīng)用于實(shí)際問題。

3 離散海洋捕食者算法

3.1 位置向量與調(diào)度解之間的轉(zhuǎn)換機(jī)制

海洋捕食者算法是為優(yōu)化各種連續(xù)型非線性函數(shù)而提出的，而作業(yè)車間調(diào)度問題屬于典型的組合優(yōu)化問題，是離散型問題。由于MPA中獵物位置向量不是用離散值生成的，所以需要對這些連續(xù)的位置值進(jìn)行編碼。離散個體更新方法旨在確保算法能直接在離散域中工作。

本文采用最小位置值法(smallest position value，SPV)[11]對調(diào)度解和位置向量進(jìn)行轉(zhuǎn)換。如圖1所示，對于已有的1組調(diào)度解(工序)，先產(chǎn)生1組相應(yīng)的隨機(jī)數(shù)，隨機(jī)數(shù)的索引值依據(jù)SPV規(guī)則按從小到大排序，此SPV值與工序一一對應(yīng)；之后按照工序號的編碼順序?qū)PV值進(jìn)行重排；最后重排的每個SPV值對應(yīng)的隨機(jī)數(shù)即為位置向量中元素的值。逆過程如圖2所示。

圖1 調(diào)度解轉(zhuǎn)為位置向量

圖2 位置向量轉(zhuǎn)為調(diào)度解

3.2 對立學(xué)習(xí)初始化

在元啟發(fā)式算法中，優(yōu)化過程從隨機(jī)產(chǎn)生的初始種群開始，原海洋捕食者算法也不例外。如果隨機(jī)生成的初始種群接近最優(yōu)解，則很可能會更快地得到正確解。但隨機(jī)生成的部分個體往往會分布在遠(yuǎn)離最優(yōu)解的無效區(qū)域和邊緣區(qū)域，故優(yōu)化過程也可能是從最優(yōu)解距離最遠(yuǎn)的位置處開始，在這種情況下搜索將花費(fèi)更長的時間，甚至可能無法得到最優(yōu)解，進(jìn)而降低了種群的搜索效率。

對立學(xué)習(xí)(opposition-based learning，OBL)是2005年由Tizhoosh[12]作為機(jī)器智能的新方案首次引入的，該方法被認(rèn)為是計(jì)算智能中的一個強(qiáng)大的數(shù)學(xué)概念[13]。策略為

Oi=Xmin+Xmax-Xi

(19)

Xi為當(dāng)前向量；Oi為Xi的相反位置；Xmin和Xmax分別為問題中變量的下界和上界。

新位置有更多的機(jī)會來尋找到最佳解。Oi由目標(biāo)函數(shù)評估，如果Oi比Xi處于更好的位置，Xi將被替換。在目標(biāo)函數(shù)上下界限對稱的時候，由式(19)可以看出，所生成的反向解為原來解的完全鏡像(取負(fù))，對部分具有偶函數(shù)特性的函數(shù)，完全鏡像解與原解目標(biāo)值一致，不適合將2個種群做適應(yīng)度排序，無法有效獲得高質(zhì)量種群。但作業(yè)車間調(diào)度問題不是偶函數(shù)，上下界不對稱，因此適用對立學(xué)習(xí)策略去提高初始種群的質(zhì)量。

3.3 混沌映射

混沌映射是一種使用具有不可預(yù)測性質(zhì)的混沌變量的方法，而不是隨機(jī)變量。混沌序列存在于動態(tài)和非線性系統(tǒng)中，并且是非周期性的、非收斂的和有界的[14]。因此，混沌映射比基于概率的隨機(jī)搜索擁有更高的收斂速度，而且執(zhí)行簡單。由于混沌序列的動態(tài)行為，在元啟發(fā)式的算法中使用混沌變量而不是隨機(jī)變量將有助于更好地探索搜索空間。

不同的混沌映射已被用于優(yōu)化算法，通過改變它們的初始條件，可以很容易地生成不同的序列。本文算法采用圓形混沌映射(circle map)函數(shù)來提高M(jìn)PA的收斂速度，將原算法中的關(guān)鍵隨機(jī)數(shù)替換為混沌函數(shù)的變量數(shù)。從而廣泛地探索空間，以獲得更好的結(jié)果，使其避免陷入局部最優(yōu)。過程表示為

(20)

xi+1為當(dāng)前迭代產(chǎn)生的混沌隨機(jī)數(shù)；xi為上一次迭代產(chǎn)生的混沌隨機(jī)數(shù)；a和b分別為0.5和0.2；x0為0.01；mod為求余函數(shù)。圖3為圓形混沌映射函數(shù)視圖。

圖3 圓形混沌映射函數(shù)

3.4 非線性步長控制策略

在MPA迭代優(yōu)化中，步長控制參數(shù)CF對全局勘探和局部開發(fā)的平衡性影響較大。由式(14) ～ 式(18)可知，在迭代過程中，CF從1降低到0，較大的步長控制參數(shù)有利于全局探索，較小的步長控制參數(shù)有利于開發(fā)。因此，為了進(jìn)一步提高勘探與開發(fā)的平衡性，增強(qiáng)全局勘探能力，促進(jìn)局部開發(fā)的快速收斂，本文使用了一種新的非線性步長參數(shù)控制策略，定義為

(21)

為了驗(yàn)證所提出的控制參數(shù)的有效性，將本文提出的控制參數(shù)與原始的MPA非線性控制參數(shù)策略(式(15))進(jìn)行對比。如圖4所示，本文采用的非線性控制參數(shù)在早期緩慢減小，增加了全局搜索的時間；在后期迅速減小，在算法后期盡快收斂。

圖4 步長參數(shù)對比

3.5 離散海洋捕食者算法流程

綜上所述，離散海洋捕食者算法在原算法的基礎(chǔ)上，增加個體位置與調(diào)度解間的轉(zhuǎn)換方法，使用對立學(xué)習(xí)方法優(yōu)化初始種群，采用圓形混沌映射函數(shù)來提高算法的收斂速度，改進(jìn)自適應(yīng)步長策略從而更好地平衡勘探和開發(fā)。離散海洋捕食者流程如圖5所示。

圖5 離散海洋捕食者算法流程

4 實(shí)驗(yàn)結(jié)果與分析

4.1 基準(zhǔn)算例仿真

用FT06作為基準(zhǔn)算例進(jìn)行仿真來驗(yàn)證DMPA的算法性能，該算例為6(工件)×6(機(jī)器)的典型JSP問題，經(jīng)過DMPA計(jì)算得到最優(yōu)調(diào)度序列，甘特圖如圖6所示。

圖6 FT06調(diào)度結(jié)果甘特圖

在圖6中，縱坐標(biāo)為操作機(jī)器號；每個矩形代表1個工序，其左右邊界分別為工序的開始時間和結(jié)束時間。以3號工件為例，其第1道工序在3號機(jī)器加工(301)，第2道工序在4號機(jī)器加工(302)，第3道工序在6號機(jī)器加工(303)……直至其第6道工序(最后一步)在5號機(jī)器完成(306)。從圖中可看出該算例最大完工時間(Makespan)為55，這也是FT06問題已知的最優(yōu)解，證明了該算法的可行性與有效性。

4.2 算法性能評價

將本文所提出的DMPA應(yīng)用于JSP的7個基準(zhǔn)算例，這7個基準(zhǔn)算例具有不同的問題規(guī)模，比較具有代表性。將其與蟻群算法(ant colony algorithm，ACA)、禁忌搜索算法(tabu search algorithm，TSA)及鯨魚優(yōu)化算法(whale optimization algorithm，WOA)得到的結(jié)果進(jìn)行對比，從而測試DMPA求解JSP的性能；ACA和TSA結(jié)果數(shù)據(jù)來源于文獻(xiàn)[15]，WOA結(jié)果數(shù)據(jù)來源于文獻(xiàn)[16]。DMPA參數(shù)按照文獻(xiàn)[16]設(shè)置，初始種群規(guī)模為200，最大迭代次數(shù)為100；實(shí)驗(yàn)結(jié)果如表1所示，較好的結(jié)果用粗體標(biāo)出。

表1 算法結(jié)果對比

表1中的“/”表示文獻(xiàn)[15]沒有進(jìn)行測試。從表1可以看出，無論是較早的蟻群算法(1992年提出)、禁忌搜索算法(1986年提出)，還是新興的鯨魚優(yōu)化算法(2016年提出)，DMPA都更具有優(yōu)越性。在求解LA01、LA05這些較小規(guī)模問題時，DMPA可取得最優(yōu)解。在求解LA16、FT10、LA21這些中等規(guī)模問題時，這些算法均不能取得最優(yōu)解，DMPA僅在LA16這個問題上次于ACA，其他問題DMPA結(jié)果均更具有優(yōu)勢。而在處理大規(guī)模問題LA36、LA26時，DMPA比WOA表現(xiàn)出非常明顯的優(yōu)勢，能夠得到更好的結(jié)果。

5 結(jié)束語

MPA作為目前新穎的一種元啟發(fā)式算法，針對于它的廣泛應(yīng)用還在研究和探索之中。本文將提出的離散海洋捕食者算法(DMPA)用于求解JSP問題，提高了海洋捕食者算法的適用性。DMPA使用對立學(xué)習(xí)方法增加了初始種群的多樣性，采用圓形混沌映射函數(shù)提高了算法的收斂速度，改進(jìn)了原算法的自適應(yīng)步長策略從而更好地平衡全局勘探和局部開發(fā)。通過對7個基準(zhǔn)算例的仿真實(shí)驗(yàn)，證明了本文算法的有效性和優(yōu)越性。