Shift Design with Answer Set Programming^*

Issue title: Eighth ASPOCP International Workshop on “Answer Set Programming and Other Computing Paradigms”

Guest editors: Daniela Inclezan, Marco Maratea and Victor Marek

Article type: Research Article

Authors: Abseher, Michael^{a; †} | Gebser, Martin^b | Musliu, Nysret^c | Schaub, Torsten^{d; ‡} | Woltran, Stefan^e

Affiliations: [a] TU Wien, Austria. [email protected] | [b] University of Potsdam, Germany. [email protected] | [c] TU Wien, Austria. [email protected] | [d] University of Potsdam, Germany; INRIA Rennes, France. [email protected] | [e] TU Wien, Austria. [email protected]

Correspondence: [†] Address for correspondence: TU Wien, Karlsplatz 13, 1040 Wien, Austria

Note: [*] This work extends a preliminary workshop paper [1] presented at ASPOCP’15. A short version [2] appeared at LPNMR’15.

Note: [‡] Affiliated with Simon Fraser University, Canada, and IIIS Griffith University, Australia.

Abstract: Answer Set Programming (ASP) is a powerful declarative programming paradigm that has been successfully applied to many different domains. Recently, ASP has also proved successful for hard optimization problems like course timetabling and travel allotment. In this paper, we approach another important task, namely, the shift design problem, aiming at an alignment of a minimum number of shifts in order to meet required numbers of employees (which typically vary for different time periods) in such a way that over- and understaffing is minimized. We provide an ASP encoding of the shift design problem, which, to the best of our knowledge, has not been addressed by ASP yet. Our experimental results demonstrate that ASP is capable of improving the best known solutions to some benchmark problems. Other instances remain challenging and make the shift design problem an interesting benchmark for ASP-based optimization methods.

DOI: 10.3233/FI-2016-1396

Journal: Fundamenta Informaticae, vol. 147, no. 1, pp. 1-25, 2016