Personnel scheduling consists of determining least-cost employee work schedules to cover the demand of one or several jobs in each period of a time horizon. During the operations, several minor disruptions caused, for example, by a late employee may occur and must be addressed in real time by re-scheduling certain employees. In this paper, we develop a fast re-scheduling heuristic that can be used to solve the personnel re-scheduling problem in a context where the employees can be assigned to a wide variety of shifts such as in the retail industry. This heuristic considers five types of decision and is based on the dual values of the linear relaxation of the personnel scheduling problem. We also propose a procedure exploiting a multivariate adaptive regression splines method for updating the dual values after each disruption when several ones occur int he same week. Computational experiments conducted on a set of 1050 instances derived from real-life datasets involving up to 191 employees show the efficiency of the proposed re-scheduling heuristic: it can compute optimal solutions for more than 95% of these instances in less than one second on average. Furthermore, the dual value updating process allows an average reduction of 73% of the optimality gap for each disruption.
Published April 2017 , 22 pages