Publication Type
Journal Article
Version
publishedVersion
Publication Date
1-1996
Abstract
We consider the shift assignment problem in manpower scheduling, and show that a restricted version of it is NP-hard by a reduction from 3SAT. We then present polynomial algorithms to solve special cases of the problem and show how they can be deployed to solve more complex versions of the shift assignment problem. Our work formally defines the computational intractibility of manpower shift scheduling and thus justifies existing works in developing manpower scheduling systems using combinatorial and heuristic techniques.
Discipline
Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering
Research Areas
Intelligent Systems and Optimization
Publication
Computers & Operations Research
Volume
23
Issue
1
First Page
93
Last Page
102
ISSN
0305-0548
Identifier
10.1016/0305-0548(94)00094-O
Publisher
Elsevier
Citation
LAU, Hoong Chuin.
On the Complexity of Manpower Shift Scheduling. (1996). Computers & Operations Research. 23, (1), 93-102.
Available at: https://ink.library.smu.edu.sg/sis_research/37
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1016/0305-0548(94)00094-O
Included in
Numerical Analysis and Scientific Computing Commons, Operations Research, Systems Engineering and Industrial Engineering Commons