No-Overlap Constraints

Our current model has a problem: it lets both cutting tasks happen at the same time. In reality, the workshop has one saw, which can only cut one piece of wood at a time. We need to add a no-overlap constraint.

The No-Overlap Constraint

A no-overlap constraint ensures that a set of tasks never overlap in time. This models a disjunctive resource: a resource that can handle at most one task at a time (like a saw, a machine, or a single worker).

In our workshop, two tasks use the saw:

• CutDeskWood
• CutChairWood

Let's add the constraint:

Python

# The saw can only cut one thing at a time
model.no_overlap([cut_desk_wood, cut_chair_wood])

TypeScript

// The saw can only cut one thing at a time
model.noOverlap([cutDeskWood, cutChairWood]);

That's it! The no_overlap constraint guarantees that the two intervals never overlap. The solver will ensure one finishes before the other starts, but it decides which order is best.

How It Affects the Schedule

With the no-overlap constraint added to our previous model, the solver must now sequence the cutting operations. Let's rebuild the complete model and see the result:

Python

import optalcp as cp

model = cp.Model()

# Create interval variables
cut_desk_wood    = model.interval_var(length=30, name="CutDeskWood")
cut_chair_wood   = model.interval_var(length=25, name="CutChairWood")
sand_desk_parts  = model.interval_var(length=20, name="SandDeskParts")
sand_chair_parts = model.interval_var(length=15, name="SandChairParts")
assemble_desk    = model.interval_var(length=45, name="AssembleDesk")
assemble_chair   = model.interval_var(length=35, name="AssembleChair")
stain_desk       = model.interval_var(length=20, name="StainDesk")
stain_chair      = model.interval_var(length=15, name="StainChair")
apply_finish     = model.interval_var(length=30, name="ApplyFinish")
final_inspect    = model.interval_var(length=10, name="FinalInspect")

# Precedence constraints - Desk
cut_desk_wood.end_before_start(sand_desk_parts)
sand_desk_parts.end_before_start(assemble_desk)
assemble_desk.end_before_start(stain_desk)
stain_desk.end_before_start(apply_finish)

# Precedence constraints - Chair
cut_chair_wood.end_before_start(sand_chair_parts)
sand_chair_parts.end_before_start(assemble_chair)
assemble_chair.end_before_start(stain_chair)
stain_chair.end_before_start(apply_finish)

# Final inspection
apply_finish.end_before_start(final_inspect)

# [NEW] Resource constraint: one saw
model.no_overlap([cut_desk_wood, cut_chair_wood])

# Minimize makespan
model.minimize(final_inspect.end())

# Solve
result = model.solve()

if result.solution:
    print(f"Makespan: {result.objective} minutes")
    print(f"Optimal: {result.proof}")

TypeScript

import * as CP from '@scheduleopt/optalcp';

const model = new CP.Model();

// Create interval variables
const cutDeskWood    = model.intervalVar({ length: 30, name: "CutDeskWood" });
const cutChairWood   = model.intervalVar({ length: 25, name: "CutChairWood" });
const sandDeskParts  = model.intervalVar({ length: 20, name: "SandDeskParts" });
const sandChairParts = model.intervalVar({ length: 15, name: "SandChairParts" });
const assembleDesk   = model.intervalVar({ length: 45, name: "AssembleDesk" });
const assembleChair  = model.intervalVar({ length: 35, name: "AssembleChair" });
const stainDesk      = model.intervalVar({ length: 20, name: "StainDesk" });
const stainChair     = model.intervalVar({ length: 15, name: "StainChair" });
const applyFinish    = model.intervalVar({ length: 30, name: "ApplyFinish" });
const finalInspect   = model.intervalVar({ length: 10, name: "FinalInspect" });

// Precedence constraints - Desk
cutDeskWood.endBeforeStart(sandDeskParts);
sandDeskParts.endBeforeStart(assembleDesk);
assembleDesk.endBeforeStart(stainDesk);
stainDesk.endBeforeStart(applyFinish);

// Precedence constraints - Chair
cutChairWood.endBeforeStart(sandChairParts);
sandChairParts.endBeforeStart(assembleChair);
assembleChair.endBeforeStart(stainChair);
stainChair.endBeforeStart(applyFinish);

// Final inspection
applyFinish.endBeforeStart(finalInspect);

// [NEW] Resource constraint: one saw
model.noOverlap([cutDeskWood, cutChairWood]);

// Minimize makespan
model.minimize(finalInspect.end());

// Solve
const result = await model.solve();

if (result.solution) {
    console.log(`Makespan: ${result.objective} minutes`);
    console.log(`Optimal: ${result.proof}`);
}

Result

The optimal makespan is now 160 minutes (up from 155), because the cutting operations can't overlap anymore. The solver chooses an optimal sequence automatically.

Which Order Is Best?

You might wonder: should we cut the desk first or the chair first? The solver explores both options and picks the one that minimizes makespan.

In this case, cutting the desk first is optimal because:

• The desk has a longer production chain
• Starting it early allows later steps to overlap with chair production
• This minimizes idle time and reduces overall makespan

This is a simple example, but imagine scheduling hundreds of tasks on dozens of machines. The no-overlap constraint handles all the sequencing decisions automatically.

Multiple Resources

If we had multiple disjunctive resources, we'd add a no-overlap constraint for each:

Python

# Example: two machines, different tasks
model.no_overlap([task1_on_machine_a, task2_on_machine_a, task3_on_machine_a])
model.no_overlap([task4_on_machine_b, task5_on_machine_b])

TypeScript

// Example: two machines, different tasks
model.noOverlap([task1OnMachineA, task2OnMachineA, task3OnMachineA]);
model.noOverlap([task4OnMachineB, task5OnMachineB]);

Disjunctive vs Cumulative

The no-overlap constraint is for disjunctive resources: resources with capacity 1 (one task at a time).

What if a resource can handle multiple tasks simultaneously, but only up to a limit? For example, our workshop has 2 workers. Most tasks need 1 worker, but assembling the desk needs 2 workers. This is a cumulative resource, which we'll model in the next chapter.

What We Learned

In this chapter, we:

• Added a no-overlap constraint to model a disjunctive resource (the saw)
• Let the solver choose the optimal sequencing automatically
• Understood that disjunctive resources (capacity 1) are modeled with no_overlap

Our model is getting more realistic, but we still assume unlimited workers. That changes next.

See Also

• Resources / No-Overlap — Complete reference for disjunctive resources
• Resources / Overview — When to use no-overlap vs cumulative vs reservoir

Next Steps

In the next chapter, we'll add cumulative resource constraints to model our 2 workers.

Continue to: Cumulative Constraints →