A hybrid integer and constraint programming approach to solve nurse rostering problems

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

The Nurse Rostering Problem can be defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some limitations and preferences. The inherent benefits of generating higher-quality schedules are a reduction in outsourcing costs and an increase in job satisfaction of employees. In this paper, we present a hybrid algorithm, which combines Integer Programming and Constraint Programming to efficiently solve the highly-constrained Nurse Rostering Problem. We exploit the strength of IP in obtaining lower-bounds and finding an optimal solution with the capability of CP in finding feasible solutions in a co-operative manner. To improve the performance of the algorithm, and therefore, to obtain high-quality solutions as well as strong lower-bounds for a relatively short time, we apply some innovative ways to extract useful information such as the computational difficulty of in- stances and constraints to adaptively set the search parameters. We test our algorithm using two different datasets consisting of various problem instances, and report competitive results benchmarked with the state-of-the-art algorithms from the recent literature as well as standard IP and CP solvers, showing that the proposed algorithm is able to solve a wide variety of instances effectively.
LanguageEnglish
Pages83-94
Number of pages12
JournalComputers & Operations Research
Volume82
Early online date27 Jan 2017
DOIs
Publication statusE-pub ahead of print - 27 Jan 2017

Fingerprint

Constraint Programming
Integer Programming
Nurses
Schedule
Job Satisfaction
Lower bound
Appointments and Schedules
Outsourcing
Outsourced Services
Job satisfaction
Hybrid Algorithm
Integer programming
Horizon
Optimal Solution
Planning
Series
Constraint programming
Personnel
Costs
Costs and Cost Analysis

Keywords

  • timetabling
  • nurse rostering
  • hybrid algorithm
  • integer programming
  • constraint programming

Cite this

@article{820c903fe2454b79bad88365ea5c097c,
title = "A hybrid integer and constraint programming approach to solve nurse rostering problems",
abstract = "The Nurse Rostering Problem can be defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some limitations and preferences. The inherent benefits of generating higher-quality schedules are a reduction in outsourcing costs and an increase in job satisfaction of employees. In this paper, we present a hybrid algorithm, which combines Integer Programming and Constraint Programming to efficiently solve the highly-constrained Nurse Rostering Problem. We exploit the strength of IP in obtaining lower-bounds and finding an optimal solution with the capability of CP in finding feasible solutions in a co-operative manner. To improve the performance of the algorithm, and therefore, to obtain high-quality solutions as well as strong lower-bounds for a relatively short time, we apply some innovative ways to extract useful information such as the computational difficulty of in- stances and constraints to adaptively set the search parameters. We test our algorithm using two different datasets consisting of various problem instances, and report competitive results benchmarked with the state-of-the-art algorithms from the recent literature as well as standard IP and CP solvers, showing that the proposed algorithm is able to solve a wide variety of instances effectively.",
keywords = "timetabling, nurse rostering, hybrid algorithm, integer programming, constraint programming",
author = "Erfan Rahimian and Kerem Akartunali and John Levine",
year = "2017",
month = "1",
day = "27",
doi = "10.1016/j.cor.2017.01.016",
language = "English",
volume = "82",
pages = "83--94",
journal = "Computers & Operations Research",
issn = "0305-0548",

}

TY - JOUR

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

AU - Rahimian, Erfan

AU - Akartunali, Kerem

AU - Levine, John

PY - 2017/1/27

Y1 - 2017/1/27

N2 - The Nurse Rostering Problem can be defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some limitations and preferences. The inherent benefits of generating higher-quality schedules are a reduction in outsourcing costs and an increase in job satisfaction of employees. In this paper, we present a hybrid algorithm, which combines Integer Programming and Constraint Programming to efficiently solve the highly-constrained Nurse Rostering Problem. We exploit the strength of IP in obtaining lower-bounds and finding an optimal solution with the capability of CP in finding feasible solutions in a co-operative manner. To improve the performance of the algorithm, and therefore, to obtain high-quality solutions as well as strong lower-bounds for a relatively short time, we apply some innovative ways to extract useful information such as the computational difficulty of in- stances and constraints to adaptively set the search parameters. We test our algorithm using two different datasets consisting of various problem instances, and report competitive results benchmarked with the state-of-the-art algorithms from the recent literature as well as standard IP and CP solvers, showing that the proposed algorithm is able to solve a wide variety of instances effectively.

AB - The Nurse Rostering Problem can be defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some limitations and preferences. The inherent benefits of generating higher-quality schedules are a reduction in outsourcing costs and an increase in job satisfaction of employees. In this paper, we present a hybrid algorithm, which combines Integer Programming and Constraint Programming to efficiently solve the highly-constrained Nurse Rostering Problem. We exploit the strength of IP in obtaining lower-bounds and finding an optimal solution with the capability of CP in finding feasible solutions in a co-operative manner. To improve the performance of the algorithm, and therefore, to obtain high-quality solutions as well as strong lower-bounds for a relatively short time, we apply some innovative ways to extract useful information such as the computational difficulty of in- stances and constraints to adaptively set the search parameters. We test our algorithm using two different datasets consisting of various problem instances, and report competitive results benchmarked with the state-of-the-art algorithms from the recent literature as well as standard IP and CP solvers, showing that the proposed algorithm is able to solve a wide variety of instances effectively.

KW - timetabling

KW - nurse rostering

KW - hybrid algorithm

KW - integer programming

KW - constraint programming

U2 - 10.1016/j.cor.2017.01.016

DO - 10.1016/j.cor.2017.01.016

M3 - Article

VL - 82

SP - 83

EP - 94

JO - Computers & Operations Research

T2 - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

ER -