基于動態(tài)學(xué)習(xí)和個體淘汰的鯨魚算法求解訂單接受與調(diào)度問題

任丹萍，鄭子威，陳湘國

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

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

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

1 訂單接受與調(diào)度問題描述及建模

企業(yè)在收到來自客戶的訂單時，安排合理的生產(chǎn)計劃的關(guān)鍵在于結(jié)合生產(chǎn)線的實際生產(chǎn)能力和影響訂單收益的各種因素建立貼合實際的數(shù)學(xué)模型。本文研究的訂單接受與調(diào)度問題描述如下：

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

Ai={0,1}

(1)

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

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

(2)

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

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

(3)

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

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

(4)

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

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

(5)

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

(6)

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

Pi=max{Pi,-1×BPi}

(7)

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

SRPi=(1-Ai)×RPi

(8)

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

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

(9)

FTi,j=STi,j+PTi,j

(10)

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

(11)

2 標(biāo)準(zhǔn)鯨魚優(yōu)化算法

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

2.1 包圍獵物

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

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為迭代搜尋次數(shù)；tmax是最大迭代次數(shù)；x(t)為鯨魚位置；xbest(t)是全局最優(yōu)位置；A和C為系數(shù)矩陣；r1和r2是[0，1]均勻分布隨機數(shù)；a為收斂因子，從2到0線性遞減；p為[0，1]均勻分布隨機數(shù)。

2.2 旋轉(zhuǎn)搜尋

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

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

(17)

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

2.3 隨機搜尋

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

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

(18)

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

3 改進鯨魚優(yōu)化算法

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

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

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

表1 原鯨魚個體

表2 排序后鯨魚個體

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

p=|Ex-x|/Ex

(19)

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

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

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

3.2 基于二次反向?qū)W習(xí)和混沌序列的種群初始化策略

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

Tent 混沌映射:

(20)

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

初始種群:

(21)

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

反向點:

(22)

二次反向點:

(23)

3.3 動態(tài)學(xué)習(xí)策略

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

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

(24)

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

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

(25)

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

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

3.4 個體淘汰策略

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

(26)

(27)

3.5 算法步驟

經(jīng)過改進后IWOA算法偽代碼如算法1所示：

算法1 IWOA算法偽代碼

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

(b)對種群進行編碼。

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

(d)保留當(dāng)前最優(yōu)個體。

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

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

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

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

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

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

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

(l)如果當(dāng)前種群最優(yōu)解>歷史最優(yōu)解則更新全局最優(yōu)解和歷史最優(yōu)解。

(m)判斷是否到達最大迭代次數(shù)，若到達輸出當(dāng)前最優(yōu)值，否則跳轉(zhuǎn)步驟(d)。

4 實驗結(jié)果分析

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

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

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

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

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

圖2 排產(chǎn)甘特圖Fig.2 Scheduling Gantt Chart

表5 排產(chǎn)結(jié)果統(tǒng)計表

5 結(jié)論

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