Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
11012405 | European Journal of Operational Research | 2019 | 9 Pages |
Abstract
The multi-activity shift scheduling problem involves assigning a sequence of activities to a set of employees. In this paper, we consider the variant where the employees have different qualifications and each activity must be performed in a specified time window; i.e., we specify the earliest start period and the latest finish period. We propose a matheuristic in which Lagrangian relaxation is used to identify a subset of promising shifts, and a restricted set covering problem is solved to find a feasible solution. Each shift is represented by a context-free grammar. Computational tests are carried out on two sets of instances from the literature. For the first set, the matheuristic finds a solution with an optimality gap less than 0.01% for 70% of the instances and improves the best-known solution for 16% of them; for the second set, the matheuristic reaches the best-known solutions for 55% of the instances and finds better solutions for 37.5% of them.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Noberto A. Hernández-Leandro, Vincent Boyer, M. Angélica Salazar-Aguilar, Louis-Martin Rousseau,