A Dedicated Pricing Algorithm to Solve a Large Family of Nurse Scheduling Problems with Branch-and-Price

Antoine Legrain () and Jérémy Omer ()
Additional contact information
Antoine Legrain: Polytechnique Montreal, Montreal, Quebec H3T 1J4, Canada; CIRRELT, Montreal, Quebec H3T 1J4, Canada; GERAD, Montreal, Quebec H3T 1J4, Canada
Jérémy Omer: University Rennes, INSA Rennes, CNRS, IRMAR, UMR 6625, Rennes 35000, France

INFORMS Journal on Computing, 2024, vol. 36, issue 4, 1108-1128

Abstract: In this paper, we describe a branch-and-price algorithm for the personalized nurse scheduling problem. The variants that appear in the literature involve a large number of constraints that can be hard or soft, meaning that they can be violated at the price of a penalty. We capture the diversity of the constraints on individual schedules by seven generic constraints characterized by lower and upper bounds on a given quantity. The core of the column generation procedure is in the identification of individual schedules with minimum reduced cost. For this, we solve a shortest path problem with resource constraints (SPPRC) where several generic constraints are modeled as resource constraints. We then describe dominance rules adapted to the presence of both upper and lower bounds on the resources and leverage soft constraints to improve the dominance. We also describe several acceleration techniques for the solution of the SPPRC, and branching rules that fit the specificities of the problem. Our numerical experiments are based on the instances of three benchmarks of the literature including those of the two international nurse rostering competitions (INRC-I and INRC-II). Their objective is threefold: assess the dominance rules and the acceleration techniques, investigate the capacity of the algorithm to find provable optimal solutions of instances that are still open, and conduct a comparison with best published results. The most noticeable conclusion is that the improved solution of the SPPRC allows to solve optimally all the INRC-II instances where a four-week planning horizon is considered and 40% of the eight-week instances.

Keywords: nurse scheduling; column generation; decomposition; branch-and-price; dynamic programming; soft constraints (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0019 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:4:p:1108-1128

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().