job-shop-scheduling

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:

1. 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)

2. Operation Details

   • Operations per job?
   • Processing times known and deterministic?
   • Precedence constraints within each job?
   • Setup times between operations?

3. Objectives

   • Minimize makespan (total completion time)?
   • Minimize total tardiness?
   • Minimize maximum lateness?
   • Weighted combination?

4. Constraints

   • No-wait (operations must start immediately after previous)?
   • Limited buffers between machines?
   • Machine breakdown/maintenance windows?
   • Due dates for jobs?

5. 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 lower bound: max completion time for each machine
        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 lower bound: max total time for each job
        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)

    # Track state
    machine_available = [0] * machines
    job_available = [0] * n_jobs
    job_next_op = [0] * n_jobs
    schedule = []

    # Total operations
    n_ops = sum(len(job) for job in jobs)

    for _ in range(n_ops):
        # Find all eligible operations (next operation for each job)
        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]

                # Calculate earliest start time
                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

        # Select operation based on rule
         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)

    # Initialize
    scheduled_machines = set()
    machine_schedules = {m: [] for m in range(machines)}

    while len(scheduled_machines) < machines:
        # Find bottleneck machine
        max_delay = 0
        bottleneck = None

        for machine in range(machines):
            if machine in scheduled_machines:
                continue

            # Calculate delay caused by this machine
            # (simplified: sum of processing times)
            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

        # Schedule operations on bottleneck machine
        # using one-machine scheduling (EDD or other rule)
        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)

    # Create operation list (job_id repeated by number of operations)
    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

1. How many jobs and machines?
2. Is routing fixed or flexible (FJSP)?
3. What's the objective? (makespan, tardiness, flowtime)
4. Are there due dates?
5. Setup times between operations?
6. Can operations be interrupted (preemption)?
7. Are machines always available?
8. 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