[Back]

M. Abseher:
"Solving shift design problems with answer set programming";
Supervisor: N. Musliu, S. Woltran; Institut für Informationssysteme, 2013; final examination: 2013.

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.
To generate shift schedules in a comfortable and automated way, sophisticated exact and
heuristic algorithms were developed in the last decades to tackle the various kinds of workforce
scheduling problems. Apart from mathematical programming models, many of these algorithms
are implemented in procedural or object-oriented programming languages. In this 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, since the search space sometimes is too large to be handled efficiently by the
exhaustive approach for search as implemented by ASP. Due to our encouraging results we are
confident that we could provide a solid starting point for further research in the area of logic
programming for solving optimization problems.

Aufgrund ökonomischer Überlegungen zum optimalen Einsatz des zur Verfügung stehenden
Personals zählen Schichtplanungsprobleme bereits seit Langem zu den wichtigsten Punkte bei
der Organisation vieler Unternehmen. Den Bedarf an benötigter Arbeitskraft immer möglichst
exakt abzudecken kann einen entscheidenden Vorteil gegenüber Mitbewerbern bedeuten, aber
auch für eine Vielzahl von gemeinnützigen Einrichtungen wie beispielsweise Krankenhäuser
kann eine gute Auswahl der möglichen Schichten einen großen Effizienzgewinn bedeuten.
Aufgrund dieser immensen Wichtigkeit im Bereich der Unternehmensorganisation wurde
bereits sehr früh versucht, den Schichtplanungsproblemen mit computergestützten Methoden zu
begegnen um diese automatisiert und komfortabel lösen zu können.
Seitdem wurden zahlreiche exakte und heuristische Methoden entwickelt, um Werkzeuge
für optimale Organisation zu liefern. Abgesehen von mathematischen Modellierungen wurden
die meisten dieser Anwendungen unter Verwendung von prozeduralen sowie objektorientierten
Programmiersprachen entwickelt. In dieser Arbeit werden wir unseren Fokus auf deklarative
Konzepte legen und untersuchen, wie gut sich diese zur Lösung von Schichtplanungsprobleme
einsetzen lassen.
Wir stellen drei Modellierungsansätze vor, welche Antwortmengenprogrammierung (ASP)
als Programmierparadigma nutzen. ASP ist eine deklarativen Programmiertechnik, die oft auch
als die Verkörperung des nicht-monotonen Schließens basierend auf der Semantik von stabilen
Modellen bezeichnet wird. Das Ziel der von uns entwickelten logikorientierten Programme ist
es, das sogenannte "Minimum Shift Design Problem" zu lösen.
Da ASP den kompletten Suchraum in strukturierter Art und Weise durchsucht, wird das
globale Optimum, sofern existent, theoretisch immer gefunden. In der Praxis ist allerdings oft
die Zeit ein limitierender Faktor, weshalb diese Aussage nicht als Garantie verstanden werden
soll, dass es sich hierbei um die perfekte Lösung für unsere Problemstellung handelt. Um eine
wissenschaftlich fundierte Aussage treffen zu können, präsentieren wir in unserer Arbeit eine
Reihe von Experimenten, die es uns ermöglichen, ein Gefühl für die Leistungsfähigkeit unserer
Programme in Kombination mit aktuellen Programmierumgebungen zu bekommen.
Unsere Ergebnisse zeigen, dass ASP in zahlreichen Fällen bereits jetzt vielversprechende
Resultate liefert, es aber vermutlich noch ein weiter Weg ist bis Implementierungen entstehen,
die ähnliche Leistungsfähigkeit aufweisen wie aktuellen Heuristiken. Aufgrund ermutigender
Ergebnisse sind wir allerdings zuversichtlich, dass sich unsere Arbeit als ein solider Startpunkt
für weitere Forschungen erweisen wird.

http://www.dbai.tuwien.ac.at/staff/abseher/publications/Abseher13thesis.pdf

Project Head Nysret Musliu:
Künstliche Intelligenz in der Personalplanung