訂單接受與調(diào)度問題求解方法與仿真研究

摘 要： 在按訂單生產(chǎn)的制造系統(tǒng)中，有限的生產(chǎn)能力與嚴格的訂單交貨期要求決策者從若干候選訂單中選擇接受某些訂單并編制生產(chǎn)計劃。決策者需在訂單收益與拖期懲罰之間進行權(quán)衡，以所有接受訂單的實際收益之和最大為目標進行優(yōu)化。提出了一種禁忌搜索算法用于求解考慮發(fā)布日期和隊列準備時間的單機環(huán)境下的訂單接受與調(diào)度問題。通過計算仿真方法模擬決策過程，并與兩種現(xiàn)有的啟發(fā)式算法比較，驗證了提出的解法在收斂速度以及求解效果方面有更好的表現(xiàn)。

關(guān)鍵詞： 訂單接受與調(diào)度； 隊列準備時間； 禁忌搜索； 計算仿真

中圖分類號： TP311 文獻標識碼： A 文章編號：2095-2163（2013）03-0033-04

Solution and Simulation for Order Acceptance and Scheduling Problem

WANG Lei， ZHAN Dechen， NIE Lanshun

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract： In a make-to-order production system， limited production capacity and strict order delivery date requires selection and acceptance from a set of candidate orders for production schedule. Order acceptance and scheduling decisions must trade-off to maximize total revenue. This paper presents a taboo search algorithm that solves the order acceptance and scheduling problem in the make-to-order production system on a single machine with release dates and sequence dependent setup time. Compared with two heuristics from the literature， the simulation experiment results show that the algorithm in this paper obtains near optimal solutions which are significantly better than the other two heuristics both with convergence and solution quality.

Key words： Order Acceptance and Scheduling； Sequence Dependent Setup Time； Taboo Search； Computational Simulation

0 引 言

在按訂單生產(chǎn)（Make-To-Order， MTO）類型的制造系統(tǒng)中，決策者需要在有限的生產(chǎn)能力和嚴格的訂單交貨期兩項重要約束下對多個候選訂單的接受與否以及如何調(diào)度進行科學決策，確定接受其中哪些訂單，并對已接訂單進行生產(chǎn)時間安排，這類問題稱為訂單接受與調(diào)度問題（Order Acceptance and Scheduling， OAS）[1]。實際過程中，訂單接受決策一般由企業(yè)銷售和運營部門制訂，這些部門希望接受更多的訂單，從而帶來更多的預期收益，而負責訂單執(zhí)行的生產(chǎn)部門更傾向于根據(jù)實際產(chǎn)能接受訂單，最大程度滿足交貨期要求。于是訂單接受和生產(chǎn)調(diào)度兩階段決策的分離即成為影響MTO型企業(yè)生產(chǎn)計劃有效性的主要原因之一。在當今激烈的市場競爭環(huán)境下，將訂單接受與生產(chǎn)調(diào)度進行集成決策，高效利用有限的生產(chǎn)資源和能力在交貨期約束下圓滿完成訂單，力圖獲得更多的訂單實際收益以及更高的客戶滿意度，這就給MTO型生產(chǎn)企業(yè)以及信息管理系統(tǒng)提出無可回避的嚴峻挑戰(zhàn)。

近年來，訂單接受與調(diào)度問題倍受工業(yè)界和學術(shù)界的熱切關(guān)注。該類問題可視為組合優(yōu)化研究領域的權(quán)衡（trade off）問題，一方面希望增加訂單數(shù)量獲得更多的預期收益，另一方面由于訂單過多必將導致拖期而受到經(jīng)濟懲罰，因此需要合理安排生產(chǎn)資源和能力，減少訂單拖期，經(jīng)證明該問題屬于NP-hard問題[2]。Slotnick從面向問題特點的角度對近20年來訂單接受與調(diào)度問題的研究進行了系統(tǒng)綜述與分類，主要針對單機調(diào)度、多機調(diào)度、確定型調(diào)度、隨機型調(diào)度以及優(yōu)化目標等五類不同的訂單接受與調(diào)度問題進行分析[3]。從求解方法分析，現(xiàn)有研究主要分為以分支定界算法為代表的精確算法，和以各種啟發(fā)式算法為代表的近似算法兩類。文獻[4]對一種擴展的帶有拖期懲罰的單機環(huán)境訂單接受問題進行了研究，提出了兩種線性規(guī)劃形式，并且構(gòu)造了兩種不同的分支定界算法，又通過仿真實驗證明了對于求解訂單數(shù)量小于50的測試實例則具有較好的求解效果。針對候選訂單數(shù)量較多的問題實例，近似算法往往具有更好的實際應用可行性。文獻[5]考慮了訂單接受與調(diào)度問題中隊列準備時間給計算帶來的復雜性，提出了一種混合整數(shù)規(guī)劃形式化模型；由于精確算法對于訂單數(shù)量較大問題的求解速度表現(xiàn)欠佳，又提出了ISFAN和m-ATCS兩種啟發(fā)式方法，并在生成的較大規(guī)模測試實例上進行了仿真實驗，結(jié)果表明兩種啟發(fā)式方法能夠獲得較高的收斂速度并得到可接受的解。文獻[6]提出一種基于遺傳算法和極值優(yōu)化的混合進化算法求解生產(chǎn)調(diào)度問題中的訂單選擇與訂單排序問題，通過一種組合優(yōu)化模型對問題進行形式化描述，并結(jié)合遺傳算法的搜索能力和極值優(yōu)化算法的局部優(yōu)化效率，設計了適用于該問題的混合進化算法，并通過仿真實驗證明了該算法對于較大規(guī)模的訂單接受與調(diào)度問題具有良好的求解質(zhì)量和求解效率。

禁忌搜索（Taboo Search， TS）算法作為一種相對較為成熟的元啟發(fā)式算法，已經(jīng)在調(diào)度以及網(wǎng)絡優(yōu)化等多個研究領域取得了不俗的實現(xiàn)結(jié)果。本文針對單機環(huán)境下同時考慮發(fā)布日期和隊列準備時間的訂單接受與調(diào)度問題進行研究。首先形式化描述該問題，然后提出一種基于禁忌搜索的啟發(fā)式算法求解該類組合優(yōu)化問題。通過計算仿真與兩種現(xiàn)有的啟發(fā)式算法進行比較，仿真結(jié)果驗證了本文提出的算法在求解質(zhì)量以及運行時間方面均有優(yōu)質(zhì)的表現(xiàn)。最后總結(jié)了本文的主要貢獻及未來工作方向。第3期 王磊，等：訂單接受與調(diào)度問題求解方法與仿真研究 智能計算機與應用 第3卷

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

n個候選訂單等待決策，記為集合N={1，2，…，n}，其中i訂單的執(zhí)行時間為pi，發(fā)布日期為ri，交貨期為di，訂單完工時間底線為d′i，最大預期收益為Qi，訂單權(quán)重為wi，訂單實際開始時間為si。單機環(huán)境下訂單j與前序訂單i之間的隊列準備時間為setij，表示訂單i結(jié)束之后，至少需要setji時間之后才能開始執(zhí)行訂單j。

企業(yè)通過完成訂單獲得收益，如果在交貨期之前完成訂單i則可獲得最大預期收益Qi。但是，如果訂單拖期獲得的實際收益將隨訂單拖期時間Ti線性遞減，每超出一個時間單元即產(chǎn)生一定量的拖期懲罰；如果超出底線d′i，則制造企業(yè)無法獲得任何收益。本文設定訂單i的權(quán)重為wi=Qi/（d′i-di）。訂單i的拖期時長Ti=max{0，si+pi-di}。企業(yè)由訂單i獲得的實際收益即為Qi-wiTi。決策目標是從候選訂單集合N中選擇子集N′，N′N，使得企業(yè)通過執(zhí)行集合N′中的訂單而獲得實際收益最大化。

采用布爾型變量yi∈{0，1}表示是否接受訂單i，i∈N，如果接受訂單i則yi=1，否則yi=0。布爾變量xit∈{0，1}表示所接受訂單i的排序位置，其中i∈N且t∈{1，2，…，n}，如果訂單i被接受且排在訂單隊列的位置t則xit=1，否則xit=0。基于以上定義，提出考慮發(fā)布時間和隊列準備時間的單機環(huán)境下訂單接受與調(diào)度問題的混合整數(shù)規(guī)劃模型：

其中，目標函數(shù)（1）表示接受訂單的實際總收益最大，Ti=max{0，si+pi-di}表示訂單i的拖期時間；約束（2）表示所接受的每個訂單都被安排在訂單隊列的一個具體位置，而被拒絕的訂單則不在訂單隊列之中；約束（3）限定訂單隊列的每個位置至多安排一個訂單；約束（4）表示訂單之間的準備時間約束，即前序訂單i完成并經(jīng)過至少準備時間setij之后才能開始執(zhí)行訂單j；約束（5）表示訂單必須在時間底線之前完成，否則即使完成，也不會得到任何收益；公式（6）表示變量yi，xit均為布爾變量。

本文通過設計一種基于禁忌搜索策略的啟發(fā)式算法求該問題的近似最優(yōu)解，并通過仿真實驗檢驗算法的有效性。

2 禁忌搜索算法設計

禁忌搜索算法是一種模擬人工智能的元啟發(fā)式算法，為了彌補一般的局部搜索算法易于陷入局部最優(yōu)解的缺陷，引入禁忌表以及相應的禁忌準則來避免迂回搜索，通過設定藐視準則來赦免一些被禁忌的優(yōu)良狀態(tài)，算法能夠保證多樣化的有效搜索以最終實現(xiàn)全局優(yōu)化。

本文提出一種基于禁忌搜索策略的啟發(fā)式算法，求解上一節(jié)描述的訂單接受與調(diào)度問題。禁忌搜索算法包括以下核心要素：初始解、鄰域結(jié)構(gòu)、禁忌表、鄰域搜索策略以及藐視準則，通過設計上述算法核心要素，提出適于求解訂單接受與調(diào)度問題的啟發(fā)式算法。

2.1 可行解的表示

在求解訂單接受與調(diào)度問題中，采用向量v=（v1，v2，…，vi，…，vn）表示解空間中的一個解，其中，vi表示訂單i在訂單隊列中的排序位置。如果訂單i被拒絕，則vi=0。例如，對于包含10個候選訂單的集合N={1，2，…，10}來說，如果接受并按時間排序訂單1、7、9、8、3，則該解可表示為向量v=（1，0，5，0，0，0，2，4，3，0）。這種解的表達方式同時包含了訂單接受的決策結(jié)果以及訂單排序的調(diào)度結(jié)果。

2.2 構(gòu)造初始解

禁忌搜索算法由初始解開始迭代地尋找更優(yōu)解。對于訂單接受與調(diào)度問題，采用一種貪婪規(guī)則構(gòu)造該問題的初始解s0，這種貪婪規(guī)則同時考慮訂單收益、訂單執(zhí)行時間以及隊列準備時間三個因素。對于訂單i∈N，首先計算其收益負載率RLRi，其計算公式為：

RLRi=Qi/（pi+s′i）

（7）

其中，Qi表示訂單i的最大預期收益，pi為訂單執(zhí)行時間，s′i=（si0+si1+…+sin）/（n+1）。

訂單通過這種比例按照由高到低進行排序，從而促進能夠獲得更高收益的訂單具有更高的優(yōu)先級被接受并且排在執(zhí)行隊列的前面，而收益較低的訂單將排在后面。同時，被拒絕訂單的收益為0。一旦某個訂單被拒絕，則隊列中其余訂單的收益負載率RLRi將要進行重新計算。

2.3 領域結(jié)構(gòu)與移動操作

將禁忌搜索算法中的移動操作定義為交換和插入，并且設定當前解s*的鄰域結(jié)構(gòu)為N（s*）。通過交換當前解向量s*中的兩個值，可以構(gòu)造出相應的鄰域結(jié)構(gòu)。這種移動操作可以調(diào)整接受訂單的決策結(jié)果以及訂單排序。舉例來說，當前解向量（1，0，5，0，0，0，2，4，3，0），訂單執(zhí)行隊列為1、7、9、8、3，通過移動操作，可以得到兩個鄰域（5，0，1，0，0，0，2，4，3，0）以及（0，1，5，0，0，0，2，4，3，0）。第一個鄰域解沒有改變訂單接受/拒絕的決策結(jié)果，只是調(diào)整了訂單1和訂單3的執(zhí)行順序；而第二個鄰域解不僅調(diào)整了訂單執(zhí)行順序，而且改變了訂單接受/拒絕的決策結(jié)果，即拒絕訂單1而接受訂單2。而且，為了避免循環(huán)搜索，不允許交換解向量中兩個均為0的值。不難分析，給定解的鄰域結(jié)構(gòu)中，解的個數(shù)不超過n（n-1）/2。

進一步分析可以得到，如果交換了兩個訂單的執(zhí)行順序，則整個訂單集合中每個訂單的完成時間、拖期懲罰以及最終實際收益都可能由于訂單開始日期、隊列準備時間以及交貨期的影響而發(fā)生變化。如果因此造成某個訂單的收益為0，則需要拒絕該訂單。綜上所述，通過這種移動操作以及鄰域結(jié)構(gòu)，可能使得決策結(jié)果中接受訂單的數(shù)量減少。

2.4 禁忌表與禁忌長度

在禁忌搜索算法中，禁忌表中記錄了最近的搜索步驟，通過禁忌重復搜索這些業(yè)已經(jīng)過搜索的空間，避免算法陷入局部最優(yōu)解或者循環(huán)中。本文設計的算法中，設定禁忌表中存儲最近的n個搜索位置，在未來的搜索操作中將不再執(zhí)行這些操作，除非滿足特赦準則或者禁忌對象已經(jīng)獲得釋放。比如，當前解向量為（1，0，5，0，0，0，1，4，3，0），通過交換訂單1和訂單3的執(zhí)行順序得到新的解向量（5，0，1，0，0，0，2，4，3，0），其中的交換操作為交換訂單對（1，3）或（3，1），則將該交換訂單對置于禁忌表中并在禁忌長度內(nèi)不得重復交換訂單1或3。

2.5 特赦準則及結(jié)束條件

本文設計的禁忌搜索算法設定的特赦準則為：如果禁忌表中的操作能夠得到比當前解更優(yōu)的解，則忽視該操作被禁忌的特點而得到新的當前解。而為了綜合考慮問題的規(guī)模，又設定結(jié)束條件為n（n-1）/2次迭代操作。其中，n為待決策訂單的數(shù)量。

2.6 禁忌搜索算法流程設計

根據(jù)以上定義的禁忌搜索算法主要元素和實施策略，構(gòu)造求解訂單接受與調(diào)度問題的禁忌搜索算法流程如下：

初始化禁忌表Tabulist并置空：

1.讀入集合N中所有訂單i的發(fā)布時間ri，執(zhí)行時間pi，隊列準備時間setij，交貨期di以及訂單權(quán)重wi

2. 基于貪婪規(guī)則構(gòu)造生成初始解s0

3. 設定初始解為當前最好解s*s0

4. while 不滿足終止條件 do

5. 構(gòu)造鄰域結(jié)構(gòu)N（s*）

6. 在鄰域中搜索優(yōu)于當前解s*的更優(yōu)解s′

7. if 存在更優(yōu)解s′ then

8. s*s′，s′置于禁忌表TabuList中

9. else

10. 設置l=0

11. for l≤tabuLen do

12. 從N（s*）中選出相對較優(yōu)解s#

13. s*s#，l++

14. end for

15. 從禁忌表Tabulist中刪除s#

16. end if

17. 更新禁忌表TabuList

18. end while

3 仿真實驗與結(jié)果分析

本節(jié)根據(jù)所研究問題的特點設計了仿真實驗，分析所提出的禁忌搜索算法對問題求解的效果。通過與文獻[5]中提出的ISFAN和m-ATCS兩種啟發(fā)式方法進行比較，對算法的求解質(zhì)量以及收斂速度兩方面給出分析結(jié)果。

3.1 測試實例

為了驗證所提出的禁忌搜索算法對訂單接受與調(diào)度問題的求解效果，本文首先生成了一系列測試實例。基于文獻[5]提出的問題測試實例生成方法，文中根據(jù)實際問題特點對問題特征參數(shù)進行調(diào)整，并生成了更大規(guī)模的測試實例。比如，本文選擇的延遲因子λ為0.1，0.5，0.9，交貨期范圍取值ξ分別為0.3，0.5，0.7以及0.9，針對每一組延遲因子、交貨期組合，生成10個問題測試實例，因此每類問題均生成共計10×3×4=120個測試實例。同時，為了檢驗算法對于不同問題規(guī)模的相應效果，候選訂單的數(shù)量n分別取10和100，生成了小規(guī)模、大規(guī)模兩類問題實例。

3.2 仿真結(jié)果與分析

通過計算機仿真實驗，本文針對候選訂單數(shù)量n各自為10和100的兩種小、大規(guī)模的問題測試實例，分別比較了提出的禁忌搜索算法（TS）以及文獻[5]給出的ISFAN和m-ATCS兩種啟發(fā)式方法在求解效果、收斂速度兩方面的實現(xiàn)性能。具體來說，針對每個測試問題，分別比較三種算法在10個實例上獲得優(yōu)化解的個數(shù)，以及運算時間。所有實驗均在CPU主頻2GHz，內(nèi)存4GB的工作站執(zhí)行。在問題規(guī)模n=10情況下的仿真實驗結(jié)果如表1所示。

表1 n=10時m-ATCS、ISFAN和TS的性能

0.9 2 6 8 19.25 16.32 3.10

0.5 0.3 0 4 7 38.45 36.07 7.04

0.5 1 6 6 35.86 34.32 5.06

0.7 0 8 8 30.53 28.53 3.23

0.9 0 5 7 27.34 23.97 2.05

0.9 0.3 0 8 9 47.94 43.58 5.93

0.5 2 6 9 43.51 38.57 4.27

0.7 1 5 8 38.43 32.47 3.06

0.9 2 7 7 28.40 26.32 2.95

由表1所示的實驗結(jié)果比較分析可知：針對候選訂單數(shù)量n=10的小規(guī)模測試實例，ISFAN以及本文提出的TS算法表現(xiàn)較好，均能夠從每組問題的10個實例中快速找到數(shù)量相近的優(yōu)化解，而m-ATCS算法的求解效果相對稍差。

問題規(guī)模n=100情況下的仿真實驗結(jié)果見表2。

表2 n=100時m-ATCS、ISFAN和TS的性能

Tab.2 Performance of m-ATCS， ISFAN and TS with n=100

n=10 優(yōu)化解個數(shù) 計算時間

λ ξ m-AT ISF FCFS m-AT ISF FCFS

0.1 0.3 0 0 3 673.23 632.43 24.38

0.5 0 0 4 640.56 621.21 22.04

0.7 1 0 5 629.85 602.34 18.23

0.9 2 1 5 596.32 549.63 13.20

0.5 0.3 0 1 4 730.23 697.30 26.38

0.5 1 0 6 703.45 674.21 23.84

0.7 0 2 8 678.86 632.85 19.02

0.9 0 1 7 630.95 604.34 15.03

0.9 0.3 1 1 5 848.04 820.36 39.40

0.5 2 2 5 833.27 813.20 34.96

0.7 1 2 6 810.23 793.02 29.03

0.9 2 1 7 793.04 783.42 27.84

由表2所示的實驗結(jié)果比較分析可得：針對候選訂單數(shù)量n=100的大規(guī)模測試實例，m-ATCS和ISFAN兩種啟發(fā)式算法找到的優(yōu)化解數(shù)量相對較少，而本文提出的TS算法仍能尋求到一定數(shù)量的優(yōu)化解。還值得一提的是，TS算法的收斂性能更好，運算時間明顯優(yōu)越于另外兩種啟發(fā)式算法。

基于以上仿真實驗及結(jié)果對比分析，驗證了本文提出的禁忌搜索算法針對同時考慮訂單發(fā)布日期和隊列準備時間的訂單接受與調(diào)度問題能夠求得滿意解，尤其對大規(guī)模問題，禁忌搜索算法能夠更加快速地達到收斂，對于實際問題的求解將具有更好的實用價值。

4 結(jié)束語

本文針對單機環(huán)境下考慮發(fā)布日期和隊列準備時間的訂單接受與調(diào)度問題提出了一種基于禁忌搜索策略的啟發(fā)式算法，將訂單接受選擇決策與訂單排序生產(chǎn)計劃決策集成優(yōu)化，一定程度上解決了隊列準備時間給問題求解帶來的復雜性。通過計算仿真的方式與現(xiàn)有的兩種啟發(fā)式算法進行比較分析，驗證了本文提出算法具有較好的求解效果，尤其針對規(guī)模較大的問題實例能夠獲得更快的收斂速度。下一步研究可以在解的魯棒性方面進一步深入探討，考察訂單變化對于調(diào)度算法以及結(jié)果的影響。

參考文獻：

[1]SLOTNICK S， MORTON T. Order acceptance with weighted tardiness [J]. Computers and Operations Research， 2007， 34（10）： 3029-3042.

[2]LAWLER E， LENSTRA J， RINNOOY K A. Recent developments in deterministic sequencing and scheduling： a survey [M]. DEMPSTER M， LENSTRA J， RINNOOY K A， editors. Deterministic and stochastic scheduling， 1982： 35–73.

[3]SLOTNICK S A. Order acceptance and scheduling： a taxonomy and review [J]. European Journal of Operational Research， 2010， 212（1）： 1-11.

[4]NOBIBON F T， LEUS R. Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment [J]. Computers Operations Research， 2011， 38（1）： 367-378.

[5]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.

[6]CHEN Y， LI Y， YANG G K. Hybrid evolutionary algorithm with marriage of genetic algorithm and extremal optimization for production scheduling [J]. International Journal of Advanced Manufacturing Technology， 2008， 36（9-10）： 959-968.