Improved Job sequencing Bounds from Decision Diagrams
Improved Job sequencing Bounds from Decision Diagrams
复制标题
改进了决策图的作业排序界限
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
J. Hooker
中科院分区：
文献类型：
--
作者：
J. Hooker
我们介绍了一种松弛决策图的通用方法，该方法允许人们通过在松弛图上解决拉格朗日对偶问题来限制作业排序问题。我们还提供了识别问题的指南，对于这些问题，这种方法可以产生有用的界限。由于决策图依赖于 DP 公式，因此这些相同的准则通常可应用于边界确定性动态规划问题。计算测试表明，决策图上的 mbox{拉格朗日} 松弛可以为某些类别的困难作业排序问题产生非常严格的界限。例如，它首次证明 Biskup-Feldman 实例的最佳解与最优值的差距在 1% 以内，有时甚至是最优的。
We introduce a general method for relaxing decision diagrams that allows one to bound job sequencing problems by solving a Lagrangian dual problem on a relaxed diagram. We also provide guidelines for identifying problems for which this approach can result in useful bounds. These same guidelines can be applied to bounding deterministic dynamic programming problems in general, since decision diagrams rely on DP formulations. Computational tests show that mbox{Lagrangian} relaxation on a decision diagram can yield very tight bounds for certain classes of hard job sequencing problems. For example, it proves for the first time that the best known solutions for Biskup-Feldman instances are within a small fraction of 1% of the optimal value, and sometimes optimal.