Operations Research Seminars Amsterdam

Vitaly Strusevich (University of Greenwich, United Kingdom)
Thursday, 9 June 2016

The talk demonstrates how scheduling problems with controllable processing times can be reformulated as maximization linear programming problems over a submodular polyhedron intersected with a box. We explain a decomposition algorithm for solving the latter problem and discuss its implications for the relevant problems of preemptive scheduling on a single machine and parallel machines. This approach leads to a fairly easy justification of the solution algorithms for the relevant single criterion and bicriteria problems with the best known (often best possible) running times.