Combinatorial approaches for hard problems in manpower scheduling

Manpower scheduling is concerned with the construction of a workers’ schedule which meets demands while satisfying given constraints. The paper considers a manpower scheduling problem, called the Change Shift Assignment Problem (CSAP). In previous work, it proved that the CSAP is NP-hard and presented greedy methods to solve some restricted versions. This paper presents combinatorial algorithms to solve more general and realistic versions of CSAP which are unlikely to be solvable by greedy methods. First, the paper models the 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, it shows 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, the paper shows 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.