论文标题
离散平行机调度位置问题的精确和启发式方法问题
Exact and heuristic methods for the discrete parallel machine scheduling location problem
论文作者
论文摘要
离散的并行机器MakePAN调度位置（SCHELOC）问题是一个集成的组合优化问题，可以结合设施位置和作业计划。问题在于在有限的候选人中选择$ p $机器的位置，并在这些机器上安排一组作业，以最大程度地减少Makepan。根据机器位置的不同，工作可能具有不同的发布日期，因此位置决策对调度决策有直接影响。为了解决该问题，提出了一种新的弧光公式，列的生成和三个启发式程序，这些程序通过广泛的计算实验进行了评估。通过将提出的程序嵌入框架算法中，我们可以找到相关文献中所有基准实例的经过验证的最佳解决方案，并为一组新的具有挑战性的实例获得较小的差距。
The discrete parallel machine makespan scheduling location (ScheLoc) problem is an integrated combinatorial optimization problem that combines facility location and job scheduling. The problem consists in choosing the locations of $p$ machines among a finite set of candidates and scheduling a set of jobs on these machines, aiming to minimize the makespan. Depending on the machine location, the jobs may have different release dates, and thus the location decisions have a direct impact on the scheduling decisions. To solve the problem, it is proposed a new arc-flow formulation, a column generation and three heuristic procedures that are evaluated through extensive computational experiments. By embedding the proposed procedures into a framework algorithm, we are able to find proven optimal solutions for all benchmark instances from the related literature and to obtain small percentage gaps for a new set of challenging instances.
