Bibliographic Metadata

MaxSAT modeling and metaheuristic methods for the employee scheduling problem / von Felix Winter
AuthorWinter, Felix
CensorMusliu, Nysret
PublishedWien, 2017
Descriptionxiii, 80 Seiten : Illustrationen
Institutional NoteTechnische Universität Wien, Diplomarbeit, 2017
Zusammenfassung in deutscher Sprache
Document typeThesis (Diplom)
Keywords (EN)Employee Scheduling / MaxSAT / Metaheuristics / Constraint programming / Iterated Local Search
URNurn:nbn:at:at-ubtuw:1-97401 Persistent Identifier (URN)
 The work is publicly available
MaxSAT modeling and metaheuristic methods for the employee scheduling problem [0.79 mb]
Abstract (English)

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.

The PDF-Document has been downloaded 37 times.