Groupe d’études et de recherche en analyse des décisions

G-2011-23

Two-Phase Mathematical-Programming Heuristic for Flexible Assignment of Activities and Tasks to Work Shifts

, et

In the service industry, the employees perform work shifts and are assigned to interruptible activities and uninterruptible tasks during their shifts. The work shifts of the regular employees are often constructed a few weeks in advance of the operations when the activity and task demands are still uncertain. Just a few days before the operations when these demands unveil with more accuracy, the planned schedules can be slightly modified and on-call temporary employees can be scheduled to satisfy the demands as best as possible. As acceptable modifications, extending the planned shifts and moving their meal breaks are considered. In this paper, we are interested in the scheduling problem encountered in this second step that also involves assigning activities and tasks to the scheduled work shifts. To produce good quality solutions in fast computational times for large-sized instances, we develop a two-phase heuristic. In the first phase, an approximate mixed integer programming model is used to suggest temporary shifts and extensions to regular shifts, and to schedule and assign the tasks. In the second phase, a column generation heuristic embedded into a rolling horizon procedure determines the final shifts and assigns activities to them. Computational results obtained on randomly generated instances are reported to evaluate the validity of the proposed solution method.

, 24 pages