Applying column generation to the general employee scheduling problem

Session date: 27 May 2024

Summary:

The employee scheduling problem has found many applications in multiple different fields like hospital scheduling or tour scheduling. Over the years many different variants with their own models and constraints appeared, specifically tailored to the individual needs of the problem origin. In 2019, a general version of this problem, combining many of the pre-existing constraints into a single all-encompassing schema. Due to previous successes of column generation on different versions of employee scheduling problems, this research aims to apply a column generation method on the general version of the problem. To accomplish this, a mathematical model of the schema has been developed as well as its decomposition into multiple master and sub-problems. Three avenues are to be explored by splitting the problem in any of the following ways: by employee, by shift, or by day and the effects each of these splits will have on the quality of the solutions.

Relevant papers

Solving the general employee scheduling problem

Lucas Kletzander, and Nysret Musliu

Computers & Operations Research, Nov 2020

Abs

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. 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 a new framework is proposed 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. 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 with good results. For one problem class our framework could obtain better solutions for several benchmark instances.