韦 康，李昕昀，陈 鑫

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

韦 康，李昕昀，陈 鑫

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

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

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

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

Blazewicz[4]在研究并行机环境的调度问题中首次提出误工损失这一概念，并慢慢将其泛化，引入到不同的处理机环境下加以研究。……