SOLVING A REAL MANPOWER ROSTERING PROBLEM

Abstract

This study is targeted at a real-life manpower rostering problem based on an UK automobile company. The UK automobile company provides on-the-road assistance in 100 over regions in UK and it faces the problem of rostering its servicing staff while managing complex constraints. A consultancy company was then tasked in May 2006 to produce a more efficient and automated way to do the roster. A 3-stage heuristic was designed by the consultancy company. The first stage comprises of an optimization program to fix the workday assignment and the second stage encompasses a construction heuristic to fix the shift assignments within the days. The last stage is a search algorithm to seek a better solution. I joined the project in June and was tasked with the coding of the construction heuristic (stage 2) to construct a good initial feasible solution. This paper is divided into 2 parts. The first part will provide the detailed problem setup and give you an introduction to the 3-stage heuristic. I will also go through the details of the construction heuristic which I have coded. In all, based on the 9 test regions, the results of the 3-stage heuristic mark a 48% improvement over the current roster. In the second part, I will touch upon a mathematical programming approach to further improve the construction heuristic. The derived mathematical model is then translated into an optimization programming language to be solved in ILOG CPLEX. The results are encouraging and the CPLEX model manages to make further improvements to the original construction heuristic.