Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times

作者：Shioura Akiyoshi; Shakhlevich Natalia V; Strusevich Vitaly A^*

来源：Mathematical Programming, 2015, 153(2): 495-534.

DOI：10.1007/s10107-014-0814-9

• Submodular optimization
• Parallel machine scheduling
• Controllable processing times
• Decomposition

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.

• 出版日期2015-11