Getting Started with Job Shop Lib

Recall that the Job Shop Scheduling Problem consists of determining the optimal sequence of operations for a set of jobs to be processed on a set of machines, where each job is composed of a series of operations that must be performed in a specific order, and each operation requires a specific machine for a given processing time. The objective is typically to minimize a performance criterion such as the total completion time (makespan) while respecting constraints such as machine capacity (only one job can be processed on a machine at a time) and job precedence relationships.

The main class of the library is the JobShopInstance class, which stores a list of jobs and its operations.

Each operation is also a class, which stores the machine(s) in which the operation can be processed and its duration (also known as processing time). Let’s see an example of how to use the JobShopInstance class to model a JSSP instance.

In this example, we model a simple Job Shop Scheduling Problem using the JobShopInstance class. We define three types of machines: CPU, GPU, and Data Center, each represented by a unique identifier. This just defines the problem, later on, we will find solutions and finally we will try to optimize them.

from job_shop_lib import JobShopInstance, Operation

CPU = 0
GPU = 1
DATA_CENTER = 2

job_1 = [Operation(CPU, 1), Operation(GPU, 1), Operation(DATA_CENTER, 7)]
job_2 = [Operation(GPU, 5), Operation(DATA_CENTER, 1), Operation(CPU, 1)]
job_3 = [Operation(DATA_CENTER, 1), Operation(CPU, 3), Operation(GPU, 2)]

jobs = [job_1, job_2, job_3]

instance = JobShopInstance(
    jobs,
    name="Example",
    # Any extra parameters are stored inside the
    # metadata attribute as a dictionary:
    lower_bound=7,
)
instance

JobShopInstance(name=Example, num_jobs=3, num_machines=3)

The job and its position in it are automatically inferred. Now, we can access to some stats of the instance:

print("Number of jobs:", instance.num_jobs)
print("Number of machines:", instance.num_machines)
print("Number of operations:", instance.num_operations)
print("Name:", instance.name)
print("Is flexible?:", instance.is_flexible)
print("Max operation time:", instance.max_duration)
print("Machine loads:", instance.machine_loads)

Number of jobs: 3
Number of machines: 3
Number of operations: 9
Name: Example
Is flexible?: False
Max operation time: 7
Machine loads: [5, 8, 9]

import numpy as np

np.array(instance.durations_matrix)

array([[1, 1, 7],
       [5, 1, 1],
       [1, 3, 2]])

np.array(instance.machines_matrix)

array([[0, 1, 2],
       [1, 2, 0],
       [2, 0, 1]])

Some of this attributes could take \(O(num\_operations)\) to compute. This is the reason we use the functools.cached_property decorator to cache the results of the computation of these attributes.

Note that we just had to specify the machines in which the operation can be processed and its duration. The job_id and the position of the operation in the job are automatically inferred by the JobShopInstance class.

first_operation = job_1[0]
print("Machine id:", first_operation.machine_id)
print("Duration:", first_operation.duration)
# If the operation only has one machine, we can use the `machine_id` property
# instead of the `machines` attribute:
print("Job id:", first_operation.job_id)
print("Position in the job:", first_operation.position_in_job)
print("Operation id:", first_operation.operation_id)
print("String representation:", str(first_operation))

Machine id: 0
Duration: 1
Job id: 0
Position in the job: 0
Operation id: 0
String representation: O(m=0, d=1, j=0, p=0)