🧩 Constraint Solving POTD:Problem of the Day: Real-Time Constraint-Based Scheduling

[github-actions[bot]]

Problem Statement

Imagine you're managing a small manufacturing facility with 4 machines and 6 jobs. Each job must be processed on exactly one machine in a fixed sequence of stages. Jobs arrive dynamically, and you need to assign each to a machine before knowing future arrivals. The challenge: minimize lateness (how late each job finishes vs. its deadline) while respecting machine capacity and setup times between jobs.

Concrete Instance

Job	Arrival Time	Processing Time	Deadline	Required Machine Sequence
J1	0	3	15	M1 → M2
J2	2	2	18	M1 → M3
J3	4	4	20	M2 → M3 → M1
J4	5	2	22	M1 → M2
J5	7	3	25	M3 → M1
J6	9	2	24	M2 → M1

Setup times between any two different jobs on the same machine: 1 time unit.

Objective: Minimize total lateness = Σ max(0, completion_time - deadline) for all jobs.

---

Why It Matters

Manufacturing & semiconductors: Fabs and job shops must schedule production runs subject to machine constraints and due dates—late shipments cost money and customers.

Cloud computing: Data center job schedulers balance workload across servers with dynamic arrivals; delays directly impact service-level agreements (SLAs).

Emergency services: Dispatchers allocate ambulances, fire trucks, and personnel to calls in real time, with completion deadlines and heterogeneous capabilities.

Robotics & autonomous systems: Mobile manipulators must plan task sequences reactively while honoring time and resource constraints.

Real-time scheduling is foundational to operational efficiency everywhere—and the moment new jobs arrive, static solutions break down. That's what makes this problem live.

---

Modeling Approaches

Approach 1: Classical Constraint Programming (CP) with Temporal Constraints

Paradigm: Constraint Programming with scheduling global constraints.

Key variables:

• start[j, k] = start time of job j on its k-th machine (continuous or integer)
• end[j, k] = completion time of job j on machine m
• lateness[j] = max(0, end[j, last] - deadline[j])

Key constraints:

1. Precedence (job must complete stage k before starting k+1):
   end[j, k] + setup_time ≤ start[j, k+1]

2. Machine capacity (no two jobs overlap on same machine):
   For all pairs of jobs (j1, j2) on machine m:
     OR( end[j1, k] + setup ≤ start[j2, k],
         end[j2, k] + setup ≤ start[j1, k] )

3. Arrival constraint (can't start before arrival):
   start[j, 0] ≥ arrival[j]

4. Lateness definition:
   lateness[j] ≥ end[j, num_stages[j]] - deadline[j]
   lateness[j] ≥ 0

Objective: Minimize Σ lateness[j]

Strengths:

• Global constraints (e.g., cumulative, no_overlap) encode machine constraints efficiently with strong propagation.
• Easy to add new constraints (e.g., job precedence, maintenance windows).
• Adaptive search can handle dynamic arrivals by incrementally adding jobs and re-optimizing.

Weaknesses:

• Disjunctive constraints (job pairs) blow up search space quickly as jobs grow.
• Real-time response requires fast bounds; full re-optimization is slow.

---

Approach 2: Mixed-Integer Programming (MIP) with Big-M Formulation

Paradigm: Integer Linear Programming over binary assignment and timing variables.

Key variables:

• s[j, m] = start time of job j on machine m (continuous)
• x[j1, j2, m] ∈ {0, 1} = 1 if job j1 precedes job j2 on machine m
• lateness[j] ≥ 0

Key constraints:

1. Precedence between stages (if job j uses stage k then k+1):
   s[j, m_{k+1}] ≥ c[j, m_k] + setup

2. Machine sequencing (Big-M disjunction):
   s[j2, m] ≥ c[j1, m] + setup - M*(1 - x[j1,j2,m])
   s[j1, m] ≥ c[j2, m] + setup - M*x[j1,j2,m]
   where M is a large constant

3. One sequence per machine:
   For each unordered pair (j1, j2) on machine m:
     x[j1,j2,m] + x[j2,j1,m] ≤ 1  (or = 1 if both must use it)

4. Lateness:
   lateness[j] ≥ max_stage_end[j] - deadline[j]

Objective: Minimize Σ lateness[j]

Strengths:

• Powerful solvers (CPLEX, Gurobi) exploit LP relaxations for tight bounds.
• Industry-standard for offline/batch scheduling problems.
• Supports warm-starting: previous solution helps solver find next solution faster when jobs arrive incrementally.

Weaknesses:

• Big-M constants and binary variable count explode with problem size.
• Real-time response is harder; MIP solving is CPU-intensive.
• Less suitable for highly dynamic scenarios.

---

Example Model (OR-Tools Python)

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# Variables
num_jobs, num_machines = 6, 4
horizon = 100  # Max time

start = {}
end = {}
for j in range(num_jobs):
    for m in range(num_machines):
        start[(j,m)] = model.NewIntVar(0, horizon, f's_{j}_{m}')
        end[(j,m)] = model.NewIntVar(0, horizon, f'e_{j}_{m}')

lateness = [model.NewIntVar(0, horizon, f'late_{j}') 
            for j in range(num_jobs)]

# Constraints: job j1 completes before j2 on machine m
intervals = {}
for j in range(num_jobs):
    for m in range(num_machines):
        intervals[(j,m)] = model.NewIntervalVar(
            start[(j,m)], 2, end[(j,m)], f'iv_{j}_{m}')

# No overlap on any machine
for m in range(num_machines):
    model.AddNoOverlap([intervals[(j,m)] for j in range(num_jobs)])

# Precedence: job j must respect deadline lateness
for j in range(num_jobs):
    model.Add(lateness[j] >= end[(j, 0)] - 20)  # Simplified
    model.Add(lateness[j] >= 0)

# Objective
model.Minimize(sum(lateness))

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    print(f"Total lateness: {solver.ObjectiveValue()}")
    for j in range(num_jobs):
        print(f"Job {j}: lateness = {solver.Value(lateness[j])}")

This snippet uses OR-Tools' NoOverlap global constraint and interval variables, which encode both timing and machine assignment compactly.

---

Key Techniques

1. Shaving & Reduced Cost Fixing

In branch-and-bound search, pruning branches early is critical:

• Domain shaving: before branching on start[j,m], compute lower bounds on lateness assuming job j starts at each candidate time. If lateness + bound on remaining jobs exceeds incumbent, remove that value.
• Reduced-cost fixing: in MIP, if the dual LP solution shows a variable's cost to include it is too high, fix it to 0 without harming optimality.

These techniques are essential for real-time response—they shrink the search space before expensive search.

2. Cumulative & Global Constraint Propagation

The cumulative constraint captures machine capacity: resource demand over time must never exceed capacity. Modern solvers propagate this via:

• Edge-finding: if a set of jobs cannot fit before/after a particular job, they must be on the opposite side.
• Timetabling: domain values for start times are pruned by analyzing conflicts with fixed intervals.

These reduce variable domains dramatically, making search exponentially faster.

3. Online & Anytime Algorithms

For real-time scenarios, you cannot wait for optimality:

• Anytime search: run branch-and-bound with a time limit, returning the best solution found so far (incumbent bound).
• Rolling horizon: solve only the next k jobs in detail, commit the first few to the schedule, then re-optimize as new jobs arrive. This trades optimality for responsiveness.
• Greedy + local improvement: dispatch urgent jobs greedily, then repair with local search (e.g., swaps, insertions) to recover quality.

---

Challenge Corner

Can you design a symmetry-breaking strategy for this problem?

Notice that if two jobs have identical processing times, deadlines, and arrival times, the order in which they appear in a schedule is symmetric—swapping them gives an equally good solution. This symmetry can waste search effort exploring equivalent schedules.

• Can you add constraints that break this symmetry?
• Hint: consider lexicographic ordering on job pairs.
• How would you exploit machine symmetry (e.g., if all machines are identical)?

Bonus thought: In a real-time setting where jobs arrive online, how would you balance:

• Committing early assignments (to avoid thrashing), vs.
• Flexibility to accommodate future urgent jobs?

What if you allowed a small window for "uncommitted" jobs to be rescheduled if a high-priority job arrives?

---

References

1. Brucker, P. (2007). Scheduling Algorithms (5th ed.). Springer. – Classic reference on scheduling models and exact/approximation algorithms.

2. Vilím, P. (2011). "Global Constraints in Scheduling." In Handbook of Constraint Programming, chapters on scheduling. – Deep dive into constraint propagation for cumulative, edge-finding, and timetabling.

3. Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer Academic. – Practical CP modeling for real scheduling.

4. OR-Tools Scheduling Examples: (developers.google.com/redacted) – Hands-on tutorials and source code for job-shop and resource scheduling.

---

Ready to dig deeper? Constraint-based real-time scheduling is where CP shines: the expressiveness of constraints meets the urgency of live systems. Experiment with one of the reference implementations, tweak arrival times and deadlines, and watch how search strategies adapt!

Warning

Firewall blocked 1 domain

The following domain was blocked by the firewall during workflow execution:

• o205451.ingest.us.sentry.io

To allow these domains, add them to the network.allowed list in your workflow frontmatter:

network:
  allowed:
    - defaults
    - "o205451.ingest.us.sentry.io"

See Network Configuration for more information.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 6.72 AIC · ⌖ 7.54 AIC · ⊞ 6.1K · ◷

• expires on Oct 1, 2026, 3:35 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #63417.