job_shop_lib.metaheuristics¶

Metaheuristic algorithms for solving job shop scheduling problems.

This module provides implementations of various metaheuristic optimization algorithms designed to solve the job shop scheduling problem.

Metaheuristics are particularly well-suited for JSSP due to their ability to:

Handle large solution spaces efficiently
Escape local optima through stochastic mechanisms
Balance exploration and exploitation of the search space
Provide good quality solutions within reasonable computational time

Currently implemented algorithms:

Simulated annealing: A probabilistic technique that accepts worse solutions with decreasing probability to escape local optima

The module aims to contain implementations of other metaheuristic algorithms such as genetic algorithms, particle swarm optimization, tabu search, etc. Feel free to open an issue if you want to contribute!

`JobShopAnnealer`	Helper class for the `SimulatedAnnealingSolver`.
`SimulatedAnnealingSolver`	Wraps the `JobShopAnnealer` to follow the :class`~job_shop_lib.BaseSolver` interface.
`NeighborGenerator`	alias of `Callable`[[`Schedule`, `Random`], `Schedule`]
`swap_adjacent_operations`	Generates a neighbor schedule by swapping two adjacent operations.
`swap_in_critical_path`	Generates a neighbor by targeting swaps on the critical path.
`swap_random_operations`	Generates a neighbor schedule by swapping two random operations.
`ObjectiveFunction`	alias of `Callable`[[`Schedule`], `float`]
`get_makespan_with_penalties_objective`	Builds an objective function that returns the makespan plus penalties.
`compute_penalty_for_deadlines`	Compute the total penalty for deadline violations in a schedule.
`compute_penalty_for_due_dates`	Compute the total penalty for due date violations in a schedule.

class JobShopAnnealer(instance, initial_state, *, seed=None, neighbor_generator=<function swap_in_critical_path>, objective_function=None)[source]¶

Bases: Annealer

Helper class for the SimulatedAnnealingSolver.

It uses simanneal as the backend.

In the context of the job shop scheduling problem, simulated annealing is particularly useful for improving previous solutions.

The neighbor move is pluggable via a neighbor_generator function. By default it uses swap_in_critical_path(), but any function that takes a schedule and a random generator and returns a new schedule can be provided to tailor the exploration of the search space.

The process involves iteratively exploring the solution space:

A random move is made to alter the current state. This is done by swapping two operations in the sequence of a machine.
The "energy" of the new state is evaluated using an objective function. With the default objective function, the energy is calculated as the makespan of the schedule plus penalties for any constraint violations (such as deadlines and due dates). See get_makespan_with_penalties_objective() for details. You can create custom objective functions by implementing the ObjectiveFunction interface, which takes a schedule and returns a float representing the energy of that schedule.
The new state is accepted if it has lower energy (a better solution). If it has higher energy, it might still be accepted with a certain probability, which depends on the current "temperature". The temperature decreases over time, reducing the chance of accepting worse solutions as the algorithm progresses. This helps to avoid getting stuck in local optima.

This is repeated until the solution converges or a maximum number of steps is reached.

Tuning the annealer is crucial for performance. The base simanneal.Annealer class provides parameters that can be adjusted:

Tmax: Maximum (starting) temperature (default: 25000.0).
Tmin: Minimum (ending) temperature (default: 2.5).
steps: Number of iterations (default: 50000).
updates: Number of progress updates (default: 100).

A good starting point is to set Tmax to a value that accepts about 98% of moves and Tmin to a value where the solution no longer improves. The number of steps should be large enough to explore the search space thoroughly.

These parameters can be set on the annealer instance. For example: annealer.Tmax = 12000.0

Alternatively, this class provides an auto method to find reasonable parameters based on a desired runtime: auto_schedule = annealer.auto(minutes=1) annealer.set_schedule(auto_schedule)

instance¶: The job shop instance to solve.

random_generator¶: Random generator for reproducibility.

neighbor_generator¶: Function used to generate neighbors from the current schedule. Defaults to swap_in_critical_path().

objective_function¶: Function that computes the energy of the schedule. If None, it defaults to get_makespan_with_penalties_objective(). This function receives a schedule and returns the energy that will be minimized by the annealer.

Parameters:

instance (JobShopInstance) -- The job shop instance to solve. It retrieves the jobs and machines from the instance and uses them to create the schedule.
initial_state (Schedule) -- Initial state of the schedule as a list of lists, where each sublist represents the operations of a job.
seed (int | None) -- Random seed for reproducibility. If None, random behavior will be non-deterministic.
neighbor_generator (Callable[[Schedule, Random], Schedule]) -- Function that receives the current schedule and a random generator and returns a new schedule to explore. Defaults to swap_in_critical_path(). Use this to plug in custom neighborhoods (e.g., adjacent swaps).
objective_function (Callable[[Schedule], float] | None) -- Function that computes the energy of the schedule. If None, it defaults to get_makespan_with_penalties_objective(). This callable receives a Schedule and returns a float that will be minimized by the annealer.

copy_strategy = 'method'¶

move()[source]¶

Generates a neighbor state using the configured neighbor generator.

Delegates to self.neighbor_generator with the current schedule and the internal random generator, enabling pluggable neighborhoods.

Return type:: None

anneal()[source]¶

Minimizes the energy of a system by simulated annealing.

Overrides the anneal method from the base class to use the random generator defined in the constructor.

Returns:: The best state and energy found during the annealing process.
Return type:: tuple[Schedule, float]

energy()[source]¶

Computes the energy of the current schedule using the objective function provided.

Return type:: float

class SimulatedAnnealingSolver(*, initial_temperature=25000, ending_temperature=2.5, steps=50000, updates=100, objective_function=None, seed=None, neighbor_generator=<function swap_in_critical_path>)[source]¶

Bases: BaseSolver

Wraps the JobShopAnnealer to follow the :class`~job_shop_lib.BaseSolver` interface.

See also

See the documentation of the JobShopAnnealer class for more details on the annealing process.

initial_temperature¶: Initial temperature for the annealing process. It controls the probability of accepting worse solutions. That sets the metropolis criterion. Corresponds to the tmax parameter in the annealer.

ending_temperature¶: Ending temperature for the annealing process. It controls when to stop accepting worse solutions. Corresponds to the tmin parameter in the annealer.

steps¶: Number of steps to perform in the annealing process. This is the number of iterations the algorithm will run.

updates¶: The number of progress updates to print during the annealing process. Set to 0 to disable updates.

seed¶: Random seed for reproducibility. If None, random behavior will be non-deterministic.

Parameters:

initial_temperature (float) -- Initial temperature for the annealing process. It controls the probability of accepting worse solutions. That sets the metropolis criterion. Corresponds to the tmax parameter in the annealer.
ending_temperature (float) -- Ending temperature for the annealing process. It controls when to stop accepting worse solutions. Corresponds to the tmin parameter in the annealer.
steps (int) -- Number of steps to perform in the annealing process. This is the number of iterations the algorithm will run.
updates (int) -- The number of progress updates to print during the annealing process. Set to 0 to disable updates.
seed (int | None) -- Random seed for reproducibility. If None, random behavior will be non-deterministic.
objective_function (Callable[[Schedule], float] | None)
neighbor_generator (Callable[[Schedule, Random], Schedule])

setup_annealer(instance, initial_state=None)[source]¶

Initializes the annealer with the given instance and initial state.

Parameters:

instance (JobShopInstance) -- The job shop instance to solve.
initial_state (Schedule | None) -- Initial state of the schedule as a list of lists, where each sublist represents the operations of a job.

Return type:

None

solve(instance, initial_state=None)[source]¶

Solves the given Job Shop Scheduling problem using simulated annealing.

Parameters:

instance (JobShopInstance) -- The job shop problem instance to solve.
initial_state (Schedule | None) -- Initial job sequences for each machine. A job sequence is a list of job ids. Each list of job ids represents the order of operations on the machine. The machine that the list corresponds to is determined by the index of the list. If None, the solver will generate an initial state using the DispatchingRuleSolver.

Returns:

The best schedule found.

Return type:

Schedule

swap_adjacent_operations(schedule, random_generator=None)[source]¶

Generates a neighbor schedule by swapping two adjacent operations.

Selects a machine at random with at least two operations and swaps a pair of adjacent operations in its sequence. Internally tries several times to produce a valid neighbor; if none is found, the original schedule is returned.

Parameters:

schedule (Schedule) -- Current schedule to perturb.
random_generator (Random | None) -- Source of randomness. If None, a new generator is created.

Returns:

A valid neighbor schedule with one adjacent swap applied, or the original schedule if no valid swap is found.

Return type:

Schedule

swap_in_critical_path(schedule, random_generator=None)[source]¶

Generates a neighbor by targeting swaps on the critical path.

This operator focuses on pairs of consecutive scheduled operations along the current critical path that share the same machine. Swapping such operations directly perturbs the longest-duration chain of precedence and resource constraints that determines the makespan.

Why target the critical path:

The makespan is the length of the critical path; operations not on it typically have slack, so reordering them often does not improve the objective. By contrast, modifying machine order on the critical path can shorten the longest path or unlock constraints that reduce blocking and idle times.
Swapping consecutive critical operations on the same machine always results in a feasible schedule.

Behavior:

Identifies all consecutive pairs on the critical path that run on the same machine and swaps one of them at random.
If no such pairs exist, it falls back to a standard adjacent swap.

Parameters:

schedule (Schedule) -- Current schedule to perturb.
random_generator (Random | None) -- Source of randomness. If None, a new generator is created.

Returns:

A valid neighbor schedule that prioritizes swaps on the critical path, or a neighbor produced by an adjacent swap fallback when none applies.

Return type:

Schedule

swap_random_operations(schedule, random_generator=None)[source]¶

Generates a neighbor schedule by swapping two random operations.

Selects a machine at random with at least two operations and swaps two randomly chosen positions in its sequence. Internally tries several times to produce a valid neighbor; if none is found, the original schedule is returned.

Parameters:

schedule (Schedule) -- Current schedule to perturb.
random_generator (Random | None) -- Source of randomness. If None, a new generator is created.

Returns:

A valid neighbor schedule with one random swap applied, or the original schedule if no valid swap is found.

Return type:

Schedule

get_makespan_with_penalties_objective(deadline_penalty_factor=1000000, due_date_penalty_factor=100)[source]¶

Builds an objective function that returns the makespan plus penalties.

This factory returns a callable that evaluates a Schedule as the sum of its makespan and penalties for violating operation-level deadlines and due dates.

Penalties are applied per scheduled operation that finishes after its corresponding attribute value:

Deadline violation: adds deadline_penalty_factor once per violating operation (hard constraint surrogate).
Due date violation: adds due_date_penalty_factor once per violating operation (soft constraint surrogate).

Parameters:

deadline_penalty_factor (float) -- Cost added for each operation that finishes after its deadline. Defaults to 1_000_000.
due_date_penalty_factor (float) -- Cost added for each operation that finishes after its due date. Defaults to 100.

Returns:

A function f(schedule) -> float that computes schedule.makespan() + penalty.

Return type:

Callable[[Schedule], float]

Notes

Deadlines and due dates are taken from each operation. If an operation does not define the attribute (None), no penalty is applied for that attribute.
If the instance has neither deadlines nor due dates, the objective is simply the makespan.

compute_penalty_for_deadlines(schedule, penalty_per_violation)[source]¶

Compute the total penalty for deadline violations in a schedule.

Parameters:

schedule (Schedule) -- The schedule to evaluate.
penalty_per_violation (float) -- The penalty to apply for each operation that finishes after its deadline.

Returns:

The total penalty for deadline violations.

Return type:

float

compute_penalty_for_due_dates(schedule, penalty_per_violation)[source]¶

Compute the total penalty for due date violations in a schedule.

Parameters:

schedule (Schedule) -- The schedule to evaluate.
penalty_per_violation (float) -- The penalty to apply for each operation that finishes after its due date.

Returns:

The total penalty for due date violations.

Return type:

float