School of Computing Research Colloquia

Linking Submodular Optimisation to Scheduling with Controllable Parameters

Natasha Shakhlevich, Algorithms and Complexity Research Group

Scheduling with Controllable Processing Parameters (SCPP) has been pursued for the past 30 years and has developed into an important field of study with various application areas including supply chain management, operations management, imprecise computation, power-aware computer processing, etc. Until recently no general methodological framework to handle the SCPP problems has been offered. Moreover, the problems arising from different application domains but sharing the same underlying model were often treated independently, without a careful study of their common properties.

In our research we have established a link between the powerful but abstract area of Submodular Optimisation and a more applied but less methodologically developed area of SCPP. Reducing the scheduling problems to the Submodular Optimisation problems makes it possible to solve SCPP problems efficiently using the advanced optimisation techniques known for optimisation over polymatroids and base polyhedra. On the other hand, the specific features of the models typical for SCPP give rise to interesting new developments in the area of Submodular Optimisation.

The talk will give a general introduction into SCPP and provide some examples illustrating the advantages of the new methodology.