On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem |
| |
Authors: | Jeroen Beliën Erik Demeulemeester |
| |
Affiliation: | (1) Faculty of Economics and Applied Economics, Department DSIM: Decision Sciences & Information Management, Research Center for Operations Management, Katholieke Universiteit Leuven, Naamsestraat 69, 3000 Leuven, Belgium |
| |
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. |
| |
Keywords: | Decomposition Staff scheduling Set partitioning Multi-commodity flow Branch-and-price |
本文献已被 SpringerLink 等数据库收录! |