Solving shift design problems with answer set programming

Abstract

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.<br />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.<br />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.<br />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.