Simulated Annealing for the Job Shop Scheduling Problem

Simulated annealing is a metaheuristic optimization technique inspired by the process of annealing in metallurgy. In the context of the JSSP, it’s used to find a schedule that minimizes a certain objective, typically the makespan (the total time required to complete all jobs).

The process can be summarized as follows:

  1. Start with an initial solution: We begin with a valid, but likely suboptimal, schedule. This initial solution can be generated using a simple heuristic, like a dispatching rule.

  2. Define an “energy” function: In our case, the energy of a schedule is its makespan, plus penalties for any violated constraints (like deadlines). A lower energy means a better solution.

  3. Iteratively explore neighbors: The algorithm then iteratively explores “neighboring” solutions. A neighbor is a new schedule created by making a small change to the current one, for example, by swapping the order of two operations on a single machine.

  4. Accept or reject new solutions:

    • If the neighbor solution has a lower energy (is better), it is always accepted as the new current solution.

    • If the neighbor solution has a higher energy (is worse), it might still be accepted with a certain probability. This probability is higher at the beginning (when the “temperature” is high) and decreases over time. This allows the algorithm to escape local optima and explore a wider range of solutions.

  5. Cooling down: The “temperature” gradually decreases, reducing the probability of accepting worse solutions. The process stops when the system has “cooled down” (the temperature is low) or after a certain number of iterations.

Core Components

The implementation is structured into a few key components:

  • ``SimulatedAnnealingSolver``: This is the main high-level solver class that you will interact with. It wraps the core annealing logic and provides a simple solve method.

  • ``JobShopAnnealer``: This is a helper class that inherits from the simanneal library’s Annealer class. It implements the core simulated annealing logic, including the move and energy functions.

  • Neighbor Generators: These are functions that define how to create a “neighbor” schedule from a current one.

  • Objective Functions: The energy function calculates the objective value of a schedule, which is typically the makespan plus any penalties for constraint violations.

The SimulatedAnnealingSolver

This is the main entry point for using the solver. When you create an instance of this class, you can configure various parameters of the annealing process:

  • initial_temperature (Tmax): The starting temperature. A higher value increases the initial probability of accepting worse solutions.

  • ending_temperature (Tmin): The final temperature. The algorithm stops when it approaches this temperature.

  • steps: The total number of iterations to run.

  • neighbor_generator: The function used to generate neighboring solutions. The default is swap_in_critical_path.

  • seed: A random seed for reproducibility.

Neighbor Generation Strategies

A key part of the simulated annealing process is how you explore the solution space by moving from one solution to a “neighbor”. This implementation provides three different neighbor generation strategies in _neighbor_generators.py:

  1. ``swap_adjacent_operations``: This function randomly selects a machine and swaps two adjacent operations in its sequence. This is a very localized search.

  2. ``swap_random_operations``: This function randomly selects a machine and swaps two random operations in its sequence. This allows for larger jumps in the solution space compared to adjacent swaps.

  3. ``swap_in_critical_path`` (Default): This is the most sophisticated of the three. It identifies the critical path of the current schedule (the sequence of operations that determines the makespan) and looks for consecutive operations on that path that are on the same machine. It then swaps one of these pairs. The idea is that modifying the critical path is the most direct way to try to reduce the makespan. If no such pair exists, it falls back to a standard adjacent swap.

The Objective Function

The objective function is what the simulated annealing algorithm tries to minimize. In the context of job shop scheduling, this is typically the makespan (the total time to complete all jobs) plus any penalties for violating constraints (like deadlines).

Examples

Here are some examples of how to use the solver.

Basic Usage

This example shows how to solve a benchmark instance (“ft06”) with a specific seed to get a reproducible result.

[1]:

from job_shop_lib.benchmarking import load_benchmark_instance
from job_shop_lib.metaheuristics import SimulatedAnnealingSolver


ft06_instance = load_benchmark_instance("ft06")

solver = SimulatedAnnealingSolver(
    seed=42,  # Seed for reproducibility
    initial_temperature=10,  # Low temperature --> more greedy search
    steps=1000,  # The number of schedules to try before stopping
    updates=100,  # How often the display table is updated
)

schedule = solver.solve(ft06_instance)
makespan = schedule.makespan()
print(f"The makespan found for ft06 is: {makespan}")

 Temperature        Energy    Accept   Improve     Elapsed   Remaining
     2.50000         60.00    70.00%    20.00%     0:00:00     0:00:00

The makespan found for ft06 is: 55

Using a Different Neighbor Generator

Although it’s not recommended, you can easily plug in a different neighbor generation strategy by passing it to the SimulatedAnnealingSolver’s constructor. Here’s how to use swap_adjacent_operations:

[2]:

from job_shop_lib.metaheuristics import swap_adjacent_operations

# This time, we specify a different neighbor generator
solver_adj_swap = SimulatedAnnealingSolver(
    seed=42,
    initial_temperature=10,
    steps=1000,
    updates=100,
    neighbor_generator=swap_adjacent_operations,
)

schedule_adj_swap = solver_adj_swap.solve(ft06_instance)
makespan_adj_swap = schedule_adj_swap.makespan()
print(f"The makespan for ft06 with adjacent swaps is: {makespan_adj_swap}")

 Temperature        Energy    Accept   Improve     Elapsed   Remaining
     2.50000         67.00   100.00%    20.00%     0:00:01     0:00:00

The makespan for ft06 with adjacent swaps is: 61

Similarly, you can use swap_random_operations:

[3]:

from job_shop_lib.metaheuristics import swap_random_operations

solver_rand_swap = SimulatedAnnealingSolver(
    seed=42,
    initial_temperature=10,
    steps=1000,
    updates=100,
    neighbor_generator=swap_random_operations,
)
schedule_rand_swap = solver_rand_swap.solve(ft06_instance)
makespan_rand_swap = schedule_rand_swap.makespan()
print(f"The makespan for ft06 with random swaps is: {makespan_rand_swap}")

 Temperature        Energy    Accept   Improve     Elapsed   Remaining
     2.50000         70.00    50.00%     0.00%     0:00:04     0:00:00

The makespan for ft06 with random swaps is: 61

In both cases, the algorithm doesn’t find a better solution than the starting one (found with the Most Work Remaining dispatching rule). Additionally, while using these alternative neighbor generators, you may notice that each step takes longer to compute. This happens because swapping operations randomly often results in unfeasible schedules. If the schedule is invalid, the neighbor generator will try again until it finds a valid neighbor.

We allow the possibility of customizing the neighbor generation strategy because for schedules with deadlines or due dates, the default swap_in_critical_path may not always yield the best results. In such cases, creating a custom neighbor generator that swaps operations that violate deadlines can be beneficial.

Handling Deadlines

In this section we illustrate how simulated annealing can improve a schedule when deadlines are present.

We will:

  1. Generate a random 6x6 instance (6 jobs, 6 machines) with operation deadlines using the generation module.

  2. Build a baseline schedule with a dispatching rule (Most Work Remaining, for example).

  3. Count deadline violations in the baseline schedule.

  4. Use the SimulatedAnnealingSolver with a penalty-aware objective to reduce (ideally eliminate) violations. This may increase makespan but satisfies constraints.

  5. Compare before/after metrics (violations, makespan, objective value).

Deadlines here are synthetic: for each job we accumulate processing times and assign each operation a deadline = cumulative_duration * 2 (rounded with ceil). You can adapt the strategy for your domain.

Below we first construct the instance and a baseline schedule, then run Simulated Annealing that explicitly penalizes deadline violations. A large penalty coefficient strongly biases the search toward feasibility (meeting deadlines) even at the cost of a longer makespan.

[ ]:

# Deadlines example: baseline vs simulated annealing
import math
from job_shop_lib.generation import (
    modular_instance_generator,
    get_default_machine_matrix_creator,
    get_default_duration_matrix_creator,
)
from job_shop_lib.dispatching.rules import (
    DispatchingRuleSolver,
    most_work_remaining_rule,
)
from job_shop_lib.metaheuristics import (
    SimulatedAnnealingSolver,
    get_makespan_with_penalties_objective,
)
from job_shop_lib.constraint_programming import ORToolsSolver
from job_shop_lib.exceptions import NoSolutionFoundError

# 1. Create a 6x6 instance (fixed size) with synthetic deadlines
SEED = 123
NUM_JOBS = 6
NUM_MACHINES = 6

machine_creator = get_default_machine_matrix_creator(
    size_selector=lambda rng: (NUM_JOBS, NUM_MACHINES),
    with_recirculation=False,
)
# Durations between 2 and 15 to have some variability
duration_creator = get_default_duration_matrix_creator((2, 15))


def deadlines_creator(duration_matrix, rng):
    deadlines: list[list[int]] = []
    for job_row in duration_matrix:
        cum = 0
        row = []
        for d in job_row:
            cum += d
            # 100% slack factor
            row.append(math.ceil(cum * 2))
        deadlines.append(row)
    return deadlines


instance_gen = modular_instance_generator(
    machine_matrix_creator=machine_creator,
    duration_matrix_creator=duration_creator,
    deadlines_matrix_creator=deadlines_creator,
    seed=SEED,
)
for i, instance in enumerate(instance_gen):
    # Compute a (near) perfect solution via CP-SAT for comparison
    cp_solver = ORToolsSolver()
    try:
        perfect_schedule = cp_solver.solve(instance)
        break
    except NoSolutionFoundError:
        print(f"Instance {i} has no feasible solution, retrying...")
print(instance)

# 2. Baseline schedule with a dispatching rule
baseline_solver = DispatchingRuleSolver(
    dispatching_rule=most_work_remaining_rule
)
baseline_schedule = baseline_solver.solve(instance)

# Helper: count deadline violations


def count_deadline_violations(schedule):
    violations = 0
    for machine_sched in schedule.schedule:
        for s_op in machine_sched:
            op = s_op.operation
            if op.deadline is not None and s_op.end_time > op.deadline:
                violations += 1
    return violations


baseline_makespan = baseline_schedule.makespan()
baseline_violations = count_deadline_violations(baseline_schedule)
print(f"Baseline makespan: {baseline_makespan}")
print(f"Baseline deadline violations: {baseline_violations}")

# Perfect (CP) reference
perfect_makespan = perfect_schedule.makespan()
perfect_violations = count_deadline_violations(perfect_schedule)
print(f"Optimal (CP-SAT) makespan: {perfect_makespan}")
print(f"Optimal (CP-SAT) deadline violations: {perfect_violations}")

# 3. Simulated Annealing with penalty-aware objective
objective = get_makespan_with_penalties_objective(
    deadline_penalty_factor=10_000  # large => prioritize feasibility
)
sa_solver = SimulatedAnnealingSolver(
    seed=SEED,
    initial_temperature=30_000,  # moderate starting temperature
    ending_temperature=5,  # cool down
    steps=10_000,  # reasonable effort for tutorial
    updates=10,
    objective_function=objective,
)

improved_schedule = sa_solver.solve(instance, initial_state=baseline_schedule)
improved_makespan = improved_schedule.makespan()
improved_violations = count_deadline_violations(improved_schedule)

# Objective values (makespan + penalties)
baseline_objective = objective(baseline_schedule)
improved_objective = objective(improved_schedule)
perfect_objective = objective(perfect_schedule)

print("\nAfter Simulated Annealing:")
print(f"Improved makespan: {improved_makespan}")
print(f"Improved deadline violations: {improved_violations}")
print(f"Improved objective (makespan + penalties): {improved_objective}")

# 4. Comparative summary vs baseline and optimal
print("\nComparative Summary:")
print(f"Baseline objective: {baseline_objective}")
print(f"Optimal (CP-SAT) objective: {perfect_objective}")
print(
    f"Delta Baseline -> SA objective: {improved_objective - baseline_objective}"
)
print(
    f"Delta SA -> Optimal objective: {improved_objective - perfect_objective}"
)
print(
    f"Delta Baseline -> SA makespan: {improved_makespan - baseline_makespan}"
)
print(f"Delta SA -> Optimal makespan: {improved_makespan - perfect_makespan}")

if improved_violations < baseline_violations:
    print("Deadline violations reduced ✅")
elif improved_violations == baseline_violations:
    print("No change in deadline violations")
else:
    print("More violations (unexpected if penalty large)")

if improved_violations == 0 and baseline_violations > 0:
    print("All deadlines met after annealing (feasible schedule obtained).")

if perfect_violations == 0 and improved_violations > 0:
    print(
        "Note: CP-SAT met all deadlines while SA still has violations — consider higher penalty or more steps."
    )

 Temperature        Energy    Accept   Improve     Elapsed   Remaining
  5266.12307      10084.00    43.80%    21.50%     0:00:00     0:00:01

JobShopInstance(name=generated_instance_0, num_jobs=6, num_machines=6)
Baseline makespan: 86
Baseline deadline violations: 9
Optimal (CP-SAT) makespan: 84
Optimal (CP-SAT) deadline violations: 0

     5.00000      10084.00     0.00%     0.00%     0:00:01     0:00:00


After Simulated Annealing:
Improved makespan: 84
Improved deadline violations: 0
Improved objective (makespan + penalties): 84.0

Comparative Summary:
Baseline objective: 90086.0
Optimal (CP-SAT) objective: 84.0
Delta Baseline -> SA objective: -90002.0
Delta SA -> Optimal objective: 0.0
Delta Baseline -> SA makespan: -2
Delta SA -> Optimal makespan: 0
Deadline violations reduced ✅
All deadlines met after annealing (feasible schedule obtained).

Note that, in this case, we needed to use a higher initial temperature to effectively explore the solution space and reduce deadline violations. Otherwise, because of the high penalty, very few solutions would be accepted, hindering the search process. In general, the more violations we expect, the higher the initial temperature should be to allow the algorithm to explore a wider range of solutions.