期刊
OPERATIONS RESEARCH LETTERS
卷 51, 期 5, 页码 483-487出版社
ELSEVIER
DOI: 10.1016/j.orl.2023.07.004
关键词
Scheduling; Complexity; NP-completeness; Nurse scheduling
This paper investigates the computational complexity of Nurse Rostering problems and shows that a problem with coverage constraints, day off requests, and forbidden sequences of shifts of length 2 is NP-hard in the strong sense, even for a small number of work shifts and a day off shift.
In Nurse Rostering problems the goal is to assign nurses to shifts, subject to a number of constraints. In this paper we consider the computational complexity of such problems. We review the major complexity results obtained so far and show that a problem with coverage constraints, day off requests, and forbidden sequences of shifts of length 2 is NP-hard in the strong sense, even if there are only three work shifts and a day off shift involved. & COPY; 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据