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

Junya Inafune; Shinya Watanabe; Masayoshi Okudera

doi:10.20965/jaciii.2017.p1251

single-jc.php

« previous

JACIII Vol.21 No.7 pp. 1251-1261

doi: 10.20965/jaciii.2017.p1251

(2017)

Paper:

Views over last 60 days: 1,128

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

Received:

February 20, 2017

Accepted:

August 31, 2017

Published:

November 20, 2017

Keywords:

nurse scheduling problem, branch-and-price, metaheuristics, evolutionary multi-objective optimization

Abstract

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:

References

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

[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: http://www.cs.nott.ac.uk/ 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.