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 are determining how many staff to employ and the times at which shifts should start. The problem is expressed as a large MIP problem initially presenting computational difficulties. The difficulties vanish when the formulation is modified and a package allowing the use of reduce and (especially) special ordered sets becomes available. The client has 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 precisely known.