CP or DP? Why Not Both: A Case Study in the Partial... | AI Research

CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem
This paper explores a hybrid approach to solving the Partial Shop Scheduling Problem (PSSP), a complex task where operations must be scheduled on machines subject to specific precedence constraints. Traditionally, Dynamic Programming (DP) and Constraint Programming (CP) are used as separate tools for such optimization problems. This research demonstrates that these two paradigms can be combined effectively, using DP as the primary search framework while utilizing CP as a subroutine to improve the efficiency of the search process.

Combining DP and CP

The core of the proposed method is to integrate CP’s powerful global constraint propagation into the DP search process. In this hybrid model, the DP framework manages the overall search, while the CP solver acts as a subroutine. At each step of the DP search, the current state and scheduling decisions are passed to the CP model. The CP solver then uses its "NoOverlap" global constraint to perform advanced filtering, such as edge-finding and precedence analysis. This process tightens the execution intervals for tasks and strengthens the lower bounds for the makespan, which significantly reduces the number of transitions the DP algorithm needs to explore.

Improving Search Flexibility

The original DP approach for this problem relied on a strict, layer-wise exploration of the search space, which often resulted in poor performance until the very end of the process. To address this, the authors replaced the layer-based search with an Anytime Column Search (ACS). This strategy allows the algorithm to prioritize the most promising paths and maintain a fixed number of nodes at each layer, similar to a beam search. This shift improves the "anytime" performance, meaning the algorithm can find high-quality solutions more quickly and continue to refine them over time.

Large Neighborhood Search

The flexibility of the hybrid model also enables the design of a Large Neighborhood Search (LNS) scheme. By reusing the DP model and imposing partial-order schedules across different restarts, the algorithm can effectively improve upon an existing incumbent solution. This allows the system to explore different areas of the search space by relaxing a subset of the precedence constraints, providing a robust way to find better schedules.

Performance and Scope

The authors note that while their hybrid approach is not currently faster than state-of-the-art pure CP solvers for this specific problem, it successfully proves that the integration of DP and CP is a viable and elegant strategy. The framework is flexible enough to handle any precedence graph, making it a versatile tool for general scheduling challenges. The research highlights that the true value of this hybridization lies in its ability to leverage the strengths of CP’s global constraints within a DP search structure, offering a new way to tackle complex combinatorial optimization problems.