A Population Based Variable Neighborhood Search Algorithm for the Minimum Shift Design Problem

For many companies in different industries to be able to reduce their costs and improve on their efficiency, it is necessary for them to make use of optimized shift schedules and rosters. In this thesis we propose to use the Min-Shift Design (MSD) problem formulation to create workforce schedules at a tactical level for an express company called TNT Express. At this company, the estimated workforce requirements for the coming planning horizon are known beforehand. The goal is to be able to create a tactical workforce schedule based on the estimated workforce requirements that covers all estimated workload. This tactical workforce schedule should specify the start and end times of each shift to be used and also the number of employees needed for each such shift. To solve the MSD problem, we developed a new solution method called Population Based Variable Neighborhood Search (PBVNS). This method is based on the principles of Variable Neighborhood Search and Evolutionary Algorithms. By combining some of the key elements of both methods, we developed an algorithm that can be used to solve synthetic and real world instances of shift design problems.