A branch-and-price algorithm for the single machine scheduling problem with periodic maintenance to minimize makespan

DOI码：10.1016/j.cor.2025.107214

发表刊物：Computers & Operations Research

关键字：Scheduling, Single machine scheduling, Periodic maintenance, Makespan, Branch-and-price

摘要：对机器进行定期维护对于防止意外停机、保障安全可靠生产至关重要。本文研究了带定期维护的单机调度问题，该问题需要在一台需要定期维护的单一设备上顺序处理多个作业，目标是最小化最大完成时间。我们首先将该问题构建为包含整型变量集和连续变量集的集合划分模型，随后开发了分支定价算法对该模型进行高效求解。算法中设计了分层分支策略生成子节点，采用原始启发式方法从分数解快速生成可行解，并结合带定界过程的标号设定算法处理定价问题。通过对基准实例和新生成实例进行大量计算实验，验证了分支定价算法的有效性。结果表明，得益于精心设计的分支策略、原始启发式方法及定界程序，我们求解集合划分模型的算法性能显著优于Gurobi优化器对文献现有数学模型的求解效果。

论文类型：SCI

是否译文：否

发表时间：2025-07-05

收录刊物：SCI