Combining Integer Programming and the Randomization Method to Schedule Employees

We describe a method to find low cost employee shift schedules that guarantee that the fraction of customers who wait less than a specified time (the service level) is always at or above a specified minimum. Most previous approaches used a two-step procedure: (1) determine period-by-period staffing requirements, and (2) find a minimum cost schedule that provides the required number of employees in every period. Due to approximations used in the first step, the two-step approach sometimes results in infeasible or suboptimal solutions. Our method iterates between a schedule evaluator and a schedule generator. Each iteration begins with a schedule for which the schedule evaluator calculates transient service levels using the randomization method. The transient service levels are used to identify infeasible intervals, where the service level is lower than desired. The schedule generator solves a series of integer programs to produce improved schedules. One constraint is added to the integer program for every infeasible interval, in an attempt to eliminate infeasibility without eliminating the optimal solution. The procedure terminates when a feasible solution is found. We present results for a range of test problems and discuss factors that make our approach more likely to outperform previous approaches