Title: Solving shift design problems with answer set programming
Language: English
Authors: Abseher, Michael
Qualification level: Diploma
Keywords: ASP; Schichtplanung; Optimierung; Programmierung
ASP; Shift Design; Optimization; Programming
Advisor: Woltran, Stefan
Assisting Advisor: Musliu, Nysret 
Issue Date: 2013
Number of Pages: 92
Qualification level: Diploma
Shift design problems belong to a group of computational hard problems arising from economic needs for an efficient organization of a company's workforce. Given the demand of workers at each point in time, finding the best possible set of shifts and assigning the optimal amount of employees to each of the selected shifts is one of the most important tasks in the area of personnel planning.
In our work, we will focus on declarative mechanisms in order to investigate their capabilities for solving real-life instances of shift design problems. We propose three modelling approaches for the so-called "Minimum Shift Design Problem" which are implemented using the paradigm of Answer Set Programming (ASP), a declarative programming technique often described as the computational embodiment of non-monotonic reasoning based on the semantics of stable models.
Since ASP is able to investigate the whole search space in a structured way, it always finds the global optimal solution(s) in theory. In practice, this statement should indeed be treated with caution, since time is often the limiting factor. For this reason, we present a number of experiments and benchmarks in order to get an intuition of the performance of different solvers in combination with our programs.
Our experiments show that ASP performs well in many cases, although we have to admit that there is still work to do in order to obtain a competitive and robust tool for solving the Shift Design Problem.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-51534
Library ID: AC07815276
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
Solving shift design problems with answer set programming.pdf570.5 kBAdobe PDFThumbnail
Show full item record

Page view(s)

checked on Feb 18, 2021


checked on Feb 18, 2021

Google ScholarTM


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