| name | job-shop-scheduling |
| description | When the user wants to solve Job Shop Scheduling Problems (JSP), optimize production sequencing on multiple machines, or minimize makespan with precedence constraints. Also use when the user mentions "job shop," "JSP," "machine scheduling," "production scheduling," "operation sequencing," "makespan minimization," or "flexible job shop." For flow shop, see flow-shop-scheduling. For production planning, see production-scheduling. |
Job Shop Scheduling Problem (JSP)
You are an expert in Job Shop Scheduling and production sequencing optimization. Your goal is to help determine the optimal sequence of operations on machines to minimize completion time (makespan), tardiness, or other objectives, while respecting precedence constraints and machine availability.
Initial Assessment
Before solving JSP instances, understand:
-
Problem Characteristics
- How many jobs need to be scheduled?
- How many machines are available?
- Fixed routing (classic JSP) or flexible (FJSP)?
- Recirculation allowed? (job can visit same machine twice)
-
Operation Details
- Operations per job?
- Processing times known and deterministic?
- Precedence constraints within each job?
- Setup times between operations?
-
Objectives
- Minimize makespan (total completion time)?
- Minimize total tardiness?
- Minimize maximum lateness?
- Weighted combination?
-
Constraints
- No-wait (operations must start immediately after previous)?
- Limited buffers between machines?
- Machine breakdown/maintenance windows?
- Due dates for jobs?
-
Problem Scale
- Small (< 10 jobs, < 10 machines): Exact methods possible
- Medium (10-20 jobs): Advanced algorithms
- Large (20+ jobs): Metaheuristics required
Mathematical Formulation
Job Shop Scheduling (Disjunctive Graph Model)
Sets:
- J = {1, ..., n}: Jobs
- M = {1, ..., m}: Machines
- O_j: Set of operations for job j
Parameters:
- p_{ij}: Processing time of operation i of job j
- μ(i,j): Machine required for operation i of job j
- Prec_j: Precedence constraints for job j
Decision Variables:
- C_{ij}: Completion time of operation i of job j
- S_{ij}: Start time of operation i of job j
- y_{ij,kl} ∈ {0,1}: 1 if operation (i,j) is processed before (k,l) on same machine
Objective Function:
Minimize makespan: C_max = max_{j∈J, i∈O_j} C_{ij}
Or minimize total tardiness:
Minimize: Σ_{j∈J} max(0, C_{last(j)} - d_j)
Constraints:
1. Completion time relationship:
C_{ij} = S_{ij} + p_{ij}, ∀j ∈ J, ∀i ∈ O_j
2. Precedence within jobs:
C_{i,j} ≤ S_{i+1,j}, ∀j ∈ J, ∀i ∈ O_j\{last}
3. Disjunctive constraints (no machine overlap):
For operations (i,j) and (k,l) on same machine μ:
Either: S_{ij} + p_{ij} ≤ S_{kl} (i,j before k,l)
Or: S_{kl} + p_{kl} ≤ S_{ij} (k,l before i,j)
Linearized as:
S_{ij} + p_{ij} ≤ S_{kl} + M*(1 - y_{ij,kl})
S_{kl} + p_{kl} ≤ S_{ij} + M*y_{ij,kl}
4. Non-negativity:
S_{ij}, C_{ij} ≥ 0
5. Binary variables:
y_{ij,kl} ∈ {0,1}
Exact Algorithms
1. Branch and Bound for JSP
import numpy as np
from collections import defaultdict
class JobShopProblem:
"""Job Shop Scheduling Problem representation"""
def __init__(self, jobs, machines):
"""
Args:
jobs: list of jobs, each job is list of (machine, time) tuples
Example: [[(0, 3), (1, 2), (2, 2)], # Job 0
[(0, 2), (2, 1), (1, 4)]] # Job 1
machines: number of machines
"""
self.jobs = jobs
self.n_jobs = len(jobs)
self.n_machines = machines
self.n_operations = sum(len(job) for job in jobs)
def calculate_lower_bound(self, partial_schedule):
"""
Calculate lower bound on makespan
Uses machine-based and job-based bounds
"""
machine_times = [0] * self.n_machines
for job_id, job in enumerate(self.jobs):
for op_idx, (machine, time) in enumerate(job):
if (job_id, op_idx) in partial_schedule:
continue
machine_times[machine] += time
machine_lb = max(machine_times)
job_times = []
job_id, job (.jobs):
total_time = (time _, time job)
job_times.append(total_time)
job_lb = (job_times)
(machine_lb, job_lb)
():
time
problem = JobShopProblem(jobs, machines)
best_makespan = ()
best_schedule =
schedule = []
machine_available = [] * machines
job_next_op = [] * problem.n_jobs
job_available = [] * problem.n_jobs
start_time = time.time()
():
best_makespan, best_schedule
time.time() - start_time > time_limit:
depth == problem.n_operations:
makespan = (machine_available)
makespan < best_makespan:
best_makespan = makespan
best_schedule = schedule.copy()
(machine_available) >= best_makespan:
job_id (problem.n_jobs):
op_idx = job_next_op[job_id]
op_idx >= (jobs[job_id]):
machine, proc_time = jobs[job_id][op_idx]
start = (job_available[job_id], machine_available[machine])
schedule.append((job_id, op_idx, start, machine))
old_machine_avail = machine_available[machine]
old_job_avail = job_available[job_id]
machine_available[machine] = start + proc_time
job_available[job_id] = start + proc_time
job_next_op[job_id] +=
backtrack(depth + )
schedule.pop()
machine_available[machine] = old_machine_avail
job_available[job_id] = old_job_avail
job_next_op[job_id] -=
backtrack()
{
: best_makespan,
: best_schedule
}
Classical Heuristics
1. Priority Dispatch Rules
def jsp_dispatch_rule(jobs, machines, rule='SPT'):
"""
Dispatch rule heuristic for JSP
Priority rules:
- SPT: Shortest Processing Time
- LPT: Longest Processing Time
- FCFS: First Come First Served
- EDD: Earliest Due Date
- MWR: Most Work Remaining
Args:
jobs: list of jobs (each job is list of (machine, time))
machines: number of machines
rule: dispatch rule to use
Returns:
schedule and makespan
"""
n_jobs = len(jobs)
machine_available = [0] * machines
job_available = [0] * n_jobs
job_next_op = [0] * n_jobs
schedule = []
n_ops = sum(len(job) for job in jobs)
for _ in range(n_ops):
eligible = []
for job_id in range(n_jobs):
op_idx = job_next_op[job_id]
if op_idx < len(jobs[job_id]):
machine, proc_time = jobs[job_id][op_idx]
earliest_start = max(job_available[job_id],
machine_available[machine])
eligible.append({
'job_id': job_id,
'op_idx': op_idx,
'machine': machine,
'time': proc_time,
'start': earliest_start
})
if not eligible:
break
rule == :
selected = (eligible, key= x: x[])
rule == :
selected = (eligible, key= x: x[])
rule == :
selected = (eligible, key= x: x[])
rule == :
():
job_id = op[]
op_idx = op[]
remaining = (t _, t jobs[job_id][op_idx:])
remaining
selected = (eligible, key=remaining_work)
:
selected = eligible[]
job_id = selected[]
machine = selected[]
start_time = selected[]
proc_time = selected[]
schedule.append({
: job_id,
: selected[],
: machine,
: start_time,
: start_time + proc_time
})
machine_available[machine] = start_time + proc_time
job_available[job_id] = start_time + proc_time
job_next_op[job_id] +=
makespan = (machine_available)
{
: schedule,
: makespan,
: rule
}
2. Shifting Bottleneck Heuristic
def shifting_bottleneck_jsp(jobs, machines):
"""
Shifting Bottleneck Heuristic for JSP
One of the best constructive heuristics for JSP
Args:
jobs: list of jobs
machines: number of machines
Returns:
schedule and makespan
"""
n_jobs = len(jobs)
scheduled_machines = set()
machine_schedules = {m: [] for m in range(machines)}
while len(scheduled_machines) < machines:
max_delay = 0
bottleneck = None
for machine in range(machines):
if machine in scheduled_machines:
continue
delay = sum(
proc_time for job in jobs
for m, proc_time in job
if m == machine
)
if delay > max_delay:
max_delay = delay
bottleneck = machine
if bottleneck is None:
break
ops_on_machine = []
for job_id, job in enumerate(jobs):
for op_idx, (m, proc_time) (job):
m == bottleneck:
ops_on_machine.append((job_id, op_idx, proc_time))
ops_on_machine.sort(key= x: x[])
current_time =
job_id, op_idx, proc_time ops_on_machine:
machine_schedules[bottleneck].append({
: job_id,
: op_idx,
: current_time,
: current_time + proc_time
})
current_time += proc_time
scheduled_machines.add(bottleneck)
all_schedule = []
machine, ops machine_schedules.items():
all_schedule.extend(ops)
makespan = (op[] ops machine_schedules.values()
op ops) all_schedule
{
: all_schedule,
: makespan
}
Metaheuristics
1. Genetic Algorithm for JSP
import random
def jsp_genetic_algorithm(jobs, machines, population_size=50,
generations=200, mutation_rate=0.1):
"""
Genetic Algorithm for JSP
Chromosome representation: operation-based encoding
Args:
jobs: list of jobs
machines: number of machines
population_size: GA population size
generations: number of generations
mutation_rate: mutation probability
Returns:
best schedule found
"""
n_jobs = len(jobs)
operations = []
for job_id, job in enumerate(jobs):
operations.extend([job_id] * len(job))
def decode_chromosome(chromosome):
"""
Decode chromosome to schedule
Chromosome is a permutation of operations
"""
job_next_op = [0] * n_jobs
machine_available = [0] * machines
job_available = [0] * n_jobs
schedule = []
for job_id in chromosome:
op_idx = job_next_op[job_id]
if op_idx >= len(jobs[job_id]):
continue
machine, proc_time = jobs[job_id][op_idx]
start = max(job_available[job_id], machine_available[machine])
schedule.append({
'job': job_id,
'operation': op_idx,
'machine': machine,
'start': start,
'end': start + proc_time
})
machine_available[machine] = start + proc_time
job_available[job_id] = start + proc_time
job_next_op[job_id] +=
makespan = (machine_available)
schedule, makespan
():
_, makespan = decode_chromosome(chromosome)
/ ( + makespan)
():
child = []
remaining1 = parent1.copy()
remaining2 = parent2.copy()
remaining1 remaining2:
random.random() < remaining1:
job = remaining1.pop()
child.append(job)
job remaining2:
remaining2.remove(job)
remaining2:
job = remaining2.pop()
child.append(job)
job remaining1:
remaining1.remove(job)
child
():
random.random() < mutation_rate:
i, j = random.sample(((chromosome)), )
chromosome[i], chromosome[j] = chromosome[j], chromosome[i]
chromosome
population = []
_ (population_size):
individual = operations.copy()
random.shuffle(individual)
population.append(individual)
best_chromosome =
best_makespan = ()
generation (generations):
fitnesses = [fitness(ind) ind population]
ind, fit (population, fitnesses):
_, makespan = decode_chromosome(ind)
makespan < best_makespan:
best_makespan = makespan
best_chromosome = ind.copy()
new_population = []
elite_count = ( * population_size)
elite_indices = (((fitnesses)),
key= i: fitnesses[i],
reverse=)[:elite_count]
new_population = [population[i].copy() i elite_indices]
(new_population) < population_size:
parent1 = (random.sample(((population, fitnesses)), ),
key= x: x[])[]
parent2 = (random.sample(((population, fitnesses)), ),
key= x: x[])[]
child = precedence_crossover(parent1, parent2)
child = mutate(child)
new_population.append(child)
population = new_population
best_schedule, _ = decode_chromosome(best_chromosome)
{
: best_schedule,
: best_makespan,
: best_chromosome
}
__name__ == :
jobs = [
[(, ), (, ), (, )],
[(, ), (, ), (, )],
[(, ), (, ), (, )]
]
machines =
()
()
()
i, job (jobs):
()
( + *)
()
(*)
rule [, , , ]:
result = jsp_dispatch_rule(jobs, machines, rule)
()
( + *)
()
(*)
ga_result = jsp_genetic_algorithm(jobs, machines,
population_size=,
generations=)
()
()
op (ga_result[], key= x: x[]):
(
)
()
( * )
machine (machines):
(, end=)
ops_on_machine = [op op ga_result[]
op[] == machine]
ops_on_machine.sort(key= x: x[])
op ops_on_machine:
(, end=)
()
Tools & Libraries
Python Libraries
- OR-Tools (Google): CP-SAT solver for JSP
- Pyomo: MIP/CP modeling
- simpy: Discrete event simulation
- matplotlib: Gantt chart visualization
Specialized Software
- CPLEX CP Optimizer: Constraint programming
- Gurobi: MIP solver
- OptaPlanner: Java-based scheduling
Common Challenges & Solutions
Challenge: Large Search Space
Problem:
- n jobs × m machines creates huge solution space
- Exponential complexity (NP-hard)
Solutions:
- Use metaheuristics (GA, Tabu Search)
- Good initial solutions from dispatch rules
- Decomposition approaches
Challenge: Flexible Job Shop (FJSP)
Problem:
- Operations can be performed on multiple machines
- Even more complex than classic JSP
Solutions:
- Two-level optimization: machine assignment + sequencing
- Hierarchical GA
- OR-Tools handles naturally
Challenge: Dynamic Arrivals
Problem:
- New jobs arrive during execution
- Need to reschedule
Solutions:
- Rolling horizon approach
- Right-shift rescheduling
- Robust schedules with buffers
Output Format
JSP Solution Report
Problem:
- Jobs: 10
- Machines: 5
- Total Operations: 47
- Objective: Minimize Makespan
Solution:
| Metric | Value |
|---|
| Makespan | 243 minutes |
| Machine Utilization | 78% average |
| Idle Time | 187 minutes total |
Gantt Chart:
Machine 0: J2[0-15] J5[15-32] J1[35-48] ...
Machine 1: J1[0-22] J3[22-40] J7[45-67] ...
Machine 2: J4[0-18] J2[20-35] J6[35-52] ...
...
Questions to Ask
- How many jobs and machines?
- Is routing fixed or flexible (FJSP)?
- What's the objective? (makespan, tardiness, flowtime)
- Are there due dates?
- Setup times between operations?
- Can operations be interrupted (preemption)?
- Are machines always available?
- Is this static or dynamic (new jobs arrive)?
Related Skills
- flow-shop-scheduling: For linear routing
- production-scheduling: For broader manufacturing
- master-production-scheduling: For planning integration
- constraint-programming: For CP approaches
- optimization-modeling: For MIP formulation
