基于模擬退火算法的多節(jié)點(diǎn)訂單排序模型
2009-01-01 00:00:00肖依永常文兵張人千
計(jì)算機(jī)應(yīng)用研究 2009年2期
(北京航空航天大學(xué) a.工程系統(tǒng)工程系；b.經(jīng)濟(jì)管理學(xué)院， 北京 100191)
摘 要：將Slotnick等人的單節(jié)點(diǎn)的訂單選擇模型擴(kuò)展到多節(jié)點(diǎn)，給出了較復(fù)雜的多處理節(jié)點(diǎn)的訂單排序優(yōu)化模型。采用了模擬退火算法來求解所建模型的優(yōu)化解，給出了詳細(xì)的算法步驟和幾種相鄰解的搜索策略。對模擬數(shù)據(jù)進(jìn)行了仿真求解計(jì)算，驗(yàn)證了算法的求解效果和計(jì)算效率，算例結(jié)果也表明：多節(jié)點(diǎn)的訂單選擇模型比單節(jié)點(diǎn)模型更加符合實(shí)際情況，能更準(zhǔn)確地計(jì)算訂單收益與延遲處罰，克服了單節(jié)點(diǎn)模型中的失真問題。
關(guān)鍵詞：訂單選擇；訂單排序；模擬退火算法；生產(chǎn)計(jì)劃
中圖分類號：TP273；C934 文獻(xiàn)標(biāo)志碼：A
文章編號：10013695(2009)02046004
Multistage order acceptance model based on simulated annealing algorithm
XIAO Yiyonga，CHANG Wenbinga，ZHANG Renqianb
(a.Dept. of System Engineering of Engineering Technology，b.School of Economics Management， Beihang University， Beijing 100191， China)
Abstract:This paper extended the singlestage model of order acceptance presented by Slotnick to multistage， and presented a more complicated model of sequencing order on multistage processing.Employed simulated annealing algorithm to find the optimal solution of the new model， and gave the detailed algorithm steps， as well as several feasible strategies on searching neighboring solutions.Subsequently，ran the algorithm on experimental data to validate its effect on finding optimal solution and its computational efficient as well. The results show that the multistage model is more close to the practices， and can find out the revenue and tardiness more accurately， which may be distorted in the singlestage model.
Key words:order acceptance; order sequencing; simulated annealing algorithm; production scheduling
0 引言
訂單選擇問題[1~3]，最初由Slotnick等人提出，描述的是在工廠有限處理能力下，如何從大量的訂單進(jìn)行選擇，以達(dá)到利潤最大化的目的。訂單選擇問題在近十年來得到了廣泛的理論研究和實(shí)踐應(yīng)用[4]。一個(gè)新訂單的接收與否主要是看訂單為企業(yè)帶來的收益是否大于其處理成本，這也是企業(yè)管理中比較常見的決策問題，在不同應(yīng)用場合、不同資源類型和不同假設(shè)條件下，模型的表現(xiàn)形式具有多種。其中比較典型的形式化描述如下[3，5]：
設(shè)一個(gè)工廠接收到n個(gè)客戶訂單，對于其中任何訂單i，其處理時(shí)間ai，交貨期di，以及銷售收益為pi，都是已知的。由于生產(chǎn)能力限制，某些訂單可能需要延遲交貨，對延遲交貨的訂單對應(yīng)有與延遲時(shí)間成正相關(guān)的處罰（或者銷售價(jià)折扣），而提前完成卻沒有任何額外的獎(jiǎng)勵(lì)。設(shè)wi表示延遲懲罰系數(shù)，ci為訂單i的完成時(shí)間。設(shè)S為所有訂單集U的某個(gè)子集，o是訂單子集S的一個(gè)排序，則訂單選擇的決策目標(biāo)就是尋找一個(gè)訂單集合S和訂單排序o，以最大化收益函數(shù)：z(S，o)=i∈S[pi-wi(ci-di)+]。向S中添加任何來自US的訂單都會(huì)使收益下降。
分支與界定(branch and bound，BB)算法[3，4，6]被用來快速求解小規(guī)模的此類問題，BB算法通過類似決策樹的帶有啟發(fā)式深度搜索的方式來得到較優(yōu)的近似解。對于大規(guī)模的此類問題，Slotnick則建議用啟發(fā)式算法如退火算法、禁忌搜索、遺傳算法來進(jìn)行近似優(yōu)化求解[4]。
Ghosh證明這是一個(gè)考慮訂單排序的01整數(shù)規(guī)劃問題，且具有NPhard的計(jì)算復(fù)雜性[5]，并給出了一種BS(beam search，BS)算法來對解空間進(jìn)行分支和選優(yōu)。Alidaee將問題分為排序和選擇兩部分，運(yùn)用貪婪式算法(greedy method)來進(jìn)行計(jì)算[7]。后來Slotnick還研究過此類問題的多個(gè)計(jì)劃期的訂單選擇問題[8]，主要是在訂單選擇時(shí)考慮了其未來關(guān)聯(lián)訂單的收益影響。文獻(xiàn)[9]考慮了單機(jī)器批量能力約束，訂單不再是一次性處理完畢，而是分批處理情況下的選擇問題，同時(shí)考慮了新增訂單的動(dòng)態(tài)插入問題。
然而，在現(xiàn)有的有關(guān)訂單選擇的研究文獻(xiàn)中都是假定訂單處理過程為單節(jié)點(diǎn)的（singlestage），假定只需一個(gè)環(huán)節(jié)（或?qū)⒍鄠€(gè)環(huán)節(jié)簡化為一個(gè)環(huán)節(jié)）即完成訂單處理。對于多節(jié)點(diǎn)(multistage)的訂單選擇優(yōu)化問題目前研究文獻(xiàn)還比較少。
與單節(jié)點(diǎn)的訂單選擇模型相比，多節(jié)點(diǎn)的訂單選擇模型必將更為復(fù)雜。但多節(jié)點(diǎn)的訂單處理更加接近于工廠實(shí)際，事實(shí)上很少有僅經(jīng)過一個(gè)環(huán)節(jié)就完成訂單處理的情況。如果將訂單的多個(gè)環(huán)節(jié)處理過程強(qiáng)行合并為一個(gè)環(huán)節(jié)，并應(yīng)用單節(jié)點(diǎn)模型進(jìn)行訂單選擇決策，那么通過本文的對比研究發(fā)現(xiàn)，這將導(dǎo)致不可容忍的計(jì)算誤差，進(jìn)而導(dǎo)致決策失誤而拒絕一些能夠獲益的訂單。
本文研究了多環(huán)節(jié)的訂單處理過程，給出了一種多節(jié)點(diǎn)的訂單選擇優(yōu)化模型。訂單排序是訂單選擇問題的難點(diǎn)及核心部分，設(shè)計(jì)了模擬退火算法來解決訂單排序問題。通過與單節(jié)點(diǎn)模型的計(jì)算比較，認(rèn)為多節(jié)點(diǎn)模型比單節(jié)點(diǎn)模型更具有準(zhǔn)確計(jì)算的優(yōu)勢，是后者的必要擴(kuò)展。
1 問題描述
訂單選擇問題包括選擇與排序兩個(gè)方面。其中排序是核心和難點(diǎn)，選擇是在排序的基礎(chǔ)上比較收益和損失而進(jìn)行決策，因而下面的模型主要面向訂單排序優(yōu)化問題。a）~g）形式化描述了多節(jié)點(diǎn)訂單排序問題：
a）設(shè)工廠處理訂單均有m個(gè)節(jié)點(diǎn)，表示為節(jié)點(diǎn)集J，以腳標(biāo)j表示第j個(gè)處理節(jié)點(diǎn)。所有訂單均需要該m個(gè)節(jié)點(diǎn)順序處理完畢后才能交付客戶。
b）在某期間內(nèi)，收到了n個(gè)訂單，表示為訂單集I。其中第i個(gè)訂單（i∈I）的交貨期設(shè)為di，收益設(shè)為pi，在第j個(gè)節(jié)點(diǎn)（j∈J）的處理時(shí)間為aij，且均為已知。
c）O={〈o， t〉ij}是各節(jié)點(diǎn)的訂單排序和完成時(shí)間。其中oij是在第j節(jié)點(diǎn)第i個(gè)順序號所對應(yīng)的訂單號；tij表示該節(jié)點(diǎn)的完成時(shí)間。這是需要求解計(jì)算的內(nèi)容。
d）C={〈c， s〉ij}是訂單集I中各訂單在各節(jié)點(diǎn)的完成時(shí)間和處理順序號。其中：cij表示訂單i在第j節(jié)點(diǎn)的完成時(shí)間；sij表示訂單i的第j節(jié)點(diǎn)的排序號。sij和oij可以相互轉(zhuǎn)換，cij和tij可以相互轉(zhuǎn)換，是為計(jì)算方面的數(shù)據(jù)。
e）對于訂單延遲交貨設(shè)置懲罰（或稱銷售折扣），處罰量與延遲時(shí)間量相關(guān)，為wi(cim-di)。其中：wi是訂單i的延遲懲罰系數(shù)；cim是訂單i的最后節(jié)點(diǎn)的完成時(shí)間。這里允許對不同訂單設(shè)置不同的延遲懲罰系數(shù)，以表示對不同訂單有著重視區(qū)別。
f）收益最大化函數(shù)定義為f(I，O)=i∈I[pi-wi](cim-di)+]。其中：cim表示訂單i在最后節(jié)點(diǎn)的完成時(shí)間，也即訂單完成時(shí)間；+號表示僅取正數(shù)。由于所有訂單必須按節(jié)點(diǎn)順序處理，訂單i在節(jié)點(diǎn)j開始處理的前提條件有兩個(gè)：一是在j節(jié)點(diǎn)處排在訂單i前面的訂單必須完成；二是訂單i前面j-1個(gè)節(jié)點(diǎn)也必須處理完畢。這樣，訂單i在節(jié)點(diǎn)j的開始時(shí)間必為兩者之最大值，完成時(shí)間即為cij=aij+max{ci，j-1，tkj}，tkj是在j節(jié)點(diǎn)排在訂單i前面的訂單完成時(shí)間。其中k=sij-1。
g）滿足約束條件下的利潤最大化的訂單排序優(yōu)化模型表示如下：
f(I，O)=maxi∈I[pi-wi(cim-di)+]（1）
滿足約束：
cij=aij+max{ci，j-1，tkj}；k=sij-1
(2)
tij=aoijj+ti-1， j當(dāng)j=1;i=1，2，3，…，n
aoijj+coij， j-1當(dāng)i=1;j=1，2，3，…，m
aoijj+max{coij， j-1，ti-1，j}當(dāng)i=2，3，…，n;j=2，3，…，m(3)
cij=tsijj且tij=coijj（4）
訂單選擇的過程則比較簡單，分兩步以下：
a）對所有訂單集合進(jìn)行收益優(yōu)化排序。
b）如果存在收益小于0的訂單，則剔除最小收益訂單，轉(zhuǎn)a）重新排序，直到所有訂單的收益均大于0。
多節(jié)點(diǎn)訂單選擇模型主要有以下幾個(gè)方面的改進(jìn)意義：（a）考慮階段性生產(chǎn)轉(zhuǎn)移的空閑利用效率，使訂單交付時(shí)間的計(jì)算更加精確。實(shí)際上，每工序的某訂單完成后一般即可開始后面訂單的處理，而不是要等到所有工序全部完成后才開始處理下一個(gè)訂單。（b）排序結(jié)果使訂單生產(chǎn)任務(wù)具體到每個(gè)作業(yè)點(diǎn)，對各個(gè)節(jié)點(diǎn)具有實(shí)際生產(chǎn)指導(dǎo)意義。（c）可以根據(jù)整體完成時(shí)間的優(yōu)化要求或節(jié)點(diǎn)局部的生產(chǎn)任務(wù)優(yōu)化，允許各個(gè)節(jié)點(diǎn)有不同的訂單處理順序，使整體計(jì)劃更優(yōu)。
2 模擬退火算法的求解策略
由于多節(jié)點(diǎn)模型的排序節(jié)點(diǎn)數(shù)遠(yuǎn)遠(yuǎn)多于單節(jié)點(diǎn)模型，其組合的解空間更大，隨著節(jié)點(diǎn)數(shù)的增多，計(jì)算復(fù)雜度也迅速增大。因而BB算法或者BS算法這類深度遍歷式分析算法，已難以適合這樣規(guī)模問題的最優(yōu)化求解。本文設(shè)計(jì)了模擬退火算法來求解題，結(jié)果表明具有很好的求解效果和計(jì)算效率。
退火過程是指金屬或玻璃經(jīng)過加熱后逐漸冷卻，從而有效改善其穩(wěn)定性的一種物理現(xiàn)象。模擬退火(simulated annealing，SA) 算法則是通過類比這種物理過程來求解組合優(yōu)化問題的一種啟發(fā)式算法[10，11]。其主要過程是：首先隨機(jī)給出一個(gè)初始解x0，然后按照一定方式尋找其相鄰解，再以式（5）的Metropolis概率來確定相鄰解是否被接受為當(dāng)前解，然后不斷重復(fù)這個(gè)過程，直到溫度降低到指定的閾值。
P（Oold→Onew）=1if ΔF≥0
exp(ΔF/T)else（5）
其中：ΔF=f(Onew)-f(Oold)，是相鄰解與當(dāng)前解的目標(biāo)函數(shù)差值；參數(shù)T稱為計(jì)算溫度，它在退火過程中逐漸降低。
模擬退火算法的解空間搜索策略是比較關(guān)鍵的技巧，其基本要求是：在高溫狀態(tài)下，解空間的所有可行解有均等的概率被搜索到，而隨著計(jì)算溫度的降低，解空間可行解被搜索到的概率服從GIBBS正則分布。簡言之，就是在搜索下一個(gè)解時(shí)，不能存在啟發(fā)式搜索達(dá)不到的某些解區(qū)域。圖1是解的矩陣存儲(chǔ)形式。O={oij}，表示了訂單在各節(jié)點(diǎn)的排序結(jié)果，圓圈節(jié)點(diǎn)oij中的值為訂單號。
為使所有排序組合的解均有可能產(chǎn)生，采用了完全隨機(jī)方式產(chǎn)生相鄰解。步驟如下：
a）隨機(jī)選擇一個(gè)訂單處理節(jié)點(diǎn)j，滿足1≤j≤m；
b）隨機(jī)選擇兩個(gè)排序位置i1，i2，滿足1≤i1，i2≤n且i1≠i2；
c）交換oi1， j和oi2， j的值（即訂單號），產(chǎn)生下一個(gè)相鄰的可行解。
計(jì)算可行解的收益函數(shù)之前，需要計(jì)算訂單的完成時(shí)間。訂單完成時(shí)間即指訂單在最后節(jié)點(diǎn)（即第m節(jié)點(diǎn)）的完成時(shí)間cim，需要從第1節(jié)點(diǎn)開始，根據(jù)式（2）~（4）遞推計(jì)算逐個(gè)節(jié)點(diǎn)的完成時(shí)間，直到計(jì)算出最后節(jié)點(diǎn)；然后再根據(jù)式（1）計(jì)算收益函數(shù)值。
根據(jù)上文所述，可行解的目標(biāo)函數(shù)值的計(jì)算步驟概要如下子過程：
a)輸入多節(jié)點(diǎn)訂單排序方案{oij}
b)計(jì)算第1節(jié)點(diǎn)（j=1時(shí)）訂單完成時(shí)間：
(a)t11=ak1，其中k=o11
(b)對于i=2，3，…，n順序計(jì)算：
ti1= ti-1，1+ak1，其中k=oi1
c）對于j=2，3，…，m，計(jì)算下面(a)(b)：
(a)t1j= ck， j-1+akj，其中k=o1j
(b)對于i=2，3，…，n順序計(jì)算：
tij=akj+max(ck，j-1，ti-1，j)，其中k=oij
d)計(jì)算：f=i∈I[pi-wi(cim-di)]
e)返回f
下面是模擬退火過程求解最優(yōu)收益函數(shù)的具體算法步驟：
a)隨機(jī)給定訂單排序{oij}作為初始解x0；
b)將當(dāng)前解連續(xù)1 000次轉(zhuǎn)換為相鄰解且接受為當(dāng)前解；
//加熱達(dá)到熱平衡
c)將b）中相鄰解間目標(biāo)函數(shù)最大差異作為初始溫度T0；
//退火初始溫度
d)T=T0；
e)do while (T>endT)
f) T=T*τ//計(jì)算溫度下降
g) for k=1 to N//循環(huán)N次達(dá)到熱平衡
h)隨機(jī)生成相鄰解Onew；
i)計(jì)算偏差ΔF=f(Onew)-f(Oold)；
j)根據(jù)Metropolis概率接受或拒絕Onew；
k) next
l) loop
m)獲得近似優(yōu)化解O及對應(yīng)的目標(biāo)函數(shù)值。
上述退火算法中，設(shè)計(jì)了三個(gè)計(jì)算參數(shù)，可設(shè)置不同參數(shù)值以適應(yīng)于不同規(guī)模的計(jì)算需求。三個(gè)參數(shù)分別是：
τ——降溫系數(shù)，取值在（0，1）；endT——計(jì)算結(jié)束溫度；N——熱平衡循環(huán)次數(shù)。
當(dāng)計(jì)算規(guī)模較大時(shí)，N需要相應(yīng)的較大值，才能使每個(gè)溫度層達(dá)到熱平衡；當(dāng)需要較好的優(yōu)化解時(shí)，降溫系數(shù)需要盡量接近1，如0.99，使降溫過程更慢，代價(jià)是需要更長的計(jì)算時(shí)間。End T是結(jié)束退火計(jì)算的截止溫度，與函數(shù)目標(biāo)函數(shù)值的規(guī)模相關(guān)，一般可設(shè)置為0.1。
3 算例驗(yàn)證
3.1 與單節(jié)點(diǎn)訂單排序的比較
本節(jié)以例子說明多節(jié)點(diǎn)訂單排序與單節(jié)點(diǎn)訂單排序的差異，以及驗(yàn)證模擬退火算法的計(jì)算
運(yùn)用上節(jié)設(shè)計(jì)的模擬退火算法，對表1數(shù)據(jù)分別采取了兩種處理方式計(jì)算最優(yōu)訂單排序，以比較不同模型策略下的求解差異。
方式1 單節(jié)點(diǎn)排序。將多節(jié)點(diǎn)的訂單處理過程簡化為單節(jié)點(diǎn)訂單處理過程，單節(jié)點(diǎn)處理時(shí)間為多個(gè)節(jié)點(diǎn)處理時(shí)間之和，計(jì)算這種簡化后的訂單排序結(jié)果以及收益函數(shù)。這也正是Slotnick等人最初提出的單節(jié)點(diǎn)訂單排序優(yōu)化模型。
方式2 多節(jié)點(diǎn)自由排序。按多節(jié)點(diǎn)優(yōu)化訂單排序，且各節(jié)點(diǎn)的訂單處理順序可自由排序，計(jì)算這種情況下的訂單排序結(jié)果和最好收益。
計(jì)算環(huán)境為Windows XP系統(tǒng)、VC 6.0編程環(huán)境、CPU主頻為1.6GHz的筆記本電腦。所采用模擬退火算法的計(jì)算參數(shù)τ=0.95；endT=0.01，N=300。重復(fù)100次地隨機(jī)初始化求解，保留其中最好的計(jì)算結(jié)果。表2和3分別給出了方式1、2的最好計(jì)算結(jié)果，各自僅用了7
比較表2和3的訂單排序結(jié)果可以看出，盡管所處理的仿真數(shù)據(jù)對象完全一樣，多節(jié)點(diǎn)訂單排序模型和單節(jié)點(diǎn)訂單排序模型的仿真優(yōu)化結(jié)果之間具有非常大的差異。延期的訂單數(shù)量也由七個(gè)降低到兩個(gè)，并且表2中的最后三個(gè)訂單（訂單號10、1、5）由于處罰大于收益，可能會(huì)被訂單選擇算法拒絕接單，而在表3的計(jì)算結(jié)果中卻都是盈利的訂單。這是由于多節(jié)點(diǎn)排序模型考慮了更細(xì)的生產(chǎn)過程，納入了更多信息而導(dǎo)致計(jì)算更加精確。如果強(qiáng)行將實(shí)際的多節(jié)點(diǎn)簡化為單節(jié)點(diǎn)模型，由于忽略了具體的處理過程，計(jì)算結(jié)果將會(huì)有較大的失真。事實(shí)上當(dāng)多節(jié)點(diǎn)模型的節(jié)點(diǎn)數(shù)縮減為1時(shí)，便自然退化為單節(jié)點(diǎn)模型。
由此可以得出這樣一個(gè)結(jié)論：多節(jié)點(diǎn)訂單排序模型是比單節(jié)點(diǎn)訂單模型更優(yōu)的擴(kuò)展模型，具有更加符合實(shí)際情況的優(yōu)勢，模型的仿真失真度更小，能獲得更優(yōu)化的訂單排序結(jié)果。
3.2 多節(jié)點(diǎn)的同步排序優(yōu)化
上文的多節(jié)點(diǎn)訂單排序模型中，各節(jié)點(diǎn)的訂單處理順序完全是自由的，最終目標(biāo)是為了收益函數(shù)的最大化。本節(jié)對多節(jié)點(diǎn)訂單排序的同步特性進(jìn)行了計(jì)算對比，即各節(jié)點(diǎn)的訂單處理順序控制為完全一致，所得到的最大收益函數(shù)值，與允許各節(jié)點(diǎn)自由排序所得到的最大收益函數(shù)值進(jìn)行對比。仍然采取表1的模擬數(shù)據(jù)，運(yùn)用模擬退火算法求解收益函數(shù)最大化的訂單排序，按下面方式3的處理搜索相鄰解：
方式3 多節(jié)點(diǎn)同步排序。按多節(jié)點(diǎn)優(yōu)化訂單排序，控制各節(jié)點(diǎn)的訂單排序完全一致。從當(dāng)前解搜索鄰近可行解采用如下尋找步驟：
a）隨機(jī)選擇兩個(gè)排序位置i1，i2，滿足1≤i1，i2≤n且i1≠i2；
b）對于j=1，2，…，m，交換oi1，j和oi2，j的值（即訂單號），產(chǎn)生下一個(gè)相鄰的可行解。
因而，當(dāng)初始化解時(shí)保證各節(jié)點(diǎn)訂單處理順序是一致的，以后按照方式3獲得的相鄰解也將保持各節(jié)點(diǎn)訂單處理順序的一致性。
所采用模擬退火算法的計(jì)算參數(shù)為τ=0.95，endT=0.01，N=300。重復(fù)100次地隨機(jī)初始化求解，保留其中最好的計(jì)算結(jié)果。表4是其中最好的計(jì)算結(jié)果，僅用了10 s計(jì)算時(shí)間。
對比表3和4的排序結(jié)果，可以發(fā)現(xiàn)各個(gè)節(jié)點(diǎn)的訂單順序略有不同，但是兩者具有相同的收益函數(shù)值370.75。實(shí)際上經(jīng)過筆者反復(fù)調(diào)整計(jì)算參數(shù)，經(jīng)多次大規(guī)模計(jì)算表明，370.75已經(jīng)是最大的收益值，但相同最大收益的訂單排序還有其他幾種方式，限于篇幅這里不再一一列出。
再對比方式2和3情況下，重復(fù)100次計(jì)算得到的解的分布情況，如圖2所示。
從圖2和3的求解分布情況來看，圖3中的100次求解過程中有85次得到最優(yōu)解370.75，而圖2中的100次求解過程中僅有4次得到最優(yōu)解，圖3的求解效果明顯優(yōu)于圖2。從本次模擬算例的計(jì)算結(jié)果看來，采用方式3，即各節(jié)點(diǎn)保持相同的訂單排序方式，具有極其優(yōu)越的求解效果，得到的收益函數(shù)基本都集中分布在最優(yōu)解附近。
上述計(jì)算之后，筆者隨機(jī)生成了100次類似表1的多節(jié)點(diǎn)訂單排序數(shù)據(jù)，依次采用多節(jié)點(diǎn)自由排序（方式2）和多節(jié)點(diǎn)同步排序（方式3）各重復(fù)100次計(jì)算最好的收益函數(shù)及其累積次數(shù)。結(jié)果表明：多節(jié)點(diǎn)自由排序算法下的最大收益函數(shù)值總是等于或低于同步排序算法的最大收益函數(shù)，且100次中的最好解累積次數(shù)也遠(yuǎn)遠(yuǎn)高于后者。算例結(jié)果表明：延遲懲罰的多節(jié)點(diǎn)訂單排序問題的最優(yōu)解集合中，必定存在一個(gè)最優(yōu)解，其中各節(jié)點(diǎn)的訂單排序順序完全一致。
3.3 求解過程的比較
最后，比較了本文給出的針對訂單排序優(yōu)化模型的三種求解方式的最優(yōu)解逼近特性。仍然按照表1的模擬數(shù)據(jù)計(jì)算。模擬退火計(jì)算參數(shù)為τ=0.95，endT=0.01，N=300。在三種方式各自的求解過程中，記錄退火過程中每層溫度的最后解的收益函數(shù)。得到如圖4所示的趨勢圖。
從圖4可以看出，方式3具有最好的逼近效果，方式2次之，方式1（即單節(jié)點(diǎn)模型）的求解結(jié)果具有較大失真度，其得到的收益值遠(yuǎn)低于前面兩種。
4 結(jié)束語
訂單選擇與排序是生產(chǎn)管理中常見的決策問題，也得到了廣泛的理論研究和實(shí)踐應(yīng)用。本文研究的貢獻(xiàn)是嘗試了建立多節(jié)點(diǎn)的訂單選擇和排序模型，并通過算例表明其相對于單節(jié)點(diǎn)訂單選擇模型的卓越優(yōu)勢，能更精確地計(jì)算交付時(shí)間，從而支持更準(zhǔn)確的訂單選擇決策。本文僅選擇了模擬退火算法來求解此類問題的最優(yōu)解，并且求解效果和計(jì)算效率也很令人滿意。但其他的啟發(fā)式智能算法，如遺傳、粒子群、群蟻、禁忌搜索等，均可以應(yīng)用于多節(jié)點(diǎn)訂單排序模型的優(yōu)化求解。比較其中的計(jì)算優(yōu)勢，改進(jìn)效率，或者將訂單排序和選擇集成起來，設(shè)計(jì)適合的啟發(fā)式求解算法也是一個(gè)值得進(jìn)一步研究的內(nèi)容。
參考文獻(xiàn)：
［1］
DE P，GHOSH J B，WELLS C E.Job selection and sequencing on a single machine in a random environment[J].European Journal of Operational Research，1993，70:425431.
[2]FORST F G.Bicriterion stochastic scheduling on one or more machines[J].European Journal of Operational Research，1995，80:404409.
[3]SLOTNICK S A，MORTON T E.Selecting jobs for a heavily loaded shop with lateness penalties[J].Computers Operations Research，1996，23(2):131140.
[4]SLOTNICKA S A，MORTONB T E.Order acceptance with weighted tardiness[J].Computers Operations Research，2007，34:30293042.
[5]GHOST J B.Job selection in a heavily loaded shop[J].Computers Operations Research，1997，24(2):141145.
[6]GUTJAHR W J，HELLMAYR A，PFLUG G C.Optimal stochastic singlemachinetardiness scheduling by stochastic branch and bound[J].European Journal of Operational Research，1999，117:396413.
[7]ALIDAEE B，KOCHENBERGER G A，AMINI M M.Greedy solutions of selection and ordering problems[J].European Journal of Operational Research，2001，134:203215.
[8]SLOTNICK S A，LEWIS H F.Multiperiod job selection: planning work loads to maximize profit[J].Computers Operations Research，2002，29(9):10811098.
[9]ROUNDY R，CHEN C，CHEN P，et al.Capacitydriven acceptance of customer orders for a multistage batch manufacturing system: models and algorithms[J].IIE Transactions，2005，37(12): 10931095.
[10]KIRKPATRICK S，GELATT C，VECCHI M.Optimization by simulated annealing[J].Science，1983，220:671680.
[11]KAKU I，XIAO Yiyong，XIA Guoping.The deterministic annealing algorithms for vehicle routing problems[J].International Journal of Smart Engineering System Design，2003，5(4):327339.
