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

计算机科学 数学优化 调度(生产过程) 算法 数学
作者
Antoine Legrain,Jérémy Omer
出处
期刊:Informs Journal on Computing 卷期号:36 (4): 1108-1128 被引量:2
标识
DOI:10.1287/ijoc.2023.0019
摘要

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. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.0019 .
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
PDF的下载单位、IP信息已删除 (2025-6-4)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
颜云尔发布了新的文献求助10
刚刚
天天快乐应助tay采纳,获得10
1秒前
chen发布了新的文献求助10
2秒前
酷波er应助girl采纳,获得10
2秒前
2秒前
3秒前
猫南北完成签到,获得积分10
3秒前
江恋完成签到,获得积分10
6秒前
GGBOND发布了新的文献求助10
9秒前
11秒前
hhhblabla应助yyyyyyy111采纳,获得10
13秒前
哈哈发布了新的文献求助10
14秒前
19秒前
21秒前
背后初南完成签到,获得积分10
22秒前
神勇馒头完成签到,获得积分10
22秒前
GGBOND发布了新的文献求助10
23秒前
23秒前
24秒前
以戈完成签到,获得积分10
26秒前
28秒前
泡泡脑瓜发布了新的文献求助10
29秒前
358489228完成签到,获得积分10
29秒前
30秒前
xww发布了新的文献求助10
32秒前
33秒前
神勇馒头发布了新的文献求助10
36秒前
36秒前
chen完成签到,获得积分10
38秒前
cindywu发布了新的文献求助10
38秒前
贰叁发布了新的文献求助10
39秒前
40秒前
量子星尘发布了新的文献求助10
41秒前
42秒前
Lu发布了新的文献求助10
44秒前
45秒前
泡泡脑瓜关注了科研通微信公众号
46秒前
丫丫丫完成签到,获得积分20
47秒前
无花果应助GGBOND采纳,获得10
47秒前
跳跃盼波完成签到,获得积分10
49秒前
高分求助中
A new approach to the extrapolation of accelerated life test data 1000
ACSM’s Guidelines for Exercise Testing and Prescription, 12th edition 500
‘Unruly’ Children: Historical Fieldnotes and Learning Morality in a Taiwan Village (New Departures in Anthropology) 400
Indomethacinのヒトにおける経皮吸収 400
Phylogenetic study of the order Polydesmida (Myriapoda: Diplopoda) 370
基于可调谐半导体激光吸收光谱技术泄漏气体检测系统的研究 350
Robot-supported joining of reinforcement textiles with one-sided sewing heads 320
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 遗传学 基因 物理化学 催化作用 冶金 细胞生物学 免疫学
热门帖子
关注 科研通微信公众号,转发送积分 3989115
求助须知:如何正确求助?哪些是违规求助? 3531367
关于积分的说明 11253688
捐赠科研通 3269986
什么是DOI,文献DOI怎么找? 1804868
邀请新用户注册赠送积分活动 882078
科研通“疑难数据库(出版商)”最低求助积分说明 809105