job_shop_lib

Contains the main data structures and base classes.

Operation	Stores machine and duration information for a job operation.
JobShopInstance	Data structure to store a Job Shop Scheduling Problem instance.
ScheduledOperation	Data structure to store a scheduled operation.
Schedule	Data structure to store a complete or partial solution for a particular JobShopInstance.
Solver	alias of Callable[[JobShopInstance], Schedule]
BaseSolver	Base class for all solvers implemented as classes.

class Operation(machines, duration, release_date=0, deadline=None, due_date=None)

Bases: object

Stores machine and duration information for a job operation.

An operation is a task that must be performed on a machine. It is part of a job and has a duration that represents the time it takes to complete the task.

Tip

To use custom attributes, such as due dates or priorities, subclass this class and add the desired attributes.

Note

To increase performance, some solvers such as the CP-SAT solver use only integers to represent the operation's attributes. Should a problem involve operations with non-integer durations, it would be necessary to multiply all durations by a sufficiently large integer so that every duration is an integer.

Parameters:

• machines (list[int]) -- A list of machine ids that can perform the operation. If only one machine can perform the operation, it can be passed as an integer.

• duration (int) -- The time it takes to perform the operation.

• release_date (int) -- The earliest moment this operation can be scheduled to start. Defaults to 0.

• deadline (int | None) -- A hard cutoff time by which the job must be finished. A schedule is invalid if the job completes after this time. Defaults to None.

• due_date (int | None) -- The target completion time for the job. Finishing late is allowed but incurs a penalty (e.g., tardiness). Defaults to None.

machines: list[int]

A list of machine ids that can perform the operation. If only one machine can perform the operation, it can be passed as an integer.

duration: int

The time it takes to perform the operation. Often referred to as the processing time.

release_date: int

The earliest moment this operation can be scheduled to start. Defaults to 0.

deadline: int | None

A hard cutoff time by which the job must be finished. A schedule is invalid if the job completes after this time. Defaults to None.

due_date: int | None

The target completion time for the job. Finishing late is allowed but incurs a penalty (e.g., tardiness). Defaults to None.

job_id: int

The id of the job the operation belongs to. Defaults to -1. It is usually set by the JobShopInstance class after initialization.

position_in_job: int

The index of the operation in the job. Defaults to -1. It is usually set by the JobShopInstance class after initialization.

operation_id: int

The id of the operation. This is unique within a JobShopInstance. Defaults to -1. It is usually set by the JobShopInstance class after initialization.

property machine_id: int

Returns the id of the machine associated with the operation.

Raises:

UninitializedAttributeError -- If the operation has multiple machines in its list.

is_initialized()

Returns whether the operation has been initialized.

Return type:

bool

class JobShopInstance(jobs, name='JobShopInstance', set_operation_attributes=True, **metadata)

Bases: object

Data structure to store a Job Shop Scheduling Problem instance.

Additional attributes such as num_machines or durations_matrix can be computed from the instance and are cached for performance since they might require expensive computations.

Methods:

from_taillard_file	Creates a JobShopInstance from a file following Taillard's format.
to_dict	Returns a dictionary representation of the instance.
from_matrices	Creates a JobShopInstance from duration and machines matrices.
set_operation_attributes	Sets the job_id, position_in_job, and operation_id attributes for each operation in the instance.

Properties:

num_jobs	Returns the number of jobs in the instance.
num_machines	Returns the number of machines in the instance.
num_operations	Returns the number of operations in the instance.
is_flexible	Returns True if any operation has more than one machine.
duration_matrix	Returns the duration matrix of the instance.
machines_matrix	Returns the machines matrix of the instance.
release_dates_matrix	Returns the release dates matrix of the instance.
deadlines_matrix	Returns the deadlines matrix of the instance.
due_dates_matrix	Returns the due dates matrix of the instance.
duration_matrix_array	Returns the duration matrix of the instance as a numpy array.
machines_matrix_array	Returns the machines matrix of the instance as a numpy array.
operations_by_machine	Returns a list of lists of operations.
max_duration	Returns the maximum duration of the instance.
max_duration_per_job	Returns the maximum duration of each job in the instance.
max_duration_per_machine	Returns the maximum duration of each machine in the instance.
job_durations	Returns a list with the duration of each job in the instance.
machine_loads	Returns the total machine load of each machine in the instance.
total_duration	Returns the sum of the durations of all operations in all jobs.

jobs

A list of lists of operations. Each list of operations represents a job, and the operations are ordered by their position in the job. The job_id, position_in_job, and operation_id attributes of the operations are set when the instance is created.

Type:

list[list[Operation]]

name

A string with the name of the instance.

Type:

str

metadata

A dictionary with additional information about the instance.

Type:

dict[str, Any]

Parameters:

• jobs (list[list[Operation]]) -- A list of lists of operations. Each list of operations represents a job, and the operations are ordered by their position in the job. The job_id, position_in_job, and operation_id attributes of the operations are set when the instance is created.

• name (str) -- A string with the name of the instance.

• set_operation_attributes (bool) -- If True, the job_id, position_in_job, and operation_id attributes of the operations are set when the instance is created. See set_operation_attributes() for more information. Defaults to True.

• **metadata (Any) -- Additional information about the instance.

set_operation_attributes()

Sets the job_id, position_in_job, and operation_id attributes for each operation in the instance.

The job_id attribute is set to the id of the job to which the operation belongs.

The position_in_job attribute is set to the position of the operation in the job (starts from 0).

The operation_id attribute is set to a unique identifier for the operation (starting from 0).

The formula to compute the operation_id in a job shop instance with a fixed number of operations per job is:

operation_id = job_id * num_operations_per_job + position_in_job

classmethod from_taillard_file(file_path, encoding='utf-8', comment_symbol='#', name=None, **metadata)

Creates a JobShopInstance from a file following Taillard's format.

Parameters:

• file_path (PathLike | str | bytes) -- A path-like object or string representing the path to the file.

• encoding (str) -- The encoding of the file.

• comment_symbol (str) -- A string representing the comment symbol used in the file. Lines starting with this symbol are ignored.

• name (str | None) -- A string with the name of the instance. If not provided, the name of the instance is set to the name of the file.

• **metadata (Any) -- Additional information about the instance.

Returns:

A JobShopInstance object with the operations read from the file, and the name and metadata provided.

Return type:

JobShopInstance

to_dict()

Returns a dictionary representation of the instance.

This representation is useful for saving the instance to a JSON file, which is a more computer-friendly format than more traditional ones like Taillard's.

Returns:

The returned dictionary has the following structure:

{
    "name": self.name,
    "duration_matrix": self.duration_matrix,
    "machines_matrix": self.machines_matrix,
    "metadata": self.metadata,
    # Optionally (if the instance has them):
    "release_dates_matrix": self.release_dates_matrix,
    "deadlines_matrix": self.deadlines_matrix,
    "due_dates_matrix": self.due_dates_matrix,
}

Return type:

dict[str, Any]

classmethod from_matrices(duration_matrix, machines_matrix, name='JobShopInstance', metadata=None, release_dates_matrix=None, deadlines_matrix=None, due_dates_matrix=None)

Creates a JobShopInstance from duration and machines matrices.

Parameters:

• duration_matrix (list[list[int]]) -- A list of lists of integers. The i-th list contains the durations of the operations of the job with id i.

• machines_matrix (list[list[list[int]]] | list[list[int]]) -- A list of lists of lists of integers if the instance is flexible, or a list of lists of integers if the instance is not flexible. The i-th list contains the machines in which the operations of the job with id i can be processed.

• name (str) -- A string with the name of the instance.

• metadata (dict[str, Any] | None) -- A dictionary with additional information about the instance.

• release_dates_matrix (list[list[int]] | None) -- A list of lists of integers. The i-th list contains the release dates of the operations of the job with id i.

• deadlines_matrix (list[list[int | None]] | None) -- A list of lists of optional integers. The i-th list contains the deadlines of the operations of the job with id i.

• due_dates_matrix (list[list[int | None]] | None) -- A list of lists of optional integers. The i-th list contains the due dates of the operations of the job with id i.

Returns:

A JobShopInstance object.

Return type:

JobShopInstance

property num_jobs: int

Returns the number of jobs in the instance.

property num_machines: int

Returns the number of machines in the instance.

Computed as the maximum machine id present in the instance plus one.

property num_operations: int

Returns the number of operations in the instance.

property is_flexible: bool

Returns True if any operation has more than one machine.

property has_release_dates: bool

Returns True if any operation has a release date > 0.

property has_deadlines: bool

Returns True if any operation has a deadline.

property has_due_dates: bool

Returns True if any operation has a due date.

property durations_matrix: list[list[int]]

Another name for duration_matrix attribute, kept for backward compatibility.

It may be removed in future versions.

property duration_matrix: list[list[int]]

Returns the duration matrix of the instance.

The duration of the operation with job_id i and position_in_job j is stored in the i-th position of the j-th list of the returned matrix:

duration = instance.durations_matrix[i][j]

property machines_matrix: list[list[list[int]]] | list[list[int]]

Returns the machines matrix of the instance.

If the instance is flexible (i.e., if any operation has more than one machine in which it can be processed), the returned matrix is a list of lists of lists of integers.

Otherwise, the returned matrix is a list of lists of integers.

To access the machines of the operation with position i in the job with id j, the following code must be used:

machines = instance.machines_matrix[j][i]

property release_dates_matrix: list[list[int]]

Returns the release dates matrix of the instance.

The release date of the operation with job_id i and position_in_job j is stored in the i-th position of the j-th list of the returned matrix.

property deadlines_matrix: list[list[int | None]]

Returns the deadlines matrix of the instance.

The deadline of the operation with job_id i and position_in_job j is stored in the i-th position of the j-th list of the returned matrix.

property due_dates_matrix: list[list[int | None]]

Returns the due dates matrix of the instance.

The due date of the operation with job_id i and position_in_job j is stored in the i-th position of the j-th list of the returned matrix.

property durations_matrix_array: ndarray[tuple[int, ...], dtype[float32]]

Returns the duration matrix of the instance as a numpy array.

If the jobs have different number of operations, the matrix is padded with np.nan to make it rectangular.

property duration_matrix_array: ndarray[tuple[int, ...], dtype[float32]]

Returns the duration matrix of the instance as a numpy array.

If the jobs have different number of operations, the matrix is padded with np.nan to make it rectangular.

property release_dates_matrix_array: ndarray[tuple[int, ...], dtype[float32]]

Returns the release dates matrix of the instance as a numpy array.

If the jobs have different number of operations, the matrix is padded with np.nan to make it rectangular.

property deadlines_matrix_array: ndarray[tuple[int, ...], dtype[float32]]

Returns the deadlines matrix of the instance as a numpy array.

If the jobs have different number of operations, the matrix is padded with np.nan to make it rectangular. None values are also converted to np.nan.

property due_dates_matrix_array: ndarray[tuple[int, ...], dtype[float32]]

Returns the due dates matrix of the instance as a numpy array.

If the jobs have different number of operations, the matrix is padded with np.nan to make it rectangular. None values are also converted to np.nan.

property machines_matrix_array: ndarray[tuple[int, ...], dtype[float32]]

Returns the machines matrix of the instance as a numpy array.

The returned array has shape (num_jobs, max_num_operations_per_job, max_num_machines_per_operation). Non-existing machines are filled with np.nan.

Example

>>> jobs = [
...     [Operation([0, 1], 2), Operation(1, 3)], [Operation(0, 6)]
... ]
>>> instance = JobShopInstance(jobs)
>>> instance.machines_matrix_array
array([[[ 0.,  1.],
        [ 1., nan]],
       [[ 0., nan],
        [nan, nan]]], dtype=float32)

property operations_by_machine: list[list[Operation]]

Returns a list of lists of operations.

The i-th list contains the operations that can be processed in the machine with id i.

property max_duration: float

Returns the maximum duration of the instance.

Useful for normalizing the durations of the operations.

property max_duration_per_job: list[float]

Returns the maximum duration of each job in the instance.

The maximum duration of the job with id i is stored in the i-th position of the returned list.

Useful for normalizing the durations of the operations.

property max_duration_per_machine: list[int]

Returns the maximum duration of each machine in the instance.

The maximum duration of the machine with id i is stored in the i-th position of the returned list.

Useful for normalizing the durations of the operations.

property job_durations: list[int]

Returns a list with the duration of each job in the instance.

The duration of a job is the sum of the durations of its operations.

The duration of the job with id i is stored in the i-th position of the returned list.

property machine_loads: list[int]

Returns the total machine load of each machine in the instance.

The total machine load of a machine is the sum of the durations of the operations that can be processed in that machine.

The total machine load of the machine with id i is stored in the i-th position of the returned list.

property total_duration: int

Returns the sum of the durations of all operations in all jobs.

class ScheduledOperation(operation, start_time, machine_id)

Bases: object

Data structure to store a scheduled operation.

Parameters:

• operation (Operation) -- The Operation object that is scheduled.

• start_time (int) -- The time at which the operation is scheduled to start.

• machine_id (int) -- The id of the machine on which the operation is scheduled.

Raises:

ValidationError -- If the given machine_id is not in the list of valid machines for the operation.

operation: Operation

The Operation object that is scheduled.

start_time: int

The time at which the operation is scheduled to start.

property machine_id: int

Returns the id of the machine on which the operation has been scheduled.

property job_id: int

Returns the id of the job that the operation belongs to.

property position_in_job: int

Returns the position (starting at zero) of the operation in the job.

property end_time: int

Returns the time at which the operation is scheduled to end.

class Schedule(instance, schedule=None, **metadata)

Bases: object

Data structure to store a complete or partial solution for a particular JobShopInstance.

A schedule is a list of lists of ScheduledOperation objects. Each list represents the order of operations on a machine.

The main methods of this class are:

makespan	Returns the makespan of the schedule.
is_complete	Returns True if all operations have been scheduled.
add	Adds a new ScheduledOperation to the schedule.
reset	Resets the schedule to an empty state.

Parameters:

• instance (JobShopInstance) -- The JobShopInstance object that the schedule is for.

• schedule (list[list[ScheduledOperation]] | None) -- A list of lists of ScheduledOperation objects. Each list represents the order of operations on a machine. If not provided, the schedule is initialized as an empty schedule.

• **metadata (dict[str, Any]) -- Additional information about the schedule.

instance: JobShopInstance

The JobShopInstance object that the schedule is for.

metadata: dict[str, Any]

A dictionary with additional information about the schedule. It can be used to store information about the algorithm that generated the schedule, for example.

operation_to_scheduled_operation: dict[Operation, ScheduledOperation]

A dictionary that maps an Operation to its ScheduledOperation in the schedule. This is used to quickly find the scheduled operation associated with a given operation.

num_scheduled_operations

The number of operations that have been scheduled so far.

operation_with_latest_end_time: ScheduledOperation | None

The ScheduledOperation with the latest end time. This is used to quickly find the last operation in the schedule.

property schedule: list[list[ScheduledOperation]]

A list of lists of ScheduledOperation objects. Each list represents the order of operations on a machine.

to_dict()

Returns a dictionary representation of the schedule.

This representation is useful for saving the instance to a JSON file.

Returns:

A dictionary representation of the schedule with the following keys:

• "instance": A dictionary representation of the instance.

• "job_sequences": A list of lists 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.

• "metadata": A dictionary with additional information about the schedule.

Return type:

dict

static from_dict(instance, job_sequences, metadata=None)

Creates a schedule from a dictionary representation.

Parameters:

• instance (dict[str, Any] | JobShopInstance) -- The instance to create the schedule for. Can be a dictionary representation of a JobShopInstance or a JobShopInstance object.

• job_sequences (list[list[int]]) -- A list of lists 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.

• metadata (dict[str, Any] | None) -- A dictionary with additional information about the schedule.

Returns:

A Schedule object with the given job sequences.

Return type:

Schedule

static from_job_sequences(instance, job_sequences, dispatcher=None)

Creates an active schedule from a list of job sequences.

An active schedule is the optimal schedule for the given job sequences. In other words, it is not possible to construct another schedule, through changes in the order of processing on the machines, with at least one operation finishing earlier and no operation finishing later.

Parameters:

• instance (JobShopInstance) -- The JobShopInstance object that the schedule is for.

• job_sequences (list[list[int]]) -- A list of lists 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.

• dispatcher (Dispatcher | None) --

  A Dispatcher to use for scheduling. If not provided, a new dispatcher will be created.

  Note

  You will need to provide a dispatcher if you want to take into account start time calculators different from the default one.

Returns:

A Schedule object with the given job sequences.

Return type:

Schedule

See also

See job_shop_lib.dispatching for more information about dispatchers and the start time calculators available.

job_sequences()

Returns the sequence of jobs for each machine in the schedule.

This method returns a list of lists, where each sublist contains the job ids of the operations scheduled on that machine.

Return type:

list[list[int]]

reset()

Resets the schedule to an empty state.

makespan()

Returns the makespan of the schedule.

The makespan is the time at which all operations are completed.

Return type:

int

is_complete()

Returns True if all operations have been scheduled.

Return type:

bool

add(scheduled_operation)

Adds a new ScheduledOperation to the schedule.

Parameters:

scheduled_operation (ScheduledOperation) -- The ScheduledOperation to add to the schedule.

Raises:

ValidationError -- If the start time of the new operation is before the end time of the last operation on the same machine. In favor of performance, this method does not checks precedence constraints.

static check_schedule(schedule)

Checks if a schedule is valid and raises a ValidationError if it is not.

A schedule is considered invalid if:

• A ScheduledOperation has a machine id that does not match the machine id of the machine schedule (the list of ScheduledOperation objects) that it belongs to.

• The start time of a ScheduledOperation is before the end time of the last operation on the same machine.

Parameters:

schedule (list[list[ScheduledOperation]]) -- The schedule (a list of lists of ScheduledOperation objects) to check.

Raises:

ValidationError -- If the schedule is invalid.

copy()

Returns a copy of the schedule.

Return type:

Schedule

critical_path()

Returns the critical path of the schedule.

The critical path is the longest path of dependent operations through the schedule, which determines the makespan. This implementation correctly identifies the path even in non-compact schedules where idle time may exist.

It works by starting from an operation that determines the makespan and tracing backwards, at each step choosing the predecessor (either from the same job or the same machine) that finished latest.

Return type:

list[ScheduledOperation]

class BaseSolver

Bases: ABC

Base class for all solvers implemented as classes.

A Solver is any Callable that takes a JobShopInstance and returns a Schedule. Therefore, solvers can be implemented as functions or as classes. This class is provided as a base class for solvers implemented as classes. It provides a default implementation of the __call__ method that measures the time taken to solve the instance and stores it in the schedule's metadata under the key "elapsed_time" if it is not alreadypresent.

abstract solve(instance)

Solves the given job shop instance and returns the schedule.

Parameters:

instance (JobShopInstance)

Return type:

Schedule

__call__(instance)

Call self as a function.

Parameters:

instance (JobShopInstance)

Return type:

Schedule

Modules

benchmarking	Contains functions to load benchmark instances.
constraint_programming	Contains solvers based on Constraint Programming (CP).
dispatching	Contains classes and functions to solve the Job Shop Scheduling Problem step-by-step.
exceptions	Exceptions for the job shop scheduling library.
generation	Package for generating job shop instances.
graphs	Package for graph related classes and functions.
metaheuristics	Metaheuristic algorithms for solving job shop scheduling problems.
reinforcement_learning	Contains reinforcement learning components.
visualization