Scheduling Staff Using Mixed Integer Programming

This paper describes the solution of a problem of scheduling a workforce so as to meet demand which varies markedly with the time of day and moderately with the day of week. The main objectives were determining how many staff to emply and the times at which shifts should start. The problem was expressed as a large MIP problem initially presenting computational difficulties. The difficulties vanished when the formulation was modified and when a package allowing use of reduce and (especially) special ordered sets became available. The client commissioned the study primarily to benchmark its existing schedule by comparing it with a theoretical optimum. The optimal schedule and comparison are very sensitive to technical and cost coefficients which are not preciesely known.