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)[source]¶

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.

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.

job_id: int¶: The id of the job the operation belongs to.

position_in_job: int¶: The index of the operation in the job.

operation_id: int¶: The id of the operation. This is unique within a JobShopInstance.

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()[source]¶

Returns whether the operation has been initialized.

Return type:: bool

class JobShopInstance(jobs, name='JobShopInstance', **metadata)[source]¶

Bases: object

Data structure to store a Job Shop Scheduling Problem instance.

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

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.
**metadata (Any) -- Additional information about the instance.

set_operation_attributes()[source]¶: Sets the job_id and position of each operation.

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

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()[source]¶

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.durations_matrix, "machines_matrix": self.machines_matrix, "metadata": self.metadata,

}

Return type:: dict[str, Any]

classmethod from_matrices(duration_matrix, machines_matrix, name='JobShopInstance', metadata=None)[source]¶

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]])
the (A list of lists of lists of integers if) -- 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.

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 durations_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:

`python 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:

`python machines = instance.machines_matrix[j][i] `

property durations_matrix_array: ndarray[Any, dtype[float32]]¶

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

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

Example

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

property machines_matrix_array: ndarray[Any, 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(machines=[0, 1], 2), Operation(machines=1, 3)],
...     [Operation(machines=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)[source]¶

Bases: object

Data structure to store a scheduled operation.

Parameters:

operation (Operation)
start_time (int)
machine_id (int)

__init__(operation, start_time, machine_id)[source]¶

Initializes a new instance of the ScheduledOperation class.

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)[source]¶

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)
schedule (list[list[ScheduledOperation]] | None)
metadata (dict[str, Any])

__init__(instance, schedule=None, **metadata)[source]¶

Initializes the object with the given instance and schedule.

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 (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.

property schedule: list[list[ScheduledOperation]]¶: A list of lists of ScheduledOperation objects. Each list represents the order of operations on a machine.

property num_scheduled_operations: int¶: The number of operations that have been scheduled so far.

to_dict()[source]¶

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)[source]¶

Creates a schedule from a dictionary representation.

Parameters:

instance (dict[str, Any] | JobShopInstance)
job_sequences (list[list[int]])
metadata (dict[str, Any] | None)

Return type:

Schedule

static from_job_sequences(instance, job_sequences)[source]¶

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.

Returns:

A Schedule object with the given job sequences.

Return type:

Schedule

reset()[source]¶: Resets the schedule to an empty state.

makespan()[source]¶

Returns the makespan of the schedule.

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

Return type:: int

is_complete()[source]¶

Returns True if all operations have been scheduled.

Return type:: bool

add(scheduled_operation)[source]¶

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)[source]¶

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.

class BaseSolver[source]¶

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 already present.

abstract solve(instance)[source]¶

Solves the given job shop instance and returns the schedule.

Parameters:: instance (JobShopInstance)
Return type:: Schedule

__call__(instance)[source]¶

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.
`reinforcement_learning`	Package for reinforcement learning components.
`visualization`	Package for visualization.