Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines

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

来源：INFORMS Journal on Computing, 2016, 28(1): 148-161.

DOI：10.1287/ijoc.2015.0660

• programming: linear
• production scheduling: deterministic, single machine
• analysis of algorithms: computational complexity

In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible schedule that minimizes the total cost of reducing the processing times. We reformulate the problem in terms of maximizing a linear function over a submodular polyhedron intersected with a box. For the latter problem of submodular optimization, we develop a recursive decomposition algorithm and apply it to solving the single machine scheduling problem to achieve the best possible running time.

• 出版日期2016