EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4021. Flexible shift scheduling of healthcare workers using column generation

Invited abstract in session TC-15: Staffing and workforce planning and scheduling, stream OR in Health Services (ORAHS).

Tuesday, 12:30-14:00
Room: 18 (building: 116)

Authors (first author is the speaker)

1. David Ajit Kirpekar-Sauer
2. Jens Brunner
Department of Technology, Management, and Economics, Technical University of Denmark

Abstract

We consider a tactical shift scheduling problem, consisting of assigning health care workers in a hospital to shifts for handling a given number of tasks spread out over a fixed time horizon. We will implement a branch-and-price algorithm with the master problem assigning schedules to workers and the subproblem generating columns (shift schedules) to add to the master problem. The master problem will minimize the total cost of the chosen shift schedules and assigning outside workers to handle understaffing. The novelty in our approach is the use of a network flow model in the shift subproblem. Instead of formulating the subproblem as a MIP, we will make use of a novel network formulation. By traversing the network from the starting period to the end period a path, corresponding to a valid shift schedule, will be achieved. As such the subproblem can be solved, and a maximum reduced cost schedule can be found, by solving the shortest path problem for the graph. We will implement Dijkstra's algorithm with a labelling and readout step to find the shortest path through the network. In addition we will evaluate the possibility of scheduling flexible and in-flexible workers to achieve a greater flexibility in the generated schedules. The fraction of flexible workers will be evaluated with varying degrees of flexibility to ensure a feasible application of the method. The method will be applied and tested on a number of test instances generated from real-world data.

Keywords

Status: accepted

Back to the list of papers