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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bard, J. F., & Purnomo, H. W. (2005). Preference scheduling for nurses using column generation. European Journal of Operational Research, 164, 510–534.
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: column generation for solving huge integer programs. Operations Research, 46, 316–329.
Beliën, J., & Demeulemeester, E. (2006). Scheduling trainees at a hospital department using a branch-and-price approach. European Journal of Operational Research, 175, 258–278.
Bellman, R. (1957). Dynamic programming. Princeton: Princeton University Press.
Billionnet, A. (1999). Integer programming to schedule a hierarchical workforce with variable demands. European Journal of Operational Research, 114, 105–114.
Burke, E. K., De Causmaecker, P., Vanden Berghe, G., & Van Landeghem, H. (2004). The state of the art of nurse rostering. The Journal of Scheduling, 7, 441–499.
Caprara, A., Monaci, M., & Toth, P. (2003). Models and algorithms for a staff scheduling problem. Mathematical Programming, 98, 445–476.
Cheang, B., Li, H., Lim, A., & Rodrigues, B. (2003). Nurse rostering problems—a bibliographic survey. European Journal of Operational Research, 151, 447–460.
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8, 101–111.
Dreyfus, S. E., & Law, A. M. (1977). The art and theory of dynamic programming. New York: Academic.
Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting stock problem. Operations Research, 9, 849–859.
Jaumard, B., Demet, F., & Vovor, T. (1998). A generalized linear programming model for nurse scheduling. European Journal of Operational Research, 107, 1–18.
Mason, A. J., & Smith, M. C. (1998). A nested column generator for solving rostering problems with integer programming. In International conference on optimisation: techniques and applications (pp. 827–834).
Mehrotra, A., Murphy, K. E., & Trick, M. A. (2000). Optimal shift scheduling: a branch-and-price approach. Naval Research Logistics, 47, 185–200.
Vanderbeck, F. (2000). On Dantzig–Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research, 48, 111–128.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Beliën, J., Demeulemeester, E. On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem. Ann Oper Res 155, 143–166 (2007). https://doi.org/10.1007/s10479-007-0220-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-007-0220-2