Combining Dynamic and Constraint Programming for Scheduling

A recent study published on arXiv introduces a hybrid methodology that merges Dynamic Programming (DP) with Constraint Programming (CP) to address the Partial Shop Scheduling Problem (PSSP). In this strategy, DP serves as the main search framework, while CP functions as a subroutine for the propagation of global constraints. This combination enables the use of anytime DP techniques, such as anytime column search, which were not feasible with the original DP algorithm. The PSSP represents a broad scheduling challenge, where jobs consist of operations subject to various precedence constraints. This approach is adaptable and utilizes established CP filtering algorithms.