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
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.
-  A. Ikegami, “A Model for the Nurse Scheduling Problem,” IPSJ SIG Notes, Vol.96, No.10, pp. 1-6, Jan. 1996.
-  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.
-  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.
-  T. Curtois, “Employee Shift Scheduling Benchmark Data Sets,” Available from: http://www.cs.nott.ac.uk/ psztc/NRP/
-  A. A. Musa and U. Saxena, “Scheduling Nurses Using Goal-Programming Techniques,” IIE Trans., Vol.16, No.3, pp. 216-221, 1984.
-  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.
-  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.
-  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.
-  J. Desrosiers and M. E. Lübbecke, “A Primer in Column Generation,” pp. 1-32, Springer US, Boston, MA, 2005.
-  A. Ikegami and A. Niwa, “A Subproblem-centric Model and Approach to the Nurse Scheduling Problem,” 2003.
-  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.
-  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.
-  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.
-  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.