[Back]


Diploma and Master Theses (authored and supervised):

S. Teuschl:
"Casual Employee Scheduling with Constraint Programming and Metaheuristics";
Supervisor: G. Raidl, N. Frohner; Institute of Logic and Computation, 2020; final examination: 2020-11.



English abstract:
The field of personnel scheduling in general and of the nurse rostering problem in particular
has been studied for a long time, most often focused on unique real-world applications.
In this thesis, a problem similar to the nurse rostering problem but focused on casual
employees is studied. Casual employees as described in the thesis differ from full-time
employees in many aspects, most important of which are time constraints. Casual
employees are expected to work a few days a month on days they choose, at possibly
different locations, and a roster has to be created from their offerings.
This thesis provides an algorithm that is able to generate such a roster when given the
offerings from casual employees and the requirements of their workplaces. In addition to
maximizing the amount of employees than can be staffed at any open shift, the fairness
of the assignments as well as the preference of workplace of the casual employees is
considered. The problem is formalised and approached from two different methodic
perspectives. A constraint programming as well as a metaheuristic approach are developed
and later hybridised. The chosen metaheuristic is a variable neighbourhood search (VNS),
implemented as a general VNS (GVNS) with an embedded variable neighbourhood
descent (VND). The initial solution is given by constraint programming (CP) or an
additionally implemented greedy construction heuristic.
Different configurations of either GVNS or VND with different types of initial solutions
are tested on ten real-world instances and subsequently compared.
Due to the complexity of the problem, pure constraint programming is not able to deliver
competitive solutions, whereas approaches combining an initial solution obtained from
either CP or a greedy heuristic with the VNS are more promising. Our experimental
evaluation indicates that in practice, initial solutions from the custom greedy heuristic
that are subsequently improved by the GVNS are most promising. While our approach
was not designed to automatically handle all real-world peculiarities arising, it serves
as a powerful tool to generate high quality solutions within a few hours to be further
adapted by the human planner.

German abstract:
Das Feld der Personaleinsatzplanung im Allgemeinen und des Nurse Rostering Problems
(NRP) im Speziellen wird seit geraumer Zeit wissenschaftlich untersucht. Oft liegt bei
diesen Studien der Fokus auf einzelnen Bereichen wie Krankenhäusern und stationären
Einrichtungen. In dieser Diplomarbeit wird ein Problem beschrieben, welches dem NRP
ähnelt, den Fokus aber auf geringfügig beschäftige Arbeitskräfte legt. Diese gelegentlichen
Mitarbeiter unterscheiden sich von traditionellen Vollzeitmitarbeitern in vielen Bereichen,
am Gravierendsten allerdings in deren Zeitvorgaben. Von ihnen wird erwartet, dass sie im
Laufe eines Monats und im Rahmen ihrer zeitlichen Möglichkeiten eine gewisse Anzahl
von Stunden bzw. Tagen einsatzbereit sind, und das potenziell an unterschiedlichen
Arbeitsplätzen und örtlichen Gegebenheiten. Aus den von ihnen bereitgestellten Angaben
ihrer Verfügbarkeit muss danach eine Arbeitseinteilung erstellt werden.
Diese Diplomarbeit beschreibt einen Algorithmus, der in der Lage ist, solch eine Einteilung
mittels der Angebote der Mitarbeiter und den Anforderungen der Arbeitsplätze zu
erstellen. Neben der Optimierung der Anforderungen für die diversen Arbeitsplätze,
wird auch die Fairness der Einteilung sowie die Präferenzen der Mitarbeiter an welchen
Arbeitsplätzen sie arbeiten wollen, berücksichtigt.
Das Problem wird formell definiert und von zwei unterschiedlichen methodischen Perspektiven
beleuchtet: ein Constraint Programming (CP) und ein metaheuristischer Ansatz
werden implementiert und hybridisiert. Die gewählte Metaheuristic ist eine Variable
Neighbourhood Search, welche als General VNS (GVNS) mit einem integrierten Variable
Neighbourhood Descent (VND) implementiert wird. Die zu verbessernde initiale Lösung
wird durch CP oder durch eine zusätzlich implementierte greedy Heuristik geliefert.
Von zehn verschiedenen realen Instanzen werden verschiedene Konfigurationen des GVNS
und VND mit unterschiedlich generierten initialen Lösungen getestet und verglichen.
Durch die Komplexität des Problems ist CP nicht in der Lage, kompetitive Resultate
zu erzielen. Resultate, die mittels einer initialen Lösung und einem darauf folgenden
VNS erzielt werden, sind generell erfolgsversprechender. Für einen realen Einsatz liefern
Lösungen, die durch eine greedy Heuristik generiert und mittels GVNS verbessert werden,
die besten Ergebnisse. Unser Lösungsansatz ist ein mächtiges Werkzeug für menschliche
Planer, um innerhalb weniger Stunden hochqualitative Lösungen zu generieren, die mit
wenig Adaptionsaufwand in der Praxis benutzt werden können.


Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_294891.pdf


Created from the Publication Database of the Vienna University of Technology.