基于動態學習和個體淘汰的鯨魚算法求解訂單接受與調度問題

任丹萍，鄭子威，陳湘國

(1.河北工程大學 信息與電氣工程學院，河北 邯鄲 056038； 2.河北工程大學 河北省安防信息感知與處理重點實驗室，河北 邯鄲 056038)

對于按訂單生產型的企業(Make To Order，MTO)，在收到來自客戶的訂單時，要根據生產線的實際生產能力考慮訂單的完工時間以及訂單的最終收益。當訂單不能按時完工，不僅需要承擔延遲的懲罰還會對企業的信譽有所影響，造成客戶的流失。所以企業如果想獲得最大的收益，那么有選擇性地接受訂單和合理地安排訂單的生產尤為重要。針對訂單的接受與調度問題，已經有很多的學者對此建立了相關的數學模型并提出了多種智能優化算法進行求解。Oguz等人[1]較早地對考慮了訂單延遲懲罰的訂單接受與調度問題進行了研究，并提出了迭代啟發式算法，使用模擬退火算法概念來處理所選訂單的排序。Xie等人[2]使用改進的蜂群算法來解決帶有延遲懲罰的訂單調度問題。Noroozi等人[3]使用粒子群算法與遺傳算法相結合的混合算法進行求解訂單調度問題并證明了混合算法的優勢。宋李俊等人[4]針對多機器下的訂單接受與調度問題提出了雙層編碼的遺傳算法，使用將訂單順序和機器順序分開編碼的方式進行求解。Wang等人[5]提出一種基于列表調度的多目標孤雌遺傳算法求解多機器生產環境下的訂單調度問題。Guhlich等人[6]在按需生產的背景下，對隨機的訂單生產需求，結合出價價格收入和基于清算功能的訂單下達計劃來建立決策模型。王雷等人[7]考慮了生產線有限緩沖區的問題，在訂單接受與調度模型中加入緩沖區的成本這一要素，并使用和聲搜索算法和變鄰域搜索的混合方法進行求解。Ou等人[8]限制了訂單的拒絕數量，并提出兩種啟發式算法進行求解，通過實驗對算法的時間復雜度進行分析。王思涵等人[9]采用新型的鯨魚優化算法(Whale Optimization Algorithm，WOA)來求解生產線中車間調度的問題并取得了良好的成效。呂新橋等人[10]使用新型的灰狼優化算法(Gray Wolf Optimization，GWO)應用在車間調度的問題當中并與傳統的優化算法作比較，證明了其更有優勢。

本文在以上傳統的訂單接受與調度模型的基礎上加入訂單拒絕成本這一重要因素，并采用新型的智能優化算法WOA應用在模型當中。針對WOA依然存在像其它尋優算法容易陷入局部最優的缺點，而且不能直接用于求解訂單接受與調度這類整數域問題。本文提出改進的鯨魚優化算法(IWOA)，從編碼方式、種群初始化、動態學習、個體淘汰多個方面對WOA進行了改進，使其可以應用于訂單接受與調度模型當中，并在一定程度上改善了算法本身過早收斂的缺陷。最后將IWOA和WOA以及文獻[10]中改進的灰狼優化算法(HGWO)進行實驗對比，證明了IWOA在訂單接受與調度問題上的求解效果更好。

1 訂單接受與調度問題描述及建模

企業在收到來自客戶的訂單時，安排合理的生產計劃的關鍵在于結合生產線的實際生產能力和影響訂單收益的各種因素建立貼合實際的數學模型。本文研究的訂單接受與調度問題描述如下：

(1)在某一時間共有N個訂單等待排產，訂單可以有選擇性的接受。以下公式中Ai為1代表i號訂單被接受，0表示i號訂單不被接受。

Ai={0,1}

(1)

(2)生產線有M個節點，每個節點只有一臺加工機器,每種訂單都會經過M個節點處理，若訂單在交貨期后完成產生延時懲罰。以下公式中SLPi表示訂單i產生的延時懲罰，LPi代表i號訂單的單位延遲懲罰；FTi,m代表i號訂單在m號機器上的完工時間；DTi代表i號訂單的交貨時間。

SLPi=LPi×max{FTi,m-DTi,0}

(2)

(3)若訂單在交貨期前完成會積壓在庫存產生庫存成本。以下公式中SSPi表示訂單i產生的庫存成本。

SSPi=SPi×max{DTi-FTi,m,0}

(3)

(4)訂單分為F種類型，若當前訂單和上一個加工的訂單類型相同時，機器沒有準備時間；若當前訂單和上一個加工的訂單類型不相同時，存在機器切換的準備時間。以下公式中HTj,i-1,i表示j節點上的機器從訂單i-1類型切換到訂單i的時間，STi,j表示訂單i在j節點的開始時間，式(4)為約束條件，表示訂單i在j節點的開始時間大于等于訂單i在上一個節點的完工時間并且大于等于上個訂單在j節點的完工時間加上j節點上的機器從訂單i-1類型切換到訂單i的時間。

max{FTi,j-1,FTi-1,j+HTj,i-1,i}≤STi,j

(4)

(5)訂單在當前節點加工完成則馬上進入下一個節點進行加工，無需等待；如果下一個節點機器正在加工其他訂單，則當前訂單需要等待。以下公式中WTi,j代表i號訂單在j號機器的等待時間，式(5)為約束條件，表示訂單i在j節點的等待時間等于上個訂單在j節點的完工時間加上j節點上的機器從訂單i-1類型切換到訂單i的時間減去訂單i在上個節點的完工時間。

WTi,j=max{FTi-1,j+HTj,i-1,i-FTi,j-1,0}

(5)

(6)訂單在節點間等待時會進入緩沖區，訂單在緩沖區等待時會存在緩沖成本。以下公式中SWPi表示訂單i產生的緩沖區成本，WPi代表i號訂單的單位緩沖區成本，SPi代表i號訂單的單位庫存成本。

(6)

(7)如果訂單的最終收益賠錢，并且價格在毀約金以上，則撤銷該訂單并支付毀約金。以下公式中Pi表示訂單i的最終收益，BPi表示訂單i的違約金，式(7)為約束條件，表示訂單i的最終收益要大于訂單的毀約金。

Pi=max{Pi,-1×BPi}

(7)

(8)如果拒絕掉客戶的訂單會產生拒絕成本。以下公式中SRPi表示訂單i產生的拒絕成本，RPi代表i號訂單的拒絕成本。

SRPi=(1-Ai)×RPi

(8)

(9)以下公式中PTi,j表示訂單i在j節點的加工時間，式(9)為約束條件，表示訂單i在j節點的開始時間等于訂單i在上一個節點的結束時間加上訂單i在j節點的等待時間，式(10)為約束條件，表示訂單i在j節點的完工時間等于訂單i在j節點的開始時間加上訂單i在j節點的加工時間。

STi,j=FTi,j-1+WTi,j

(9)

FTi,j=STi,j+PTi,j

(10)

根據以上問題描述建立的最終表示訂單實際收益的數學模型如式(11)所示，公式中MPi代表i號訂單的市場收益。

(11)

2 標準鯨魚優化算法

對于像訂單調度這類NP-hard問題，是無法求解到最優解的，使用類似先來先服務、短訂單優先、最短交貨期優先等標準的、確定型的調度算法求解結果并不可靠，而使用不斷尋優的智能優化算法求解效率更高。WOA是模仿鯨魚捕食這一生物特性而提出的新型智能優化算法，具有參數少、尋優能力強的特點，而且收斂速度和精度優于傳統智能優化算法[11]。在算法中每一個鯨魚個體的位置就可以代表求解函數的一個目標解，即代表一種訂單調度結果。WOA包含三種更新位置的方式，分別為包圍捕食、螺旋更新、搜尋獵物，鯨魚首先通過搜尋獵物逐漸獲取獵物的相關信息，然后通過包圍獵物和螺旋靠近的方式不斷地靠近獵物，最終找到獵物，即找到問題的最優解[12]。

2.1 包圍獵物

鯨魚在尋找到目標獵物后，便包圍捕獲獵物，即向獵物位置前進，在尋優問題中目標獵物就是當前的最優個體，種群中的鯨魚個體在迭代過程中向最優個體位置前進，位置更新公式如式(12)所示，當p<0.5并且|A|<1時采用鯨魚當前方式進行移動。

x(t+1)=xbest(t)-A×D

(12)

D=|C×xbest(t)-x(t)|

(13)

A=2×a×r1-a

(14)

C=2×r2

(15)

a=2-2×t/tmax

(16)

式中：t為迭代搜尋次數；tmax是最大迭代次數；x(t)為鯨魚位置；xbest(t)是全局最優位置；A和C為系數矩陣；r1和r2是[0，1]均勻分布隨機數；a為收斂因子，從2到0線性遞減；p為[0，1]均勻分布隨機數。

2.2 旋轉搜尋

鯨魚在靠近獵物過程中，采用螺旋的方式進行移動，搜索路徑中可能存在的最優解，位置更新公式如式(17)所示，當p≥0.5時采用鯨魚當前方式進行移動。

x(t+1)=xbest(t)+D×ebl×cos2πl

(17)

式中b為常數1，可以改變螺旋的形狀；l為[-1，1]均勻分布隨機數。

2.3 隨機搜尋

鯨魚向隨機的個體方向移動，進行全局搜索，位置更新公式如式(18)所示，當p<0.5并且|A|≥1時采用鯨魚當前方式進行移動。

x(t+1)=xrand(t)-A×|C×xrand(t)-x(t)|

(18)

式中xrand(t)為一個隨機的鯨魚位置。

3 改進鯨魚優化算法

雖然WOA在尋優效率和求解精度等方面優于其他傳統優化算法，但是依然存在易陷入局部最優、易偏離全局最優方向的問題。針對這些問題本文分別在編碼、種群初始化、向歷史個體動態學習、淘汰劣質個體4方面進行了改進。

3.1 基于排序和偏離度的編碼方式

WOA被提出是用來解決連續問題的，其解空間是實數域[13]。但是訂單接受與調度問題是整數域問題，每一個鯨魚個體必須可以代表一個訂單的加工順序，文獻[13]使用按照鯨魚個體大小排序來確定車間的加工順序。本文采取文獻[13]的思路，按照鯨魚個體大小升序排序來確定訂單的加工順序，如表1、表2所示。

表1 原鯨魚個體

表2 排序后鯨魚個體

訂單的加工順序:1->3->0->2，但是這種編碼方式卻不能表示含訂單接受的問題，針對這一問題本文在此基礎上引入基于偏離度的編碼策略，計算鯨魚個體每一維度和平均值的偏離度，拒絕偏離度大的訂單，偏離度計算如式(19)所示：

p=|Ex-x|/Ex

(19)

式中p為偏離度；Ex為均值；x為鯨魚個體每一維度的數值，則訂單的接受情況如表3所示。

表3 加入偏離度后鯨魚個體

若取p為0.7，1號訂單的偏離度大于p，則接受后的訂單順序為3->0->2。

3.2 基于二次反向學習和混沌序列的種群初始化策略

初始化的種群質量影響著整個算法的收斂速度和尋優效果，WOA采用隨機的種群初始化方式并不能保證種群的多樣性與優質性。孟磊等[14]提出二次反向學習應用于分布估計算法并取得了良好的效果。本文將二次反向學習策略應用于WOA并進行改進，在二次反向學習的基礎上加入混沌序列, 混沌映射可以用來生成混沌序列，在種群初始化方面混沌映射產生的混沌序列比偽隨機數有更好的效果。比較常用的離散混沌映射是Tent 混沌映射和logistic混沌映射，而且Tent 混沌映射比 logistic混沌映射具有更好的均勻遍歷特性[15]。本文將Tent混沌序列和二次反向學習相結合應用于WOA保證種群的多樣性與優質性。具體公式如下：

Tent 混沌映射:

(20)

式中，參數p和混沌序列zk都在區間(0，1)之間。

初始種群:

(21)

式中ai表示鯨魚個體的上界；bi表示鯨魚個體的下界。

反向點:

(22)

二次反向點:

(23)

3.3 動態學習策略

WOA在旋轉搜尋和包圍獵物的過程中都是向最優的區域靠攏，但是當前的最優位置有可能是局部最優，在這種情況下若只有當前最優個體指導鯨魚種群的移動方向，即每次迭代過程中種群中的鯨魚個體都向當前局部最優個體靠攏，很容易使算法出現早熟，針對這個問題，本文受到GWO利用三個領頭狼共同指導灰狼個體位置移動策略的啟發，在WOA中保留歷史最優的個體，讓當前最優個體和歷史最優個體進行信息交流，共同指導當前迭代個體的移動方向，這樣以來即使當前最優個體是局部最優，因為還有歷史最優個體對鯨魚移動位置的指導，在極大程度上可以使鯨魚種群跳出當前局部最優，原公式(12)和公式(17)變為以下公式:

x(t+1)=xbest(t)-A×D+L(t)×(xhistory(t)-x(t))

(24)

x(t+1)=xbest(t)+D×ebl×cos2πl+

L(t)×(xhistory(t)-x(t))

(25)

式中xhistory(t)代表歷史最優個體。

L(t)=cos(t×π)/(tmax×2)為從1到0遞減的非線性函數，使算法前期歷史個體比重較大，增加搜索范圍；算法后期歷史個體比重較小，加快向最優個體的收斂速度。

3.4 個體淘汰策略

當WOA隨即搜尋時，是向隨機的位置靠攏，這種方法雖然能在一定程度上保證種群的多樣性，但是容易產生偏離最優方向的劣質解，影響收斂速度。針對此問題，本文采用了遺傳算法的交叉選擇策略，每次迭代后，將種群按適應度排序并平均分為兩部分，一部分為相對優質的個體，另一部分為相對劣質的個體，兩部分進行兩兩算術交叉生成一個新的種群，讓優質個體和劣質個體進行交叉可以保證種群的多樣性；將原種群和新種群進行合并，按照適應度排序，淘汰合并后種群中的劣質個體，讓保留下來的優質個體進入下一次迭代，保證種群的優質性。具體算術交叉公式如下：

(26)

(27)

3.5 算法步驟

經過改進后IWOA算法偽代碼如算法1所示：

算法1 IWOA算法偽代碼

(a)按照式(23)方法初始化種群。

(b)對種群進行編碼。

(c)按照式(11)計算種群適應度并進行排序。

(d)保留當前最優個體。

(e)按照式(16)計算a的值。

(f)按照式(13)、(14)計算D、A的值。

(g)如果p<0.5執行步驟(h)，否則按照式(25)進行旋轉搜尋。

(h)如果Math.abs(A)>=1按照式(18)進行隨即搜尋，否則按照式(24)進行旋轉搜尋。

(i)判斷個體維度是否遍歷完畢，若遍歷完執行下一步，否則跳轉步驟(g)。

(j)判斷種群是否遍歷完畢，若遍歷完執行下一步，否則跳轉步驟(f)。

(k)按照式(26)、(27)進行交叉選擇。

(l)如果當前種群最優解>歷史最優解則更新全局最優解和歷史最優解。

(m)判斷是否到達最大迭代次數，若到達輸出當前最優值，否則跳轉步驟(d)。

4 實驗結果分析

本次實驗設置的相關參數為：種群數量20；迭代次數400；生產線節點數4；訂單數量10/20/30；開始加工時間0(當前時間)；10訂單下數據集如表4所示；除此之外還有單位緩沖區成本、每種訂單在每個節點加工時間、機器切換時間等生產線數據參數。

通過迭代曲線圖1所示，三條曲線分別代表3個算法的迭代過程，在不同訂單規模下，以最終收益結果、初始收益值、收斂時間作為評價指標，比起HGWO和WOA，IWOA收益更高即更易跳出局部最優，收斂速度更快，初始種群也更加優質，而且在訂單數量增加的情況下IWOA的優勢也更加明顯。

此次排程的甘特圖如圖2所示，訂單順序為9-7-5-1-6-0-3；拒絕訂單號為2、4、8，總收益為32 484.5元；開始排產時間為0，即當前時刻；每個訂單需要經過4個節點進行加工，由圖2可以看出(由于空間問題中間5、1、6號訂單沒有展開)，每個訂單都需要經過4個加工節點加工，每個訂單的開始加工時間就是其在第一個節點的開始加工時間，完工時間就是其在最后一個節點的完工時間，因最開始開工的9號訂單前面沒有正在加工的訂單，所以在每個節點都是無縫加工；下一個訂單開始由于和之前的訂單類型不同，在節點上需要等待機器的切換時間，所以并不是無縫加工；從第一個訂單在第一個節點加工開始到最后一個訂單在最后一個節點加工完成大約需要54個小時。

對IWOA、WOA、HGWO，3個算法分別在10訂單、20訂單、30訂單環境下進行多次排產，結果如表5所示，從表5中可以看出，IWOA在收斂速度和平均收益以及訂單的接受情況上都明顯優于其他兩種算法。將每次實驗中實際收益和平均收益的最大差值與平均收益的比值作為最大偏離度，則在10訂單的環境下，IWOA的收益最大偏離度為1.6%，HGWO為3.0%，WOA為4.8%；在20訂單的環境下，IWOA的收益最大偏離度為3.8%，HGWO為7.0%，WOA為6.6%；在30訂單的環境下，IWOA的收益最大偏離度為3.2%，HGWO為3.3%，WOA為6.2%；IWOA的排產結果偏離度最小，數據都集中在平均值左右，證明IWOA算法的穩定性也優于其他兩種算法。

圖1 三組訂單迭代曲線圖Fig.1 Three sets of order iterative graphs

圖2 排產甘特圖Fig.2 Scheduling Gantt Chart

表5 排產結果統計表

5 結論

本文建立了以最大收益為目標的訂單接受與調度一體化模型，在傳統模型的基礎上考慮了訂單的拒絕成本，使模型更加貼合企業的實際利潤，并提出了改進的鯨魚優化算法(IWOA)求解模型，通過實驗結果表明，在多組訂單環境下IWOA對模型的求解結果、結果的穩定性以及算法本身的收斂速度、初始解的優質程度都優于鯨魚優化算法(WOA)和改進的灰狼優化算法(HGWO)。