Output details

A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines

This research has been undertaken within the project EP/J019755/1 “Linking Submodular Optimisation to Scheduling with Controllable Parameters” funded by the EPSRC (2012-2013). Scheduling with controllable processing time, an active research area in the 1980-90s, stagnated in the late 1990s mainly because of lack of new methodological ideas. Since 2005, the team of authors have pursued a novel approach based on the reformulation of relevant scheduling problems in terms of mathematical programming problems with submodular constraints. This paper is a good illustration of the power of this “schedule-free” approach and contains several breakthrough results for the bicriteria scheduling models.