Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem. (English) Zbl 1185.90085
Summary: 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.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Abernathy, W. J., Baloff, N., & Hershey, J. C. (1971). The nurse staffing problem: issues and prospects. Sloan Management Review, 13, 87–99. |
| [2] | Arthur, J. L., & Ravidran, A. (1981). A multiple objective nurse scheduling model. IIE Transactions, 13, 55–60. doi: 10.1080/05695558108974536 . · doi:10.1080/05695558108974536 |
| [3] | 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 . · Zbl 1061.90042 · doi:10.1016/S0305-0548(03)00249-1 |
| [4] | Balakrishnan, A., & Wong, R. (1990). A network model for the rotating workforce scheduling problem. Networks, 20, 25–42. doi: 10.1002/net.3230200103 . · doi:10.1002/net.3230200103 |
| [5] | 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 . · Zbl 1068.90053 · doi:10.1016/j.ejor.2003.06.046 |
| [6] | 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 . · doi:10.1016/j.seps.2004.04.001 |
| [7] | 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. · Zbl 0979.90092 · doi:10.1287/opre.46.3.316 |
| [8] | 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 . · Zbl 0930.90045 · doi:10.1016/S0377-2217(97)00055-6 |
| [9] | 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. · Zbl 1146.90404 · doi:10.1016/j.ejor.2006.10.060 |
| [10] | 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 . · Zbl 1137.90479 · doi:10.1016/j.ejor.2005.04.028 |
| [11] | 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 . · doi:10.1016/0038-0121(96)00010-9 |
| [12] | 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 . · Zbl 0945.90019 · doi:10.1016/S0377-2217(98)00182-9 |
| [13] | 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 . · doi:10.1016/0360-8352(95)00017-U |
| [14] | 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. |
| [15] | 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 . · Zbl 1154.90422 · doi:10.1023/B:JOSH.0000046076.75950.0b |
| [16] | 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 . · Zbl 1160.90471 · doi:10.1007/s10107-003-0413-7 |
| [17] | Caron, G., Hansen, P., & Jaumard, B. (1999). The assignment problem with seniority and job priority problems. Operations Research, 47, 449–453. · Zbl 0979.90102 · doi:10.1287/opre.47.3.449 |
| [18] | Cline, D., Reilly, C., & Moore, J. F. (2003). What’s behind RN turnover?. Nursing Management, 34, 50–53. doi: 10.1097/00006247-200310000-00016 . |
| [19] | 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 . · Zbl 0909.90175 · doi:10.1016/S0305-0548(97)00043-9 |
| [20] | 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 . · Zbl 1053.90034 · doi:10.1016/S0377-2217(03)00095-X |
| [21] | Falkner, J., & Ryan, D. (1987). A bus crew scheduling system using a set partitioning model. Asia Pacific Journal of Operational Research, 4, 39–56. |
| [22] | 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. |
| [23] | Gamache, M., Soumis, F., Marquis, G., & Desrosiers, J. (1999). A column generation approach for large-scale aircrew rostering problems. Operations Research, 47, 247–263. · Zbl 1041.90513 · doi:10.1287/opre.47.2.247 |
| [24] | 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 . · doi:10.1136/bmj.327.7425.1219 |
| [25] | 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 . · Zbl 0943.90032 · doi:10.1016/S0377-2217(97)00330-5 |
| [26] | Kazahaya, G. (2005). Harnessing technology to redesign labor cost management reports. Healthcare Financial Management, 59, 94–100. |
| [27] | 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 . · Zbl 0972.90032 · doi:10.1002/(SICI)1520-6750(200004)47:3<185::AID-NAV1>3.0.CO;2-7 |
| [28] | Morris, J. G., & Showalter, M. J. (1983). Simple approaches to shift, days-off, and tour scheduling programs. Management Science, 29, 942–950. · doi:10.1287/mnsc.29.8.942 |
| [29] | Musa, A. A., & Saxena, U. (1984). Scheduling nurses using goal programming techniques. IIE Transactions, 16, 216–221. doi: 10.1080/07408178408974687 . · doi:10.1080/07408178408974687 |
| [30] | 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 . · Zbl 1044.90509 · doi:10.1007/3-540-40996-3_7 |
| [31] | 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. |
| [32] | Schrage, L. (1995). LINDO: optimization software for linear programming. Chicago: LINDO Systems Inc. |
| [33] | 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. |
| [34] | Trivedi, V. M., & Warner, M. (1976). A branch and bound algorithm for optimum allocation of float nurses. Management Science, 22, 972–981. · Zbl 0326.90069 · doi:10.1287/mnsc.22.9.972 |
| [35] | 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. |
| [36] | 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 . · Zbl 1238.90096 · doi:10.1287/ijoc.14.1.37.7706 |
| [37] | 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 . · Zbl 1106.90360 · doi:10.1287/opre.48.1.111.12453 |
| [38] | 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 . · Zbl 0873.90074 · doi:10.1016/0167-6377(96)00033-8 |
| [39] | Vanhoucke, M., & Maenhout, B. (2005). Characterisation and generation of nurse scheduling problem instances (Working Paper 05/339). Ghent University, Belgium. |
| [40] | 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. |
| [41] | Warner, H. W. (1976). Scheduling nursing personnel according to nursing preference: a mathematical approach. Operations Research, 24, 842–856. · Zbl 0337.90033 · doi:10.1287/opre.24.5.842 |
| [42] | Welton, J. (2006). Paying for nursing care in hospitals. American Journal of Nursing, 106, 67–69. |
| [43] | Zurn, P., Dolea, C., & Stilwell, B. (2005). Nurse retention and recruitment: developing a motivated workforce. Global Nursing Review Initiative, 4, 1–31. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
