一類單機(jī)排序問題的改進(jìn)禁忌搜索算法

《一類單機(jī)排序問題的改進(jìn)禁忌搜索算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、一類單機(jī)排序問題的改進(jìn)禁忌搜索算法一類單機(jī)排序問題的改進(jìn)禁忌搜索算法　　引言　　禁忌搜索（TabularSearch或TabooSearch，簡(jiǎn)稱TS）算法是繼遺傳算法之后出現(xiàn)的又一種元啟發(fā)式（Meta-Heuristic）優(yōu)化算法，最早于1977年由Glover提出。禁忌搜索算法已成功用于解決組合優(yōu)化問題。本文應(yīng)用禁忌搜索算法求解一類單機(jī)排序問題：SMTTP（theSingleMachineTotalTardinessProblem）。SMTTP是NP-hard組合優(yōu)化問題，解決這類問題的方法已

2、經(jīng)有各種最優(yōu)化算法和啟發(fā)式算法?！　”疚闹饕芯磕康模和ㄟ^一種本文由.LTTP的改進(jìn)禁忌搜索算法，計(jì)算實(shí)例說明此改進(jìn)禁忌算法是有效的。　　本文后面內(nèi)容安排如下：第二部分介紹SMTTP，并對(duì)相關(guān)的研究成果進(jìn)行簡(jiǎn)單回顧；第三部分介紹禁忌搜索算法；第四、五部分結(jié)合算例介紹求解SMTTP的改進(jìn)禁忌搜索算法；第六部分進(jìn)行總結(jié)?！　螜C(jī)總延遲問題（SMTTP）　　1、問題描述　　單機(jī)總延遲問題（SMTTP）考慮在一臺(tái)機(jī)器上加工n個(gè)工作或零件，其中同一時(shí)刻只能加工一個(gè)零件且零件的加工順序不預(yù)先設(shè)定。每一個(gè)零件j

3、（j=1，2，，n）的加工時(shí)間為Pj，且可在0時(shí)刻到達(dá)加工。另外，設(shè)dj，Cj和Tj=max{0，Cj-dj}分別為零件j的交貨時(shí)間、完工時(shí)間和延遲時(shí)間。SMTTP的目標(biāo)函數(shù)是在所有可能的零件排序中找到一個(gè)最優(yōu)排序，使得總延遲時(shí)間最小。SMTTP是更一般的具有加權(quán)延遲問題的特例，這類問題中，每個(gè)零件都分配了一個(gè)不同的權(quán)值。　　2、研究回顧　　單機(jī)總延遲問題是NP-hard問題，因此當(dāng)問題規(guī)模很大時(shí)很難找到最優(yōu)解。分支定界算法和動(dòng)態(tài)規(guī)劃算法是尋找此類問題最優(yōu)解的常用方法，而尋找加權(quán)延遲問題最優(yōu)解的方

4、法通常是枚舉算法。Emmons提出的幾條定理和優(yōu)先原則可以簡(jiǎn)化分支定界算法的搜索過程?；贓mmons的優(yōu)先原則，F(xiàn)isher提出了對(duì)偶變拉格朗日問題。Schrage和Baker，Lamons和Lamons的優(yōu)先原理。Pane）、改進(jìn)交貨時(shí)間序列（MDD，theModifiedDueDate）、改進(jìn)預(yù)期交貨時(shí)間序列（L-MDD，Look-aheadMDD）等。本文采用以下步驟生成初始解：　　第一步：輸入加工零件數(shù)n，零件加工時(shí)間ti（i=1，2，...，n），零件交貨時(shí)間di（i=1，2，...，

5、n）；初始時(shí)，所有零件未排序，標(biāo)記為INDEX（i）=0，i=1，2，...，n，且初始序列的最后位置L為0；　　第二步：計(jì)算所有未調(diào)度零件的總加工時(shí)間　　SUMT=？鄱INDEX（i）=0ti；　　第三步：計(jì)算所有未調(diào)度零件的總加工時(shí)間與交貨時(shí)間的盈余Si=SUMT-di；　　第四步：計(jì)算所有未調(diào)度零件單位加工時(shí)間內(nèi)的盈余量　??；　　第五步：找到所有未調(diào)度零件單位時(shí)間內(nèi)的最大盈余量，設(shè)對(duì)應(yīng)的零件編號(hào)為K；　　第六步：令L=L+1；　　第七步：在序列位置處安排加工零件K，即設(shè)FS（L）=K，置IN

6、DEX（K）=1；　　第八步：如果所有的零件已經(jīng)調(diào)度完，算法結(jié)束，否則轉(zhuǎn)第二步?！　?、鄰域移動(dòng)　　設(shè)零件調(diào)度序列為1，2，...，n的一個(gè)排列，其中序列S的位置i處零件標(biāo)號(hào)為Si，假設(shè)序列S中位置m處出現(xiàn)第一個(gè)延遲時(shí)間為正的零件，將Sm與序列S前m-1以及后n-m個(gè)位置的零件標(biāo)號(hào)的交換操作定義為禁忌搜索算法的鄰域移動(dòng)?！　?、禁忌策略　　禁忌對(duì)象選擇為鄰域移動(dòng)，禁忌表的長(zhǎng)度設(shè)為n-1?！　∷憷　≡O(shè)有7件零件在一臺(tái)機(jī)器上加工，它們的加工時(shí)間、交貨時(shí)間以及編號(hào)如下表1所示，試安排零件加工順序，使得

7、零件總延遲時(shí)間最短?！　∫陨厦娼o出的新解S中第一個(gè)出現(xiàn)延遲時(shí)間為正的零件序號(hào)S3=3構(gòu)造鄰域移動(dòng)，分別為（3，6）、（3，2）、（3，1）、（3，5）、（3，7）、（3，4）。當(dāng)前解的鄰域中所有移動(dòng)都不能改善總延遲時(shí)間，證明當(dāng)前解S=6，2，3，1，5，7，4為局部最優(yōu)解，由SMTTP的特殊性，此解也為最優(yōu)解。即解S=6，2，3，1，5，7，4為最優(yōu)解，總延遲時(shí)間?！　】偨Y(jié)　　禁忌搜索算法在解決旅行商、車輛路徑、圖著色、二次分配以及流水/作業(yè)車間調(diào)度等各種組合優(yōu)化問題時(shí)表現(xiàn)出很好的性能。針對(duì)一類特

8、殊的單機(jī)排序問題：?jiǎn)螜C(jī)總延遲問題（SMTTP），本文提出一種改進(jìn)禁忌搜索算法。算例表明改進(jìn)的禁忌搜索算法能快速找到問題的優(yōu)質(zhì)解。