title: "Job Scheduling" description: "Use CP-SAT to solve job scheduling problems, including machine allocation, sequence dependencies, and due date constraints." order: 2

Job Scheduling

Problem Description

Imagine you run a factory with 3 machines and 8 jobs to process. Each job requires a specific machine, a specific processing time, and some jobs have precedence relationships. How do you schedule everything to complete all jobs in the shortest possible time?

from ortools.sat.python import cp_model
import matplotlib.pyplot as plt

# === Define Jobs ===
# (JobID, MachineID, Duration)
jobs = [
    (0, 0, 3),  # Job 0, needs machine 0 for 3 hours
    (1, 1, 2),  # Job 1, needs machine 1 for 2 hours
    (2, 2, 5),  # Job 2, needs machine 2 for 5 hours
    (3, 0, 4),  # Job 3, needs machine 0 for 4 hours
    (4, 1, 3),  # Job 4, needs machine 1 for 3 hours
    (5, 2, 2),  # Job 5, needs machine 2 for 2 hours
    (6, 0, 2),  # Job 6, needs machine 0 for 2 hours
    (7, 1, 4),  # Job 7, needs machine 1 for 4 hours
]

# Precedence constraints: (JobA, JobB) means A must finish before B starts
precedences = [(0, 3), (1, 4), (2, 5)]

num_machines = 3
# Jobs on each machine
machine_jobs = {m: [] for m in range(num_machines)}
for jid, mid, dur in jobs:
    machine_jobs[mid].append((jid, dur))

# === Build Model ===
model = cp_model.CpModel()

horizon = sum(dur for _, _, dur in jobs)
start_times = {}
end_times = {}
intervals = {}

for jid, mid, dur in jobs:
    start = model.NewIntVar(0, horizon, f"start_{jid}")
    end = model.NewIntVar(0, horizon, f"end_{jid}")
    interval = model.NewIntervalVar(start, dur, end, f"interval_{jid}")
    start_times[jid] = start
    end_times[jid] = end
    intervals[jid] = interval

# Constraint: jobs on same machine cannot overlap
for m in range(num_machines):
    model.AddNoOverlap([intervals[jid] for jid, _ in machine_jobs[m]])

# Constraint: precedence order
for before, after in precedences:
    model.Add(start_times[after] >= end_times[before])

# Objective: minimize makespan (max completion time)
makespan = model.NewIntVar(0, horizon, "makespan")
model.AddMaxEquality(makespan, [end_times[jid] for jid, _, _ in jobs])
model.Minimize(makespan)

# === Solve ===
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"
=== Scheduling Results ===")
    print(f"Min Makespan: {solver.ObjectiveValue()}")

    result = []
    for jid, mid, dur in jobs:
        s = solver.Value(start_times[jid])
        e = solver.Value(end_times[jid])
        print(f"Job {jid} (Machine {mid}, {dur}h): {s} -> {e}")
        result.append((jid, mid, dur, s, e))

    # Draw Gantt chart
    fig, ax = plt.subplots(figsize=(12, 6))
    colors = ['#FF6B6B', '#4ECDC4', '#45B7D1', '#96CEB4', '#FFEAA7',
              '#DDA0DD', '#98D8C8', '#F7DC6F']

    for i, (jid, mid, dur, s, e) in enumerate(result):
        ax.barh(mid, e - s, left=s, height=0.5, color=colors[i],
                edgecolor='black', label=f"Job {jid}")
        ax.text((s + e) / 2, mid, f"J{jid}", ha='center', va='center',
                fontweight='bold', fontsize=10)

    ax.set_yticks(range(num_machines))
    ax.set_yticklabels([f"Machine {m}" for m in range(num_machines)])
    ax.set_xlabel("Time")
    ax.set_title("Job Scheduling Gantt Chart")
    ax.grid(True, alpha=0.3)
    plt.tight_layout()
    plt.show()
else:
    print("No solution found")

Scheduling: Assigning the Right Work to the Right People

Job scheduling is a problem you solve every day without realizing it:

Factory Scheduling: 3 machines, 5 orders, each order requires specific operations. How to arrange for fastest completion?
Staff Scheduling: 10 employees, 7-day schedule, each has shift preferences. How to satisfy everyone?
Cloud Task Orchestration: 100 batch tasks, 20 servers. How to minimize total completion time?

These are all scheduling problems - and CP-SAT is Google OR-Tools core solver for these problems.

Key Elements of Scheduling Problems

Next Chapter: From Single to Multiple Resources

Single-machine scheduling has only one resource type. The next chapter Multi-Knapsack Problem introduces multiple resource constraints - closer to real-world complex problems.

Job Scheduling with CP-SAT

from ortools.sat.python import cp_model

def job_scheduling(jobs, num_machines):
    """
    Schedule jobs on machines to minimize makespan (completion time).
    
    Args:
        jobs: list of (duration, machine) tuples
        num_machines: number of parallel machines
    """
    model = cp_model.CpModel()
    horizon = sum(job[0] for job in jobs)  # upper bound

    # Variables
    start_times = [model.NewIntVar(0, horizon, f"start_{i}") for i in range(len(jobs))]
    end_times = [model.NewIntVar(0, horizon, f"end_{i}") for i in range(len(jobs))]
    intervals = []

    for i, (duration, machine) in enumerate(jobs):
        interval = model.NewIntervalVar(
            start_times[i], duration, end_times[i], f"interval_{i}"
        )
        intervals.append((interval, machine))

    # Each machine can only process one job at a time
    for m in range(num_machines):
        machine_intervals = [inv for inv, mac in intervals if mac == m]
        if len(machine_intervals) > 1:
            model.AddNoOverlap(machine_intervals)

    # Objective: minimize makespan (latest end time)
    makespan = model.NewIntVar(0, horizon, "makespan")
    model.AddMaxEquality(makespan, end_times)
    model.Minimize(makespan)

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

    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f"Makespan: {solver.Value(makespan)}")
        for i in range(len(jobs)):
            print(f"  Job {i}: start={solver.Value(start_times[i])}, "
                  f"end={solver.Value(end_times[i])}, "
                  f"duration={jobs[i][0]}, machine={jobs[i][1]}")
        return solver.Value(makespan)
    else:
        print("No solution found")
        return None

# Example: 6 jobs, 2 machines
jobs = [
    (3, 0),  # Job 0: duration 3, machine 0
    (4, 1),  # Job 1: duration 4, machine 1
    (2, 0),  # Job 2: duration 2, machine 0
    (5, 1),  # Job 3: duration 5, machine 1
    (3, 0),  # Job 4: duration 3, machine 0
    (2, 1),  # Job 5: duration 2, machine 1
]

job_scheduling(jobs, 2)

Real-World Applications

| Domain | Scheduling Problem | |--------|-------------------| | Manufacturing | Assign production orders to factory lines | | Cloud Computing | Schedule batch jobs on server clusters | | Healthcare | Schedule surgeries, appointments, staff shifts | | Transportation | Schedule deliveries, flights, train departures | | Education | Assign courses to rooms, schedule exams | | Event Planning | Schedule talks, sessions, and breaks at conferences | | Construction | Schedule tasks, workers, and equipment to phases |

Comparison with Other Approaches

| Method | Optimal? | Speed | Complexity | |--------|----------|-------|------------| | CP-SAT | ✅ Yes | Slower for large instances | Easy to model constraints | | Greedy (Earliest Deadline) | ❌ No | Very fast | Simple to implement | | Genetic Algorithm | ❌ No | Medium | Complex setup, good for large | | MILP (PuLP/CBC) | ✅ Yes | Similar to CP-SAT | Harder to model time constraints |

Summary

Job scheduling assigns tasks to machines to minimize total completion time (makespan) while respecting machine capacity constraints. Use CP-SAT for optimal solutions, greedy heuristics for fast approximations, and genetic algorithms for very large instances.

Key takeaways:

Scheduling = assign jobs to machines over time
Makespan = time when the last job finishes
CP-SAT uses IntervalVar for tasks and AddNoOverlap for resource constraints
Each machine processes one job at a time (no overlap)
Objective: minimize makespan (or maximize throughput, meet deadlines)
Real applications: manufacturing, cloud computing, healthcare, logistics
For large instances: use greedy heuristics or metaheuristics
Always consider: due dates, precedences, machine eligibility

What's Next: Algorithm — Graph Search

The next course covers graph search algorithms — BFS, DFS, Dijkstra, and A* for pathfinding and network traversal.