基于禁忌搜索算法求解流水作業(yè)最小誤工調(diào)度問題

韋 康，李昕昀，陳 鑫

基于禁忌搜索算法求解流水作業(yè)最小誤工調(diào)度問題

韋 康，李昕昀，陳 鑫

（遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001）

針對(duì)流水作業(yè)環(huán)境最小化誤工損失調(diào)度問題，提出一個(gè)禁忌搜索算法對(duì)其進(jìn)行求解。利用多個(gè)啟發(fā)式規(guī)則生成可行調(diào)度，從中選出最好解作為算法的初始解；同時(shí)，基于隨機(jī)交換策略，權(quán)衡求解質(zhì)量與運(yùn)行時(shí)間之間的關(guān)系定義鄰域搜索機(jī)制；采用雙禁忌表結(jié)構(gòu)防止算法陷于局部最優(yōu)；最后，定義算法停止規(guī)則。數(shù)值實(shí)驗(yàn)表明，與傳統(tǒng)禁忌搜索算法相比，新算法在求解質(zhì)量和處理速度上進(jìn)一步優(yōu)化，且該優(yōu)勢(shì)隨著問題規(guī)模的增大而更加明顯。

誤工損失；流水作業(yè)；調(diào)度問題；禁忌搜索算法

調(diào)度是管理者在經(jīng)營(yíng)過程中需要做出的重要決策之一，可以涉及制造、運(yùn)輸、分配等多種生產(chǎn)場(chǎng)景，有效的調(diào)度策略不僅可以對(duì)生產(chǎn)資源進(jìn)行充分利用，而且還可以提高用戶的滿意度[1-2]。其中，是否按時(shí)完成任務(wù)是衡量用戶滿意度的重要指標(biāo)之一，因此，在用戶期待的時(shí)間（即任務(wù)的交付期，due date）之前完成任務(wù)十分重要。任務(wù)的誤工損失（late work）是一個(gè)與其交付期有關(guān)的懲罰量，其完工時(shí)間越滯后于交付期，所對(duì)應(yīng)的懲罰量越大（但最大不會(huì)超過任務(wù)的加工時(shí)間）。由于誤工損失指標(biāo)能夠描述實(shí)際生產(chǎn)中的多種場(chǎng)景，基于該指標(biāo)的調(diào)度問題吸引著諸多學(xué)者的廣泛關(guān)注[3]。

Blazewicz[4]在研究并行機(jī)環(huán)境的調(diào)度問題中首次提出誤工損失這一概念，并慢慢將其泛化，引入到不同的處理機(jī)環(huán)境下加以研究。在調(diào)度問題三參數(shù)表示法[5]中，最小化該指標(biāo)用符號(hào)表示。20世紀(jì)末期，Potts等[6]對(duì)單機(jī)調(diào)度問題1||加以研究，證明了該問題是NP難問題，并給出了解決此問題的偽多項(xiàng)式時(shí)間（Pseudo-polynomial time）動(dòng)態(tài)規(guī)劃算法。進(jìn)而，Kovalyov等[7]將關(guān)注點(diǎn)擴(kuò)展至考慮權(quán)重的模型，并給出了問題1||Y的多項(xiàng)式時(shí)間近似方案（fully polynomial-time approximation scheme，F(xiàn)PTAS）。2002年，Kethley等[8]針對(duì)這一問題（1||Y）再次進(jìn)行了研究，他們?cè)O(shè)計(jì)了一系列算法，并通過數(shù)值實(shí)驗(yàn)對(duì)算法的性能進(jìn)行對(duì)比分析。Ren等[9]考慮了批處理單機(jī)調(diào)度中的最小誤工損失問題1|≥|Y，證明該問題依然為NP難，并給出了偽多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法。隨后，Wu等[10]研究了帶學(xué)習(xí)效應(yīng)的單機(jī)調(diào)度問題1||，并設(shè)計(jì)了一個(gè)分支定界算法和一系列遺傳算法進(jìn)行對(duì)比分析。近期，Chen等[11]將截止期（deadline）引入最小化誤工損失的單機(jī)調(diào)度問題，給出了與1|d|Y有關(guān)的一系列復(fù)雜性和可近似性結(jié)果。

針對(duì)誤工損失指標(biāo)的研究起源于平行機(jī)環(huán)境。Blazewicz[4]在其開創(chuàng)性文章中，將允許搶占的平行機(jī)調(diào)度問題||Y和||Y歸約為網(wǎng)絡(luò)流問題，這樣可以在多項(xiàng)式時(shí)間內(nèi)對(duì)問題求解；且說明若不允許搶占，該問題（||Y）為強(qiáng)難問題。隨后，該結(jié)果又分別被Blazewicz等[12]、Leung[13]進(jìn)行了改進(jìn)。Xu等[14]考慮了加權(quán)公共交付期的平行機(jī)調(diào)度問題|d=|Y，設(shè)計(jì)了蟻群算法、遺傳算法和模擬退火算法對(duì)其求解，并對(duì)比了算法性能。Sterna等[15]從可近似性的角度對(duì)問題進(jìn)行了研究，她們將視角由最小化誤工損失（late work minimization）切換至最大化加工收益（early work maximization），給出了2臺(tái)平行機(jī)、公共交付期問題2|d=|max()的多項(xiàng)式時(shí)間近似方案（PTAS）。最近，這一結(jié)果被Chen等[16]改進(jìn)，他們給出了更通用的模型|d=|max()（≥ 2）的完全多項(xiàng)式時(shí)間近似方案（FPTAS）。

對(duì)于串聯(lián)機(jī)環(huán)境下最小誤工損失的研究始于自由作業(yè)（open shop）。Blazewicz等[17]于2014年基于2|d=|Y問題，首先分析了誤工損失指標(biāo)與其他優(yōu)化目標(biāo)之間的關(guān)聯(lián)關(guān)系，進(jìn)而證明所研究問題為弱NP難問題。隨后，他們將結(jié)果推廣至流水作業(yè)（flow shop）2|d=|Y問題[18]、自由作業(yè)（job shop）2|d=|Y問題[19]，分別證明了這些問題的復(fù)雜性，且設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法對(duì)其求解。除了這一團(tuán)隊(duì)，Lin等[20]證了無(wú)權(quán)重的模型2|d=|依然屬于難范圍，并設(shè)計(jì)了分支定界算法和元啟發(fā)式算法求解其通用情況2||。近期，Piroozfard等[21]考慮了柔性自由作業(yè)的多目標(biāo)調(diào)度問題，他們基于實(shí)際生產(chǎn)問題，將最小化誤工損失及碳排放作為優(yōu)化目標(biāo)，為問題構(gòu)建了數(shù)學(xué)模型，并設(shè)計(jì)了遺傳算法對(duì)其求解。

綜上，本文設(shè)計(jì)了一個(gè)禁忌搜索算法求解流水作業(yè)最小誤工損失調(diào)度問題（||）。首先通過多個(gè)啟發(fā)式規(guī)則產(chǎn)生算法的初始解，然后基于目標(biāo)函數(shù)對(duì)禁忌表和鄰域搜索方法進(jìn)行設(shè)計(jì)，最后通過公共測(cè)試集對(duì)算法性能進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明，算法可以在較快時(shí)間內(nèi)得到質(zhì)量較好的可行解，是解決所研究問題的一個(gè)有效方法。

1 問題描述

任務(wù)的誤工損失對(duì)應(yīng)其在交付期之后加工的部分，可以表示延遲加工所帶來(lái)的懲罰量；任務(wù)的延誤時(shí)間越長(zhǎng)，該懲罰量越大（但是不會(huì)超過其加工長(zhǎng)度）。本文所研究的問題可以描述如下：

2 禁忌搜索算法

2.1 算法概述

禁忌搜索（tabu search，TS）算法[22]是基于隨機(jī)搜索的元啟發(fā)式算法之一，由Glover[23]于1986年正式提出。其模仿人類思維，擁有靈活的記憶存儲(chǔ)功能，即：算法在搜索過程中記錄之前的部分搜索軌跡，從而會(huì)有意避開這些已經(jīng)搜索過的區(qū)域。主要過程為：把一個(gè)可行解作為初始解，通過鄰域搜索產(chǎn)生多個(gè)候選解并從中選擇一個(gè)質(zhì)量相對(duì)好的解作為后代，以此進(jìn)行迭代。為了避免陷入重復(fù)搜索，算法采用一種靈活的記憶存儲(chǔ)技術(shù)，即禁忌表（Tabu List）對(duì)已經(jīng)進(jìn)行搜索過的區(qū)域進(jìn)行記錄；此外，考慮到完全禁忌前期搜索軌跡將過于嚴(yán)格，算法還可以定義一系列“特赦準(zhǔn)則”，可以將某個(gè)解從禁忌表中“解禁”從而基于其繼續(xù)搜索。

2.2 求解Fm||Y問題的TS算法

為了有效地求解||問題，首先用一串值為1 ~的整數(shù)數(shù)組表示一個(gè)可行調(diào)度，數(shù)組中每個(gè)元素對(duì)應(yīng)為任務(wù)序號(hào)。也就是說，一個(gè)可行解可以表示為：

= (1,2, ...,j) （j∈ {1, 2, ...,}）

接下來(lái)，對(duì)TS算法初始解生成、鄰域搜索策略、雙禁忌表結(jié)構(gòu)、特赦規(guī)則、終止條件的設(shè)置等分別介紹如下。

2.2.1 禁忌搜索的初始解

良好的初始解能夠有效地加快收斂速度，從而提高搜索效率和解的質(zhì)量，本文采用6種啟發(fā)式策略和隨機(jī)過程生成7個(gè)可行調(diào)度方案，從中選則最好解作為TS算法的初始解。其中，6種啟發(fā)式策略分別為[24]：

EDD（earliest due date first）：交付期小的任務(wù)優(yōu)先加工；SPT（smallest processing time first）：總加工時(shí)間小的任務(wù)優(yōu)先加工；LPT（largest processing time first）：總加工時(shí)間大的任務(wù)優(yōu)先加工；FSPT（first-piece smallest processing time first）：在1上所需加工時(shí)間小的任務(wù)優(yōu)先加工；FLPT（first-piece largest processing time first）：在1上所需加工時(shí)間大的任務(wù)優(yōu)先加工；SDPT（smallest due dateprocessing time，d/p）：交付期與加工時(shí)間比值小的任務(wù)優(yōu)先加工。

2.2.2 鄰域搜索策略

基于||問題解的編碼方式，本文采用“隨機(jī)交換”的方式構(gòu)造鄰域空間。對(duì)于當(dāng)前編碼（由位正整數(shù)構(gòu)成），任意選擇2個(gè)元素進(jìn)行交換，從而形成一個(gè)新的編碼存入鄰域空間；然而，由于可行的選擇共計(jì)C2種，全部枚舉將非常耗時(shí)（而且也沒有必要），本文定義鄰域空間大小為=（為任務(wù)數(shù)量），即：每輪迭代過程中進(jìn)行次隨機(jī)選擇，從而形成個(gè)（沒有被禁忌的）有效編碼組成鄰域空間。在TS算法迭代過程中，每次從鄰域空間選擇質(zhì)量最好的解，作為下一次迭代的基本解。

2.2.3 禁忌表

禁忌表是TS算法的核心部分，用來(lái)記錄已經(jīng)搜索過的解；除非滿足特赦規(guī)則，否則禁忌表中的解在算法搜索過程中將不會(huì)被二次選中。禁忌表可以設(shè)計(jì)為先入先出的隊(duì)列，在本文中，設(shè)計(jì)短期記憶和長(zhǎng)期記憶兩類禁忌表來(lái)控制算法的搜索精度與廣度，短期禁忌表的長(zhǎng)度為鄰域大小的1.5倍（即1.5），而長(zhǎng)期禁忌表的長(zhǎng)度則設(shè)置為一個(gè)定值= 25。

在禁忌表已滿的狀態(tài)下，當(dāng)有新的編碼進(jìn)入時(shí)，禁忌表遵循先入先出方法，移除表中禁忌時(shí)間最長(zhǎng)的解，為新進(jìn)入的解釋放空間。

（1）短期記憶禁忌表。在對(duì)當(dāng)前解的鄰域解集進(jìn)行搜索過程中，短期記憶防止算法在當(dāng)前解的某一部分解集進(jìn)行重復(fù)搜索，既損耗時(shí)間，也沒有提高候選解的質(zhì)量。在實(shí)際算法設(shè)計(jì)中，由于禁忌表是一個(gè)有固定長(zhǎng)度的隊(duì)列，雖然不能完全避免算法重復(fù)搜索，但是當(dāng)禁忌解釋放出來(lái)后，如果算法又對(duì)其進(jìn)行搜索，這樣很大程度上能降低算法在解空間的收斂速度，增加判斷候選解是否為禁忌解的時(shí)間。

禁忌算法近期搜索過的解將存放在短期禁忌表中，往往在幾次迭代后從禁忌表中移除，重新成為未被搜索過的可行解；短期記憶禁忌表在一定程度上能防止算法過早陷入局部搜索循環(huán)。

當(dāng)搜索策略是隨機(jī)選取當(dāng)前解的鄰域解集時(shí)，會(huì)產(chǎn)生一個(gè)到多個(gè)完全相同的解集，可以通過短期記憶禁忌表避免搜索重復(fù)。例如，在某次迭代后，當(dāng)前解的鄰域解集為1，經(jīng)過一次迭代后，當(dāng)前解的鄰域解集為2，1和2會(huì)有一定可能出現(xiàn)交集3。這樣短期記憶禁忌表就可以讓算法避免重復(fù)搜索交集3，減少時(shí)間的損耗。

（2）長(zhǎng)期記憶禁忌表。長(zhǎng)期記憶禁忌表主要在搜索鄰域空間的廣度上起到一定作用，但與短期記憶禁忌表的禁忌對(duì)象不同，長(zhǎng)期記憶禁忌表只禁忌每次迭代后的當(dāng)前解。

長(zhǎng)期記憶禁忌表與短期記憶禁忌表相比，表中信息更新速度慢，只有在每次迭代后，才進(jìn)行一次更新。而短期記憶禁忌表的更新速度與當(dāng)前解的鄰域搜索次數(shù)有關(guān)，鄰域搜索次數(shù)越多，更新速度也越快。長(zhǎng)期記憶禁忌表能夠?qū)⒈韮?nèi)對(duì)象禁忌很長(zhǎng)時(shí)間，從而算法可以搜索其他未搜索的區(qū)域來(lái)防止算法過早陷入局部最優(yōu)。

2.2.4 特赦規(guī)則

禁忌表可能導(dǎo)致候選解全部被禁忌或者最好解被禁忌，此時(shí)需要運(yùn)用“特赦規(guī)則”將某些被禁忌的解釋放，從而讓算法繼續(xù)進(jìn)行搜索。本文采用“階梯釋放規(guī)則”完成特設(shè)過程，即：設(shè)置一系列閾值1<2<3< ……，若出現(xiàn)候選解全部被禁忌的情況，則首先釋放禁忌表中目標(biāo)函數(shù)值與當(dāng)前搜索到最好解的比值在1范圍之內(nèi)的全部解；若禁忌表中不存在這樣的解（比值在1范圍之內(nèi)），則釋放比值在2范圍之內(nèi)的全部解，以此類推。本文設(shè)1= 1.05，2= 1.1，后面的閾值（3等）按照0.05遞增。

2.2.5 算法終止條件

本文設(shè)計(jì)了2種終止條件，當(dāng)二者之一被滿足時(shí)，TS算法停止搜索，并輸出搜索到的最好解：

（1）當(dāng)達(dá)到最大迭代次數(shù)，本文設(shè)定為120；（2）當(dāng)最好解未更新的次數(shù)超過一個(gè)預(yù)定閾值時(shí)，本文設(shè)定為30。

3 實(shí)驗(yàn)及結(jié)果分析

本文算法采用C++編碼，使用的開發(fā)平臺(tái)為Visual Studio 2019，測(cè)試平臺(tái)為Intel(R) Core(TM) i5-8300H 2.30GHz、8 GB RAM的筆記本電腦。

3.1 實(shí)驗(yàn)數(shù)據(jù)

其中，是一個(gè)控制交貨期緊密程度的參數(shù)，值越大，任務(wù)的交付期普遍取值偏小，即任務(wù)的加工更為“緊迫”；否則，任務(wù)的交付期普遍取值偏大，加工安排可以更具有彈性。與文獻(xiàn)[20]保持一致，本文對(duì)的取值也設(shè)置為3、5、7。

3.2 實(shí)驗(yàn)結(jié)果及分析

本文通過傳統(tǒng)禁忌搜索算法與本文改進(jìn)禁忌搜索算法對(duì)||的求解能力進(jìn)行對(duì)比，使用質(zhì)量提升率指標(biāo)（(Y-Y)/Y*100%）來(lái)評(píng)估算法能力[25]，其中Y是某種啟發(fā)式算法得到的目標(biāo)函數(shù)值，Y是傳統(tǒng)或本文禁忌搜索得到的目標(biāo)函數(shù)值。本文使用不同的機(jī)器數(shù)量、任務(wù)數(shù)量與緊密系數(shù)進(jìn)行組合，其中分別取值為3、5、7、10；對(duì)于每一個(gè)具體的值，任務(wù)數(shù)量分別設(shè)置為10、15、20；如前所述，的取值設(shè)置為3、5、7。針對(duì)每一組參數(shù)組合，分別運(yùn)行50次實(shí)驗(yàn)取平均值，共計(jì)進(jìn)行實(shí)驗(yàn)1 800組，所得結(jié)果如表1[以(,)組合評(píng)估]和表2（以評(píng)估）所示。

表1 (, )組合不同時(shí)傳統(tǒng)與改進(jìn)禁忌搜索算法的性能表現(xiàn)

mn 隨機(jī) EDD LPT SPT FSPT FLPT SDPT 傳統(tǒng)TS時(shí)間/s改進(jìn)TS時(shí)間/s 傳統(tǒng)改進(jìn)傳統(tǒng)改進(jìn)傳統(tǒng)改進(jìn)傳統(tǒng)改進(jìn)傳統(tǒng)改進(jìn)傳統(tǒng)改進(jìn)傳統(tǒng)改進(jìn) 33025.3127.9233.5636.1117.7920.9716.3419.3817.1920.2519.9522.9530.9033.470.28730.0048 4522.7131.3427.5735.5412.8622.6110.5620.6707.6818.1716.8026.1226.4034.530.85760.0127 6024.8236.4927.8738.9311.5125.2307.6622.0606.6121.2115.0028.1226.8238.052.17960.0325 組內(nèi)平均值24.2831.9229.6736.8614.0522.9411.5220.7010.4919.8817.2525.7328.0435.351.10820.0167 55021.5834.1231.3141.9412.8226.4908.4422.7910.8024.8420.1932.5829.5140.462.00750.0315 7519.3932.2831.7542.3710.7424.3511.6125.2515.6028.7315.0728.2429.6540.686.89240.0817 10016.3628.7831.9241.7808.6621.8108.8922.2612.9025.5619.7431.3030.1040.2715.49320.2431 組內(nèi)平均值19.1131.7331.6642.0310.7424.2209.6523.4313.1026.3818.3330.7129.7540.478.13100.1188 77011.9025.6529.3040.4015.8529.0613.1526.7614.9328.2621.4033.8126.7038.207.74660.1231 10509.0427.3427.3441.8413.8130.9211.0128.6613.0530.3523.7638.7822.5638.0724.20930.3840 14023.1328.4931.3936.3427.7033.2226.0131.4825.0030.5433.7938.8133.6038.4064.21240.8237 組內(nèi)平均值14.6927.1629.3439.5319.1231.0716.7228.9717.6629.7226.3237.1327.6238.2232.05610.4436 1010020.6128.6428.9230.7433.5041.2928.0136.4628.4136.7834.1642.0929.0533.2730.12940.4666 15023.5730.9627.5529.6933.4841.0532.8539.9135.4242.4337.4944.7127.1630.5197.28021.2887 20011.9119.6927.5732.6022.4630.0423.0930.6529.6036.6332.4139.2125.8331.04265.52572.6592 組內(nèi)平均值18.7026.4328.0131.0129.8137.4627.9835.6731.1438.6134.6942.0027.3531.61130.97841.4715 平均值19.1929.3129.6737.3618.4328.9216.4727.1918.1028.6524.1533.8928.1936.4143.06840.5126

從2個(gè)表中不難看出，改進(jìn)TS算法在時(shí)間和解的質(zhì)量上都比傳統(tǒng)TS算法效果要好。例如，當(dāng)= 3、= 30時(shí)（見表1），傳統(tǒng)TS算法對(duì)SDPT解的平均改善程度為30.90%，而改進(jìn)TS則達(dá)到了33.47%。在任務(wù)數(shù)量增加的情況下，改進(jìn)TS算法的改善效果會(huì)稍微下降。在7個(gè)初始解中，TS算法對(duì)EDD的改善程度最好，對(duì)SPT的改善程度最差。因此，用SPT作為禁忌搜索的初始解效果最好，反之，用EDD作為禁忌搜索的初始解效果最差。此外，傳統(tǒng)TS算法在1 800組實(shí)驗(yàn)過程中的平均運(yùn)行時(shí)間為43.0684 s，而改進(jìn)TS算法僅僅為0.5126 s，說明改進(jìn)后的算法運(yùn)行速度遠(yuǎn)遠(yuǎn)小于傳統(tǒng)算法。

表2 不同時(shí)傳統(tǒng)與改進(jìn)禁忌搜索算法的性能表現(xiàn)

β隨機(jī) LPT SPT FSPT FLPT SDPT傳統(tǒng)TS時(shí)間/s改進(jìn)TS時(shí)間/s 傳統(tǒng)改進(jìn) 傳統(tǒng)改進(jìn) 傳統(tǒng)改進(jìn) 傳統(tǒng)改進(jìn) 傳統(tǒng)改進(jìn) 傳統(tǒng)改進(jìn) 323.3131.20 31.3639.57 27.0135.68 27.7636.46 37.6645.05 27.9133.5241.35750.5448 515.2226.68 14.9626.07 12.9424.33 15.0926.17 20.2330.63 29.1138.5540.11860.5343 719.0530.04 08.9721.12 09.4721.57 11.4523.31 14.5526.00 27.5537.1747.72920.4588 平均值19.1929.31 18.4328.92 16.4727.19 18.1028.65 24.1533.89 28.1936.4143.06840.5126

表2反映了無(wú)論是傳統(tǒng)禁忌搜索算法，還是改進(jìn)禁忌搜索，其性能都會(huì)隨著的上升而下降，說明隨著任務(wù)的交付期d取值變小，TS算法對(duì)初始解的提升能力將會(huì)下降。

4 結(jié)論

本文為流水作業(yè)環(huán)境下的最小化工件誤工損失調(diào)度問題設(shè)計(jì)了一個(gè)禁忌搜索算法，對(duì)其的初始解生成、鄰域搜索策略、禁忌表設(shè)置等進(jìn)行了進(jìn)一步的優(yōu)化，并與6個(gè)啟發(fā)式策略EDD、LPT、SPT、FSPT、FLPT、SDPT和隨機(jī)過程生成的可行調(diào)度方案進(jìn)行對(duì)比評(píng)估，得出結(jié)論：作為元啟發(fā)式的禁忌搜索算法得到解質(zhì)量得到明顯提高，而改進(jìn)后的禁忌搜索無(wú)論從解質(zhì)量、還是從運(yùn)行時(shí)間角度，均優(yōu)于傳統(tǒng)的禁忌搜索算法。

下一步研究可以從2個(gè)角度予以考慮：

（1）針對(duì)理論模型，設(shè)計(jì)精確算法或其他啟發(fā)式算法，進(jìn)一步提高算法的求解質(zhì)量；（2）構(gòu)造更能體現(xiàn)實(shí)際生產(chǎn)環(huán)境的問題模型并設(shè)計(jì)算法，使用算法求解真實(shí)的生產(chǎn)問題。

[1] Blazewicz J, Ecker K H, Pesch E, et al. Handbook on scheduling: from theory to practice[M]. Switzerland: Springer International Publishing, 2019.

[2] Pinedo M. 調(diào)度：原理、算法和系統(tǒng)[M]. 2版. 北京: 清華大學(xué)出版社, 2007.

[3] Sterna M. A survey of scheduling problems with late work criteria[J]. Omega, 2011, 39(2): 120-129.

[4] Blazewicz J. Scheduling preemptible tasks on parallel processors with information loss[J]. Technique et Science Informatiques, 1984, 3(6): 415-420.

[5] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5: 287-326.

[6] Potts C N, Van Wassenhove L N. Single machine scheduling to minimize total late work[J]. Operations Research, 1992, 40(3): 586-595.

[7] Kovalyov M Y, Potts C N, Wassenhove L N V. A fully polynomial approximation scheme for scheduling a single machine to minimize total weighted late work[J]. Mathematics of Operations Research, 1994, 19(1): 86-93.

[8] Kethley R B, Aliedee B. Single machine scheduling to minimize total weighted late work: a comparison of scheduling rules and search algorithms[J]. Computers & Industrial Engineering, 2002, 43(3): 509-528.

[9] Ren J, Zhang Y, Sun G. The np-hardness of minimizing the total late work on an unbounded batch machine[J]. Asia-Pacific Journal of Operational Research, 2009, 26(3): 351-363.

[10] Wu C C, Yin Y, Wu W, et al. Using a branch and bound and a genetic algorithm for a single machine total late work scheduling problem[J]. Soft Computing, 2016, 20(4): 1329-1339.

[11] Chen R, Yuan J, Ng C T, et al. Single-machine scheduling with deadlines to minimize the total weighted late work[J]. Naval Research Logistics (NRL), 2019, 66(7): 582-595.

[12] Blazewicz, Finke G. Minimizing mean weighted execution time loss on identical and uniform processors[J]. Information processing letters, 1987, 24(4): 259-263.

[13] Leung J Y. Minimizing total weighted error for imprecise computation tasks and related problems[G]//Handbook of scheduling: algorithms, models, and performance analysis. Chapman and Hall/CRC, 2004.

[14] Xu Z, Zou Y, Kong X. Metaheuristic algorithms for parallel identical machines scheduling problem with weighted late work criterion and common due date[J]. Springerplus, 2015, 4(1): 1-13.

[15] Sterna M, Czerniachowska K. Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work[J]. Journal of Optimization Theory & Applications, 2017, 174(3): 927-944.

[16] Chen X, Liang Y, Sterna M, et al. Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date[J]. European Journal of Operational Research, DOI: 0.1016/j.ejor.2019.12.003.

[17] Blazewicz J, Pesch E, Sterna M, et al. Open shop scheduling problems with late work criteria[J]. Discrete Applied Mathematics, 2004, 134(1): 1-24.

[18] Blazewicz J, Pesch E, Sterna M, et al. The two-machine flow-shop problem with weighted late work criterion and common due date[J]. European Journal of Operational Research, 2005, 165(2): 408-415.

[19] Blazewicz J, Pesch E, Sterna M, et al. A note on the two machine job shop with the weighted late work criterion[J]. Journal of Scheduling, 2007, 10(2): 87-95.

[20] Lin B M, Lin F, Lee R. Two-machine flow-shop scheduling to minimize total late work[J]. Engineering Optimization, 2006, 38(4): 501-509.

[21] Piroozfard H, Wong K Y, Wong W P. Minimizing total carbon footprint and total late work criterion in flexible job shop scheduling by using an improved multi-objective genetic algorithm[J]. Resources, Conservation and Recycling, 2018, 128: 267-283.

[22] Nowicki E, Smutnicki C. A Fast Taboo Search Algorithm for the Job Shop Problem[J]. Management Science, 1996, 42: 797-813.

[23] Glover F. Future Paths for Integer Programming and Links to Artificial Intelligence[J]. Computers and Operations Research, 1986, 13(5): 533-549.

[24] Chen X, Wang Z, Pesch E, STERNA M, BLAZEWICZ J. Two-machine flow-shop scheduling to minimize total late work: revisited[J]. Engineering Optimization, 2019, 51(7): 1268-1278.

[25] Pesch E, Sterna M. Late work minimization in flow shops by a genetic algorithm[J]. Computers & Industrial Engineering, 2009, 57(4): 1202-1209.

Tabu Search Algorithm to Solve the Problem of Minimal Delay Scheduling in a Flowshop System

WEI Kang, LI Xin-yun, CHEN Xin

（School of Electronics & Information Engineering, Liaoning University of Technology, Jinzhou 121001, China）

In this paper, we propose a tabu search algorithm to solve the problem of minimal delay scheduling in a flowshop system. Several heuristic rules are considered to generate feasible schedules, and the best one among them is chosen to be the initial solution to tabu search. The neighborhood searching mechanism is designed based on the random exchanging approach, and two kinds of tabu lists are used to prevent local optimum. Moreover, several termination rules are defined to stop the iterations and output the best-found solution. Computational experiments show that the proposed algorithm beats the classical one, both from the viewpoints of solution quality and running time, and the advantage becomes more obvious as the problems increase.

delay loss; flowshop system; scheduling problem; tabu search algorithm

TP18

A

1674-3261(2021)02-0079-05

10.15916/j.issn1674-3261.2021.02.003

2020-03-27

韋康(1998-)，男，湖北黃石人，本科生。

陳鑫(1983-)，男，遼寧錦州人，副教授，博士。

責(zé)任編校：劉亞兵