Output details

Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times – a polymatroid optimization approach

<12>Arising from an interdisciplinary collaboration between Scheduling and Submodular Optimisation (SO) teams, this paper develops a new methodology for problems with controllable parameters that differs radically from traditional scheduling approaches, used since the 1980s. Key contributions: (i) reformulating scheduling problems as optimization problems over submodular polyhedra; (ii) advancing SO theory by developing a new divide-and-conquer algorithm; (iii) successfully applying it to three scheduling problems. Significantly, our algorithm outperforms the previous best algorithms that don’t exploit SO techniques. Follow-up funding (EP/J019755/1) reinforced the collaboration with Shioura (world-leading expert in SO) leading to further publications ([Shakhlevich2], one submitted and one under preparation).