Associate Professor Andrew Mason and Associate Professor Andrea Raith have a funded PhD project in Operations Research available. To apply, please get in touch with us as soon as possible by email.
Title: Problem Shaping for Mathematical Models of Scheduling Problems
Summary: Many organisations have complex scheduling problems that they model as generalised set partitioning models and then solve using integer programming optimisation techniques. These problems arise, for instance, in the airline operations, rostering of medical personnel, forestry management, or collection and processing of goods (such as milk) and many other contexts.
This doctoral research project will consider scheduling problems and other similarly complex problems. These problems have mathematical formulations with a special structure (generalised set partitioning models). Due to their prohibitively large size, the problems are commonly solved using decomposition algorithms. Decomposition approaches initially solve a simplified optimisation problem, and then repeatedly augment this problem with new schedules (e.g. sequences of work tasks) that improve the solution. Our recent observations hint at the impact of the augmentation approach itself, where, by carefully shaping the formulation, we can create favourable model properties that speed up the solution process. This allows us to obtain high quality solutions faster. We will systematically propose and analyse problem shaping approaches to develop a theoretical understanding of this new approach thereby addressing the following three research aims:
- Identify properties of different mathematical representations of generalised set partitioning problems and their connection to solution fractionality of the linear programming formulation.
- Propose novel problem shaping approaches and integrate them in decomposition algorithms for scheduling problems.
- Conduct a systematic analysis of our current and proposed problem shaping approaches to develop an understanding of their operation and maximise the impact they make when solving challenging scheduling problems.