Fast Heuristics for a Staff Scheduling Problem with Time Interval Demand Coverage

Staff scheduling is a key component of supporting and increasing competitiveness for many service enterprises. This is of especially urgent concern for organizations that provide service on a twenty-four hour basis and often encounter significant fluctuations of demand. By scheduling personnel, the employers have also to strictly follow local laws, industrial regulations, and workload agreements that may considerably affect the final schedule. Staff preferences have also to be taken into account when planning work schedules, since it may reduce turnover and increase productivity. In this paper we consider a staff scheduling problem that arise in the industrial fields where the demand in staff is highly dynamic and varies within time intervals throughout a day. The goal is to assign each employee with a shift for each day of a planning horizon so as to minimize the sum of unsatisfied demand over all time intervals subject to hard workplace constraints. Note that each employee may have his/her day-specific set of pre-defined shifts and a set of work-rule constraints. We formulate the scheduling problem as a mixed-integer program. We develop several fast two-stage heuristic algorithms that includes a constructive step to find an initial solution followed by fast local search procedures. We demonstrate the effectiveness of the proposed approaches on a number of real-world huge-scale scheduling problems involving thousands of employees.