The minimum shift design problem

The minimum shift design problem

0.00 Avg rating0 Votes
Article ID: iaor20082958
Country: Germany
Volume: 155
Issue: 1
Start Page Number: 79
End Page Number: 105
Publication Date: Nov 2007
Journal: Annals of Operations Research
Authors: , , , , ,
Keywords: heuristics
Abstract:

The min-SHIFT DESIGN problem (MSD) is an important scheduling problem that needs to be solved in many industrial contexts. The issue is to find a minimum number of shifts and the number of employees to be assigned to these shifts in order to minimize the deviation from workforce requirements. Our research considers both theoretical and practical aspects of the min-SHIFT DESIGN problem. This problem is closely related to the minimum edge-cost flow problem (MECF), a network flow variant that has many applications beyond shift scheduling. We show that MSD reduces to a special case of MECF and, exploiting this reduction, we prove a logarithmic hardness of approximation lower bound for MSD. On the basis of these results, we propose a hybrid heuristic for the problem, which relies on a greedy heuristic followed by a local search algorithm. The greedy part is based on the network flow analogy, and the local search algorithm makes use of multiple neighborhood relations. An experimental analysis on structured random instances shows that the hybrid heuristic clearly outperforms our previous commercial implementation. Furthermore, it highlights the respective merits of the composing heuristics for different performance parameters.

Reviews

Required fields are marked *. Your email address will not be published.