Integrated Staffing and Scheduling for Service Systems via Stochastic Integer Programming

We consider the problem of determining server schedules in multi-class service systems under uncertainty in the customer volumes. Common practice in such systems is to first identify server staffing levels that meet the quality of service targets, and then determine schedules for the servers that cover these staffing requirements. We propose a new stochastic integer programming model that integrates these two decisions. In the multi-class setting, this integrated model can yield lower scheduling costs by exploiting the presence of alternative server configurations that yield the same quality-of-service. The proposed model is a computationally challenging two-stage stochastic integer programming problem. While a branch-and-cut algorithm based on standard Benders decomposition approach can be applied to deal with the many customer volume scenarios, this fails due to the weakness of the resulting relaxation bound. We propose a novel application of mixed-integer rounding to improve the Benders cuts used in this algorithm that overcomes this drawback. Numerical results will be presented that demonstrate the computational efficiency of the proposed approach, and the benefit of solving the integrated model.

This is joint work with Merve Bodur.