基于禁忌搜索算法求解流水作业最小误工调度问题

韦 康，李昕昀，陈 鑫

基于禁忌搜索算法求解流水作业最小误工调度问题

韦 康，李昕昀，陈 鑫

（辽宁工业大学 电子与信息工程学院，辽宁 锦州 121001）

针对流水作业环境最小化误工损失调度问题，提出一个禁忌搜索算法对其进行求解。利用多个启发式规则生成可行调度，从中选出最好解作为算法的初始解；同时，基于随机交换策略，权衡求解质量与运行时间之间的关系定义邻域搜索机制；采用双禁忌表结构防止算法陷于局部最优；最后，定义算法停止规则。数值实验表明，与传统禁忌搜索算法相比，新算法在求解质量和处理速度上进一步优化，且该优势随着问题规模的增大而更加明显。

误工损失；流水作业；调度问题；禁忌搜索算法

调度是管理者在经营过程中需要做出的重要决策之一，可以涉及制造、运输、分配等多种生产场景，有效的调度策略不仅可以对生产资源进行充分利用，而且还可以提高用户的满意度[1-2]。其中，是否按时完成任务是衡量用户满意度的重要指标之一，因此，在用户期待的时间（即任务的交付期，due date）之前完成任务十分重要。任务的误工损失（late work）是一个与其交付期有关的惩罚量，其完工时间越滞后于交付期，所对应的惩罚量越大（但最大不会超过任务的加工时间）。由于误工损失指标能够描述实际生产中的多种场景，基于该指标的调度问题吸引着诸多学者的广泛关注[3]。

Blazewicz[4]在研究并行机环境的调度问题中首次提出误工损失这一概念，并慢慢将其泛化，引入到不同的处理机环境下加以研究。在调度问题三参数表示法[5]中，最小化该指标用符号表示。20世纪末期，Potts等[6]对单机调度问题1||加以研究，证明了该问题是NP难问题，并给出了解决此问题的伪多项式时间（Pseudo-polynomial time）动态规划算法。进而，Kovalyov等[7]将关注点扩展至考虑权重的模型，并给出了问题1||Y的多项式时间近似方案（fully polynomial-time approximation scheme，FPTAS）。2002年，Kethley等[8]针对这一问题（1||Y）再次进行了研究，他们设计了一系列算法，并通过数值实验对算法的性能进行对比分析。Ren等[9]考虑了批处理单机调度中的最小误工损失问题1|≥|Y，证明该问题依然为NP难，并给出了伪多项式时间动态规划算法。随后，Wu等[10]研究了带学习效应的单机调度问题1||，并设计了一个分支定界算法和一系列遗传算法进行对比分析。近期，Chen等[11]将截止期（deadline）引入最小化误工损失的单机调度问题，给出了与1|d|Y有关的一系列复杂性和可近似性结果。

针对误工损失指标的研究起源于平行机环境。Blazewicz[4]在其开创性文章中，将允许抢占的平行机调度问题||Y和||Y归约为网络流问题，这样可以在多项式时间内对问题求解；且说明若不允许抢占，该问题（||Y）为强难问题。随后，该结果又分别被Blazewicz等[12]、Leung[13]进行了改进。Xu等[14]考虑了加权公共交付期的平行机调度问题|d=|Y，设计了蚁群算法、遗传算法和模拟退火算法对其求解，并对比了算法性能。Sterna等[15]从可近似性的角度对问题进行了研究，她们将视角由最小化误工损失（late work minimization）切换至最大化加工收益（early work maximization），给出了2台平行机、公共交付期问题2|d=|max()的多项式时间近似方案（PTAS）。最近，这一结果被Chen等[16]改进，他们给出了更通用的模型|d=|max()（≥ 2）的完全多项式时间近似方案（FPTAS）。

对于串联机环境下最小误工损失的研究始于自由作业（open shop）。Blazewicz等[17]于2014年基于2|d=|Y问题，首先分析了误工损失指标与其他优化目标之间的关联关系，进而证明所研究问题为弱NP难问题。随后，他们将结果推广至流水作业（flow shop）2|d=|Y问题[18]、自由作业（job shop）2|d=|Y问题[19]，分别证明了这些问题的复杂性，且设计动态规划算法对其求解。除了这一团队，Lin等[20]证了无权重的模型2|d=|依然属于难范围，并设计了分支定界算法和元启发式算法求解其通用情况2||。近期，Piroozfard等[21]考虑了柔性自由作业的多目标调度问题，他们基于实际生产问题，将最小化误工损失及碳排放作为优化目标，为问题构建了数学模型，并设计了遗传算法对其求解。

综上，本文设计了一个禁忌搜索算法求解流水作业最小误工损失调度问题（||）。首先通过多个启发式规则产生算法的初始解，然后基于目标函数对禁忌表和邻域搜索方法进行设计，最后通过公共测试集对算法性能进行测试。实验结果表明，算法可以在较快时间内得到质量较好的可行解，是解决所研究问题的一个有效方法。

1 问题描述

任务的误工损失对应其在交付期之后加工的部分，可以表示延迟加工所带来的惩罚量；任务的延误时间越长，该惩罚量越大（但是不会超过其加工长度）。本文所研究的问题可以描述如下：

2 禁忌搜索算法

2.1 算法概述

禁忌搜索（tabu search，TS）算法[22]是基于随机搜索的元启发式算法之一，由Glover[23]于1986年正式提出。其模仿人类思维，拥有灵活的记忆存储功能，即：算法在搜索过程中记录之前的部分搜索轨迹，从而会有意避开这些已经搜索过的区域。主要过程为：把一个可行解作为初始解，通过邻域搜索产生多个候选解并从中选择一个质量相对好的解作为后代，以此进行迭代。为了避免陷入重复搜索，算法采用一种灵活的记忆存储技术，即禁忌表（Tabu List）对已经进行搜索过的区域进行记录；此外，考虑到完全禁忌前期搜索轨迹将过于严格，算法还可以定义一系列“特赦准则”，可以将某个解从禁忌表中“解禁”从而基于其继续搜索。

2.2 求解Fm||Y问题的TS算法

为了有效地求解||问题，首先用一串值为1 ~的整数数组表示一个可行调度，数组中每个元素对应为任务序号。也就是说，一个可行解可以表示为：

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

接下来，对TS算法初始解生成、邻域搜索策略、双禁忌表结构、特赦规则、终止条件的设置等分别介绍如下。

2.2.1 禁忌搜索的初始解

良好的初始解能够有效地加快收敛速度，从而提高搜索效率和解的质量，本文采用6种启发式策略和随机过程生成7个可行调度方案，从中选则最好解作为TS算法的初始解。其中，6种启发式策略分别为[24]：

EDD（earliest due date first）：交付期小的任务优先加工；SPT（smallest processing time first）：总加工时间小的任务优先加工；LPT（largest processing time first）：总加工时间大的任务优先加工；FSPT（first-piece smallest processing time first）：在1上所需加工时间小的任务优先加工；FLPT（first-piece largest processing time first）：在1上所需加工时间大的任务优先加工；SDPT（smallest due dateprocessing time，d/p）：交付期与加工时间比值小的任务优先加工。

2.2.2 邻域搜索策略

基于||问题解的编码方式，本文采用“随机交换”的方式构造邻域空间。对于当前编码（由位正整数构成），任意选择2个元素进行交换，从而形成一个新的编码存入邻域空间；然而，由于可行的选择共计C2种，全部枚举将非常耗时（而且也没有必要），本文定义邻域空间大小为=（为任务数量），即：每轮迭代过程中进行次随机选择，从而形成个（没有被禁忌的）有效编码组成邻域空间。在TS算法迭代过程中，每次从邻域空间选择质量最好的解，作为下一次迭代的基本解。

2.2.3 禁忌表

禁忌表是TS算法的核心部分，用来记录已经搜索过的解；除非满足特赦规则，否则禁忌表中的解在算法搜索过程中将不会被二次选中。禁忌表可以设计为先入先出的队列，在本文中，设计短期记忆和长期记忆两类禁忌表来控制算法的搜索精度与广度，短期禁忌表的长度为邻域大小的1.5倍（即1.5），而长期禁忌表的长度则设置为一个定值= 25。

在禁忌表已满的状态下，当有新的编码进入时，禁忌表遵循先入先出方法，移除表中禁忌时间最长的解，为新进入的解释放空间。

（1）短期记忆禁忌表。在对当前解的邻域解集进行搜索过程中，短期记忆防止算法在当前解的某一部分解集进行重复搜索，既损耗时间，也没有提高候选解的质量。在实际算法设计中，由于禁忌表是一个有固定长度的队列，虽然不能完全避免算法重复搜索，但是当禁忌解释放出来后，如果算法又对其进行搜索，这样很大程度上能降低算法在解空间的收敛速度，增加判断候选解是否为禁忌解的时间。

禁忌算法近期搜索过的解将存放在短期禁忌表中，往往在几次迭代后从禁忌表中移除，重新成为未被搜索过的可行解；短期记忆禁忌表在一定程度上能防止算法过早陷入局部搜索循环。

当搜索策略是随机选取当前解的邻域解集时，会产生一个到多个完全相同的解集，可以通过短期记忆禁忌表避免搜索重复。例如，在某次迭代后，当前解的邻域解集为1，经过一次迭代后，当前解的邻域解集为2，1和2会有一定可能出现交集3。这样短期记忆禁忌表就可以让算法避免重复搜索交集3，减少时间的损耗。

（2）长期记忆禁忌表。长期记忆禁忌表主要在搜索邻域空间的广度上起到一定作用，但与短期记忆禁忌表的禁忌对象不同，长期记忆禁忌表只禁忌每次迭代后的当前解。

长期记忆禁忌表与短期记忆禁忌表相比，表中信息更新速度慢，只有在每次迭代后，才进行一次更新。而短期记忆禁忌表的更新速度与当前解的邻域搜索次数有关，邻域搜索次数越多，更新速度也越快。长期记忆禁忌表能够将表内对象禁忌很长时间，从而算法可以搜索其他未搜索的区域来防止算法过早陷入局部最优。

2.2.4 特赦规则

禁忌表可能导致候选解全部被禁忌或者最好解被禁忌，此时需要运用“特赦规则”将某些被禁忌的解释放，从而让算法继续进行搜索。本文采用“阶梯释放规则”完成特设过程，即：设置一系列阈值1<2<3< ……，若出现候选解全部被禁忌的情况，则首先释放禁忌表中目标函数值与当前搜索到最好解的比值在1范围之内的全部解；若禁忌表中不存在这样的解（比值在1范围之内），则释放比值在2范围之内的全部解，以此类推。本文设1= 1.05，2= 1.1，后面的阈值（3等）按照0.05递增。

2.2.5 算法终止条件

本文设计了2种终止条件，当二者之一被满足时，TS算法停止搜索，并输出搜索到的最好解：

（1）当达到最大迭代次数，本文设定为120；（2）当最好解未更新的次数超过一个预定阈值时，本文设定为30。

3 实验及结果分析

本文算法采用C++编码，使用的开发平台为Visual Studio 2019，测试平台为Intel(R) Core(TM) i5-8300H 2.30GHz、8 GB RAM的笔记本电脑。

3.1 实验数据

其中，是一个控制交货期紧密程度的参数，值越大，任务的交付期普遍取值偏小，即任务的加工更为“紧迫”；否则，任务的交付期普遍取值偏大，加工安排可以更具有弹性。与文献[20]保持一致，本文对的取值也设置为3、5、7。

3.2 实验结果及分析

本文通过传统禁忌搜索算法与本文改进禁忌搜索算法对||的求解能力进行对比，使用质量提升率指标（(Y-Y)/Y*100%）来评估算法能力[25]，其中Y是某种启发式算法得到的目标函数值，Y是传统或本文禁忌搜索得到的目标函数值。本文使用不同的机器数量、任务数量与紧密系数进行组合，其中分别取值为3、5、7、10；对于每一个具体的值，任务数量分别设置为10、15、20；如前所述，的取值设置为3、5、7。针对每一组参数组合，分别运行50次实验取平均值，共计进行实验1 800组，所得结果如表1[以(,)组合评估]和表2（以评估）所示。

表1 (, )组合不同时传统与改进禁忌搜索算法的性能表现

mn 随机 EDD LPT SPT FSPT FLPT SDPT 传统TS时间/s改进TS时间/s 传统改进传统改进传统改进传统改进传统改进传统改进传统改进 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 组内平均值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 组内平均值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 组内平均值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 组内平均值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个表中不难看出，改进TS算法在时间和解的质量上都比传统TS算法效果要好。例如，当= 3、= 30时（见表1），传统TS算法对SDPT解的平均改善程度为30.90%，而改进TS则达到了33.47%。在任务数量增加的情况下，改进TS算法的改善效果会稍微下降。在7个初始解中，TS算法对EDD的改善程度最好，对SPT的改善程度最差。因此，用SPT作为禁忌搜索的初始解效果最好，反之，用EDD作为禁忌搜索的初始解效果最差。此外，传统TS算法在1 800组实验过程中的平均运行时间为43.0684 s，而改进TS算法仅仅为0.5126 s，说明改进后的算法运行速度远远小于传统算法。

表2 不同时传统与改进禁忌搜索算法的性能表现

β随机 LPT SPT FSPT FLPT SDPT传统TS时间/s改进TS时间/s 传统改进 传统改进 传统改进 传统改进 传统改进 传统改进 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反映了无论是传统禁忌搜索算法，还是改进禁忌搜索，其性能都会随着的上升而下降，说明随着任务的交付期d取值变小，TS算法对初始解的提升能力将会下降。

4 结论

本文为流水作业环境下的最小化工件误工损失调度问题设计了一个禁忌搜索算法，对其的初始解生成、邻域搜索策略、禁忌表设置等进行了进一步的优化，并与6个启发式策略EDD、LPT、SPT、FSPT、FLPT、SDPT和随机过程生成的可行调度方案进行对比评估，得出结论：作为元启发式的禁忌搜索算法得到解质量得到明显提高，而改进后的禁忌搜索无论从解质量、还是从运行时间角度，均优于传统的禁忌搜索算法。

下一步研究可以从2个角度予以考虑：

（1）针对理论模型，设计精确算法或其他启发式算法，进一步提高算法的求解质量；（2）构造更能体现实际生产环境的问题模型并设计算法，使用算法求解真实的生产问题。

[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. 调度：原理、算法和系统[M]. 2版. 北京: 清华大学出版社, 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-)，男，辽宁锦州人，副教授，博士。

责任编校：刘亚兵