TEMPLE - a domain specific language for modeling and solving real-life staff scheduling problems

Abstract

Ziel von Personalplanungsproblemen ist es, Dienstpläne zu erstellen, damit Unternehmen den Bedarf nach ihren Produkten und Dienstleistungen unter Einhaltung arbeitsrechtlicher Bestimmungen erfüllen können. Optimale oder nahezu optimale Lösungen für Personalplanungsprobleme verbessern die Arbeitsbedingungen für Mitarbeiter und helfen Betrieben, ihr Personal effizient und kostensparend einzusetzen. Unglücklicherweise sind Personalplanungsprobleme im Allgemeinen NP-hart und können daher nicht in polynomieller Zeit gelöst werden. Das Entwickeln guter Algorithmen für Personalplanungsaufgaben ist eine Kunst für sich selbst, und normalerweise sind solche Algorithmen sehr stark auf eine bestimmte Problemstellung zugeschnitten. Diese stark angepassten Lösungen können in der Regel nur sehr schwer für andere Probleme wiederverwendet werden, da bereits wenige geringfügige Änderungen in einem Problem zu vielen gravierenden Abänderungen und Erweiterungen in einem stark angepassten Algorithmus führen.<br /> Ziel dieser Dissertation ist es, eine Modellierungssprache zu entwickeln, mit der wir Personalplanungsprobleme auf sehr natürliche, einfache und intuitive Weise modellieren und lösen können. Infolgedessen werden neue Lösungen für Personalplanungsprobleme wesentlich schneller entwickelt und bereits existierende Lösungen viel einfacher geändert und erweitert.<br /> Um dieses Ziel zu erreichen, betrachten wir zuerst zwei konkrete Personalplanungsprobleme. Das erste stammt aus einem Call Center, das zweite Problem betrachtet eine ähnliche Aufgabenstellung für Überwachungspersonal. Für diese beiden Probleme entwickeln wir zwei maßgeschneiderte Lokale Suche Algorithmen, die in vertretbarer Zeit qualitativ hochwertige Lösungen erzielen. Basierend auf diesen beiden Lösungen identifizieren wir grundlegende Bestandteile von Personalplanungsproblemen und Lokale Suche Algorithmen und entwickeln die Modellierungssprache TEMPLE, in welcher diese Bestandteile realisiert werden. Des Weiteren implementieren wir einen TEMPLE - Übersetzer mit dessen Hilfe wir für jedes Problemmodell in TEMPLE drei Lokale Suche Algorithmen erzeugen können. Diese Algorithmen können sofort, ohne weitere Nutzereingabe auf ein konkretes Problem angewandt werden, um optimierte Lösungen zu erzeugen.<br /> Wir demonstrieren die Zweckmäßigkeit unseres Ansatzes, indem wir das Personalplanungsproblem aus dem Bereich Überwachungspersonal in TEMPLE modellieren und lösen, und zeigen, dass wir mit unserem Ansatz konkurrenzfähige Ergebnisse erzielen. Abschließend modellieren wir ein vielschichtiges Personalplanungsproblem in TEMPLE, in welchem wir zuerst ein legales, hinsichtlich des Personalbedarf optimiertes Pausenmuster berechnen, und anschließend konkrete Arbeitsaufgaben den einzelnen Mitarbeitern unter Berücksichtigung ihrer Qualifikationen zuweisen. Die Lokale Suche Algorithmen, die wir aus unserem TEMPLE Modellen generiert haben, sind Bestandteil eines kommerziellen Personalplanungstools, das bereits erfolgreich kundenseitig eingesetzt wird.<br />

Staff scheduling is the process of creating work timetables for personnel so that companies can satisfy the demands for their goods and services. Optimal or close to optimal solutions for staff scheduling tasks help companies to deploy their staff efficiently and cost savingly, and improve the working conditions for deployed staff as well.<br />Unfortunately, staff scheduling problems are NP-hard in general, thus, they cannot be solved to optimality in polynomial time. As a consequence, the design of solutions for staff scheduling problems is an art in itself and results in algorithms which are strongly customized to a specific staff scheduling task. Customized solutions are usually very difficult to adapt, extend, and reuse for other problems. In this thesis we develop a modeling language to formulate and solve staff scheduling tasks in a very natural, simple, and intuitive manner.<br />Consequently, new algorithms for staff scheduling problems can be obtained more quickly, and already existing solutions can be modified and extended easily. To achieve that goal, we first consider two real-life staff scheduling problems, one originating in a call center, the other arising from the area of supervisory personnel, and we develop two customized local search algorithms, which are able to generate high-quality solutions for the two problems in reasonable time. On the basis of these two customized solutions we abstract common features and basic building blocks of staff scheduling problems and local search techniques. Then, to model staff scheduling problems with reduced effort, we design a novel, domain specific language called TEMPLE.<br />Furthermore, we develop and implement a TEMPLE compiler which transforms TEMPLE models of staff scheduling tasks into three generic local search algorithms, which can be executed instantaneously to optimize a considered staff scheduling problem. To deliver a proof of concept, we model the staff scheduling problem for supervisory personnel in TEMPLE, and we show that our approach is able to achieve competitive results of acceptable quality in reasonable time. Finally, we model and solve a multilayered, real-life break scheduling and task assignment problem in TEMPLE. The local search algorithms obtained from our TEMPLE model represent the core of a commercial staff scheduling tool which is already used successfully on customer's site.<br />