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.
Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
Computers & Operations Research
LAU, Hoong Chuin.
On the Complexity of Manpower Shift Scheduling. (1996). Computers & Operations Research. 23, (1), 93-102. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/37