Publication Type

Journal Article

Version

Publisher’s Version

Publication Date

1996

Abstract

Manpower scheduling is concerned with the construction of a workers' schedule which meets demands while satisfying given constraints. We consider a manpower scheduling Problem, called the Change Shift Assignment Problem(CSAP). In previous work, we proved that CSAP is NP-hard and presented greedy methods to solve some restricted versions. In this paper, we present combinatorial algorithms to solve more general and realistic versions of CSAP which are unlikely solvable by greedy methods. First, we model CSAP as a fixed-charge network and show that a feasible schedule can be obtained by finding disjoint paths in the network, which can be derived from a minimum-cost flow. Next, we show that if the schedule is tableau-shaped, then such disjoint paths can be derived from an optimal path cover, which can be found by a polynomial-time algorithm. Finally, we show that if all constraints are monotonic, then CSAP may be solved by a pseudo-polynomial backtracking algorithm which has a good run-time performance for random CSAP instances.

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Decision Analytics

Publication

Journal of the Operations Research Society of Japan

Volume

39

Issue

1

First Page

88

Last Page

98

ISSN

0453-4514

Publisher

Operations Research Society of Japan

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://ci.nii.ac.jp/naid/110001184438/