On the complexity of manpower shift scheduling

The paper considers the shift assignment problem in manpower scheduling, and show that a restricted version of it is NP-hard. It then presents polynomial algorithms to solve special cases of the problem and shows how they can be deployed to solve more complex versions of the shift assignment problem. The present 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.