MaxSAT modeling and metaheuristic methods for the employee scheduling problem

Abstract

Employee scheduling is a well known problem that appears in a wide range of different areas including health care, airlines, transportation services, and basically any other organization that has to deal with workforces. Although different approaches based on heuristics as well as exact solution techniques have been proposed in the past, there is still a great demand for innovative strategies which are able to find good solutions for the many existing variants of employee scheduling problems. This thesis proposes two novel solution approaches for well known instances of the employee scheduling problem and evaluates their performance. The first approach provides for the first time a weighted partial boolean maximum satisfiability model for employee scheduling. An analysis of different encoding variants is performed and results achieved by leading maximum satisfiability solvers are evaluated. The second solution approach which is proposed in this thesis introduces a novel hybrid algorithm that combines metaheuristic techniques with exact solution strategies that are based on constraint programming. Using an implementation of the proposed algorithm, a large number of experiments is then conducted on a number of well known problem instances from the literature. The obtained results are compared with the best known solutions acquired by state of the art methods. An empirical evaluation of the proposed methods shows their competitiveness with state of the art solutions. The maximum satisfiability model is used successfully to approve optimal bounds and to produce feasible solutions for most of the considered problem instances. Using the hybrid algorithm that is proposed in the thesis, results produced by state of the art techniques are improved for the majority of the considered problem instances. Additionally, five new unknown upper bounds are provided for the instances.