Title: Casual employee scheduling with constraint programming and metaheuristics
Other Titles: Schichtplanung von Gelegenheitsmitarbeitern mit Constraintprogrammierung und Metaheuristiken
Language: English
Authors: Teuschl, Stephan 
Qualification level: Diploma
Advisor: Raidl, Günther 
Assisting Advisor: Frohner, Nikolaus 
Issue Date: 2020
Number of Pages: 87
Qualification level: Diploma
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.

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.
Keywords: Personaleinsatzplanung; Constraintprogrammierung; multikriterielle Optimierung; Variable Nachbarschaftssuche
Employee Scheduling; Constraint Programming; Multi-Objective Optimization; Variable Neighborhood Search
URI: https://doi.org/10.34726/hss.2020.77621
http://hdl.handle.net/20.500.12708/16177
DOI: 10.34726/hss.2020.77621
Library ID: AC16071917
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

37
checked on Jun 15, 2021

Download(s)

58
checked on Jun 15, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.