Approximability of average completion time scheduling on unrelated machines
Approximability of average completion time scheduling on unrelated machines
复制标题
不相关机器上平均完成时间调度的近似性
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
René Sitters
中科院分区：
文献类型：
--
作者：
René Sitters
我们表明，如果允许抢先抢先，则将无关机器上的平均工作完成时间最小化为$$ Mathcal {apx} $$ APX-HARD。这提供了机器调度的复杂性分类中的最后一部分，并具有（加权）完成时间目标的总和。证明基于混合整数线性程序。这意味着对还原的验证部分由ILP溶剂进行。这提供了简洁的证明，易于验证。此外，我们为问题的加权版本提供了确定性的1.698-AppRoximation算法。通过修改和组合已知算法和使用新的下限来进行改进。这些结果在已知的$$ Mathcal {np} $$ np-hards和2-易X型性上得到改善。
We show that minimizing the average job completion time on unrelated machines is $$mathcal {APX}$$APX-hard if preemption of jobs is allowed. This provides one of the last missing pieces in the complexity classification of machine scheduling with (weighted) sum of completion times objective. The proof is based on a mixed integer linear program. This means that verification of the reduction is partly done by an ILP-solver. This gives a concise proof which is easy to verify. In addition, we give a deterministic 1.698-approximation algorithm for the weighted version of the problem. The improvement is made by modifying and combining known algorithms and by the use of new lower bounds. These results improve on the known $$mathcal {NP}$$NP-hardness and 2-approximability.