Timetabling, Rostering, Scheduling. Timetabling has played a role in our lives at some point or the other – class timetables at school, doctor’s appointments, schedules for your favourite sport, etc. I’ve always enjoyed the practice of scheduling and was fortunate enough to do my dissertation on “Mathematical Optimization for Scheduling Problems” in my integrated Master’s degree at the University of Edinburgh in 2023-2024.
About Nurse Rostering and other Scheduling Problems
In my dissertation, I reviewed the literature surrounding several scheduling problems such as sports scheduling and University course timetabling. These problems aim to find the “best” schedule that allocates work/jobs to machines/people while meeting certain requirements.
In particular, I worked on the nurse rostering problem which involves the allocation of nurses to hospital shifts over a planning horizon while meeting certain requirements such as contract hours, minimum rest periods and days-off requests. The nurse rostering problem has several variants based on different compulsory requirements (constraints) and objectives which define a “good” nurse schedule. In order to consider several constraints that have been used in the Nurse Rostering literature, I created a table of constraints along with a comparison of which papers in the literature use these constraints as hard (compulsory) and soft (preferred) constraints.
Solving the Nurse Rostering Problem
I also attempted to solve a formulation of the Nurse Rostering Problem introduced by Curtois and Qu (2014) by implementing a hybrid algorithm that combines a Greedy Heuristic with Variable Neighbourhood Search (VNS), a local search method, to find a “good” nurse schedule. The greedy heuristic is used to construct an initial feasible schedule, i.e., a schedule which satisfies all the hard (compulsory) constraints.
Variable Neighbourhood Search
Variable Neighbourhood Search (VNS) is a local search heuristic which uses an initial feasible solution, defines feasible neighbours and improves the current solution by choosing a “better” feasible neighbour. The VNS algorithm is used to improve the initial feasible solution provided by the Greedy Heuristic. An example of neighbourhood structures that can be formed from an initial schedule of nurses A, B and C over a four-day planning period is given in Figure A below.
The algorithm updates the current best solution to be the best neighbourhood structure so far and iteratively finds improvements to the current best solution until some stopping criterion is reached. Figure B below contains the pseudo-code for the VNS algorithm, which is widely used for solving several problems in Operational Research beyond the Nurse Rostering Problem.
The VNS algorithm was tested on 24 benchmark instances of the Nurse Rostering Problem from the Employee Shift Scheduling Benchmark Dataset. It was found that VNS improved the quality of nurse schedules in most instances. However, there was an indication of the possibility that the final solutions obtained in some cases were local minima and not global optima. This motivated the search for alternative/improved solution methods to solve the problem.
Overall Experience
As my first experience solving an Operational Research problem in depth, this dissertation provided an invaluable journey of personal and academic growth. The periods of literature review were inspirational with the exposure to extensive work being carried out on the problem over several decades and across several continents. Working under the supervision of Dr. Sergio García Quiles helped me explore several ideas in an informed manner. I also thoroughly enjoyed implementing a solution method to solve a problem that interests me. While working on the dissertation, I came to be sure that further study in Operational Research, through a PhD, would be my next best step forward.