SpringerLink
Log in

Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

The efficient management of nursing personnel is of critical importance in a hospital’s environment comprising a vast share of the hospital’s operational costs. The nurse scheduling process affects highly the nurses’ working conditions, which are strongly related to the provided quality of care. In this paper, we consider the rostering over a mid-term period that involves the construction of duty timetables for a set of heterogeneous nurses. In scheduling nursing personnel, the head nurse is typically confronted with various (conflicting) goals complying with different priority levels which represent the hospital’s policies and the nurses’ preferences. In constructing a nurse roster, nurses need to be assigned to shifts in order to maximize the quality of the constructed timetable satisfying the case-specific time related constraints imposed on the individual nurse schedules. Personnel rostering in healthcare institutions is a highly constrained and difficult problem to solve and is known to be NP-hard. In this paper, we present an exact branch-and-price algorithm for solving the nurse scheduling problem incorporating multiple objectives and discuss different branching and pruning strategies. Detailed computational results are presented comparing the proposed branching strategies and indicating the beneficial effect of various principles encouraging computational efficiency.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Abernathy, W. J., Baloff, N., & Hershey, J. C. (1971). The nurse staffing problem: issues and prospects. Sloan Management Review, 13, 87–99.

    Google Scholar 

  • Arthur, J. L., & Ravidran, A. (1981). A multiple objective nurse scheduling model. IIE Transactions, 13, 55–60. doi:10.1080/05695558108974536.

    Article  Google Scholar 

  • Azaiez, M. N., & Al Sharif, S. S. (2005). A 0–1 goal programming model for nurse scheduling. Computers & Operations Research, 32, 491–507. doi:10.1016/S0305-0548(03)00249-1.

    Article  Google Scholar 

  • Balakrishnan, A., & Wong, R. (1990). A network model for the rotating workforce scheduling problem. Networks, 20, 25–42. doi:10.1002/net.3230200103.

    Article  Google Scholar 

  • Bard, J. F., & Purnomo, H. W. (2005a). Preference scheduling for nurses using column generation. European Journal of Operational Research, 164, 510–534. doi:10.1016/j.ejor.2003.06.046.

    Article  Google Scholar 

  • Bard, J. F., & Purnomo, H. W. (2005b). A column generation-based approach to solve the preference scheduling problem for nurses with downgrading. Socio-Economic Planning Sciences, 39, 193–213. doi:10.1016/j.seps.2004.04.001.

    Article  Google Scholar 

  • Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W., & Vance, P. H. (1998). Branch-and-price: column generation for solving huge integer programs. Operations Research, 46, 316–329.

    Article  Google Scholar 

  • Beaumont, N. (1997). Scheduling staff using mixed integer programming. European Journal of Operational Research, 98, 473–484. doi:10.1016/S0377-2217(97)00055-6.

    Article  Google Scholar 

  • Beliën, J., & Demeulemeester, E. (2005). A branch-and-price approach for integrating nurse and surgery scheduling. European Journal of Operational Research, 189, 652–668.

    Article  Google Scholar 

  • 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. doi:10.1016/j.ejor.2005.04.028.

    Article  Google Scholar 

  • Berrada, I., Ferland, J. A., & Michelon, P. (1996). A multi-objective approach to nurse scheduling with both hard and soft Constraints. Socio-Economic Planning Sciences, 30, 183–193. doi:10.1016/0038-0121(96)00010-9.

    Article  Google Scholar 

  • Billionnet, A. (1999). Integer programming to schedule a hierarchical workforce with variable demands. European Journal of Operational Research, 114, 105–114. doi:10.1016/S0377-2217(98)00182-9.

    Article  Google Scholar 

  • Brusco, M. J., & Johns, T. R. (1995). Improving the dispersion of surplus labor in personnel scheduling solutions. Computers & Industrial Engineering, 28, 745–754. doi:10.1016/0360-8352(95)00017-U.

    Article  Google Scholar 

  • Burke, E. K., De Causmaecker, P., Petrovic, S., & Vanden Berghe, G. (2003). Variable neighbourhood search for nurse rostering problems. In M. G. C. Resende & J. P. de Sousa (Eds.), Metaheuristics: computer decision-making. Mechelen: Kluwer.

    Google Scholar 

  • Burke, E. K., De Causmaecker, P., Vanden Berghe, G., & Van Landeghem, H. (2004). The state of the art of nurse rostering. Journal of Scheduling, 7, 441–499. doi:10.1023/B:JOSH.0000046076.75950.0b.

    Article  Google Scholar 

  • Caprara, A., Monaci, M., & Toth, P. (2003). Models and algorithms for a staff scheduling problem. Mathematical Programming, 98, 445–476. doi:10.1007/s10107-003-0413-7.

    Article  Google Scholar 

  • Caron, G., Hansen, P., & Jaumard, B. (1999). The assignment problem with seniority and job priority problems. Operations Research, 47, 449–453.

    Article  Google Scholar 

  • Cline, D., Reilly, C., & Moore, J. F. (2003). What’s behind RN turnover?. Nursing Management, 34, 50–53. doi:10.1097/00006247-200310000-00016.

    Google Scholar 

  • De Reyck, B., & Herroelen, W. (1998). A branch-and-bound procedure for the resource constrained project scheduling problem with discounted cash flows and generalized precedence relations. Computers & Operations Research, 25, 1–17. doi:10.1016/S0305-0548(97)00043-9.

    Article  Google Scholar 

  • Ernst, A. T., Jiang, H., Krishamoorty, M., Owens, B., & Sier, D. (2004). Staff scheduling and rostering: a review of applications, methods and models. European Journal of Operational Research, 153, 3–27. doi:10.1016/S0377-2217(03)00095-X.

    Article  Google Scholar 

  • Falkner, J., & Ryan, D. (1987). A bus crew scheduling system using a set partitioning model. Asia Pacific Journal of Operational Research, 4, 39–56.

    Google Scholar 

  • Fitzpatrick, T., Farrell, L. Y., & Richter-Zeunik, M. (1987). An automated staff scheduling system that minimizes payroll costs and maximizes nurse satisfaction. Computers in Nursing, 5, 10–14.

    Google Scholar 

  • Gamache, M., Soumis, F., Marquis, G., & Desrosiers, J. (1999). A column generation approach for large-scale aircrew rostering problems. Operations Research, 47, 247–263.

    Article  Google Scholar 

  • Haggerty, J. L., Reid, R. J., Freeman, G. K., Starfield, B. H., Adair, C. E., & McKendry, R. (2003). Continuity of care: a multidisciplinary review. British Medical Journal, 327, 1219–1221. doi:10.1136/bmj.327.7425.1219.

    Article  Google Scholar 

  • Jaumard, B., Semet, F., & Vovor, T. (1998). A generalized linear programming model for nurse scheduling. European Journal of Operational Research, 107, 1–18. doi:10.1016/S0377-2217(97)00330-5.

    Article  Google Scholar 

  • Kazahaya, G. (2005). Harnessing technology to redesign labor cost management reports. Healthcare Financial Management, 59, 94–100.

    Google Scholar 

  • Mehrotra, A., Murphy, K. E., & Trick, M. A. (2000). Optimal shift scheduling: a branch-and-price approach. Naval Research Logistics, 47, 185–200. doi:10.1002/(SICI)1520-6750(200004)47:3<185::AID-NAV>13.0.CO;2-7.

    Article  Google Scholar 

  • Morris, J. G., & Showalter, M. J. (1983). Simple approaches to shift, days-off, and tour scheduling programs. Management Science, 29, 942–950.

    Article  Google Scholar 

  • Musa, A. A., & Saxena, U. (1984). Scheduling nurses using goal programming techniques. IIE Transactions, 16, 216–221. doi:10.1080/07408178408974687.

    Article  Google Scholar 

  • Osogami, T., & Imai, H. (2000). Classification of various neighbourhood operations for the nurse scheduling problem. Lecture Notes in Computer Science, 1969, 72–83. doi:10.1007/3-540-40996-3_7.

    Article  Google Scholar 

  • Ryan, D. M., & Foster, B. A. (1981). An integer programming approach to scheduling. In A. Wren (Ed.), Computer scheduling of public transport urban passenger vehicle and crew scheduling. Amsterdam: North-Holland.

    Google Scholar 

  • Schrage, L. (1995). LINDO: optimization software for linear programming. Chicago: LINDO Systems Inc.

    Google Scholar 

  • Sol, M., & Savelsbergh, M. (1994). A branch-and-price algorithm for the pickup and delivery problem with time windows. Memorandum COSOR 94-22, TUE, The Netherlands.

  • Trivedi, V. M., & Warner, M. (1976). A branch and bound algorithm for optimum allocation of float nurses. Management Science, 22, 972–981.

    Article  Google Scholar 

  • Vance, P. H., Atamturk, A., Barnhart, C., Gelman, E., Johnson, E. L., Krishna, A., Mahidhara, D., Nemhauser, G. L., & Rebello, R. (1997). A heuristic branch-and-price approach for the airline crew pairing problem (Technical Report TLI/LEC-97-06). Georgia, Institute of Technology, Atlanta, GA.

  • Van den Akker, M., Hoogeveen, H., & Van de Velde, S. (2002). Combining column generation and Lagrangean relaxation to solve a single-machine common due date problem. INFORMS Journal on Computing, 14, 37–51. doi:10.1287/ijoc.14.1.37.7706.

    Article  Google Scholar 

  • 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. doi:10.1287/opre.48.1.111.12453.

    Article  Google Scholar 

  • Vanderbeck, F., & Wolsey, L. A. (1996). An exact algorithm for IP column generation. Operations Research Letters, 19, 151–159. doi:10.1016/0167-6377(96)00033-8.

    Article  Google Scholar 

  • Vanhoucke, M., & Maenhout, B. (2005). Characterisation and generation of nurse scheduling problem instances (Working Paper 05/339). Ghent University, Belgium.

  • Vanhoucke, M., & Maenhout, B. (2007). NSPLib—a tool to evaluate (meta-)heuristic procedures. In S. Brailsford & P. Harper (Eds.), Operational research for health policy: making better decisions, proceedings of the 31st meeting of the European working group on operational research applied to health services (pp. 151–165), Southampton, Great Britain.

  • Warner, H. W. (1976). Scheduling nursing personnel according to nursing preference: a mathematical approach. Operations Research, 24, 842–856.

    Article  Google Scholar 

  • Welton, J. (2006). Paying for nursing care in hospitals. American Journal of Nursing, 106, 67–69.

    Google Scholar 

  • Zurn, P., Dolea, C., & Stilwell, B. (2005). Nurse retention and recruitment: develo** a motivated workforce. Global Nursing Review Initiative, 4, 1–31.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Economics and Business Administration, Ghent University, Tweekerkenstraat 2, 9000, Gent, Belgium

    Broos Maenhout

  2. Operations & Technology Management Centre, Vlerick Leuven Gent Management School, Reep 1, 9000, Gent, Belgium

    Mario Vanhoucke

Authors
  1. Broos Maenhout
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mario Vanhoucke
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mario Vanhoucke.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Maenhout, B., Vanhoucke, M. Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem. J Sched 13, 77–93 (2010). https://doi.org/10.1007/s10951-009-0108-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-009-0108-x

Keywords

Search

Navigation