Optimisation-Based Solution Methods for Set Partitioning Models

The scheduling of crew, i.e. the construction of work schedules for crew members, is often not a trivial task, but a complex puzzle. The task is complicated by rules, restrictions, and preferences. Therefore, manual solutions as well as solutions from standard software packages are not always su_cient with respect to solution quality and solution time.

Enhancement of the overall solution quality as well as the solution time can be of vital importance to many organisations. The _elds of operations research and mathematical optimisation deal with mathematical modelling of di_cult scheduling problems (among other topics). The _elds also deal with the development of sophisticated solution methods for these mathematical models.

This thesis describes the set partitioning model which has been widely used for modelling crew scheduling problems. Integer properties for the set partitioning model are shown, and exact and optimisation-based heuristic solution methods for the model are described. All these methods are centered around the wellknown column generation technique.

Di_erent practical applications of crew scheduling are presented, and some of these applications are considered in detail in four included scienti_c papers. It is shown how these applications all _t into a generalisation of the set partitioning model. Each of the four papers contribute a novel solution method for the speci_c application treated in the paper.