Cumulative Constraints

So far, we've modeled task precedence and a disjunctive resource (the saw). Now let's tackle a different kind of resource: workers.

Our workshop has 2 equivalent workers (either worker can do any task). Most tasks need 1 worker, but assembling the desk requires 2 workers (it's heavy and needs two people). This is a cumulative resource: a resource with limited capacity that can be shared among tasks.

Understanding Cumulative Resources

A cumulative resource has:

• A capacity (e.g., 2 workers)
• Tasks with demands (e.g., task A needs 1 worker, task B needs 2)
• A constraint: total demand at any time must not exceed capacity

At time 50, if three 1-worker tasks are running, we'd need 3 workers—but we only have 2. The cumulative constraint prevents this.

Pulse Expressions

To model cumulative resources in OptalCP, we use pulse expressions. A pulse represents the resource usage profile of a task:

• While the task executes, it consumes a certain amount of resource (the height of the pulse)
• Before and after, it consumes zero

For example, pulse(task, 1) creates a pulse of height 1 during the task's execution.

Python

# A task that uses 1 worker while it executes
worker_usage = model.pulse(cut_desk_wood, 1)
# Alternative syntax:
worker_usage = cut_desk_wood.pulse(1)

TypeScript

// A task that uses 1 worker while it executes
const workerUsage = model.pulse(cutDeskWood, 1);
// Alternative syntax:
const workerUsage = cutDeskWood.pulse(1);

Cumulative Constraint

We create pulse expressions for all tasks, then enforce that the sum never exceeds the capacity:

Python

# Worker demands: most tasks need 1 worker, assembling desk needs 2
worker_usage = [
    model.pulse(cut_desk_wood, 1),
    model.pulse(cut_chair_wood, 1),
    model.pulse(sand_desk_parts, 1),
    model.pulse(sand_chair_parts, 1),
    model.pulse(assemble_desk, 2),      # Needs 2 workers
    model.pulse(assemble_chair, 1),
    model.pulse(stain_desk, 1),
    model.pulse(stain_chair, 1),
    model.pulse(apply_finish, 1),
    model.pulse(final_inspect, 1),
]

# Total worker usage at any time <= 2
model.enforce(model.sum(worker_usage) <= 2)

TypeScript

// Worker demands: most tasks need 1 worker, assembling desk needs 2
const workerUsage = [
    model.pulse(cutDeskWood, 1),
    model.pulse(cutChairWood, 1),
    model.pulse(sandDeskParts, 1),
    model.pulse(sandChairParts, 1),
    model.pulse(assembleDesk, 2),      // Needs 2 workers
    model.pulse(assembleChair, 1),
    model.pulse(stainDesk, 1),
    model.pulse(stainChair, 1),
    model.pulse(applyFinish, 1),
    model.pulse(finalInspect, 1),
];

// Total worker usage at any time <= 2
model.enforce(model.sum(workerUsage).le(2));

The model.sum() combines pulse expressions into a step function that represents the total resource usage at each point in time. When tasks overlap, their pulses stack. The constraint ensures this sum never exceeds our capacity of 2 workers.

Complete Model with Workers

Let's add the worker constraint to our full model:

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)

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

# [NEW] Resource constraint: 2 workers (AssembleDesk needs both)
worker_usage = [
    model.pulse(cut_desk_wood, 1),
    model.pulse(cut_chair_wood, 1),
    model.pulse(sand_desk_parts, 1),
    model.pulse(sand_chair_parts, 1),
    model.pulse(assemble_desk, 2),      # Needs 2 workers
    model.pulse(assemble_chair, 1),
    model.pulse(stain_desk, 1),
    model.pulse(stain_chair, 1),
    model.pulse(apply_finish, 1),
    model.pulse(final_inspect, 1),
]
model.enforce(model.sum(worker_usage) <= 2)

# 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);

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

// [NEW] Resource constraint: 2 workers (AssembleDesk needs both)
const workerUsage = [
    model.pulse(cutDeskWood, 1),
    model.pulse(cutChairWood, 1),
    model.pulse(sandDeskParts, 1),
    model.pulse(sandChairParts, 1),
    model.pulse(assembleDesk, 2),      // Needs 2 workers
    model.pulse(assembleChair, 1),
    model.pulse(stainDesk, 1),
    model.pulse(stainChair, 1),
    model.pulse(applyFinish, 1),
    model.pulse(finalInspect, 1),
];
model.enforce(model.sum(workerUsage).le(2));

// 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}`);
}

Impact on the Schedule

The worker constraint forces the solver to be more careful about parallelism:

• When AssembleDesk is running (needs 2 workers), no other task can execute
• At other times, up to 2 single-worker tasks can run in parallel

The optimal makespan is now 180 minutes (up from 160), because we can't run as many tasks simultaneously.

Variable Heights

In our example, all tasks have fixed worker demands (1 or 2). But OptalCP also supports variable heights: you can use an IntVar as the pulse height.

Python

# Task can use 1, 2, or 3 workers (solver decides)
demand = model.int_var(min=1, max=3, name="TaskDemand")
usage = model.pulse(task, demand)

TypeScript

// Task can use 1, 2, or 3 workers (solver decides)
const demand = model.intVar({ min: 1, max: 3, name: "TaskDemand" });
const usage = model.pulse(task, demand);

The solver will choose the number of workers to optimize your objective. The same IntVar can be used in other constraints—for example, to make task duration inversely proportional to the number of workers assigned.

Variable Capacity

Not only can pulse heights be decision variables—the capacity itself can be an IntVar or IntExpr. This enables capacity planning problems where the resource limit is part of the optimization:

Python

# Capacity is a decision: hire between 2 and 5 workers
num_workers = model.int_var(min=2, max=5, name="NumWorkers")
model.enforce(model.sum(worker_usage) <= num_workers)

# Minimize hiring cost while meeting deadlines
model.minimize(num_workers)

TypeScript

// Capacity is a decision: hire between 2 and 5 workers
const numWorkers = model.intVar({ min: 2, max: 5, name: "NumWorkers" });
model.enforce(model.sum(workerUsage).le(numWorkers));

// Minimize hiring cost while meeting deadlines
model.minimize(numWorkers);

This is useful for scenarios like workforce sizing, machine selection, or any problem where you're deciding how much capacity to provision. See Resources / Cumulative for more details.

Disjunctive as Cumulative

Interestingly, a no-overlap constraint is just a special case of cumulative with capacity 1:

Python

# These are equivalent:
model.no_overlap([task1, task2, task3])

# vs
model.enforce(model.sum([
    model.pulse(task1, 1),
    model.pulse(task2, 1),
    model.pulse(task3, 1)
]) <= 1)

TypeScript

// These are equivalent:
model.noOverlap([task1, task2, task3]);

// vs
model.enforce(model.sum([
    model.pulse(task1, 1),
    model.pulse(task2, 1),
    model.pulse(task3, 1)
]).le(1));

The solver automatically recognizes cumulative constraints with capacity 1 and applies specialized no-overlap algorithms. However, no_overlap is preferred: it's clearer and supports additional features like transition times and sequence position queries.

What We Learned

In this chapter, we:

• Modeled a cumulative resource (workers with capacity 2)
• Used pulse expressions to represent resource demand over time
• Enforced that total demand never exceeds capacity
• Handled tasks with different demands (1 vs 2 workers)
• Learned that both pulse heights and capacity can be decision variables

Our model now captures precedence, the saw, and workers. Next, we'll add transition times for the spray booth.

See Also

• Resources / Cumulative — Complete reference for cumulative resources
• Resources / Overview — When to use cumulative vs other resource types
• Modeling / Expressions — Working with cumulative expressions

Next Steps

In the next chapter, we'll model transition times: the spray booth needs cleaning when switching between different stain colors.

Continue to: Transition Times →