Large neighborhood search for break scheduling

Abstract

In gewissen Arbeitsbereichen, wie etwa in der Flugverkehrskontrolle oder bei Fließbandarbeit, ist ein hohes Maß an Konzentration erforderlich. In solchen Bereichen sind regelmäßige Pausen verpflichtend um fatale Fehler zu vermeiden. Pausen sind streng geregelt durch etwa Sicherheitsregeln oder rechtlichen Forderungen. Das Break Scheduling Problem (BSP) befasst sich mit diesen Regelungen. Das BSP hat zum Ziel Pausen in einem gegebenen Schichtplan einzuplanen, sodass alle Pausenregeln erfüllt sind während Abweichungen vom Personalbedarf minimiert werden. In dieser Arbeit stellen wir eine Mixed Integer Programming Formulierung für das generelle BSP vor. Um das BSP zu lösen schlagen wir einen Large Neighborhood Suchalgorithmus (LNS) vor. Er besteht aus einer Initialisierungsphase und zwei Unteralgorithmen: ein Local Search und ein Mixed Integer Programming (MIP) Algorithmus. Um die MIP-Formulierung zu lösen kommt der Constraintlöser CPLEX zum Einsatz. Der Local Search Algorithmus verwendet zwei Nachbarschaftsoperationen: Swap und Assignment. Zusätzlich wird eine Random-Walk Methode genutzt um lokalen Optima zu entkommen. Local Search fokussiert sich auf einzelne Pausen. Der MIP Algorithmus entfernt alle Pausen einer gesamten Schicht um sie dann optimal wieder einzuplanen. Die Unteralgorithmen werden abwechselnd eingesetzt und bei jeder Iteration durch einen Selector gewählt. Wir testeten drei Auswahlverfahren: Random-Selector, Timebound-Selector und Probability-Selector. Der Probability-Selector, welcher die Wahrscheinlichkeit mittels einer Funktion regelt, erwies sich als überlegen. Zudem wurden Parameter, welche einen Einfluss auf die Leistung des Algorithmus haben, evaluiert. Wir berechneten Endergebnisse zu 30 Fallbeispielen, 20 von einem realen Szenario und 10 zufällig generierte. Der LNS Algorithmus übertrifft in den meisten Fällen unsere Implementierung von Local Search. Jedoch konnte er noch nicht an die besten bislang bekannten Resultate herankommen.

A high a level of concentration is essential in certain working areas such as in air traffic control, assembly line works or supervision. In such areas breaks are mandatory to avoid fatal errors. Breaks are regulated due to safety rules or legal demands. The break scheduling problem (Bsp) deals with these kind of regulations. The aim of the Bsp is to assign breaks to a given shift plan so that all regulations regarding breaks are fulfilled while violations of staff requirements are minimized. We give a mixed integer programming formulation for the general Bsp. To solve the Bsp we propose a large neighborhood search (LNS) algorithm. It is made up of an initialisation phase and two sub-algorithms: a local search algorithm and a mixed integer programming (MIP) algorithm. To solve the MIP formulation the solver CPLEX is used. The local search sub-algorithm uses two moves to optimize the solution: swap and assignment. In addition, a random-walk procedure is used to escape local optima. Local search focuses only on single breaks. The MIP sub-algorithm removes the break assignment of an entire shift and reassigns the breaks optimally. Sub-algorithms are applied alternately and are chosen by a selector at each iteration. We tested three different selection procedures: random-selector, timebound-selector and probability-selector. The probability-selector, using a function to regulate the probability, has shown to be superior. Further, different parameter settings, which influence the performance of the algorithm, are evaluated. In total 56 experiments were performed taking a total runtime of 2,736 hours. We computed final results for 30 instances, 20 obtained from a real-life scenario and 10 randomly generated. The LNS algorithm outperforms our local search implementation in most of the cases. However, it did not yet reach the upper bounds of the best known results so far.