带包容性处理集限制的作业接受与两台并行机调度问题的拉格朗日松弛算法

作者：朱倩倩; 王秀利^*

来源：工业工程与管理, 2023, 28(04): 28-37.

DOI：10.19495/j.cnki.1007-5429.2023.04.004

• 并行机调度
• 作业接受
• 包容性处理集
• 拉格朗日松弛算法

在资源主体加工能力有限和客户作业需要承诺交货期限的双重约束下，本文研究具有包容性处理集限制的作业接受与并行机调度问题，其目标是最大化资源主体收益。研究问题中，资源主体拥有两台加工速度相同，但功能不同的机器，其中一台机器的可处理作业集合是另一台机器可处理作业集合的子集或超集。针对该NP难问题，基于拉格朗日松弛技巧设计了一种高效的启发式算法。广泛的数值实验结果显示，拉格朗日松弛启发式算法结果与最优解平均相差不超过7.5%，该算法能够在合理的时间内获取大规模问题的优化解。

• 单位
  南京理工大学; 经济管理学院