并行變鄰域搜索下的訂單接收與流水車間調(diào)度

鄭 凡，雷德明

(武漢理工大學 自動化學院，湖北 武漢430070)

面對競爭日益激烈的態(tài)勢，越來越多的制造企業(yè)開始采用訂單型生產(chǎn)模式來滿足客戶個性化的產(chǎn)品需求。客戶一般要求制造商在規(guī)定的交貨期內(nèi)完成訂單生產(chǎn)，否則制造商將承擔經(jīng)濟和市場信譽等方面的損失［1］。因此，在有限的生產(chǎn)能力和嚴格交貨要求下，制造商必須同時進行訂單接收和訂單調(diào)度的決策以實現(xiàn)其總收益的最大化［2］。訂單接收與調(diào)度(OAS)問題是一種聯(lián)合決策問題，屬于NP -hard 問題，它可以分解成兩個子問題：①企業(yè)要綜合考慮來決策能夠接收哪些訂單;②已接收的訂單如何安排加工順序。這兩個子問題相互影響和制約，最終目的是使企業(yè)在經(jīng)濟或信譽方面獲得最大收益［3-4］。

近年來，考慮訂單接收的車間調(diào)度問題受到研究者的廣泛關注，研究者分別研究了單機、并行機和流水車間等制造環(huán)境下的OAS 問題［5-9］，目前關于流水車間環(huán)境下的OAS 問題的研究較少。XIAO［10］針對置換流水車間環(huán)境下的OAS 問題，運用一種基于偏序優(yōu)化的模擬退火算法以解決問題的整數(shù)規(guī)劃模型并得到近似最優(yōu)解。WANG等［11］運用一種改進的人工蜂群算法解決了雙機流水車間環(huán)境下的OAS 問題。WANG 等［12］針對同樣的問題又提出了一種啟發(fā)式算法和分枝定界算法。變鄰域搜索(VNS)算法作為一種改進型啟發(fā)式算法，在求解大規(guī)模的組合優(yōu)化問題上有較為明顯的優(yōu)勢，已被廣泛應用于生產(chǎn)調(diào)度領域并具有較強的搜索優(yōu)勢。筆者研究流水車間環(huán)境下的OAS 問題，并提出一種新型的并行變鄰域搜索(PVNS)算法。將PVNS 與遺傳算法和蜂群算法進行了大量實例比較，實驗結果表明，PVNS 對所研究的問題具有良好的優(yōu)化效果。

1 問題描述

流水車間環(huán)境下的OAS 問題描述如下：存在n個訂單和m臺機器，訂單集合O={O1，O2，…，On}，機器集合M={M1，M2，…，Mm}。每個訂單按如下順序訪問所有的機器：先在M1上加工，再在M2上加工，依次進行直到所有機器訪問完畢。每個訂單在每臺機器上只加工一次，每臺機器同一時間只能加工一個訂單，各訂單在各機器上的加工時間已知。即第i個訂單Oi需要完成m道工序，這些工序由(Oi1，Oi2，…，Oim)組成，且訂單Oi的實際收益r*i由該訂單的最大收益ri、交貨期di、加工完成時間ci和延期懲罰權重ωi等共同決定。

OAS 問題由訂單接收子問題和已接收訂單的調(diào)度子問題組成。其中訂單接收子問題指如何從n個訂單中選擇j個訂單問題;調(diào)度子問題則指對已接收的訂單安排加工順序問題。在一個訂貨系統(tǒng)中，訂單的接收決策受限于有限的生產(chǎn)能力和交貨時間的要求，已接收訂單的調(diào)度決策由其開始加工時間、加工時間和最大收益等決定。

OAS 問題的目標是通過完成訂單的接收決策和合理安排已接收訂單的加工順序使訂單生產(chǎn)的實際總收益最大化。

式中：Rtotal為訂單生產(chǎn)的實際總收益;yi取值為0 或1，取1 表示訂單i被接收，取0 則表示被拒絕;∑ni=1yi=j，j為所接收訂單總數(shù)。

2 基本變鄰域搜索算法

變鄰域搜索算法(VNS)是一種啟發(fā)式策略，它具有方法簡單、容易實現(xiàn)和無需調(diào)整參數(shù)等優(yōu)點，該方法已被成功應用于許多組合優(yōu)化問題。相比于傳統(tǒng)方法的單一鄰域結構，VNS 首先預定義一系列的鄰域結構，并在搜索過程中系統(tǒng)性地不斷擴大鄰域搜索范圍，直到獲得更好的解［13］。

基本VNS 的算法流程如下：

(1)定義一系列的鄰域結構Nk，k=1，2，…，kmax，產(chǎn)生一個初始解x，并令其為當前解;

(2)重復下列過程至算法終止;

(3)令k=1;

(4)重復下列過程至算法k=kmax：①擾動。由當前解x在其第k種鄰域Nk內(nèi)隨機產(chǎn)生 一個新解x';②局部搜索。以x'為初值應用鄰域搜索方法獲得解x″;③如果x″優(yōu)于x，則x=x″，否則k=k+1。

由VNS 的算法流程可以看出，確定鄰域結構及其數(shù)量，確定各鄰域結構在搜索中應用的次序及其改變的策略是VNS 要解決的基本問題。

3 并行變鄰域搜索算法

3.1 基于訂單編號的編碼和解碼機制

筆者利用雙串來表示OAS 問題的解。對于流水車間環(huán)境下具有n個訂單的OAS 問題，串v1={θ1，θ2，…，θn}表示訂單的調(diào)度情況，其中θi∈{1，2，…，n}，{θ1，θ2，…，θn}={1，2，…，n};串v2={y1，y2，…，yn}表示訂單的接收情況。

解碼過程如下：首先根據(jù)v2確定被接收的訂單;然后從v1中剔除被拒絕的訂單，剩余部分則為已接受訂單的排列;最后根據(jù)已接收訂單的排列順序，依次安排這些訂單的加工，再結合每個訂單的懲罰權重算出每個訂單的收益，進而得出OAS 問題的目標函數(shù)值即所有訂單的實際總收益。

假設PVNS 處理器的個數(shù)為npr，隨機產(chǎn)生npr個初始解，每個處理器采用一個初始解。

3.2 鄰域結構

鄰域結構是PVNS 產(chǎn)生新解的主要方式。在利用PVNS 求解OAS 問題時，鄰域結構使算法從當前解轉移到其相鄰解，并保證解的可行性。動態(tài)地改變鄰域結構以使搜索過程順利跳出局部最優(yōu)，確保得到的解近似于全局最優(yōu)解。根據(jù)上述編碼機制，設計了6 種鄰域結構。

(1)鄰域結構Ns1。鄰域結構Ns1通過改變處理器當前解的調(diào)度串來構造鄰域解。在接收串不變的情況下，Ns1從調(diào)度串中隨機選擇兩個不同的位置，并將兩個位置上的訂單編號進行互換來產(chǎn)生鄰域解。

(2)鄰域結構Ns2。鄰域結構Ns2通過改變處理器當前解的接收串來產(chǎn)生鄰域解。Ns2通過從接收串中隨機選擇兩個不同的位置，并將兩個位置上的數(shù)字(1 或0)進行互換來產(chǎn)生鄰域解，且調(diào)度串保持不變。

(3)鄰域結構Ns3。鄰域結構Ns3是鄰域結構Ns2的進一步加強。在調(diào)度串不變的情況下，從接收串中隨機選擇4 個不同的位置，并將這4 個位置上的訂單編號兩兩互換，這樣擴大了鄰域搜索范圍，使搜索更加豐富。

(4)鄰域結構Ns4。鄰域結構Ns4通過倒置處理器當前解的調(diào)度串的部分訂單編號來構造鄰域解。從調(diào)度串中隨機選擇兩個不同的位置，并將兩個位置之間的訂單編號進行倒置產(chǎn)生鄰域解，且接收串v2保持不變。

(5)鄰域結構Ns5。鄰域結構Ns5通過插入操作改變處理器當前解的調(diào)度串來構造鄰域解。在接收串保持不變的情況下，從調(diào)度串中隨機選擇兩個位置j和k(k＞j+1)，并將k位置上的訂單編號插入到j位置，且j位置到k-1 位置上的訂單編號依次向后移動一位。

(6)鄰域結構Ns6。鄰域結構Ns6是鄰域結構Ns1的進一步加強。其具體過程如下：對于處理器的當前解，從調(diào)度串中隨機選擇兩個不同的位置，然后將調(diào)度串分割為左、中、右3 個部分，再將左右兩部分的訂單編號子串進行互換，且接收串保持不變。

3.3 PVNS 算法

如何在最短時間內(nèi)獲得最優(yōu)解或接近最優(yōu)解是解決OAS 問題要面對的首要難題。為了解決這個難題，將并行搜索策略視為一種可行方案。并行搜索策略下的啟發(fā)式算法允許同時運行多個鄰域結構來搜索解空間，且各鄰域結構在搜索中應用的數(shù)目和次序各不相同。并行化的應用增加了對解空間的探測，避免了算法陷入局部最優(yōu)，從而大大提升了算法的尋優(yōu)能力。為了有效地解決OAS 問題，提出了一種新型的并行變鄰域搜索(PVNS)算法。

筆者提出的基于流水車間環(huán)境下OAS 問題的PVNS 的實現(xiàn)流程如下：

(1)初始化。定義用于擾動的鄰域結構集合P={Ns1，Ns4，Ns5，Ns6}和用于局部搜索的鄰域結構集合L={Ns1，Ns2，Ns3，Ns4，Ns5，Ns6}，以及處理器的個數(shù)，為每個處理器確定要使用的鄰域結構和相應的次序;

(2)產(chǎn)生npr個初始解，確定精英解x*;

(3)選擇算法終止條件(設置最大迭代次數(shù))。重復下列過程直至算法結束：①For 每個并行處理器的當前解xi執(zhí)行如下過程mmax次：擾動過程。隨機從集合P中選擇鄰域結構，產(chǎn)生一個解xi∈Nsk(xi);局部搜索。根據(jù)該處理器的鄰域結構及其使用次序，確定相應的鄰域結構，產(chǎn)生新解ˉxi;若f(ˉxi)＞f(xi)則xi←ˉxi，更新精英解x*;否則當前解保持不變。②執(zhí)行上述過程α 次，指定兩個處理器互換其當前解。

PVNS 的并行變鄰域搜索階段的設計是PVNS 的重要內(nèi)容，是PVNS 能否快速找到最優(yōu)解的關鍵。筆者設置npr個處理器，每個處理器采用VNS 對當前解實施擾動和局部搜索，用于局部搜索的鄰域結構各有不同，使用次序也有差異。部分處理器可采用只改變調(diào)度串的鄰域結構，在不改變訂單接收情況下通過變鄰域搜索獲得更好的解;其他處理器則采用同時改變雙串的鄰域結構，雖然改變了訂單的接收狀況，但擴大了搜索空間，增大了鄰域搜索后所得當前解的多樣性。

PVNS 中處理器當前解的互換是指處理器獨立運行一定迭代次數(shù)后，處理器的當前解兩兩互換的過程。這個階段的設計能有效地避免算法陷入局部最優(yōu)，大大增強PVNS 全局優(yōu)化能力。該階段的互換過程如下：每個處理器迭代α 次后獲得當前解xi，解碼后獲得相應的目標值f(xi)，再按照目標值的大小將npr個當前解xi依次排列，最后將該序列首尾兩兩互換即可。當算法的最大迭代次數(shù)到達指定值時，算法停止運行，并輸出最終的精英解x*。

4 實驗測試及結果分析

4.1 實例描述

為了測試及比較PVNS 的性能，選擇了7 個計算實例，這7 個實例的訂單數(shù)目分別為10，20，30，40，50，60 及80。對第i個訂單Oi，它的最大收益ri為［100，300］范圍內(nèi)的隨機數(shù)，它在每臺機器上的加工時間為［5，10］范圍內(nèi)的隨機數(shù)。筆者將每個訂單的交貨期設置成其在所有機器上的加工時間之和的ρ 倍。這7 個實例每個訂單的值分別為1.5，1.5，2.0，3.0，4.0，8.0，8.0 。因為只有ρ取適當?shù)闹禃r，大多數(shù)訂單才能在交貨期內(nèi)完成所有加工，從而保證所得到的交貨期有意義。通過大量的計算實驗，獲得每個實例相應的ρ 值。另外設置了3 種不同的懲罰權重ω：0.3，0.6，0.9。隨著訂單數(shù)n的增加，實驗的計算難度和時間隨之增加。設置參數(shù)ρ 和ω 后，每種算法運行20 次，從而獲得實驗所需結果：最優(yōu)解max(實際總收益最大的解)，最差解min(實際總收益最小的解)，平均解avg及運行時間t。

4.2 算法的比較

筆者選擇GA 和ABC 作為比較對象。GA 作為一種經(jīng)典的進化算法，具有隱含并行性和全局解空間搜索兩大顯著特點，其自組織、自適應、自學習和群體進化能力使其被廣泛應用于大規(guī)模復雜優(yōu)化問題中;ABC 作為一種新興的智能算法，機制簡單，參數(shù)少，在各種NP -hard 問題上取得了較好的優(yōu)化效果。針對流水車間環(huán)境下的OAS 問題，采用改進的PVNS、GA 和ABC，進行比較實驗的3 種算法的編碼解碼機制和算法的終止條件已知且相同。

4.3 實驗結果

所采用實驗平臺是一臺2.50 GHz 主頻和4 G 內(nèi)存配置的筆記本電腦。筆記本電腦的操作系統(tǒng)是Windows 7 系統(tǒng)，且Visual C+ + 6.0 軟件實現(xiàn)了所有算法的編譯。

在PVNS 中，處理器的個數(shù)、每個處理器鄰域結構的使用類型及次序和其局部搜索中鄰域搜索的最大迭代次數(shù)由大量的計算實驗決定。根據(jù)對算法不同參數(shù)值的測試試驗及其結果，PVNS 的參數(shù)設置如下：處理器的個數(shù)npr=4;每個處理器鄰域搜索的最大迭代次數(shù)nmax=850。

在比較實驗中，總迭代次數(shù)的設定十分關鍵，如果總迭代次數(shù)太小，每種算法的鄰域搜索不充分將導致算法無法收斂從而無法得到最優(yōu)解;反之，雖然能獲得最優(yōu)解但大大增加了計算時間，影響了算法的效率。通過在其他參數(shù)不變的情況下改變總迭代次數(shù)觀察實際總收益變化的實驗來得到合適的總迭代次數(shù)。即為不同訂單數(shù)目的OAS 問題選擇適當?shù)目偟螖?shù)：訂單數(shù)目為10和20 時，實例的總迭代次數(shù)為20 000;訂單數(shù)目為30、40 和50 時，實例的總迭代次數(shù)為60 000;訂單數(shù)目為60 和80 時，實例的總迭代次數(shù)則為80 000。當懲罰權重ω =0.6 時，3 種算法的實驗結果如表1 所示。另外，為了更好地比較大規(guī)模訂單數(shù)目下PVNS、GA 和ABC 這3 種算法的優(yōu)化能力，進行了如下實驗：在n=60，ρ =8，ω =0.9的參數(shù)條件下，不斷增加總迭代次數(shù)，記錄下不同總迭代次數(shù)下3 種算法獲得的實際總收益的最優(yōu)解。實驗結果如圖1 和圖2 所示。

表1 懲罰權重為0.6 時3 種算法的實驗結果

圖1 PVNS 與GA 實驗比較圖

圖2 PVNS 和ABC 實驗比較圖

從實驗結果可以看出，PVNS 的尋優(yōu)能力優(yōu)于GA，且略勝于ABC。GA 不能優(yōu)化流水車間大規(guī)模訂單下的OAS 問題的原因如下：GA 對解空間的探索能力有限，易收斂到局部最優(yōu)解;GA 的參數(shù)較多，例如交叉率和變異率，且這些參數(shù)的選擇嚴重影響最優(yōu)解的結果;GA 算法實現(xiàn)比較復雜，計算時間長(訂單數(shù)目增加時，該問題尤為嚴重)。而ABC 則主要受限于其較差的全局優(yōu)化能力，從算法解的性質(zhì)看，ABC 是在尋找一個比較好的局部最優(yōu)解，而不是全局最優(yōu)解。因此，PVNS 相比其他兩種算法擁有參數(shù)少、結構簡單、易于實現(xiàn)和局部搜索充分等優(yōu)點，具有全局優(yōu)化能力。

5 結論

筆者研究了多機器流水車間環(huán)境下訂單接收與生產(chǎn)調(diào)度問題，提出了一種并行變鄰域搜索算法。在大量的不同訂單數(shù)目的實例實驗中，證明PVNS 算法具有優(yōu)秀的優(yōu)化能力和優(yōu)化效果。其原因在于：①運用雙串來表示問題的解決方案，大大提高了算法的可行性和操作能力;②PVNS 的結構簡單易于實現(xiàn);③多鄰域搜索結構的設計使鄰域搜索更加靈活多變，互換、插入和倒置等操作的局部特性使每個處理器能更好地逼近最優(yōu)解;④PVNS 算法中多處理器當前解的互換階段擴大了解空間，有效避免陷入局部優(yōu)化，使PVNS 具有良好的全局優(yōu)化能力。

［1］ 唐恒永，趙傳立.排序引論［M］.北京：科學出版社，2002：3 -12.

［2］ 劉民，吳澄. 制造過程智能優(yōu)化調(diào)度算法及其應用［M］.北京：國防工業(yè)出版社，2008：36 -45.

［3］ 雷德明. 現(xiàn)代制造系統(tǒng)智能調(diào)度技術及其應用［M］.北京：中國電力出版社，2010：56 -98.

［4］ ZHANG L，LU L，YUAN J.Single machine scheduling with release dates and rejection［J］. European Journal of Operational Research，2009(198)：975 -978.

［5］ LU L，ZHANG L，YUAN J. The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan［J］. Theoretical Computer Science，2009(396)：283 -289.

［6］ OGUZ C，SALMAN F S，YALCIN Z B. Order acceptance and scheduling decisions in make - to - order systems［J］. International Journal of Production Economics，2010，125(1)：200 -211.

［7］ CESARET B，OGUZ C.A tabu search algorithm for order acceptance and scheduling［J］.Computers ＆ Operations Research，2012，39(6)：1197 -1205.

［8］ SU N，ZHANG M J，MARK J，et al.Learning reusable initial solutions for multi - objective order acceptance and scheduling problems with genetic programming［J］. European Conference on Genetic Programming，2013(7831)：157 -168.

［9］ LIN S W，YING K C.Increasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithm［J］.Journal of the Operational Research Society，2013，64(2)：293 -311.

［10］ XIAO Y Y.Permutation flow shop scheduling with order acceptance and weighted tardiness［J］.Applied Mathematics and Computation，2012，218(15)：7911-7926.

［11］ WANG X L，XIE X Z.A modified artificial bee colony algorithm for order acceptance in two -machine flow shops［J］. International Journal of Production Economics，2013，141(1)：14 -23.

［12］ WANG X L，XIE X Z.Order acceptance and scheduling in a two-machine flowshop［J］.International Journal of Production Economics，2013，141(1)：366-376.

［13］ 王凌.車間調(diào)度及其遺傳算法［M］.北京：清華大學出版社，2003：103 -123.