On the complexity of Nurse Rostering problems

被引：3

作者：

den Hartog, Steven J. M.

Hoogeveen, Han ^{[1
]}

van der Zanden, Tom C. ^{[2
,3
]}

机构：

[1] Univ Utrecht, Dept Informat & Comp Sci, Utrecht, Netherlands

[2] Maastricht Univ, Dept Data Analyt & Digitalisat, Maastricht, Netherlands

[3] Dept Data Analyt & Digitalisat, Tongersestr 53, NL-6211 LM Maastricht, Netherlands

来源：

OPERATIONS RESEARCH LETTERS | 2023年 / 51卷 / 05期

关键词：

Scheduling; Complexity; NP-completeness; Nurse scheduling;

D O I：

10.1016/j.orl.2023.07.004

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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/).

引用

页码：483 / 487

页数：5

共 19 条

[1] Personnel scheduling: Models and complexity [J].