This paper introduces an effective hybrid approach combining Dynamic Programming (DP) as the primary search framework and Constraint Programming (CP) for global constraint propagation to solve the complex Partial Shop Scheduling Problem (PSSP).
The research explores combining two established combinatorial optimization paradigms, DP and CP, to tackle complex scheduling problems like the Partial Shop Scheduling Problem (PSSP). Unlike traditional approaches that use these methods separately, the proposed method leverages DP for the search strategy and CP as a subroutine to facilitate global constraint propagation. This integration allows the model to naturally handle arbitrary precedence constraints and supports flexible strategies, such as anytime DP approaches. The framework also enables the design of Large Neighborhood Search (LNS) schemes by reusing the DP model, demonstrating the viability of this hybrid integration in optimization.