基于提前和延误惩罚的单机调度问题启发式算法研究

摘要

基于提前惩罚和延误惩罚的单机调度问题（简称SMSP-LEQT）是经典的组合优化问题，在实时生产理念、机场飞机起降和供应链管理中都有着非常重要的应用。已经证明，在计算复杂性理论中，SMSP-LEQT是NP难问题，对SMSP-LEQT问题的求解具有重要的理论研究价值和实际应用价值。 SMSP-LEQT问题的求解目标是使得所有工件线性的提前惩罚和二次的延误惩罚之和最小，提出用一种基于多扰动机制的迭代局部搜索算法（ILS-MP）来求解SMSP-LEQT问题。为了搜索更广泛的邻域空间，设计了两种不同的邻域动作，包括工件的插入和交换动作，并通过增量评估策略和设置动作距离阈值来减少邻域评估时间，提高搜索效率。另外，创新性地提出了多扰动机制来增强搜索的疏散性，具体地，ILS-MP多扰动机制结合了三种不同的扰动方式，分别是基于禁忌的扰动、基于构造的扰动以及随机扰动，通过调整三种扰动方式的选择概率来达到平衡扰动幅度的目的，即保留了解的优良结构，也有助于搜索到新的搜索区间。 利用ILS-MP算法来求解众多广泛使用的标准测试算例，并和已有的比较前沿的求解算法进行比较，无论是计算结果还是求解时间上，ILS-MP都表现出了优势。对于规模不大的算例，ILS-MP可以计算得到绝大多数算例的最优解。另外一方面，还分析了ILS-MP在不同类型的算例上的求解性能。

目录

第一个书签之前