Variable Neighbourhood Search: A Case Study for a Highly-Constrained Workforce Scheduling Problem

Citation

Reid KN, Li J, Swan J, McCormick A & Owusu G (2016) Variable Neighbourhood Search: A Case Study for a Highly-Constrained Workforce Scheduling Problem. In: 2016 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE SSCI 2016: IEEE Symposium Series on Computational Intelligence, Athens, Greece, 06.12.2016-09.12.2016. Piscataway, NJ, USA: IEEE. https://doi.org/10.1109/SSCI.2016.7850087

Abstract
This paper describes a Variable Neighbourhood Search (VNS) combined with simulated annealing to tackle a highly constrained workforce scheduling problem at British Telecommunications plc (BT). A refined greedy algorithm is firstly designed to create an initial solution which meets all hard constraints and satisfies some of the soft constraints. The VNS is then used to swap out less promising combinations, continually moving towards a more optimal solution until meeting finishing requirements. The results are promising when compared to the stand- alone greedy algorithm. We believe there is scope for this to be extended in several ways, i.e. into a more complex variation of VNS to further improve results, to be applied to further data sets and workforce scheduling problem scenarios, and to have input parameters to the algorithm selectively optimized to discover what kind of improvements in efficiency and fitness are possible. There is also scope for this to be used in similar combinatorial optimization problems.

Keywords
Variable Neighbourhood Search; Personnel Scheduling; Engineer Rostering; Metaheuristic

• KenReidUniversityOfStirling.pdf