A Heuristic solver framework for the general employee scheduling problem

Abstract

In vielen Berufen ist es erforderlich, in verschiedenen Schichten zu arbeiten, um unterschiedliche Anforderungen abzudecken. Dazu zählen Bereiche im Gesundheitswesen, in Sicherheitsdiensten, im Transportwesen, in der Produktion oder in Callcentern. Dabei muss eine Vielzahl an Bedingungen erfüllt werden um gültige Schichtpläne zu gestalten. Die Anforderungen können auf unterschiedliche Arten festgelegt werden, diverse Gesetze müssen eingehalten werden und die Zufriedenheit der Angestellten muss berücksichtigt werden. Damit ist es nicht nur zunehmend schwerer, derartige Pläne manuell zu erstellen, umso mehr Angestellte und Bedingungen zu berücksichtigen sind, sondern auch sehr zeitraubend. Somit sind automatisierte Lösungen notwendig, um im Wettbewerb zu bestehen. Allerdings ist es auch hier schwer, in annehmbarer Zeit gute Lösungen zu erreichen, da viele dieser Probleme NP-schwer sind. Während nicht in jedem Problem alle erdenklichen Bedingungen zu berücksichtigen sind, ist es mühsam, jeweils eine neue Formulierung und eine entsprechende Lösungsmethode zu entwickeln. Diese können dann oft nur schwer auf ähnliche Probleme übertragen werden. Auf der anderen Seite ist es eine große Herausforderung, eine allgemeine Formulierung und dazu passende Lösungsmethoden zu entwickeln, da schon zahlreiche Teilprobleme alleine NP-schwer sind. Somit ist die erste Aufgabe, einen Beitrag zur Formulierung des General Employee Scheduling (GES) Problems zu leisten, die eine große Bandbreite an derartigen Personalplanungsproblemen darstellen kann. Eine umfassende Literatursuche wird ausgeführt, um zahlreiche verschiedene Probleme dieser Art in der Formulierung abzubilden. Der Hauptbeitrag dieser Arbeit ist die Entwicklung eines neuen Frameworks für das GES-Problem, mit dem verschiedene heuristische Lösungsmethoden implementiert und auf verschiedene Probleme angewandt werden können. Dies wird umgesetzt, indem ein einheitlicher Umgang mit Bedingungen und die Möglichkeit für die Implementierung verschiedener Nachbarschaften geschaffen wird, die dann in unterschiedlichen Algorithmen wiederverwendet werden können. Weiter wird eine neue Suchmethode entwickelt und in diesem Framework implementiert. Ein Generator für neue Instanzen wird bereitgestellt, um Anforderungen und Bedingungen in neuen Arten zu kombinieren, die in der Literatur noch nicht untersucht werden, und damit neue Benchmark-Instanzen zu erhalten. Um die Anwendbarkeit für eine Vielzahl von Problemen zu zeigen, nehmen wir unterschiedliche Probleme aus der Literatur, die unterschiedliche Anforderungsarten und Bedingungen verwenden, übersetzen diese in unsere Formulierung und wenden unsere Lösungsmethode auf diese Instanzen und unsere eigenen Instanzen an. Die Ergebnisse zeigen, dass zahlreiche Probleme aus unterschiedlichen Bereichen der Personalzeitplanung in unserer Formulierung dargestellt werden können und das Framework bei diesen Problemen erfolgreich angewandt werden kann. Der Vergleich mit den Ergebnissen aus der Literatur zeigt, dass der implementierte allgemeine Algorithmus gute Ergebnisse für die meisten Instanzen aus diesen Problemen liefert und eine gute Basis für die Entwicklung von spezialisierten Algorithmen in unserem Framework bildet.

In many professions the demand for work requires employees to work in different shifts to cover varying requirements including areas like health care, protection services, transportation, manufacturing or call centers. However, there are many constraints that need to be satisfied in order to create feasible schedules. The demands can be specified in various ways, different legal requirements need to be respected and employee satisfaction has to be taken into account. Not only is it increasingly difficult to generate schedules by hand for more employees and more requirements, it is also very time consuming. Therefore, automated solutions are mandatory to stay competitive. However, even then it is often hard to provide good solutions in reasonable time as many of the problems are NP-hard. While not each problem will require the whole set of available restrictions, it is cumbersome to develop a new specification format and corresponding solver for each problem. Often these can not be well applied to similar problems differing in some requirements. On the other hand it is a challenging task to provide a general formulation and solution methods that can solve large integrated problems, as even several sub-problems on their own are known to be NP-hard. Therefore, the first objective is to give a contribution to the formulation of the General Employee Scheduling (GES) problem that can be used to specify a wide range of such scheduling problems. An extensive literature review is conducted to determine a wide range of employee scheduling problems in order to cover them in the GES formulation. The main contribution of this thesis is the development of a new framework for the general employee scheduling problem that allows the implementation of various heuristic algorithms and their application to a wide range of problems. This is realized by proposing a unified handling of constraints and the possibility to implement various moves that can be reused across different algorithms. Further, a new search method is developed and implemented in the framework. An instance generator is provided that can combine the demands and constraints in ways that are not yet covered by literature to provide new benchmark instances. In order to show the applicability to a wide range of problems, we take different problems from literature that cover different types of demand and constraints, translate their instances to our formulation and apply our solver to those instances as well as our own instances. The results show that several problems from different areas of employee scheduling can be modelled in our formulation and the framework can successfully be applied to all of them. The comparison with the results from literature shows that the implemented general purpose algorithm can provide good results for most instances across all problems and provides a good foundation for the development of more specialized algorithms in the framework.