姚 雄，張永平

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

0 引言

調(diào)度是工業(yè)，尤其是制造業(yè)的基本活動之一。它對于計劃工作、流程時間以及如何處理資源非常重要，它規(guī)劃了任務(wù)的完成時間和工作活動之間的關(guān)系。作業(yè)車間調(diào)度問題(job-shop scheduling problem，JSP)是離散制造系統(tǒng)中最經(jīng)典的調(diào)度問題。JSP作為最困難的組合優(yōu)化問題之一，是一個著名的NP-hard問題，即沒有一種算法能在多項式時間內(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]等。遺傳算法是一種基于達爾文進化論和孟德爾遺傳學(xué)說的隨機自適應(yīng)搜索算法。該算法的主要操作包括相似物種在進化過程中的遺傳選擇、交叉和變異。粒子群算法模仿了簡單的社會系統(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)化方向入手，實現(xiàn)作業(yè)車間高效合理的調(diào)度。

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

1.1 問題描述

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

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

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

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

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

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

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

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

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

2 海洋捕食者算法

海洋捕食者算法是Faramarzi等[7]在2020年提出的一種新型元啟發(fā)式算法，是利用布朗運動和萊維飛行模擬海洋捕食者覓食獵物的物理行為。該算法通過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為運動步長；RB為布朗運動，它是一個正態(tài)分布的隨機矢量；R為[0,1] 中的均勻隨機向量；P為常數(shù) 0.5；It為當(dāng)前迭代次數(shù)；Mt為最大迭代次數(shù)。

(11)

(12)

RLYi是用來模擬獵物的運動；RL為基于萊維運動的隨機向量。

(13)

(14)

RB?Ei是用來模擬捕食者的運動；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]中的隨機數(shù)；Xmax和Xmin為獵物位置的上下限；U為一個值為0和1的二進制向量；Yr1和Yr2為隨機選擇的2個獵物位置。

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

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

3 離散海洋捕食者算法

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

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

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

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

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

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

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

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

Oi=Xmin+Xmax-Xi

(19)

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

新位置有更多的機會來尋找到最佳解。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ì)的混沌變量的方法，而不是隨機變量?；煦缧蛄写嬖谟趧討B(tài)和非線性系統(tǒng)中，并且是非周期性的、非收斂的和有界的[14]。因此，混沌映射比基于概率的隨機搜索擁有更高的收斂速度，而且執(zhí)行簡單。由于混沌序列的動態(tài)行為，在元啟發(fā)式的算法中使用混沌變量而不是隨機變量將有助于更好地探索搜索空間。

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

(20)

xi+1為當(dāng)前迭代產(chǎn)生的混沌隨機數(shù)；xi為上一次迭代產(chǎn)生的混沌隨機數(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ā)。因此，為了進一步提高勘探與開發(fā)的平衡性，增強全局勘探能力，促進局部開發(fā)的快速收斂，本文使用了一種新的非線性步長參數(shù)控制策略，定義為

(21)

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

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

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

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

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

4 實驗結(jié)果與分析

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

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

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

在圖6中，縱坐標(biāo)為操作機器號；每個矩形代表1個工序，其左右邊界分別為工序的開始時間和結(jié)束時間。以3號工件為例，其第1道工序在3號機器加工(301)，第2道工序在4號機器加工(302)，第3道工序在6號機器加工(303)……直至其第6道工序(最后一步)在5號機器完成(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é)果進行對比，從而測試DMPA求解JSP的性能；ACA和TSA結(jié)果數(shù)據(jù)來源于文獻[15]，WOA結(jié)果數(shù)據(jù)來源于文獻[16]。DMPA參數(shù)按照文獻[16]設(shè)置，初始種群規(guī)模為200，最大迭代次數(shù)為100；實驗結(jié)果如表1所示，較好的結(jié)果用粗體標(biāo)出。

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

表1中的“/”表示文獻[15]沒有進行測試。從表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ù)提高了算法的收斂速度，改進了原算法的自適應(yīng)步長策略從而更好地平衡全局勘探和局部開發(fā)。通過對7個基準(zhǔn)算例的仿真實驗，證明了本文算法的有效性和優(yōu)越性。