CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem

# CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem.
Source: [https://arxiv.org/html/2605.23569](https://arxiv.org/html/2605.23569)
ICTEAM, UCLouvain, Belgiumemma\.legrand@uclouvain\.behttps://orcid\.org/0009\-0000\-3836\-1782 ICTEAM, UCLouvain, Belgiumroger\.kameugne@uclouvain\.behttps://orcid\.org/0000\-0003\-1809\-9822 ICTEAM, UCLouvain, Belgiumpierre\.schaus@uclouvain\.behttps://orcid\.org/0000\-0002\-3153\-8941\\CopyrightEmma Legrand, Roger Kameugne, and Pierre Schaus\\ccsdesc\[100\]Mathematics of computing Combinatorial optimization\\supplementdetails\[subcategory=Source Code, swhid=…\]Softwarehttps://anonymous\.4open\.science/r/DP\-CP\_JobShop\-8C5E\\EventEditorsJohn Q\. Open and Joan R\. Access\\EventNoEds2\\EventLongTitle42nd Conference on Very Important Topics \(CVIT 2016\)\\EventShortTitleCVIT 2016\\EventAcronymCVIT\\EventYear2016\\EventDateDecember 24–27, 2016\\EventLocationLittle Whinging, United Kingdom\\EventLogo\\SeriesVolume42\\ArticleNo23

###### Abstract

Dynamic Programming \(DP\) and Constraint Programming \(CP\) are well\-established paradigms for solving combinatorial optimization problems\. Usually, these two approaches are used separately\. This paper aims to show that the two can be combined effectively and elegantly, with DP serving as the primary search framework and CP used as a subroutine to leverage global constraint propagation\. This paper presents such an approach for the Partial Shop Scheduling Problem \(PSSP\), for which a pure DP method has previously been proposed, and efficient CP filtering algorithms are available\. The PSSP is a general scheduling problem where each job consists of a set of operations with arbitrary precedence constraints\. The approach is flexible enough to accommodate anytime DP strategies, such as anytime column search, whereas the original DP algorithm operated in a strictly layer\-wise manner\. Moreover, the flexibility of the CP modeling makes it straightforward to incorporate arbitrary precedence constraints\. As a result, the model naturally handles any precedence graph and even enables the design of a Large Neighborhood Search \(LNS\) scheme, in which the DP model is reused, and partial\-order schedules are imposed across restarts to improve the incumbent solution\. While not competitive with state\-of\-the\-art pure CP solvers for this specific problem, our primary contribution is demonstrating the viability of this hybrid integration\.

###### keywords:

Partial Shop Scheduling Problem, dynamic programming, decision diagram, constraint programming, Large Neighborhood Search

###### category:

\\relatedversion

## 1Introduction

This work considers solving the*Partial Shop Scheduling Problem*\(PSSP\) using dynamic programming \(DP\), constraint programming \(CP\), and a hybrid DP\-CP approach\. The PSSP is a general scheduling problem where each job consists of a set of operations with arbitrary precedence constraints\. In\[HookerH18\], the authors review the integration of CP and operations research \(OR\) to solve combinatorial optimization problems\. The PSSP generalizes classical scheduling problems such as the job\-shop scheduling problem \(JSP\) and the open\-shop scheduling problem \(OSP\), which are well\-studied combinatorial optimization problems across operations research, artificial intelligence, and management science\[XiongSRH22,DauzerePeresDST24,pinedo2016scheduling,blazewicz2001scheduling,zhang2019review\]\. Their enduring relevance stems from the fact that they serve as relaxations or generalizations for numerous scheduling challenges found in a wide range of real\-world industrial settings\. In these problems, a set of operations must be scheduled on distinct machines, subject to given precedence constraints\. The common objective is to minimize the makespan, defined as the maximum completion time of all operations\.

These scheduling problems are typically strongly NP\-hard\[GareyJS76,GonzalezS76\]and have been well investigated in the literature\[XiongSRH22,DauzerePeresDST24,GromichoHST12,HoornNOG17,Ozolins19,Ozolins20,Ozolins21,zhang2019review\]\. Despite extensive research into exact methods for these problems, DP approaches remain relatively rare\.

For the JSP, Gromicho et al\.\[GromichoHST12\]introduced a DP formulation that views a solution as a sequence of operations, applying specific techniques to maintain optimality guarantees\. By leveraging dominance properties to prune the search space, this algorithm successfully solves moderate\-sized instances\. Hoorn et al\.\[HoornNOG17\]later refined this approach, proving its capability to find optimal solutions for particularly hard instances from established benchmarks\[vanHoorn\]\. Building on this DP formulation, Ozolins\[Ozolins20\]proposed an improved bounded variant, combining DP with branch\-and\-bound, experimented on medium\-sized instances\.

Pure CP approach combines the well\-knownNoOverlapglobal constraint\[vilim2007global\]with specific search strategies\[baptiste2001constraint,LaborieRSV18\]\. To achieve maximal domain filtering at each node of the search tree, this global constraint integrates several propagation techniques:*overload checking*,*edge\-finding*\(also referred to as*heads and tails adjustment*\[carlier1994adjustment\]or immediate selection\[brucker1994job\]\),*detectable precedences*, and*not\-first/not\-last*rules\. CP solvers can be employed to iteratively improve rapidly the current solution by relaxing a fraction of the assignments within a Large Neighborhood Search \(LNS\) framework and then prove optimality with a*failure directed search*\[vilim2015failure\]\.

In this paper, we demonstrate how a CP model can be elegantly integrated as a subroutine within a DP approach to leverage the powerful global constraint propagation implemented in existing CP solvers\. To achieve this, the current DP state, the upper bound on the makespan, and the current decision are imposed as constraints within the CP model\. Computing the fixpoint of this propagation results in tighter execution intervals for the tasks and a strengthened lower bound for the makespan ultimately reducing the number of transitions in the DP approach\. Furthermore, CP can be used as a proxy model to further tighten the lower bound using a dichotomic search based on feasibility checks in each state\.

This hybrid DP\-CP framework naturally models the PSSP and facilitates a Large Neighborhood Search \(LNS\) scheme by relaxing a subset of precedences\. Empirical evaluations on standard benchmarks confirm the viability of this hybridization, demonstrating that our approach effectively exploits CP global constraints and is competitive with standard pure CP approaches in minimizing the number of explored nodes\. Our contributions are summarized as follows:

- •To improve anytime performance, we replace the layer\-based DP search proposed in\[GromichoHST12\]with an*Anytime Column Search*\(ACS\)\[vadlamudi2012anytime\]\.
- •We propose a hybridization of DP and CP models where the power of the global constraintNoOverlapplays a central role\.
- •The new framework natively handles the PSSP and demonstrates its ability to improve solutions in a large neighborhood search\.
- •Empirical evaluations are conducted on well\-known suites of benchmarks\.

The rest of the paper is organized as follows\.[Section˜2](https://arxiv.org/html/2605.23569#S2)reviews the related work\.[Section˜3](https://arxiv.org/html/2605.23569#S3)presents the preliminary concepts used throughout this work\.[Section˜4](https://arxiv.org/html/2605.23569#S4)describes the state\-of\-the\-art DP model while[Section˜5](https://arxiv.org/html/2605.23569#S5)presents our adaptation of the anytime column search for the layer\-based DP\.[Section˜6](https://arxiv.org/html/2605.23569#S6)details the proposed DP\-CP hybrid framework for the PSSP\. The Large Neighborhood Search \(LNS\) is described in[Section˜7](https://arxiv.org/html/2605.23569#S7)\.[Section˜8](https://arxiv.org/html/2605.23569#S8)provides a comprehensive empirical evaluation of the proposed approach\. Finally,[Section˜9](https://arxiv.org/html/2605.23569#S9)concludes the paper\.

## 2Related Work

A closely related work by Marijnissen et al\.\[marijnissen2026domain\]developped in parallel and independently to this one also proposes a generic framework for integrating CP propagation into Domain\-Independent Dynamic Programming \(DIDP\)\[kuroiwa2023domain\]\. Their work evaluates the synergy between DP and CP on problems such as single\-machine scheduling with time windows, RCPSP, and TSPTW, primarily using A\* and Complete Anytime Beam Search \(CABS\)\. The DIDP framework of\[marijnissen2026domain\]aims for domain\-independence and generality across problem classes\. It treats CP as a black box for feasibility checks and dual bound computations but does not leverate the filtering power of CP of the domains\. Our integration is more problem\-specific and deliberately tailored to the structure of the Partial Shop Scheduling Problem \(PSSP\)\. We exploit CP propagation in a more deeply coupled way: theNoOverlapglobal constraint fixpoint is used to*discover new precedence constraints*at each DP transition, and these precedences are explicitly incorporated into the DP state itself\. A more minor difference is that we employ Anytime Column Search \(ACS\) as our primary search strategy, whereas\[marijnissen2026domain\]focuses on A\* and CABS\.

## 3The Partial Shop Scheduling Problem \(PSSP\)

We consider the*Partial Shop Scheduling Problem*\(PSSP\) defined by a finite set of operationsO=\{o1,…,oN\}O=\\\{o\_\{1\},\\dots,o\_\{N\}\\\}to be executed on a finite set of machinesM=\{M1,…,Mm\}M=\\\{M\_\{1\},\\dots,M\_\{m\}\\\}with\|M\|=m\|M\|=m\. This set of operations is partitioned inton=N/mn=N/msubsets, such that each machine is assigned to exactly one operation in each partition\.

Each operationo∈Oo\\in Ohas a specified processing timepo\>0p\_\{o\}\>0, requires a specific machinem​\(o\)∈Mm\(o\)\\in Mfor its exclusive use without preemption, and is associated with a specific partitionj​\(o\)j\(o\)\. Furthermore, the operations are subject to a set of precedence constraints represented by a directed acyclic graph \(DAG\)G=\(O,E\)G=\(O,E\)\. An edge\(o,o′\)∈E\(o,o^\{\\prime\}\)\\in Eindicates that operationoomust be completed before operationo′o^\{\\prime\}can start, denotedo⋖o′o\\lessdot o^\{\\prime\}\. The set of successors of an operationoois denoted by𝑠𝑢𝑐𝑐𝑠​\(o\)\\mathit\{succs\}\(o\)and its predecessors by𝑝𝑟𝑒𝑑𝑠​\(o\)\\mathit\{preds\}\(o\)\.

A solution to this problem is an assignment of start timesψo\\psi\_\{o\}to each operationo∈Oo\\in Osuch that all precedence constraints \(ψo′≥ψo\+po\\psi\_\{o^\{\\prime\}\}\\geq\\psi\_\{o\}\+p\_\{o\}for all\(o,o′\)∈E\(o,o^\{\\prime\}\)\\in E\) and machine and partition disjunctive constraints \(no two operations on the same machine/partition overlap in time\) are satisfied\. The objective is to minimize the makespanCmax=maxo∈O⁡\(ψo\+po\)C\_\{\\max\}=\\max\_\{o\\in O\}\(\\psi\_\{o\}\+p\_\{o\}\)\.

This general PSSP formulation encompasses classical problems such as the Job\-Shop Scheduling Problem \(JSP\) and the Open\-Shop Scheduling Problem \(OSP\)\. In the classical JSP, the set of operations is partitioned into disjoint subsets called jobs, and the precedence graphEEconsists of a set of disjoint directed paths, one for each job\. In the OSP, there are no initial precedence constraints among operations \(E=∅E=\\emptyset\), but operations belonging to the same job cannot overlap in time, requiring additional disjunctive constraints\.

For the JSP instance of three jobs and three machines shown in[Table˜2](https://arxiv.org/html/2605.23569#S3.T2), the precedencesEEis equal to\{\(o1,o2\),\(o2,o3\),\(o4,o5\),\(o5,o6\),\(o7,o8\),\(o8,o9\)\}\.\\left\\\{\(o\_\{1\},o\_\{2\}\),\(o\_\{2\},o\_\{3\}\),\(o\_\{4\},o\_\{5\}\),\(o\_\{5\},o\_\{6\}\),\(o\_\{7\},o\_\{8\}\),\(o\_\{8\},o\_\{9\}\)\\right\\\}\.The job 1 is defined by\{o1,o2,o3\}\\\{o\_\{1\},o\_\{2\},o\_\{3\}\\\}, the job 2 is\{o4,o5,o6\}\\\{o\_\{4\},o\_\{5\},o\_\{6\}\\\}and the job 3 is\{o7,o8,o9\}\\\{o\_\{7\},o\_\{8\},o\_\{9\}\\\}\.[Table˜2](https://arxiv.org/html/2605.23569#S3.T2)gives a solution for the JSP instance of[Table˜2](https://arxiv.org/html/2605.23569#S3.T2)\.

Table 1:Example of a JSP instance with 3 jobs and 3 machines\.
01234567891011M1M2M3o4o\_\{4\}o1o\_\{1\}o9o\_\{9\}o7o\_\{7\}o2o\_\{2\}o6o\_\{6\}o5o\_\{5\}o8o\_\{8\}o3o\_\{3\}Job 1Job 2Job 3Table 2:Solution for the instance of Table[2](https://arxiv.org/html/2605.23569#S3.T2)

## 4Dynamic Programming Approach

A DP formulation for the JSP was originally proposed by Gromicho et al\.\[GromichoHST12\], subsequently refined by Hoorn et al\.\[HoornNOG17\], and reused by Ozolins\[Ozolins20\]\. In this approach, operations are scheduled by fixing their start times\. An operation becomes eligible for scheduling only when all of its predecessors in the precedence graph have already been scheduled\. This operation is then scheduled at its earliest possible start time, ensuring no temporal overlap on its required machine\. A node in the search space represents a DP state, defined by the earliest possible start times of the remaining unscheduled operations\. Because different sequences of scheduling decisions can lead to the exact same state, the search space forms a graph rather than a simple tree\. The transition cost between two nodes corresponds to the incremental increase in the makespan of the partial solution\. Hoorn et al\.\[HoornNOG17\]explore this state graph layer by layer, where the shortest path through the graph yields the schedule with the optimal makespan\. Formally the DP state is a tripletS=⟨ψ,Λ,𝑑𝑜𝑛𝑒⟩S=\\langle\\psi,\\Lambda,\\mathit\{done\}\\rangle, where:

- •ψ\\psitracks the earliest possible start time for every operation\.
- •Λ\\Lambdarecords the machine ID of the last scheduled operation\.
- •𝑑𝑜𝑛𝑒\\mathit\{done\}represents the set of operations that have already been scheduled\.

The stateSSdefines a partial sequence,TST\_\{S\}, with a current makespan denoted byCmax​\(S\)C\_\{\\max\}\(S\)\. Based on our eligibility rules, the set of currently available operations is mathematically specified as:ε​\(S\)=\{o∈O∖𝑑𝑜𝑛𝑒​\(S\)∣𝑝𝑟𝑒𝑑𝑠​\(o\)⊆𝑑𝑜𝑛𝑒​\(S\)\}\\varepsilon\(S\)=\\\{o\\in O\\setminus\\mathit\{done\}\(S\)\\mid\\mathit\{preds\}\(o\)\\subseteq\\mathit\{done\}\(S\)\\\}

To mitigate the exponential size of the search space, the authors introduced dominance rules\. These rules allow the algorithm to safely discard dominated transitions and nodes while mathematically guaranteeing that at least one path to the optimal solution is preserved\.

### 4\.1Transition Dominance

Given a complete solution and a start\-time assignment, this solution can be obtained by successively selecting an operation fromε​\(S\)\\varepsilon\(S\)and scheduling it as early as possible without violating machine constraints, continuing until all tasks are scheduled\. Because multiple tasks may be eligible at a given stage, different task selection sequences can yield the same solution\. To prevent this redundancy, a*transition dominance*rule is applied, ensuring that any specific solution is generated by only a single sequence of tasks\. Formally, we defineη​\(S\)\\eta\(S\)as the subset of available operations that are legally permitted to expandTST\_\{S\}\. An operation only qualifies forη​\(S\)\\eta\(S\)if it strictly extends the makespan or resolves ties usingΛ\\Lambda:

###### Definition 4\.1\.

An operationo∈ε​\(S\)o\\in\\varepsilon\(S\)belongs toη​\(S\)\\eta\(S\)if it satisfies one of the following conditions:

- •ψo\+po\>Cmax​\(S\)\\psi\_\{o\}\+p\_\{o\}\>C\_\{\\max\}\(S\)
- •ψo\+po=Cmax​\(S\)∧m​\(o\)\>Λ​\(S\)\\psi\_\{o\}\+p\_\{o\}=C\_\{\\max\}\(S\)\\land m\(o\)\>\\Lambda\(S\)

###### Example 4\.2\.

[Figure˜2](https://arxiv.org/html/2605.23569#S4.F2)and[Figure˜2](https://arxiv.org/html/2605.23569#S4.F2)illustrate the two cases of[Definition˜4\.1](https://arxiv.org/html/2605.23569#S4.Thmtheorem1)on a stateSS\. The darker color is used for scheduled operations, while the hatched light color is for unscheduled ones\. In both cases, the ID of the last machine is 2\.

In[Figure˜2](https://arxiv.org/html/2605.23569#S4.F2), the set of available operations isε​\(S\)=\{o1,o5,o8\}\\varepsilon\(S\)=\\\{o\_\{1\},\\,o\_\{5\},\\,o\_\{8\}\\\}\. Operationso1o\_\{1\}ando8o\_\{8\}satisfy the first condition\. Operationo5o\_\{5\}does not satisfy any conditions becauseψo5\+po5=2\+1=3<Cmax​\(S\)=4\\psi\_\{o\_\{5\}\}\+p\_\{o\_\{5\}\}=2\+1=3<C\_\{\\max\}\(S\)=4\. Therefore it is excluded fromη​\(S\)\\eta\(S\)and we obtainη​\(S\)=\{o1,o8\}\\eta\(S\)=\\\{o\_\{1\},\\,o\_\{8\}\\\}\.

In[Figure˜2](https://arxiv.org/html/2605.23569#S4.F2), assuming another set of operations, the available operations areε​\(S\)=\{o3,o6,o8\}\\varepsilon\(S\)=\\\{o\_\{3\},\\,o\_\{6\},\\,o\_\{8\}\\\}\. Operationso3o\_\{3\}ando6o\_\{6\}satisfy the first condition\. Operationo8o\_\{8\}satisfies the second condition of[Definition˜4\.1](https://arxiv.org/html/2605.23569#S4.Thmtheorem1)sincem​\(o8\)=3\>Λ​\(S\)=2m\(o\_\{8\}\)=3\>\\Lambda\(S\)=2\. Consequently, all available operations satisfy the dominance rule andη​\(S\)=ε​\(S\)=\{o3,o6,o8\}\\eta\(S\)=\\varepsilon\(S\)=\\\{o\_\{3\},\\,o\_\{6\},\\,o\_\{8\}\\\}\.

The*transition function*, denoted𝑇𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛\\mathit\{Transition\}, is defined by the operations in the setη​\(S\)\\eta\(S\)\. Given a stateSSand an operationo∈η​\(S\)o\\in\\eta\(S\), the transition function returns a new stateS′=⟨ψ′,Λ′,𝑑𝑜𝑛𝑒′⟩S^\{\\prime\}=\\langle\\psi^\{\\prime\},\\Lambda^\{\\prime\},\\mathit\{done\}^\{\\prime\}\\rangle\. First, the set of scheduled operations is updated:𝑑𝑜𝑛𝑒′=𝑑𝑜𝑛𝑒​\(S\)∪\{o\}\\mathit\{done\}^\{\\prime\}=\\mathit\{done\}\(S\)\\cup\\\{o\\\}\. Second, the earliest starting timesψ\\psiare updated toψ′\\psi^\{\\prime\}using the𝑈𝑝𝑑𝑎𝑡𝑒𝐸𝑠𝑡\\mathit\{UpdateEst\}function\. This function performs the following updates:

1. 1\.It updates the earliest start time of all unscheduled operations on the same machine asoo: ψo′′=max⁡\(ψo′,ψo\+po\)∀o′∉𝑑𝑜𝑛𝑒′∣m​\(o′\)=m​\(o\)\\psi^\{\\prime\}\_\{o^\{\\prime\}\}=\\max\(\\psi\_\{o^\{\\prime\}\},\\psi\_\{o\}\+p\_\{o\}\)\\quad\\forall o^\{\\prime\}\\notin\\mathit\{done\}^\{\\prime\}\\mid m\(o^\{\\prime\}\)=m\(o\)\(1\)
2. 2\.For each operationo′o^\{\\prime\}whoseψo′′\\psi^\{\\prime\}\_\{o^\{\\prime\}\}has been increased, it recursively updates its successors in the precedence graphGG: ψo′′′=max⁡\(ψo′′,ψo′′\+po′\)∀o′′∈𝑠𝑢𝑐𝑐𝑠​\(o′\)\\psi^\{\\prime\}\_\{o^\{\\prime\\prime\}\}=\\max\(\\psi\_\{o^\{\\prime\\prime\}\},\\psi^\{\\prime\}\_\{o^\{\\prime\}\}\+p\_\{o^\{\\prime\}\}\)\\quad\\forall o^\{\\prime\\prime\}\\in\\mathit\{succs\}\(o^\{\\prime\}\)\(2\)

Third, the ID of the last machine is updated:Λ′=m​\(o\)\\Lambda^\{\\prime\}=m\(o\)\. The transition function thus returns the new stateS′=𝑇𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛​\(S,o\)=\(ψ′,Λ′,𝑑𝑜𝑛𝑒′\)S^\{\\prime\}=\\mathit\{Transition\}\(S,o\)=\(\\psi^\{\\prime\},\\Lambda^\{\\prime\},\\mathit\{done\}^\{\\prime\}\)\. From a stateSSand an operationo∈η​\(S\)o\\in\\eta\(S\), the*transition cost function*denotedhh, associated with the transition is the makespan of the new state minus the makespan of the current state, i\.e\.,h​\(S,o\)=Cmax​\(S′\)−Cmax​\(S\)h\(S,o\)=C\_\{\\max\}\(S^\{\\prime\}\)\-C\_\{\\max\}\(S\)\. The*domain function*of a stateSS, denotedd​\(S\)d\(S\), is the set of all operations that can directly extend the schedule\. The size of this set represents the branching factor of our search tree\. In the DP formulation of the JSP in\[GromichoHST12,HoornNOG17\], it is setd​\(S\)=η​\(S\)d\(S\)=\\eta\(S\)for all statesSS\.

01234567891011M1M2M3o4o\_\{4\}o1o\_\{1\}o7o\_\{7\}o5o\_\{5\}o8o\_\{8\}Job 1Job 2Job 3Figure 1:Illustration ofε​\(S\)\\varepsilon\(S\)andη​\(S\)\\eta\(S\)01234567891011M1M2M3o4o\_\{4\}o1o\_\{1\}o7o\_\{7\}o2o\_\{2\}o6o\_\{6\}o5o\_\{5\}o8o\_\{8\}o3o\_\{3\}Job 1Job 2Job 3Figure 2:Illustration ofε​\(S\)\\varepsilon\(S\)andη​\(S\)\\eta\(S\)

### 4\.2State Dominance

Another dominance rule used in\[GromichoHST12\]is based on the notion of the earliest completion time of the operationoofollowing the stateSSdenotedαS​\(o\)\\alpha\_\{S\}\(o\)and specified by:

αS​\(o\)=\{ψo\+poif​o∈η​\(S\)Cmax​\(S\)\+pootherwise\\alpha\_\{S\}\(o\)=\\begin\{cases\}&\\psi\_\{o\}\+p\_\{o\}\\quad\\text\{if \}o\\in\\eta\(S\)\\\\ &C\_\{\\max\}\(S\)\+p\_\{o\}\\quad\\text\{ otherwise\}\\end\{cases\}\(3\)
###### Definition 4\.3\.

\[GromichoHST12\]A stateS1S\_\{1\}dominates a stateS2S\_\{2\}, denotedS1⪯S2S\_\{1\}\\preceq S\_\{2\}if

\{𝑑𝑜𝑛𝑒​\(S1\)=𝑑𝑜𝑛𝑒​\(S2\)αS1​\(o\)≤αS2​\(o\)∀o∈ε​\(S1\)=ε​\(S2\)\\begin\{cases\}&\\mathit\{done\}\(S\_\{1\}\)=\\mathit\{done\}\(S\_\{2\}\)\\\\ &\\alpha\_\{S\_\{1\}\}\(o\)\\leq\\alpha\_\{S\_\{2\}\}\(o\)\\quad\\forall o\\in\\varepsilon\(S\_\{1\}\)=\\varepsilon\(S\_\{2\}\)\\end\{cases\}\(4\)

###### Example 4\.4\.

[Figure˜3](https://arxiv.org/html/2605.23569#S4.F3)illustrates[Definition˜4\.3](https://arxiv.org/html/2605.23569#S4.Thmtheorem3), that isS1⪯S2S\_\{1\}\\preceq S\_\{2\}withS1S\_\{1\}depicted in[Figure˜3\(a\)](https://arxiv.org/html/2605.23569#S4.F3.sf1)andS2S\_\{2\}in[Figure˜3\(b\)](https://arxiv.org/html/2605.23569#S4.F3.sf2)\. ForS2S\_\{2\},o5∉η​\(S2\)o\_\{5\}\\notin\\eta\(S\_\{2\}\), and thereforeαS2​\(o5\)=8\\alpha\_\{S\_\{2\}\}\(o\_\{5\}\)=8from[Equation˜3](https://arxiv.org/html/2605.23569#S4.E3)\. It follows thatαS1​\(o3\)=8<9=αS2​\(o3\)\\alpha\_\{S\_\{1\}\}\(o\_\{3\}\)=8<9=\\alpha\_\{S\_\{2\}\}\(o\_\{3\}\),αS1​\(o5\)=6<8=αS2​\(o5\)\\alpha\_\{S\_\{1\}\}\(o\_\{5\}\)=6<8=\\alpha\_\{S\_\{2\}\}\(o\_\{5\}\)andαS1​\(o8\)=7=αS2​\(o8\)\\alpha\_\{S\_\{1\}\}\(o\_\{8\}\)=7=\\alpha\_\{S\_\{2\}\}\(o\_\{8\}\)\. ThusS1⪯S2S\_\{1\}\\preceq S\_\{2\}\.

01234567891011M1M2M3o1o\_\{1\}o4o\_\{4\}o7o\_\{7\}o2o\_\{2\}o5o\_\{5\}o8o\_\{8\}o3o\_\{3\}Job 1Job 2Job 3\(a\)S1S\_\{1\}01234567891011M1M2M3o4o\_\{4\}o1o\_\{1\}o7o\_\{7\}o2o\_\{2\}o5o\_\{5\}o8o\_\{8\}o3o\_\{3\}Job 1Job 2Job 3\(b\)S2S\_\{2\}
Figure 3:Example of state dominance:S1⪯S2S\_\{1\}\\preceq S\_\{2\}Another state dominance is proposed in\[HoornNOG17\]\. A stateSSis dominated when there is at least one machine with an unscheduled operation belonging toη​\(S\)\\eta\(S\)and all operations of this machine inη​\(S\)\\eta\(S\)cannot start beforeCmax​\(S\)C\_\{\\max\}\(S\)\. Such states can be discarded, since the available operation must be scheduled at its earliest start time\. Formally a stateSSis dominated if there is a machineMjM\_\{j\}and an operationo∉η​\(S\)o\\notin\\eta\(S\)withm​\(o\)=Mjm\(o\)=M\_\{j\}such that

αS​\(o′\)=Cmax​\(S\)\+po′∀o′∈ε​\(S\)∧m​\(o′\)=Mj\.\\alpha\_\{S\}\(o^\{\\prime\}\)=C\_\{\\max\}\(S\)\+p\_\{o^\{\\prime\}\}\\quad\\forall o^\{\\prime\}\\in\\varepsilon\(S\)\\quad\\land\\quad m\(o^\{\\prime\}\)=M\_\{j\}\.\(5\)

## 5Anytime Column Search \(ACS\)

The DP model starts from the root stater^=⟨\(0,…,0\),−1,∅⟩\\hat\{r\}=\\langle\(0,\\dots,0\),\-1,\\emptyset\\rangle\. The solution space is then explored layer\-wise from the root, as in decision diagrams\[BergmanCHH16\], to apply and detect all state dominance rules\. A first drawback of this approach is that the optimal solution \(i\.e\., the shortest path in the transition graph\) is discovered only at the very end, which leads to poor anytime behavior\. A second drawback is that a branch\-and\-bound search would enable better filtering of the states by pruning nodes that are provably unable to improve the incumbent solution\. To address these issues, we propose exploring the search space using the Anytime Column Search \(ACS\)\[vadlamudi2012anytime\], as depicted in[Algorithm˜1](https://arxiv.org/html/2605.23569#algorithm1), rather than a layer\-wise exploration\.

In ACS, to limit the size of the search space, only a fixed number of nodes, denotedWW, are expanded at each layer, similarly to a beam search\. In\[vanHoorn\], the lower bound of a state is computed with the Jackson Preemptive Schedule \(JPS\)\[jackson1955scheduling\]\. The JPS works as follows\. On a machine, at least one available operation with the minimum latest completion time is scheduled\. This operation is processed either up to its completion or until a more urgent operation becomes available\. The function𝐿𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑𝐽𝑃𝑆​\(S\)\\mathit\{LowerBoundJPS\}\(S\)denotes the lower bound on the current stateSSusing JPS and taking the maximum JPS makespan across all machines\. The priority used to select the nodes to expand in ACS is defined byf​\(S\)=𝐿𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑𝐽𝑃𝑆​\(S\)f\(S\)=\\mathit\{LowerBoundJPS\}\(S\)\.

[Algorithm˜1](https://arxiv.org/html/2605.23569#algorithm1)receives as input an instanceIIof JSP or OSP and the parameterWW, and provides the optimal solution within the time limit or an approximate solution otherwise\. An array of empty queues of states \(one queue per decision layer\) sorted in increasing value offfis initialized at Line[1](https://arxiv.org/html/2605.23569#algorithm1)\. The first queue links to the decisions on the root state, is filled in the loop of Line[1](https://arxiv.org/html/2605.23569#algorithm1)with the transition from the root and their domaind​\(r^\)d\(\\hat\{r\}\)\. In the loop of Line[1](https://arxiv.org/html/2605.23569#algorithm1), the bestWWnon\-dominated states of each layer are made in the loop of Line[1](https://arxiv.org/html/2605.23569#algorithm1)\. The function𝑖𝑠𝑁𝑜𝑡𝐷𝑜𝑚𝑖𝑛𝑎𝑡𝑒𝑑\\mathit\{isNotDominated\}at Line[1](https://arxiv.org/html/2605.23569#algorithm1)checks if the state is not dominated by any other state of the same layer, i\.e\.,∀S′∈X​\[l\]∣S′⋠S\\forall S^\{\\prime\}\\in X\[l\]\\mid S^\{\\prime\}\\npreceq S, as defined in[Definition˜4\.3](https://arxiv.org/html/2605.23569#S4.Thmtheorem3)or if it is not dominated according to the[Equation˜5](https://arxiv.org/html/2605.23569#S4.E5)\. The loop at Line[1](https://arxiv.org/html/2605.23569#algorithm1)fills the queue associated with the next layer with the transition states of the selected states of the previous decision layer and their domains\. During the transition, the lower bound for the state will be computed\. The loop of Line[1](https://arxiv.org/html/2605.23569#algorithm1)checks if there exists an improving solution in the queue of the last decision\.

#### Implementation of state dominance\.

Following\[coppe\_dominance\], state dominance is implemented via a dedicated map indexed by the*dominance key*of a state, defined as its set of scheduled operations𝑑𝑜𝑛𝑒​\(S\)\\mathit\{done\}\(S\)\. For each dominance key, the map stores all non\-dominated states seen so far with that exact set of scheduled operations\. When a stateSSis dequeued and checked by𝑖𝑠𝑁𝑜𝑡𝐷𝑜𝑚𝑖𝑛𝑎𝑡𝑒𝑑\\mathit\{isNotDominated\}, it is compared against the map entry for its dominance key; if any stored stateS′S^\{\\prime\}satisfiesS′⪯SS^\{\\prime\}\\preceq S, the state is discarded\. Crucially, states remain in the map even after being dequeued and expanded, so a state created later that is dominated by an already\-expanded node is still correctly discarded\. However, the converse is not guaranteed: a state that has already been expanded may, in a later iteration, be dominated by a newly created state\. This situation can arise because ACS does not develop states strictly layer\-by\-layer as the original DP approach does\[GromichoHST12,HoornNOG17\]; consequently, some nodes may be explored that a purely layer\-wise traversal would have pruned\. This is an inherent tradeoff of ACS: accepting occasional redundant expansions in exchange for the ability to dive heuristically toward high\-quality solutions early, which in turn enables tighter bound pruning across subsequent iterations\.

Input:An instance

IIwith

NNoperations and a maximal width

WW
Output:The optimal sequence or an approximation solution

1for*l=1l=1toNN*do

X​\[l\]←∅X\[l\]\\leftarrow\\emptyset;

//empty queue of states sorted according toff

2

3

𝑢𝑏←ℎ𝑜𝑟𝑖𝑧𝑜𝑛\\mathit\{ub\}\\leftarrow\\mathit\{horizon\};

4

r^←⟨\(0,…,0\),−1,∅⟩\\hat\{r\}\\leftarrow\\langle\(0,\\dots,0\),\-1,\\emptyset\\rangle;

5

6foreach*o∈d​\(r^\)o\\in d\(\\hat\{r\}\)*do

7

X​\[1\]←X​\[1\]∪\{t​\(r^,o\)\}X\[1\]\\leftarrow X\[1\]\\cup\\\{t\(\\hat\{r\},o\)\\\};

8

9while*X≠∅X\\neq\\emptyset*do

10for*l=1l=1toN−1N\-1*do

11

𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠←∅\\mathit\{candidates\}\\leftarrow\\emptyset;

12while*\|𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠\|<W∧X​\[l\]≠∅\|\\mathit\{candidates\}\|<W\\wedge X\[l\]\\neq\\emptyset*do

13

S←𝑑𝑒𝑞𝑢𝑒𝑢𝑒𝐹𝑖𝑟𝑠𝑡​\(X​\[l\]\)S\\leftarrow\\mathit\{dequeueFirst\}\(X\[l\]\);

14if*𝑖𝑠𝑁𝑜𝑡𝐷𝑜𝑚𝑖𝑛𝑎𝑡𝑒𝑑​\(S\)∧𝐿𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑𝐽𝑃𝑆​\(S\)<𝑢𝑏\\mathit\{isNotDominated\}\(S\)\\land\\mathit\{LowerBoundJPS\}\(S\)<\\mathit\{ub\}*then

15

𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠←𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠∪\{S\}\\mathit\{candidates\}\\leftarrow\\mathit\{candidates\}\\cup\\\{S\\\};

16

17

18for*S∈𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠S\\in\\mathit\{candidates\}*do

19foreach*o∈d​\(S\)o\\in d\(S\)*do

20

S′←𝑇𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑜𝑛​\(S,o\)S^\{\\prime\}\\leftarrow\\mathit\{Transition\}\(S,o\);

21

X​\[l\+1\]←X​\[l\+1\]∪\{S′\}X\[l\+1\]\\leftarrow X\[l\+1\]\\cup\\\{S^\{\\prime\}\\\};

22

23

24

25

26while*X​\[N\]≠∅X\[N\]\\neq\\emptyset*do

27

S←𝑑𝑒𝑞𝑢𝑒𝑢𝑒𝐹𝑖𝑟𝑠𝑡​\(X​\[N\]\)S\\leftarrow\\mathit\{dequeueFirst\}\(X\[N\]\);

28if*Cmax​\(S\)<𝑢𝑏C\_\{\\max\}\(S\)<\\mathit\{ub\}*then

29

𝑢𝑏←Cmax​\(S\)\\mathit\{ub\}\\leftarrow C\_\{\\max\}\(S\);

30

31

32

Algorithm 1AnytimeColumnSearch\(I,W\)\(I,W\)

## 6Hybrid DP\-CP Model for the PSSP

In the PhD thesis of A\. van Hoorn\[vanHoorn\], the idea of using a filtering algorithm called the*parallel head–tail adjustment*\[brinkkotter2001solving\]is briefly mentioned\. In the constraint programming community, this algorithm is more commonly referred to as a type of*edge\-finding algorithm*\[vilim2007global,Martin1996ANA,baptiste2001constraint\]\. Such algorithms allow the detection of precedence constraints\. Van Hoorn informally explains that these precedences could be used to prune transitions further by allowing only expansions for which all predecessors are already in the partial solution\[vanHoorn\]\.

Our contribution with respect to this idea is twofold:

- •Use of full CP propagation\. Instead of relying on the parallel head–tail adjustment, we invoke a CP solver implementing all the filtering algorithms from\[vilim2007global\]for theNoOverlapconstraint on each machine, including*overload checking*,*edge\-finding*,*detectable precedences*, and*not\-first/not\-last*rules\. Petr Vilím proved\[vilim2007global\]that after reaching a fixpoint, all detectable precedences can be retrieved from the propagated time windows by verifying whether the earliest completion time of one activity exceeds the latest start time of another \(denoted⋖\\lessdotin the following\)\. By computing tighter time windows through CP propagation and identifying additional precedence relations, the explored search space can therefore be further reduced\.
- •Formalization of the approach\. We fully formalize this idea and provide a precise transition function based on calls to the CP solver, thereby turning the previously informal suggestion into a well\-defined algorithmic framework applicable to any scheduling problem with general precedences\.

### 6\.1Extended State and Update of the Domain Function

The state definition from\[GromichoHST12\]is extended to explicitly represent the set of precedences \(both original from the problem and those dynamically discovered through CP time\-window filtering\)\. We denote byS=⟨ψ,Λ,𝑑𝑜𝑛𝑒,δ⟩S=\\langle\\psi,\\Lambda,\\mathit\{done\},\\delta\\ranglethe extended state definition, whereδ​\(S\)\\delta\(S\)denotes the set of precedence constraints currently known\. Given an operationo∈Oo\\in O, we denote byδ​\(S,o\)\\delta\(S,o\)the set of predecessors ofooin the precedence relations ofδ​\(S\)\\delta\(S\), i\.e\.,δ​\(S,o\)=\{o′∈O∣\(o′,o\)∈δ​\(S\)\}\\delta\(S,o\)=\\\{\\,o^\{\\prime\}\\in O\\mid\(o^\{\\prime\},o\)\\in\\delta\(S\)\\,\\\}\. At the root state, the setδ\\deltais initialized toEE, the initial precedence graph of the problem\.

The domain functiond​\(S\)d\(S\)is adapted to takeδ​\(S\)\\delta\(S\)into account\. Only operations whose predecessors are all already scheduled inδ​\(S\)\\delta\(S\)can be appended, i\.e\.,\{o∈η​\(S\)∣δ​\(S,o\)⊆𝑑𝑜𝑛𝑒​\(S\)\}\\\{o\\in\\eta\(S\)\\mid\\delta\(S,o\)\\subseteq\\mathit\{done\}\(S\)\\\}\. This restriction reduces the size of the domain function and, consequently, the branching factor and the size of the search space explored by the DP approach\.

### 6\.2Transition with Constraint programming \(CP\)

The transition function relying on CP is given in[Algorithm˜3](https://arxiv.org/html/2605.23569#algorithm3)and replaces the transition function in ACS at line[1](https://arxiv.org/html/2605.23569#algorithm1)\. Given an extended stateSS, an operationo∈η​\(S\)o\\in\\eta\(S\), and an upper bound on the makespan, it returns a new stateS′S^\{\\prime\}in which the set of precedences includes both the precedence induced by the decision to append operationooto the sequence and the detectable precedences identified after CP filtering\.

Internally, this function makes use of a CP model for our scheduling problem given in[Algorithm˜2](https://arxiv.org/html/2605.23569#algorithm2), further restricted by the current state\. This function returns a constraint satisfaction problem \(CSP\) as a pairP=⟨ℐ,𝒞⟩P=\\langle\\mathcal\{I\},\\mathcal\{C\}\\ranglewhereℐ\\mathcal\{I\}is a mapping from operations to their corresponding CP interval variables\[LaborieR08,abs\-2508\-01751\]and𝒞\\mathcal\{C\}the set of CP constraints\. CP interval variable ranges are initialized by the function𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑒𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠\\mathit\{GenerateIntervals\}as follows\.

- •For operations in𝑑𝑜𝑛𝑒​\(S\)\\mathit\{done\}\(S\), the start time is fixed to their starting time in the state\.
- •For operations inη​\(S\)\\eta\(S\), the minimum start time is set to their earliest starting time inSS\.
- •For operations inε​\(S\)∖η​\(S\)\\varepsilon\(S\)\\setminus\\eta\(S\), the minimum start time is set toCmax​\(S\)C\_\{\\max\}\(S\)\.
- •For operations in𝑑𝑜𝑛𝑒​\(S\)\\mathit\{done\}\(S\), the end time is fixed to their starting time plus their duration\.
- •For operation inO∖\(𝑑𝑜𝑛𝑒​\(S\)\)O\\setminus\(\\mathit\{done\}\(S\)\), the maximum end time is fixed to the𝑢𝑏\\mathit\{ub\}\.

The precedence constraintsδ​\(S\)\\delta\(S\)and disjunction constraints for any machine and/or job are collected into a set𝒞\\mathcal\{C\}\(Lines[2](https://arxiv.org/html/2605.23569#algorithm2),[2](https://arxiv.org/html/2605.23569#algorithm2)\)\.

Input:A state

SS, an upper bound

𝑢𝑏\\mathit\{ub\}\.

Output:A CSP

P=⟨ℐ,𝒞⟩P=\\langle\\mathcal\{I\},\\mathcal\{C\}\\ranglewhere

ℐ\\mathcal\{I\}maps operations to interval variables and

𝒞\\mathcal\{C\}is a set of constraints\.

1

2

ℐ←𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑒𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠​\(S,𝑢𝑏\)\\mathcal\{I\}\\leftarrow\\mathit\{GenerateIntervals\}\(S,\\mathit\{ub\}\);

3

𝒞←∅\\mathcal\{C\}\\leftarrow\\emptyset;

4

5for*\(o′,o′′\)∈δ​\(S\)\(o^\{\\prime\},o^\{\\prime\\prime\}\)\\in\\delta\(S\)*do

6

𝒞←𝒞∪\{𝑆𝑡𝑎𝑟𝑡𝐵𝑒𝑓𝑜𝑟𝑒𝐸𝑛𝑑​\(ℐ​\(o′\),ℐ​\(o′′\)\)\}\\mathcal\{C\}\\leftarrow\\mathcal\{C\}\\cup\\\{\\mathit\{StartBeforeEnd\}\(\\mathcal\{I\}\(o^\{\\prime\}\),\\mathcal\{I\}\(o^\{\\prime\\prime\}\)\)\\\};

7

8for*j=1j=1tomm*do

9

𝒞←𝒞∪\{𝑁𝑜𝑂𝑣𝑒𝑟𝑙𝑎𝑝​\(\{ℐ​\(o′\)∣o′∈O∧m​\(o′\)=j\}\)\}\\mathcal\{C\}\\leftarrow\\mathcal\{C\}\\cup\\\{\\mathit\{NoOverlap\}\(\\\{\\mathcal\{I\}\(o^\{\\prime\}\)\\mid o^\{\\prime\}\\in O\\land m\(o^\{\\prime\}\)=j\\\}\)\\\};

10

11for*i=1i=1tonn*do

12

𝒞←𝒞∪\{𝑁𝑜𝑂𝑣𝑒𝑟𝑙𝑎𝑝​\(\{ℐ​\(o′\)∣o′∈O∧j​\(o′\)=i\}\)\}\\mathcal\{C\}\\leftarrow\\mathcal\{C\}\\cup\\\{\\mathit\{NoOverlap\}\(\\\{\\mathcal\{I\}\(o^\{\\prime\}\)\\mid o^\{\\prime\}\\in O\\land j\(o^\{\\prime\}\)=i\\\}\)\\\};

13

14

15return

⟨ℐ,𝒞⟩\\langle\\mathcal\{I\},\\mathcal\{C\}\\rangle;

16

Algorithm 2InitializeCSP\(S,𝑢𝑏\)\(S,\\mathit\{ub\}\)Input:A state

SS, an operation

ooand an upper bound

𝑢𝑏\\mathit\{ub\}\.

Output:The new state

S′S^\{\\prime\}\.

1

ψ′←𝑈𝑝𝑑𝑎𝑡𝑒𝐸𝑠𝑡​\(ψ,o\),Λ′=m​\(o\),𝑑𝑜𝑛𝑒′=𝑑𝑜𝑛𝑒​\(S\)∪\{o\},δ′←δ​\(S\)\\psi^\{\\prime\}\\leftarrow\\mathit\{UpdateEst\}\(\\psi,o\),\\Lambda^\{\\prime\}=m\(o\),\\mathit\{done\}^\{\\prime\}=\\mathit\{done\}\(S\)\\cup\\\{o\\\},\\delta^\{\\prime\}\\leftarrow\\delta\(S\);

2

S′←⟨ψ′,Λ′,𝑑𝑜𝑛𝑒′,δ′⟩S^\{\\prime\}\\leftarrow\\langle\\psi^\{\\prime\},\\Lambda^\{\\prime\},\\mathit\{done\}^\{\\prime\},\\delta^\{\\prime\}\\rangle;

3

P=⟨ℐ,𝒞⟩←𝐼𝑛𝑖𝑡𝑖𝑎𝑙𝑖𝑧𝑒𝐶𝑆𝑃​\(S′,𝑢𝑏\)P=\\langle\\mathcal\{I\},\\mathcal\{C\}\\rangle\\leftarrow\\mathit\{InitializeCSP\}\(S^\{\\prime\},\\mathit\{ub\}\);

4if*𝐹𝑖𝑥𝑝𝑜𝑖𝑛𝑡​\(P\)=𝐹𝑎𝑖𝑙𝑢𝑟𝑒\\mathit\{Fixpoint\}\(P\)=\\mathit\{Failure\}*then

5return

𝑁𝑜𝑛𝑒\\mathit\{None\}\.

6

δ′←δ​\(S\)\\delta^\{\\prime\}\\leftarrow\\delta\(S\);

7foreach*o′∈Oo^\{\\prime\}\\in O*do

8foreach*o′′∈O∖\{o′\}o^\{\\prime\\prime\}\\in O\\setminus\\\{o^\{\\prime\}\\\}*do

9if*ℐ​\(o′′\)⋖ℐ​\(o′\)\\mathcal\{I\}\(o^\{\\prime\\prime\}\)\\lessdot\\mathcal\{I\}\(o^\{\\prime\}\)*then

10

δ′←δ′∪\{\(o′′,o′\)\}\\delta^\{\\prime\}\\leftarrow\\delta^\{\\prime\}\\cup\\\{\(o^\{\\prime\\prime\},o^\{\\prime\}\)\\\};

11

12

13

14return

S′=⟨ψ′,Λ′,𝑑𝑜𝑛𝑒′,δ′⟩S^\{\\prime\}=\\langle\\psi^\{\\prime\},\\Lambda^\{\\prime\},\\mathit\{done\}^\{\\prime\},\\delta^\{\\prime\}\\rangle;

Algorithm 3TransitionCP\(S,o,𝑢𝑏\)\(S,o,\\mathit\{ub\}\)In[Algorithm˜3](https://arxiv.org/html/2605.23569#algorithm3), after the initialization of the CSP at Line[3](https://arxiv.org/html/2605.23569#algorithm3), the fixed point is computed at Line[3](https://arxiv.org/html/2605.23569#algorithm3)\. The loop of Line[3](https://arxiv.org/html/2605.23569#algorithm3)analyzes the interval at the fixed point to retrieve the detectable precedences to be added inδ′\\delta^\{\\prime\}\. The value ofψ′\\psi^\{\\prime\}is updated with the function𝑈𝑝𝑑𝑎𝑡𝑒𝐸𝑠𝑡\\mathit\{UpdateEst\}described in[Section˜4\.1](https://arxiv.org/html/2605.23569#S4.SS1)with the[Equation˜1](https://arxiv.org/html/2605.23569#S4.E1)and the[Equation˜2](https://arxiv.org/html/2605.23569#S4.E2)\.

Notice that we do not updateψ\\psiwith the earliest starting time of the interval variables inℐ\\mathcal\{I\}because we want to preserve the dominance rules defined in[Section˜4\.2](https://arxiv.org/html/2605.23569#S4.SS2)\. If we were to update it, the computation ofη\\etawould become invalid\.

### 6\.3Lower Bound With Constraint Programming

The lower bound is used in state\-space exploration to reduce the search space, thereby speeding up and tightening the problem bounds\. We adopt a lower bound similar to that in\[carlier1989algorithm\], which uses a dichotomic approach with filtering algorithms, denoted𝐿𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑𝐶𝑃\\mathit\{LowerBoundCP\}\. This function replaces the function𝐿𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑𝐽𝑃𝑆\\mathit\{LowerBoundJPS\}at line[1](https://arxiv.org/html/2605.23569#algorithm1)in the[1](https://arxiv.org/html/2605.23569#algorithm1)\.[Algorithm˜4](https://arxiv.org/html/2605.23569#algorithm4)receives as input a stateSSand an upper bound𝑢𝑏\\mathit\{ub\}and computes a lower bound fromSSto be used in the anytime column search\. The initial lower bound is computed with the Jackson preemptive scheduling procedure at Line[4](https://arxiv.org/html/2605.23569#algorithm4), and the function𝐼𝑛𝑖𝑡𝑖𝑎𝑙𝑖𝑧𝑒𝐶𝑆𝑃​\(S,𝑚𝑖𝑑\)\\mathit\{InitializeCSP\}\(S,\\mathit\{mid\}\)returns the pair⟨ℐ,𝒞⟩\\langle\\mathcal\{I\},\\mathcal\{C\}\\rangleas described in[Algorithm˜2](https://arxiv.org/html/2605.23569#algorithm2)with𝑚𝑖𝑑\\mathit\{mid\}as an upper bound\. The function𝐹𝑖𝑥𝑝𝑜𝑖𝑛𝑡\\mathit\{Fixpoint\}computes the fix\-point and returns𝐹𝑎𝑖𝑙𝑢𝑟𝑒\\mathit\{Failure\}if an inconsistency is detected\. The lower bound plays a central structural role in anytime column search \(ACS\) since it drives convergence, pruning, and the anytime behavior\.

Input:A state

SS, an upper bound

𝑢𝑏\\mathit\{ub\}\.

Output:The lower bound from the state

SS\.

1

2

𝑙𝑏←𝐽𝑎𝑐𝑘𝑠𝑜𝑛𝑃𝑟𝑒𝑒𝑚𝑝𝑡𝑖𝑣𝑒​\(S,𝑢𝑏\)\\mathit\{lb\}\\leftarrow\\mathit\{JacksonPreemptive\}\(S,\\mathit\{ub\}\);

3

4while*𝑙𝑏<𝑢𝑏\\mathit\{lb\}<\\mathit\{ub\}*do

5

𝑚𝑖𝑑←⌊\(𝑙𝑏\+𝑢𝑏\)/2⌋\\mathit\{mid\}\\leftarrow\\lfloor\(\\mathit\{lb\}\+\\mathit\{ub\}\)/2\\rfloor;

6

P=⟨ℐ,𝒞⟩←𝐼𝑛𝑖𝑡𝑖𝑎𝑙𝑖𝑧𝑒𝐶𝑆𝑃​\(S,𝑚𝑖𝑑\)P=\\langle\\mathcal\{I\},\\mathcal\{C\}\\rangle\\leftarrow\\mathit\{InitializeCSP\}\(S,\\mathit\{mid\}\);

7if*𝐹𝑖𝑥𝑝𝑜𝑖𝑛𝑡​\(P\)=𝐹𝑎𝑖𝑙𝑢𝑟𝑒\\mathit\{Fixpoint\}\(P\)=\\mathit\{Failure\}*then

8

𝑙𝑏←𝑚𝑖𝑑\+1\\mathit\{lb\}\\leftarrow\\mathit\{mid\}\+1;

9

10else

11

𝑢𝑏←𝑚𝑖𝑑\\mathit\{ub\}\\leftarrow\\mathit\{mid\};

12

13

14

15return

𝑙𝑏\\mathit\{lb\};

Algorithm 4LowerBoundCP\(S,𝑢𝑏\)\(S,\\mathit\{ub\}\)

## 7Large Neighborhood Search \(LNS\)

Given a solution to a problem, the generic form of the large neighborhood search \(LNS\) builds a large neighborhood of this solution and uses a solver to explore the neighborhood and improve the solution\[shaw1998using\]\. To build a neighborhood of a solution, a fraction of the incumbent solution is relaxed, and the corresponding problem is passed to the solver\. From the acyclic graph associated with the incumbent solution, a fraction of the precedence relations obtained during the search is relaxed, and the subproblem corresponding to this state is launched with an upper bound to allow the search to improve the solution\. To explore the search space of this subproblem, we perform an A\* search\[hart1968formal\]rather than an ACS\. A\* is a best\-first search \(BFS\) algorithm that finds the optimal solution when finished \(without improving it over time like ACS\)\.[Algorithm˜5](https://arxiv.org/html/2605.23569#algorithm5)receives as input an instanceIIof the problem, an initial solutionSb​e​s​tS\_\{best\}, and returns an improved solution\. The CSPP=⟨ℐ,𝒞⟩P=\\langle\\mathcal\{I\},\\mathcal\{C\}\\rangleis initialized with the root stater^\\hat\{r\}and the upper boundCmax​\(Sb​e​s​t\)−1C\_\{\\max\}\(S\_\{best\}\)\-1using the function of[Algorithm˜2](https://arxiv.org/html/2605.23569#algorithm2)at Line[5](https://arxiv.org/html/2605.23569#algorithm5)\. If the initialization fails \(i\.e\., the fixpoint detects a failure\), the flag𝑖𝑠𝑂𝑝𝑡𝑖𝑚𝑎𝑙\\mathit\{isOptimal\}is set to true, meaning no better solution exists, and the function returns the current solution\. A subset of the precedences from the current solution, denotedδk​e​p​t⊂δ​\(Sb​e​s​t\)∖E\\delta\_\{kept\}\\subset\\delta\(S\_\{best\}\)\\setminus E, is selected to be maintained \(relaxed precedences are ignored\) in the function𝑆𝑒𝑙𝑒𝑐𝑡𝑆𝑢𝑏𝑠𝑒𝑡𝑃𝑟𝑒𝑐𝑒𝑑𝑒𝑛𝑐𝑒𝑠\\mathit\{SelectSubsetPrecedences\}\. These are added to the set of constraints𝒞\\mathcal\{C\}in the loop of Line[5](https://arxiv.org/html/2605.23569#algorithm5)\. The CSPPPis then used to define the search space for an A\* search,𝐴𝑆𝑡𝑎𝑟𝑆𝑒𝑎𝑟𝑐ℎ​\(P\)\\mathit\{AStarSearch\}\(P\), which explores the neighborhood\. If a solutionSn​e​wS\_\{new\}is found, it replacesSb​e​s​tS\_\{best\}\.

Input:An instance

IIand an initial solution

Sb​e​s​tS\_\{best\}\.

Output:An improved solution

Sb​e​s​tS\_\{best\}and a status

𝑖𝑠𝑂𝑝𝑡𝑖𝑚𝑎𝑙\\mathit\{isOptimal\}\.

1

𝑖𝑠𝑂𝑝𝑡𝑖𝑚𝑎𝑙←𝑓𝑎𝑙𝑠𝑒\\mathit\{isOptimal\}\\leftarrow\\mathit\{false\};

2while*stopping criterion not met*do

3

P=⟨ℐ,𝒞⟩←𝐼𝑛𝑖𝑡𝑖𝑎𝑙𝑖𝑧𝑒𝐶𝑆𝑃​\(r^,Cmax​\(Sb​e​s​t\)−1\)P=\\langle\\mathcal\{I\},\\mathcal\{C\}\\rangle\\leftarrow\\mathit\{InitializeCSP\}\(\\hat\{r\},C\_\{\\max\}\(S\_\{best\}\)\-1\);

4if*𝐹𝑖𝑥𝑝𝑜𝑖𝑛𝑡​\(P\)=𝐹𝑎𝑖𝑙𝑢𝑟𝑒\\mathit\{Fixpoint\}\(P\)=\\mathit\{Failure\}*then

5

𝑖𝑠𝑂𝑝𝑡𝑖𝑚𝑎𝑙←𝑡𝑟𝑢𝑒\\mathit\{isOptimal\}\\leftarrow\\mathit\{true\};

6break;

7

8

δk​e​p​t←𝑆𝑒𝑙𝑒𝑐𝑡𝑆𝑢𝑏𝑠𝑒𝑡𝑃𝑟𝑒𝑐𝑒𝑑𝑒𝑛𝑐𝑒𝑠​\(Sb​e​s​t\)\\delta\_\{kept\}\\leftarrow\\mathit\{SelectSubsetPrecedences\}\(S\_\{best\}\);

9foreach*\(o,o′\)∈δk​e​p​t\(o,o^\{\\prime\}\)\\in\\delta\_\{kept\}*do

10

𝒞←𝒞∪\{𝑆𝑡𝑎𝑟𝑡𝐵𝑒𝑓𝑜𝑟𝑒𝐸𝑛𝑑​\(ℐ​\(o\),ℐ​\(o′\)\)\}\\mathcal\{C\}\\leftarrow\\mathcal\{C\}\\cup\\\{\\mathit\{StartBeforeEnd\}\(\\mathcal\{I\}\(o\),\\mathcal\{I\}\(o^\{\\prime\}\)\)\\\};

11

12

13

Sn​e​w←𝐴𝑆𝑡𝑎𝑟𝑆𝑒𝑎𝑟𝑐ℎ​\(P\)S\_\{new\}\\leftarrow\\mathit\{AStarSearch\}\(P\);

14if*Sn​e​w≠𝑛𝑢𝑙𝑙S\_\{new\}\\neq\\mathit\{null\}*then

15

Sb​e​s​t←Sn​e​wS\_\{best\}\\leftarrow S\_\{new\};

16

17

18return

Sb​e​s​t,𝑖𝑠𝑂𝑝𝑡𝑖𝑚𝑎𝑙S\_\{best\},\\mathit\{isOptimal\};

Algorithm 5LNS\(I,Sb​e​s​t\)\(I,S\_\{best\}\)After a large number of restarts of the A\* search without improving the solution, the fraction of precedence relaxed from the current solution is reduced\. If this percentage falls below a threshold, it returns to its initial value\. This feature is known as adaptive LNS\.

## 8Experimental Results

In this section, we report an empirical evaluation of different configurations of our DP\-CP model on six well\-known benchmarks, split as follows: three for JSP and three for OSP\. All instances are available111[https://github\.com/ScheduleOpt/benchmarks/](https://github.com/ScheduleOpt/benchmarks/)\. For the JSP, we use the benchmark suites of Fisher and Thompson\[fisher1963job\], Lawrence\[lawrance1984resource\], and Applegate and Cook\[applagate1991computational\]\. The benchmarks used for the OPS are from Taillard\[taillard1993benchmarks\], Guéret and Prins\[gueret1999new\], and Brucker, Hurink, Jurisch, and Wöstmann\[brucker1997branch\]\. The implementation of the DP part of the approach uses an open\-source Java version\[Schaus2026DDOLib\]of\[GillardSC20\]and the CP part uses MaxiCP\[maxicp\], an open source CP solver222[http://www\.maxicp\.org](http://www.maxicp.org/)\. The different search strategies available in DDOLib were tested in our DP model, among which the decision diagram–based branch and bound \(DD\-B&B\) search\[GillardSC20\], the A\* search, and the anytime column search \(ACS\)\[vadlamudi2012anytime\]\. We have not found a suitable merge operator for the DD\-B&B to speed up the approach, and the quality of the initial upper bound affects its performance, as in A\*\. The improvement over time of ACS provides a good initial solution quickly, even with a large initial upper bound\. We set the parameterWWto 5 after preliminary experiments, which is a good compromise between the number of explored nodes and execution time\.

The computational experiments reported in this section were run on an Intel\(R\) Xeon\(R\) Platinum 8160 CPU with 314GB of RAM, with a timeout of 3600 seconds\. The source code and instances are available333[https://anonymous\.4open\.science/r/DP\-CP\_JobShop\-8C5E](https://anonymous.4open.science/r/DP-CP_JobShop-8C5E)\. All acronyms used in the results are described in[Table˜3](https://arxiv.org/html/2605.23569#S8.T3)\.

Table 3:Models considered in the experimentsWe provide some answers to questions driven by our experiments\. These answers are based on detailed results presented afterward\.

Question 1Is an anytime column search necessary for the DP model and thus for the DP\-CP hybridization model? Answer:Yes, since we notice a reduction in the number of explored nodes when compared to the state\-of\-the\-art DP model, where a breadth\-first search is used\.

Question 2Does hybridization DP\-CP help to improve the individual approaches? Answer:Yes for both, since we notice a reduction in the number of explored nodes when compared to the individual approaches\.

Question 3Does the CP lower bound help the hybridization DP\-CP to be competitive with the individual approaches? Answer:Yes, since a greater reduction of explored nodes is noticed with each ingredient\.

Question 4Does hybridization DP\-CP help as a black box to explore the solution neighborhood? Answer:Yes, on both problems JSP and OSP\.

### 8\.1Question 1

We compare the number of explored nodes of DP\-JPS with the results reported from\[GromichoHST12\]\. Despite the simplicity of the lower bound \(𝐿𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑𝐽𝑃𝑆\\mathit\{LowerBoundJPS\}\) coupled with ACS, the results reported in[Table˜4](https://arxiv.org/html/2605.23569#S8.T4)clearly show that the number of explored nodes is substantially reduced by the anytime column search used to find and prove the optimality\. This is expected because the state\-of\-the\-art approach uses a breadth\-first search, and the JPS\-based lower bound enables ACS to control the search and guarantee the quality of the current solution\.

Table 4:Nodes explored: DP\-JPS vs state\-of\-the\-art\[GromichoHST12\]
### 8\.2Question 2

#### DP\-CP vs DP

The DP model, denoted DP\-JPS, is compared to our DP\-CP\-JPS model, referred to as DP\-CP, without CP in the lower bound computation\. The DP\-JSP model explores the search space with ACS but without CP in transition, and for the lower bounds computation \(𝐿𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑𝐽𝑃𝑆\\mathit\{LowerBoundJPS\}is used\)\. The models differ only in the transition phase, where the CP is used in DP\-CP\-JPS to reduce the branching factor of the DP formulation\.[Figure˜5](https://arxiv.org/html/2605.23569#S8.F5)compares the number of nodes explored needed to find and prove the optimality, while[Figure˜5](https://arxiv.org/html/2605.23569#S8.F5)compares the time used to do so in JSP\. We observe a reduction in the number of nodes explored across all instances solved to optimality by the DP\-CP\-JPS model\. However, in some instances, the DP\-CP\-JPS model requires a slight increase in time\. The running time favors DP\-JPS for instances solved in less than 100 seconds, and for hard instances, it generally favors the hybridization DP\-CP\-JPS \(see[Figure˜5](https://arxiv.org/html/2605.23569#S8.F5)\)\.

![Refer to caption](https://arxiv.org/html/2605.23569v1/x1.png)Figure 4:Nodes to optimality comparison\. Labels\(X,Y\)\(X,Y\)denoteXXjobs×\\timesYYmachines\. Dots: both solvers proved optimality; crosses: at least one solver timed out\.
![Refer to caption](https://arxiv.org/html/2605.23569v1/x2.png)Figure 5:Time to optimality comparison\. Labels\(X,Y\)\(X,Y\)denoteXXjobs×\\timesYYmachines\. Dots: both solvers proved optimality; crosses: at least one solver timed out\.

#### DP\-CP vs CP

We compare our hybridization DP\-CP model against a pure CP model on JSP\. The CP model used the interval variables and theNoOverlapglobal constraint available in MaxiCP\[maxicp\]\. The strategy search used is thesetTimes\[le1995time\]andRank\(\[baptiste2001constraint\]pages 130\)\.

![Refer to caption](https://arxiv.org/html/2605.23569v1/x3.png)Figure 6:Nodes to optimality comparison \(JSP, instances solved to optimality by both methods\)\. Labels\(X,Y\)\(X,Y\):XXjobs×\\timesYYmachines\. Note: CP\-S timed out on all20×1020\{\\times\}10and30×1030\{\\times\}10instances, which are therefore excluded\. Dots: both proved optimality; crosses: at least one timed out\.
![Refer to caption](https://arxiv.org/html/2605.23569v1/x4.png)Figure 7:Time to optimality comparison \(JSP, instances solved to optimality by both methods\)\. Labels\(X,Y\)\(X,Y\):XXjobs×\\timesYYmachines\. Dots: both proved optimality; crosses: at least one timed out\.

[Figure˜7](https://arxiv.org/html/2605.23569#S8.F7)compares the number of explored nodes needed to find and prove the optimality of approaches, while[Figure˜7](https://arxiv.org/html/2605.23569#S8.F7)compares the execution time in seconds to find and prove the optimality on JSP instances where at least one finds and proves the optimality\. Undoubtedly, the hybridization DP\-CP significantly reduces the number of explored nodes compared to the CP model, in order to find and prove optimality\. This reduction in explored nodes reduced the running time of hard instances \(instances that require more time to be solved to optimality\) in favor of the hybridization DP\-CP\. We also compare our model with a CP model using precedence branching\. The results can be found in[Section˜A\.1](https://arxiv.org/html/2605.23569#A1.SS1)of the appendix\. It also compares the number of solved instances of our model with the two CP models in terms of time\.

On OSP, we only apply thesetTimessearch and compare our DP\-CP hybridization model against CP\-S\.[Figure˜9](https://arxiv.org/html/2605.23569#S8.F9)compares the number of explored nodes needed to find and prove the optimality, while[Figure˜9](https://arxiv.org/html/2605.23569#S8.F9)compares the number of common solved instances over time\. The hybridization reduces the number of nodes needed to find and prove the optimality of almost all OSP instances\. Despite the reduction, the CP\-S model is still superior to the DP\-CP model\. This is likely due to the hardness of the OSP, in which no order is specified for operations of the same job, as in JSP\.

![Refer to caption](https://arxiv.org/html/2605.23569v1/x5.png)Figure 8:Nodes to optimality comparison \(OSP\)\. Labels\(X,Y\)\(X,Y\):XXjobs×\\timesYYmachines\. Dots: both proved optimality; crosses: at least one timed out\.
![Refer to caption](https://arxiv.org/html/2605.23569v1/x6.png)Figure 9:Solved instances over time \(OSP\)

### 8\.3Question 3

To appreciate the impact of the CP on the computation of the lower bound, we compare our model, DP\-CP, with its variant, DP\-CP\-JSP \(based on lower bound𝐿𝑜𝑤𝑒𝑟𝐵𝑜𝑢𝑛𝑑𝐽𝑃𝑆\\mathit\{LowerBoundJPS\}\)\.[Figure˜11](https://arxiv.org/html/2605.23569#S8.F11)compares the number of explored nodes needed to find and prove the optimality of JSP instances, while[Figure˜11](https://arxiv.org/html/2605.23569#S8.F11)compares the time needed by at least one model to do so\. The efficiency of filtering algorithms embedded into theNoOverlapglobal constraint significantly improves the lower bound, and thus reduces the number of explored nodes of almost all the instances\. The time spent improving the lower bound affects the execution time required to find and prove optimality in many instances\. We notice that with the strong lower bound, it is possible to solve30×1030\\times 10instances within the time limit\.

![Refer to caption](https://arxiv.org/html/2605.23569v1/x7.png)Figure 10:Nodes to optimality comparison\. Labels\(X,Y\)\(X,Y\):XXjobs×\\timesYYmachines\. Dots: both proved optimality; crosses: at least one timed out\.
![Refer to caption](https://arxiv.org/html/2605.23569v1/x8.png)Figure 11:Time to optimality comparison\. Labels\(X,Y\)\(X,Y\):XXjobs×\\timesYYmachines\. Dots: both proved optimality; crosses: at least one timed out\.

### 8\.4Question 4

The initial solution of our LNS is the first solution of the DP\-CP model, and for each instance of the problem \(JSP or OSP\), we ran 10 random seeds to randomly select the fraction of precedences to keep\. For each run, 70% of precedences are kept, and after 100 not fruitful restarts of the A\*, the number of precedences to keep is reduced by 5%\. When the percentage is less than 20%, the number of precedences is reset to its initial value, and the process is repeated until the time limit is reached\.[Figure˜13](https://arxiv.org/html/2605.23569#S8.F13)compares the best gap found at the end of the LNS with the gap at the end of the DP\-CP model for each JSP instance\. We observe that within the time limit, the LNS gap is better than that of the DP\-CP model for large instances\. There are many instances for which the gap is 0% for both searches\.[Figure˜13](https://arxiv.org/html/2605.23569#S8.F13)compares the average gap among the 10 runs of LNS on each instance with the gap of the DP\-CP model over time\. We observe that the gap decreases more rapidly for the LNS than for the DP\-CP model\. The LNS can find and prove the optimality of three instances of the Lawrence benchmarks\[lawrance1984resource\]not proved by the hybridization model DP\-CP\.

On OSP, the LNS decreases the incumbent solution gap more rapidly than the DP\-CP model\. The plots are similar to those of the JSP, and are reported in Section[A\.2](https://arxiv.org/html/2605.23569#A1.SS2)of the appendix\. Eight of the10×1010\\times 10unsolved Taillard instances\[taillard1993benchmarks\]to optimality by the DP\-CP model have been solved with the proof of optimality by the LNS\. This illustrates the ability of our LNS to guide the search towards promising regions of the solution space\.

![Refer to caption](https://arxiv.org/html/2605.23569v1/x9.png)Figure 12:Best gap comparison\. The gap is computed with respect to the best\-known solutions \(BKS\) reported in the literature for the Lawrence and Taillard benchmarks\.
![Refer to caption](https://arxiv.org/html/2605.23569v1/x10.png)Figure 13:Average gap over time\. The gap is computed with respect to the best\-known solutions \(BKS\) reported in the literature for the Lawrence and Taillard benchmarks\.

## 9Conclusion

In this paper, we have proposed for the first time a hybridization of DP and CP for the partial shop scheduling problems like JSP or OSP\. The CP was used as a subroutine to leverage global constraint propagation, and the DP serves as a primary search framework\. The DP formulation uses the CP during the transition phase to reduce the branching factor of the search, and the CP is also used to compute the lower bound, which is useful for the ACS used to explore the search space of the DP\. The proposed model always reduces the explored nodes and has solved more instances than the CP model, sometimes with additional time\. It was able to quickly improve a solution by successively exploring a promising part of the search tree in a large neighborhood search approach\. The hybridization of DP and CP seems a promising research direction for solving other combinatorial optimization problems\.

## References

## Appendix AAppendix

In this section, remaining results are reported\.

### A\.1Question 2

The second CP model, where theRankstrategy search is compared to our hybridization model DP\-CP on JSP instances\.[Figure˜15](https://arxiv.org/html/2605.23569#A1.F15)compares the number of nodes explored needed to find and prove the optimality of approaches, while[Figure˜15](https://arxiv.org/html/2605.23569#A1.F15)compares the execution time in seconds to find and prove the optimality on instances where at least one finds and proves the optimality\. Despite the systematic reduction of the number of explored nodes on almost all common solved instances, the running time is generally in favor of the rank CP model\.

![Refer to caption](https://arxiv.org/html/2605.23569v1/x11.png)Figure 14:Nodes to optimality comparison
![Refer to caption](https://arxiv.org/html/2605.23569v1/x12.png)Figure 15:Time to optimality comparison

[Figure˜16](https://arxiv.org/html/2605.23569#A1.F16)compares the number of JSP instances solved over time for the CP models against the hybridization DP\-CP model\. For JSP instances solved with less than 100 seconds, CP approaches are superior to the DP\-CP model, and the observation changes on hard instances where DP\-CP solves more instances than CP\-S\. DP\-CP and CP\-S are similar in the branching strategy since both branch on time, while CP\-R branches on precedences, like in\[GrimesH10\]\. DP\-CP model solves more instances than the CP models, and the difference is more pronounced compared to CP\-S\.

![Refer to caption](https://arxiv.org/html/2605.23569v1/x13.png)Figure 16:Solved instances over time \(JSP\)
### A\.2Question 4

On OSP, the LNS decreases the incumbent solution gap more rapidly than the DP\-CP model\.[Figure˜18](https://arxiv.org/html/2605.23569#A1.F18)compares the best gap found at the end of the LNS with the gap at the end of the DP\-CP model for each OSP instance\. We observe that within the time limit, the LNS gap is better than that of the DP\-CP model for more instances\. There are many instances for which the gap is 0% for both approaches\.[Figure˜18](https://arxiv.org/html/2605.23569#A1.F18)compares the average gap among the 10 runs of LNS on each instance with the gap of the DP\-CP model over time\. We observe that the gap decreases more rapidly for the LNS model than for the DP\-CP model\. The LNS can find and prove the optimality of eight of the10×1010\\times 10unsolved Taillard instances\[taillard1993benchmarks\]using the DP\-CP model\. The instancest​a​i​\_​10×10​\_​1tai\\\_10\\times 10\\\_1,t​a​i​\_​10×10​\_​2tai\\\_10\\times 10\\\_2,t​a​i​\_​10×10​\_​3tai\\\_10\\times 10\\\_3,t​a​i​\_​10×10​\_​4tai\\\_10\\times 10\\\_4,t​a​i​\_​10×10​\_​5tai\\\_10\\times 10\\\_5,t​a​i​\_​10×10​\_​7tai\\\_10\\times 10\\\_7,t​a​i​\_​10×10​\_​8tai\\\_10\\times 10\\\_8, andt​a​i​\_​10×10​\_​10tai\\\_10\\times 10\\\_10are those solved to optimality by the LNS\.

![Refer to caption](https://arxiv.org/html/2605.23569v1/x14.png)Figure 17:Best gap comparison over OSP
![Refer to caption](https://arxiv.org/html/2605.23569v1/x15.png)Figure 18:Average gap over timeover OSP