论文标题
与设置时间无关的平行机调度上的强大优化
Robust Optimization on Unrelated Parallel Machine Scheduling with Setup Times
论文作者
论文摘要
并行机器调度问题一直是一个流行的话题，因为其理论和实用性的重要性。本文解决了与序列相关的设置时间，处理时间不确定的无关并联机器调度上的强大的MakePAN优化问题，而唯一的知识是他们从中获取值的间隔。我们提出了一个具有Min-Max遗憾标准的强大优化模型，以提出这个问题。为了解决这个问题，我们证明，对于给定解决方案而言，最遗憾的最坏情况属于有限的极端情况。基于此理论分析，提出了获得最大遗憾的程序，并设计了增强的遗憾评估方法（ERE）来加速此过程。提出了一种基于多开始分解的启发式算法（MDH）来解决此问题。检查高质量的初始解决方案和上限，以帮助更好地解决该问题。进行计算实验以证明这些方法的性能是合理的。
The parallel machine scheduling problem has been a popular topic for many years due to its theoretical and practical importance. This paper addresses the robust makespan optimization problem on unrelated parallel machine scheduling with sequence-dependent setup times, where the processing times are uncertain, and the only knowledge is the intervals they take values from. We propose a robust optimization model with min-max regret criterion to formulate this problem. To solve this problem, we prove that the worst-case scenario with the maximum regret for a given solution belongs to a finite set of extreme scenarios. Based on this theoretical analysis, the procedure to obtain the maximum regret is proposed and an enhanced regret evaluation method (ERE) is designed to accelerate this process. A multi-start decomposition-based heuristic algorithm (MDH) is proposed to solve this problem. High-quality initial solutions and an upper bound are examined to help better solve the problem. Computational experiments are conducted to justify the performance of these methods.
