Title: MaxSAT modeling and metaheuristic methods for the employee scheduling problem
Language: English
Authors: Winter, Felix 
Qualification level: Diploma
Advisor: Musliu, Nysret  
Issue Date: 2016
Citation: 
Winter, F. (2016). MaxSAT modeling and metaheuristic methods for the employee scheduling problem [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2016.36862
Number of Pages: 80
Qualification level: Diploma
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.
Keywords: Employee Scheduling; MaxSAT; Metaheuristics; Constraint programming; Iterated Local Search
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-97401
http://hdl.handle.net/20.500.12708/1627
DOI: 10.34726/hss.2016.36862
Library ID: AC13687302
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:


Page view(s)

56
checked on Dec 29, 2021

Download(s)

129
checked on Dec 29, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.