论文标题
使用决策图的基于流的平行机计划的基于流的公式
A flow-based formulation for parallel machine scheduling using decision diagrams
论文作者
论文摘要
我们为具有常规目标函数而没有空闲时间的相同平行机计划提供了一种新的基于流的公式。该公式是借助代表所有尊重特定订购规则的作业序列的决策图来构建的。这些规则依赖于计划范围的分区，通常是不均匀的，并且不排除所有最佳解决方案，但它们限制了解决方案以遵守规范形式。新的配方具有许多变量和约束，因此我们应用了Dantzig-Wolfe分解，以便在合理的时间内计算线性编程放松；所得的下限比经典时间指数配方的结合强。我们开发了一个分支机构和价格框架，该框架首次解决了文献中的几个实例。我们通过一系列计算实验将新的公式与时间索引和弧形时间分数配方进行了比较。
We present a new flow-based formulation for identical parallel machine scheduling with a regular objective function and without idle time. The formulation is constructed with the help of a decision diagram that represents all job sequences that respect specific ordering rules. These rules rely on a partition of the planning horizon into, generally non-uniform, periods and do not exclude all optimal solutions, but they constrain solutions to adhere to a canonical form. The new formulation has numerous variables and constraints, and hence we apply a Dantzig-Wolfe decomposition in order to compute the linear programming relaxation in reasonable time; the resulting lower bound is stronger than the bound from the classical time-indexed formulation. We develop a branch-and-price framework that solves several instances from the literature for the first time. We compare the new formulation with the time-indexed and arc-time-indexed formulation by means of a series of computational experiments.
