Publication Type

Journal Article

Publication Date

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 Decision Analytics

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

Additional URL

http://dx.doi.org/10.1016/0305-0548(94)00094-o