Optimisation algorithms for planning and scheduling workplace training

Publication Type:
Thesis
Issue Date:
2017
Full metadata record
This thesis is concerned with a number of related mathematical optimisation problems in, or closely related to, the fields of scheduling, timetabling, and rostering. The studies are motivated by real world problems routinely faced at an Australian electricity distributor. Due to the computational complexity of the problems considered and typical real-world problem sizes, solution by direct application of mathematical programming is not possible in practically acceptable time. Therefore, we propose a variety of heuristic, metaheuristic, and matheuristic approaches to obtain good quality solutions in acceptable time. The first study is concerned with a large-scale class timetabling and trainer rostering problem. The problem is formulated as two Integer Programs: one for class timetabling and one for trainer rostering. A three-stage approach is presented, consisting of a timetable construction stage, a timetable improvement stage, and a trainer rostering stage. The second study investigates a variation of the timetabling problem considered in the first study, but from an analytical perspective. The problem is presented in the context of batch scheduling. Conditions that lead to NP-hardness are shown, and a previously-known NP-hardness result is strengthened. A polynomial time algorithm is presented for a particular case. Simulated Annealing and Genetic Algorithm based metaheuristics are compared by means of extensive computational experimentation. The third study is of a partitioning problem concerned with optimising the composition of study groups, which is related to, but distinct from, several well-known problems in the literature. The problem is shown to be NP-hard in the strong sense. Four approaches are proposed: the first is based on Lagrangian Relaxation, the second is based on Column Generation, the third encapsulates Column Generation within a fix-and-optimise Large Neighbourhood Search framework, and the fourth is a Genetic Algorithm amalgamated with Integer Programming. The fourth study is concerned with the timetabling of practice placements. The problem is shown to be NP-hard in the strong sense. Two approaches are presented: the first approach improves an initial timetable by means of a Simulated Annealing metaheuristic, and the second approach constructs and improves a timetable by means of a fix-and-optimise Large Neighbourhood Search procedure. The aim of this research is to study these related optimisation problems encountered at the electricity distributor from both analytical and practical perspectives, and to design successful solution approaches to them.
Please use this identifier to cite or link to this item: