Casual employee scheduling with constraint programming and metaheuristics

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.

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.