A large neighbourhood search approach to the multi-activity shift scheduling problem

作者：Quimper Claude Guy; Rousseau Louis Martin^*

来源：Journal of Heuristics, 2010, 16(3): 373-392.

DOI：10.1007/s10732-009-9106-6

• Shift scheduling
• Employee timetabling
• Large neighborhood search
• Very-large scale neighborhood
• Regular languages
• Context-free languages

The challenge in shift scheduling lies in the construction of a set of work shifts, which are subject to specific regulations, in order to cover fluctuating staff demands. This problem becomes harder when multi-skill employees can perform many different activities during the same shift. In this paper, we show how formal languages (such as regular and context-free languages) can be enhanced and used to model the complex regulations of the shift construction problem. From these languages we can derive specialized graph structures that can be searched efficiently. The overall shift scheduling problem can then be solved using a Large Neighbourhood Search. These approaches are able to return near optimal solution on traditional single activity problems and they scale well on large instances containing up to 10 activities.

• 出版日期2010-6