Bibliographic Metadata

Title
Solving shift design problems with answer set programming / von Michael Abseher
AuthorAbseher, Michael
CensorWoltran, Stefan ; Musliu, Nysret
Published2013
DescriptionX, 92 S. : Ill., graph. Darst.
Institutional NoteWien, Techn. Univ., Dipl.-Arb., 2013
Annotation
Zsfassung in dt. Sprache
LanguageEnglish
Document typeThesis (Diplom)
Keywords (DE)ASP / Schichtplanung / Optimierung / Programmierung
Keywords (EN)ASP / Shift Design / Optimization / Programming
URNurn:nbn:at:at-ubtuw:1-51534 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Solving shift design problems with answer set programming [0.55 mb]
Links
Reference
Classification
Abstract (English)

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.

Stats
The PDF-Document has been downloaded 34 times.