On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem

On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20082961
Country: Germany
Volume: 155
Issue: 1
Start Page Number: 143
End Page Number: 166
Publication Date: Nov 2007
Journal: Annals of Operations Research
Authors: ,
Keywords: programming: branch and bound, networks: flow
Abstract:

In this paper a comparison is made between two decomposition techniques to solve a staff scheduling problem with column generation. In the first approach, decomposition takes place on the staff members, whereas in the second approach decomposition takes place on the activities that have to be performed by the staff members. The resulting master LP is respectively a set partitioning problem and a capacitated multi-commodity flow problem. Both approaches have been implemented in a branch-and-price algorithm. We show a trade-off between modeling power and computation times of both techniques.

Reviews

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