Job Shop Scheduling Problem (JSSP) Example

Download Notebook

Job Shop Scheduling assigns operations of jobs to time slots on machines so that the overall makespan is minimised. It is NP-hard and central to manufacturing and production planning.

import getpass
import os

from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.job_shop_scheduling import (
    JsspCollection,
    JsspData,
    JsspFormulation,
    JsspInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define 3 jobs on 2 machines using the from_jobs() factory method. Each job has an ordered sequence of operations specified as (machine, duration) pairs.

jobs = [
    [(0, 3), (1, 2)],  # Job 0: machine 0 for 3, then machine 1 for 2
    [(1, 4), (0, 1)],  # Job 1: machine 1 for 4, then machine 0 for 1
    [(0, 2), (1, 3)],  # Job 2: machine 0 for 2, then machine 1 for 3
]
data = JsspData.from_jobs(jobs=jobs, n_machines=2, deadline=10)
print(data.to_string())

Job Shop Scheduling Data:
  Jobs: 3
  Machines: 2
  Total operations: 6
  Deadline: 10

Plot Data

Visualize job operation sequences.

data.plot()

<Axes: title={'center': 'JSS - Job Structure'}, xlabel='Duration'>

Create Formulation

Schedule operations to minimize makespan, respecting machine capacity and job ordering.

formulation = JsspFormulation()
print(formulation.to_string(data))

Job Shop Scheduling Formulation:
  Jobs: 3
  Machines: 2
  Operations: 6
  Deadline (horizon): 10

Decision Variables:
  s[o] integer for o = 0, ..., 5  (start time of operation o)
  y[o1,o2] in {0,1} for each pair on the same machine  (ordering indicator)
  C_max integer  (makespan)
  Total: 6 integer + 6 binary + 1 integer = 13 variables

Objective:
  minimize C_max

Constraints:
  1. Makespan bound (6 constraints):
     s[o] + dur[o] <= C_max  for all o = 0, ..., 5
  2. Precedence within each job (3 constraints):
     s[o_next] >= s[o_prev] + dur[o_prev]  for consecutive operations in each job
  Variable bounds (on s[o]):
     ES[o] <= s[o] <= LS[o]  (from job precedence time windows)
  4. Disjunctive (per-pair Big-M) for same-machine operations (12 constraints):
     s[o1] - s[o2] + M_a * y[o1,o2] <= M_a - dur[o1]
     s[o2] - s[o1] - M_b * y[o1,o2] <= -dur[o2]
     where M_a = LS[o1]+dur[o1]-ES[o2], M_b = LS[o2]+dur[o2]-ES[o1]

Create Instance

Combine data and formulation into a solvable instance.

instance = JsspInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Job Shop Scheduling Data:
  Jobs: 3
  Machines: 2
  Total operations: 6
  Deadline: 10
Formulation:Job Shop Scheduling Formulation:
  Jobs: 3
  Machines: 2
  Operations: 6
  Deadline (horizon): 10

Decision Variables:
  s[o] integer for o = 0, ..., 5  (start time of operation o)
  y[o1,o2] in {0,1} for each pair on the same machine  (ordering indicator)
  C_max integer  (makespan)
  Total: 6 integer + 6 binary + 1 integer = 13 variables

Objective:
  minimize C_max

Constraints:
  1. Makespan bound (6 constraints):
     s[o] + dur[o] <= C_max  for all o = 0, ..., 5
  2. Precedence within each job (3 constraints):
     s[o_next] >= s[o_prev] + dur[o_prev]  for consecutive operations in each job
  Variable bounds (on s[o]):
     ES[o] <= s[o] <= LS[o]  (from job precedence time windows)
  4. Disjunctive (per-pair Big-M) for same-machine operations (12 constraints):
     s[o1] - s[o2] + M_a * y[o1,o2] <= M_a - dur[o1]
     s[o2] - s[o1] - M_b * y[o1,o2] <= -dur[o2]
     where M_a = LS[o1]+dur[o1]-ES[o2], M_b = LS[o2]+dur[o2]-ES[o1]

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

Job Shop Scheduling Solution:
  Makespan: 9
  Valid: True
  machine_0: [(0, 0, 3), (2, 3, 2), (1, 7, 1)]
  machine_1: [(1, 0, 4), (0, 4, 2), (2, 6, 3)]

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

<Axes: title={'center': 'JSS Solution - makespan 9'}, xlabel='Time'>

Collections

Generate a benchmark collection of random instances for batch processing.

collection = JsspCollection.from_random(min_jobs=2, max_jobs=3, n_machines=2, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: job_shop_scheduling<job_shop_scheduling>
Minimize
  C_max
Subject To
  makespan_bound_0: s_0 - C_max <= -2
  makespan_bound_1: s_1 - C_max <= -2
  makespan_bound_2: s_2 - C_max <= -1
  makespan_bound_3: s_3 - C_max <= -1
  prec_j0_p0: -s_0 + s_1 >= 2
  prec_j1_p0: -s_2 + s_3 >= 1
  disj_a_0_3: s_0 - s_3 + y_0_3 <= -1
  disj_b_0_3: -s_0 + s_3 - 4 * y_0_3 <= -1
  disj_a_1_2: s_1 - s_2 + 4 * y_1_2 <= 2
  disj_b_1_2: -s_1 + s_2 - y_1_2 <= -1
Bounds
  0 <= s_0 <= 0
  2 <= s_1 <= 2
  0 <= s_2 <= 2
  1 <= s_3 <= 3
  0 <= C_max
Binary
  y_0_3 y_1_2
Integer
  s_0 s_1 s_2 s_3 C_max