论文标题
通过最小化总加权完成时间来安排与相同并行机器上的释放日期的工作
Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time
论文作者
论文摘要
本文解决了安排一组作业的问题，这些作业是在一组相同的并行机器上发布的，目的是最小化总加权完成时间。这个问题被称为$ p | r_j | \ sum w_jc_j $，在实践中非常重要，因为它建模了各种真实的应用程序。尽管它很重要，但$ p | r_j | \ sum w_jc_j $在最近的文献中并未受到太多关注。在这项工作中，我们通过提出混合整数线性程序和量身定制的分支和价格算法来填补这一空白。我们的{分支和价格}依赖于弧光公式的分解以及使用有效的精确和启发式方法来解决定价子问题。在一组随机生成的实例上进行的计算实验证明，所提出的方法可以求解具有多达200个作业和10台机器的经过验证的最佳实例，并为更大实例提供了非常低的空白。
This paper addresses the problem of scheduling a set of jobs that are released over the time on a set of identical parallel machines, aiming at the minimization of the total weighted completion time. This problem, referred to as $P|r_j|\sum w_jC_j$, is of great importance in practice, because it models a variety of real-life applications. Despite its importance, the $P|r_j|\sum w_jC_j$ has not received much attention in the recent literature. In this work, we fill this gap by proposing mixed integer linear programs and a tailored branch-and-price algorithm. Our {branch-and-price} relies on the decomposition of an arc-flow formulation and on the use of efficient exact and heuristic methods for solving the pricing subproblem. Computational experiments carried out on a set of randomly generated instances prove that the proposed methods can solve to the proven optimality instances with up to 200 jobs and 10 machines, and provide very low gaps for larger instances.
