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.
Introduction
In large organizations such as hospitals or airports, manpower scheduling is a critical operational challenge. It involves not only meeting labor demands but also respecting the "biological clock" of workers. For instance, a worker should not be assigned an evening shift followed immediately by a morning shift. This paper addresses the Change Shift Assignment Problem (CSAP), which focuses on the sequence of shifts assigned to workers over a planning period. While previous research established that even restricted versions of CSAP are NP-hard, this work provides practical combinatorial solutions for complex, realistic scenarios where simple greedy heuristics fail.
Problem Definition and Constraints
The objective of CSAP is to assign shifts to workers such that demand is met for every shift on every day, and all shift change constraints are respected. These constraints ensure that transitions between shifts allow for sufficient rest.
To accommodate "slack"—instances where available worker capacity exceeds minimum demand—the model incorporates a wildcard shift (*-shift). This allows extra capacity to be treated as a flexible resource that can be assigned without violating shift-change constraints.
Proposed Combinatorial Methods
We propose three distinct strategies based on the mathematical structure of the constraints:
1. Fixed-Charge Network Flow
CSAP is modeled as a fixed-charge network where workstretches (sequences of working days) are represented as nodes and permissible shift changes as edges. Finding a feasible schedule is shown to be equivalent to finding a set of disjoint paths in this network, which can be derived from a minimum-cost flow.
2. Optimal Path Cover for Tableau-Shaped Schedules (T-CSAP)
For schedules that are "tableau-shaped"—where workstretches are non-cyclic and can be ordered by length—the problem simplifies. We demonstrate that this specific case can be solved in polynomial time ($O(n^{2.5})$) by finding an optimal path cover in a directed acyclic graph (DAG).
3. Backtracking with Dominance Pruning (M-CSAP)
When shift changes are "monotonic" (workers transition to shifts starting at the same time or later the next day), we propose a depth-first backtracking algorithm. To prevent combinatorial explosion, we introduce dominance criteria to prune the search space. A workstretch "dominates" another if its "tail" is longer and its "head" is shorter, allowing the algorithm to skip redundant scheduling paths.
Experimental Evaluation
The backtracking algorithm was tested on 1,000 randomly generated instances of Monotonic CSAP (M-CSAP), varying the number of shifts, workstretches, and the slack ratio ($\epsilon$).
The results indicate that the algorithm's computational effort peaks when the slack ratio is between 0.1 and 0.2. In very tight or very loose scenarios, the pruning criteria are highly effective, leading to rapid solutions. Furthermore, the average number of nodes expanded in the search tree grows linearly or quadratically with problem size, suggesting the method is viable for medium-to-large organizational needs.
Conclusion
This paper presents robust combinatorial approaches for the NP-hard Change Shift Assignment Problem. By leveraging network flow models, path covers, and efficient backtracking with pruning, we provide solutions for realistic scheduling scenarios. Future research will explore whether a true polynomial-time algorithm exists for M-CSAP with slack demands and extend these methods to optimize for worker preferences.
Summary updated