Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times
成果类型：
Article
署名作者：
Shioura, Akiyoshi; Shakhlevich, Natalia V.; Strusevich, Vitaly A.
署名单位：
Tohoku University; University of Leeds; University of Greenwich
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-014-0814-9
发表日期：
2015
页码：
495-534
关键词：
摘要：
In this paper we present a decomposition algorithm for maximizing a linear function over a submodular polyhedron intersected with a box. Apart from this contribution to submodular optimization, our results extend the toolkit available in deterministic machine scheduling with controllable processing times. We demonstrate how this method can be applied to developing fast algorithms for minimizing total compression cost for preemptive schedules on parallel machines with respect to given release dates and a common deadline. Obtained scheduling algorithms are faster and easier to justify than those previously known in the scheduling literature.