A branch-and-price approach for large-scale employee tour scheduling problems

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 perfor...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2007-11, Vol.155 (1), p.167-176
Main Authors: Ni, Hua, Abeledo, Hernán
Format: Article
Language:English
Subjects:
Comparative analysis
Decomposition
Employees
Integer programming
Operations research
Scheduling
Variables
Workforce planning
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. [PUBLICATION ABSTRACT]
ISSN:0254-5330
1572-9338
DOI:10.1007/s10479-007-0212-2