论文标题
单批处理机器调度的ARC-FLOW方法
Arc-flow approach for single batch-processing machine scheduling
论文作者
论文摘要
我们解决了在单个批处理机上使用非相同大小和不同处理时间的调度作业的问题，目的是最大程度地减少MakePan。关于这个NP难题的广泛文献主要集中在启发式上。使用基于弧流的优化方法，我们构建了一种巧妙的公式，将其表示为确定图中流的问题。配方的大小随工作之间的不同大小和处理时间的数量而增加，但是随着工作数量的增加，这使得将大型实例求解达到最佳性非常有效，尤其是当多个工作的规模和处理时间相等时。我们将我们的模型与文献中的其他模型进行了比较，该模型在基准实例上表现出了明显的优势，并证明了最佳的实例具有多达1亿个工作岗位。
We address the problem of scheduling jobs with non-identical sizes and distinct processing times on a single batch processing machine, aiming at minimizing the makespan. The extensive literature on this NP-hard problem mostly focuses on heuristics. Using an arc flow-based optimization approach, we construct an ingenious formulation that represents it as a problem of determining flows in graphs. The size of the formulation increases with the number of distinct sizes and processing times among the jobs, but it does not increase with the number of jobs, which makes it very effective to solve large instances to optimality, especially when multiple jobs have equal size and processing time. We compare our model to other models from the literature showing its clear superiority on benchmark instances, and proving optimality of random instances with up to 100 million jobs.
