A hybrid constraint integer programming approach to solve nurse scheduling problems

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

Abstract

The Nurse Scheduling Problem can be simply defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some constraints and preferences. The inherent benefits of having higher-quality and more flexible schedules are a reduction in outsourcing costs and an increase of job satisfaction in health organizations. In this paper, we present a novel systematic hybrid algorithm, which combines Integer Programming (IP) and Constraint Programming (CP) to efficiently solve highly-constrained Nurse Scheduling Problems. Our focus is to exploit the problem-specific information to improve the performance of the algorithm, and therefore obtain high-quality solutions as well as strong lower bounds. We test our algorithm based on some real-world benchmark instances. Very competitive results are reported compared to the state-of-the-art algorithms from the recent literature, showing that the proposed algorithm is able to solve a wide variety of real-world instances with different complex structures.
LanguageEnglish
Title of host publicationMista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference
Subtitle of host publicationTheory and Applications
EditorsZdenek Hanzálek, Graham Kendall, Barry McCollum, Premysl Šůcha
Place of PublicationPrague, Czech Republic
Pages429-442
Number of pages14
Publication statusPublished - 25 Aug 2015
Event7th Multidisciplinary International Scheduling Conference: Theory and Applications - Marriot, Prague, Czech Republic
Duration: 25 Aug 201528 Aug 2015
http://www.schedulingconference.org/

Publication series

NameProceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications
PublisherMISTA
ISSN (Electronic)2305-249X

Conference

Conference7th Multidisciplinary International Scheduling Conference
Abbreviated titleMISTA 2015
CountryCzech Republic
CityPrague
Period25/08/1528/08/15
Internet address

Fingerprint

Integer programming
Scheduling
Job satisfaction
Outsourcing
Health
Planning
Costs

Keywords

  • nurse scheduling program
  • shift sequences
  • planning horizon
  • systematic hybrid algorithm
  • integer programming
  • constraint programming

Cite this

Rahimian, E., Akartunali, K., & Levine, J. (2015). A hybrid constraint integer programming approach to solve nurse scheduling problems. In Z. Hanzálek, G. Kendall, B. McCollum, & P. Šůcha (Eds.), Mista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference: Theory and Applications (pp. 429-442). (Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications). Prague, Czech Republic.
Rahimian, Erfan ; Akartunali, Kerem ; Levine, John. / A hybrid constraint integer programming approach to solve nurse scheduling problems. Mista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference: Theory and Applications . editor / Zdenek Hanzálek ; Graham Kendall ; Barry McCollum ; Premysl Šůcha. Prague, Czech Republic, 2015. pp. 429-442 (Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications).
@inproceedings{ffcefd67ff574f72a863a3e82deb433b,
title = "A hybrid constraint integer programming approach to solve nurse scheduling problems",
abstract = "The Nurse Scheduling Problem can be simply defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some constraints and preferences. The inherent benefits of having higher-quality and more flexible schedules are a reduction in outsourcing costs and an increase of job satisfaction in health organizations. In this paper, we present a novel systematic hybrid algorithm, which combines Integer Programming (IP) and Constraint Programming (CP) to efficiently solve highly-constrained Nurse Scheduling Problems. Our focus is to exploit the problem-specific information to improve the performance of the algorithm, and therefore obtain high-quality solutions as well as strong lower bounds. We test our algorithm based on some real-world benchmark instances. Very competitive results are reported compared to the state-of-the-art algorithms from the recent literature, showing that the proposed algorithm is able to solve a wide variety of real-world instances with different complex structures.",
keywords = "nurse scheduling program, shift sequences, planning horizon, systematic hybrid algorithm, integer programming, constraint programming",
author = "Erfan Rahimian and Kerem Akartunali and John Levine",
year = "2015",
month = "8",
day = "25",
language = "English",
isbn = "978-0954582104",
series = "Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications",
publisher = "MISTA",
pages = "429--442",
editor = "Zdenek Hanz{\'a}lek and Graham Kendall and Barry McCollum and Premysl Šůcha",
booktitle = "Mista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference",

}

Rahimian, E, Akartunali, K & Levine, J 2015, A hybrid constraint integer programming approach to solve nurse scheduling problems. in Z Hanzálek, G Kendall, B McCollum & P Šůcha (eds), Mista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference: Theory and Applications . Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications, Prague, Czech Republic, pp. 429-442, 7th Multidisciplinary International Scheduling Conference, Prague, Czech Republic, 25/08/15.

A hybrid constraint integer programming approach to solve nurse scheduling problems. / Rahimian, Erfan; Akartunali, Kerem; Levine, John.

Mista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference: Theory and Applications . ed. / Zdenek Hanzálek; Graham Kendall; Barry McCollum; Premysl Šůcha. Prague, Czech Republic, 2015. p. 429-442 (Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications).

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

T1 - A hybrid constraint integer programming approach to solve nurse scheduling problems

AU - Rahimian, Erfan

AU - Akartunali, Kerem

AU - Levine, John

PY - 2015/8/25

Y1 - 2015/8/25

N2 - The Nurse Scheduling Problem can be simply defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some constraints and preferences. The inherent benefits of having higher-quality and more flexible schedules are a reduction in outsourcing costs and an increase of job satisfaction in health organizations. In this paper, we present a novel systematic hybrid algorithm, which combines Integer Programming (IP) and Constraint Programming (CP) to efficiently solve highly-constrained Nurse Scheduling Problems. Our focus is to exploit the problem-specific information to improve the performance of the algorithm, and therefore obtain high-quality solutions as well as strong lower bounds. We test our algorithm based on some real-world benchmark instances. Very competitive results are reported compared to the state-of-the-art algorithms from the recent literature, showing that the proposed algorithm is able to solve a wide variety of real-world instances with different complex structures.

AB - The Nurse Scheduling Problem can be simply defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some constraints and preferences. The inherent benefits of having higher-quality and more flexible schedules are a reduction in outsourcing costs and an increase of job satisfaction in health organizations. In this paper, we present a novel systematic hybrid algorithm, which combines Integer Programming (IP) and Constraint Programming (CP) to efficiently solve highly-constrained Nurse Scheduling Problems. Our focus is to exploit the problem-specific information to improve the performance of the algorithm, and therefore obtain high-quality solutions as well as strong lower bounds. We test our algorithm based on some real-world benchmark instances. Very competitive results are reported compared to the state-of-the-art algorithms from the recent literature, showing that the proposed algorithm is able to solve a wide variety of real-world instances with different complex structures.

KW - nurse scheduling program

KW - shift sequences

KW - planning horizon

KW - systematic hybrid algorithm

KW - integer programming

KW - constraint programming

UR - http://www.schedulingconference.org/

UR - http://schedulingconference.org/proceedings/2015/mista2015.pdf

M3 - Conference contribution book

SN - 978-0954582104

T3 - Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications

SP - 429

EP - 442

BT - Mista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference

A2 - Hanzálek, Zdenek

A2 - Kendall, Graham

A2 - McCollum, Barry

A2 - Šůcha, Premysl

CY - Prague, Czech Republic

ER -

Rahimian E, Akartunali K, Levine J. A hybrid constraint integer programming approach to solve nurse scheduling problems. In Hanzálek Z, Kendall G, McCollum B, Šůcha P, editors, Mista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference: Theory and Applications . Prague, Czech Republic. 2015. p. 429-442. (Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications).