Skip to main content

Transition Times

Our workshop has one spray booth used for three staining tasks:

  • StainDesk (dark walnut stain)
  • StainChair (light oak stain)
  • ApplyFinish (clear coat)

These tasks can't overlap (the booth handles one item at a time), but there's an additional complication: when switching between different stain types, the booth must be cleaned—a process that takes time but doesn't require a worker.

For example:

  • Switching from dark walnut to light oak: 10 minutes delay
  • Switching from any stain to clear coat: 5 minutes delay
  • No delay if the same color is used consecutively (though this won't happen in our problem)

This is a sequence-dependent setup time, also called transition time.

Sequence Variables​

To model transition times, we need to track the order in which tasks use a resource. OptalCP provides sequence variables for this purpose.

A sequence variable represents the ordering of intervals on a resource. We can:

  1. Create a no-overlap constraint on the sequence
  2. Specify transition times between tasks
  3. Query the position of tasks in the sequence
# Create a sequence variable for spray booth tasks
spray_booth_seq = model.sequence_var([stain_desk, stain_chair, apply_finish])

# Add no-overlap constraint with transition times
model.no_overlap(spray_booth_seq, transitions)

Transition Time Matrix​

Transition times are specified as a square matrix: transitions[i][j] is the minimum delay required when task i is followed by task j.

Our spray booth has three tasks in order: [stain_desk, stain_chair, apply_finish]

The transition matrix is:

             To: StainDesk  StainChair  ApplyFinish
From: StainDesk      0          10           5
      StainChair    10           0           5
      ApplyFinish    5           5           0
  • Diagonal (same task to same task): 0 (won't happen in our model anyway)
  • Dark ↔ Light stain (StainDesk ↔ StainChair): 10 minutes
  • Any stain to finish, or finish to stain: 5 minutes
# Transition time matrix (3x3 for our 3 spray booth tasks)
# Order: [stain_desk, stain_chair, apply_finish]
transitions = [
    [0, 10, 5],   # From StainDesk to: StainDesk, StainChair, ApplyFinish
    [10, 0, 5],   # From StainChair to: StainDesk, StainChair, ApplyFinish
    [5, 5, 0],    # From ApplyFinish to: StainDesk, StainChair, ApplyFinish
]

How Transition Times Work​

When the solver sequences tasks on the spray booth, it automatically adds the transition time between consecutive tasks:

  • If StainDesk (20 min) ends at time 100, and StainChair follows it, then StainChair cannot start before 100 + 10 = 110
  • If StainChair (15 min) ends at 125, and ApplyFinish follows, then ApplyFinish cannot start before 125 + 5 = 130

The transition times are enforced between all consecutive pairs in the sequence—the solver determines the order and applies the appropriate delay based on which tasks are adjacent.

The solver chooses the sequence order to minimize makespan while respecting these delays.

Complete Model with Transition Times​

Let's add the spray booth sequence to our full model:

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])

# Resource constraint: 2 workers
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),
    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)

# [NEW] Resource constraint: spray booth with transition times
spray_booth_seq = model.sequence_var([stain_desk, stain_chair, apply_finish])
transitions = [
    [0, 10, 5],   # From StainDesk
    [10, 0, 5],   # From StainChair
    [5, 5, 0],    # From ApplyFinish
]
model.no_overlap(spray_booth_seq, transitions)

# 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}")

Impact on the Schedule​

The transition times add delays between spray booth tasks, increasing the optimal makespan to 200 minutes (up from 180). The solver chooses the best sequence order:

  • Should we stain the desk first or the chair first?
  • What's the optimal order to minimize total transition time?

The precedence constraints already require both stains to finish before ApplyFinish, so the solver has some flexibility in ordering StainDesk and StainChair.

Type-Based Transitions​

In our example, each task is unique. But imagine a factory with many tasks that use the same setup. For example, painting 10 red items and 10 blue items—switching from red to blue requires cleaning, but consecutive red items don't.

OptalCP supports type-based transitions: you assign a type to each interval, and the transition matrix uses types instead of individual tasks:

# Example: tasks have types (0=red, 1=blue)
types = [0, 0, 1, 0, 1, 1, 0]  # 7 tasks with different colors
seq = model.sequence_var(intervals, types=types)

# Transition matrix is 2x2 (one entry per type pair)
transitions = [
    [0, 15],   # From red to: red, blue
    [15, 0],   # From blue to: red, blue
]
model.no_overlap(seq, transitions)

This is much more compact when you have many tasks of the same type.

Querying Sequence Position​

You can also query a task's position in the sequence using position(). This returns an integer expression:

# Position of stain_desk in the spray booth sequence (0, 1, or 2)
position = spray_booth_seq.position(stain_desk)

# You can use this in constraints, e.g., "StainDesk must be first"
model.enforce(position == 0)

Positions are numbered from 0. If an interval is absent (optional and not executed), its position is also absent.

What We Learned​

In this chapter, we:

  • Created a sequence variable to track task ordering on a resource
  • Specified transition times using a square matrix
  • Let the solver choose the optimal sequence to minimize makespan
  • Understood how type-based transitions work for larger problems

Transition times matter in manufacturing (machine setup), vehicle routing (travel time), and many other domains.

See Also​

Next Steps​

Next, we'll explore optional intervals and the alternative constraint: what if we can choose between different ways to perform a task?

Continue to: Alternative Constraints →