JACIII Vol.21 No.7 pp. 1251-1261
doi: 10.20965/jaciii.2017.p1251


New Approach Combining Branch and Price with Metaheuristics to Solve Nurse Scheduling Problem

Junya Inafune, Shinya Watanabe, and Masayoshi Okudera

Muroran Institute of Technology
27-1, Mizumoto-cho, Muroran 050-8585, Japan

February 20, 2017
August 31, 2017
November 20, 2017
nurse scheduling problem, branch-and-price, metaheuristics, evolutionary multi-objective optimization

This paper presents a new approach combining Branch and Price (B&P) with metaheuristics to derive various high-quality schedules as solutions to a nurse scheduling problem (nurse rostering problem). There are two main features of our approach. The first is the combination of B&P and metaheuristics, and the second is the implementation of an efficient B&P algorithm. Through applying our approach to widely used benchmark instances, the effectiveness of our approach is determined.

Cite this article as:
J. Inafune, S. Watanabe, and M. Okudera, “New Approach Combining Branch and Price with Metaheuristics to Solve Nurse Scheduling Problem,” J. Adv. Comput. Intell. Intell. Inform., Vol.21, No.7, pp. 1251-1261, 2017.
Data files:
  1. [1] A. Ikegami, “A Model for the Nurse Scheduling Problem,” IPSJ SIG Notes, Vol.96, No.10, pp. 1-6, Jan. 1996.
  2. [2] B. Maenhout and M. Vanhoucke, “Branching strategies in a branchand- price approach for a multiple objective nurse scheduling problem,” J. of Scheduling, Vol.13, No.1, pp. 77-93, 2010.
  3. [3] E. K. Burke and T. Curtois, “New approaches to nurse rostering benchmark instances,” European J. of Operational Research, Vol.237, No.1, pp. 71-81, 2014.
  4. [4] T. Curtois, “Employee Shift Scheduling Benchmark Data Sets,” Available from: psztc/NRP/
  5. [5] A. A. Musa and U. Saxena, “Scheduling Nurses Using Goal-Programming Techniques,” IIE Trans., Vol.16, No.3, pp. 216-221, 1984.
  6. [6] I. Ozkarahan, “The zero-one goal programming model of a flexible nurse scheduling support system,” Proc. of Int. Industrial Engineering Conf., pp. 436-441, 1989.
  7. [7] A. Ikegami and A. Niwa, “A subproblem-centric model and approach to the nurse scheduling problem,” Mathematical Programming, Vol.97, No.3, pp. 517-541, Aug. 2003.
  8. [8] E. K. Burke, T. Curtois, G. Post, R. Qu, and B. Veltman, “A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem,” European J. of Operational Research, Vol.188, No.2, pp. 330-341, 2008.
  9. [9] J. Desrosiers and M. E. Lübbecke, “A Primer in Column Generation,” pp. 1-32, Springer US, Boston, MA, 2005.
  10. [10] A. Ikegami and A. Niwa, “A Subproblem-centric Model and Approach to the Nurse Scheduling Problem,” 2003.
  11. [11] H. Li, A. Lim, and B. Rodrigues, “A Hybrid AI Approach for Nurse Rostering Problem,” Proc. of the 2003 ACM Symp. on Applied Computing, SAC’03, pp. 730-735, New York, NY, USA, 2003, ACM.
  12. [12] M. N. Azaiez and S. S. Al Sharif, “A 0-1 Goal Programming Model for Nurse Scheduling,” Comput. Oper. Res., Vol.32, No.3, pp. 491-507, March 2005.
  13. [13] C. Valouxis and E. Housos, “Hybrid optimization techniques for the workshift and rest assignment of nursing personnel,” Artificial Intelligence in Medicine, Vol.20, No.2, pp. 155-175, 2000. Planning and Scheduling in the Hospital.
  14. [14] F. Bellanti, G. Carello, F. D. Croce, and R. Tadei, “A greedy-based neighborhood search approach to a nurse rostering problem,” European J. of Operational Research, Vol.153, No.1, pp. 28-40, 2004. Timetabling and Rostering.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, IE9,10,11, Opera.

Last updated on Jul. 06, 2018