Job Shop Scheduling

The problem is fundamentally modeled as a disjunctive graph G = (N, A, E). Nodes (N) represent operations, conjunctive arcs (A) define the fixed precedence constraints within a job's sequence, and disjunctive edges (E) connect operations requiring the same machine. Solving the problem means selecting one direction for each disjunctive edge without creating a cycle, transforming the graph into a directed acyclic graph (DAG) whose critical path determines the makespan.

JSS is strongly NP-hard, meaning no known algorithm can solve all instances to optimality in polynomial time. The solution space grows factorially: for n jobs and m machines, there are (n!)^m possible schedules. Even small instances (10×10) can challenge exact solvers. This intractability drives the use of heuristic and metaheuristic approaches like genetic algorithms, simulated annealing, and constraint programming for real-world applications.

In classical JSS, each job visits each machine at most once. This is the defining distinction from Flexible Job Shop Scheduling (where operations can choose among alternative machines) and Open Shop Scheduling (where operation order is unrestricted). If a job must visit the same machine multiple times, the problem becomes a Recirculating Job Shop, which introduces additional cycle-detection complexity in the disjunctive graph.

The canonical objective is minimizing C_max (makespan)—the completion time of the last job. This is equivalent to minimizing the length of the critical path in the solved disjunctive graph. Alternative objectives include:

• Total weighted completion time: Σ w_j · C_j
• Maximum lateness: max(C_j - d_j, 0)
• Total tardiness: Σ max(C_j - d_j, 0) Each objective function fundamentally alters the structure of optimal schedules.

Realistic JSS variants incorporate setup times that depend on the preceding operation on a machine. When switching from job A to job B, a cleaning or reconfiguration delay S_AB occurs. This transforms the problem into a Traveling Salesman Problem sub-problem on each machine, as the sequence of jobs determines total setup overhead. Setup times break the symmetry of the disjunctive graph and often make the problem significantly harder to solve.

In dynamic environments, full optimization is infeasible. Dispatching rules provide myopic, priority-based decisions when a machine becomes free:

• SPT (Shortest Processing Time): Minimizes average flow time
• EDD (Earliest Due Date): Minimizes maximum lateness
• CR (Critical Ratio): (Due Date - Now) / Remaining Processing Time
• FIFO (First-In-First-Out): Simple queue discipline These rules are often combined with look-ahead simulation in practice.

A declarative paradigm ideal for Job Shop Scheduling where the problem is defined by variables (start times), domains (time intervals), and constraints (precedence, disjunctive). A solver uses propagation and search to find feasible solutions without specifying a step-by-step algorithm.

• Excels at complex logical constraints and sequence-dependent setups
• Often finds high-quality solutions faster than MILP for highly constrained scheduling
• Uses global constraints like no_overlap to enforce machine capacity

An exact optimization method that formulates Job Shop Scheduling using continuous variables for start times and binary variables to encode machine sequencing. A solver like Gurobi or CPLEX minimizes makespan subject to linear constraints.

• Uses 'big-M' formulations to model disjunctive machine constraints
• Guarantees optimality but may suffer from exponential solve times on large instances
• Provides tight lower bounds via linear relaxation for benchmarking heuristics

A metaheuristic inspired by natural selection that evolves a population of schedules. Candidate solutions are encoded as chromosomes (e.g., priority lists). Operators like crossover and mutation generate new offspring, while a fitness function evaluates makespan.

• Highly effective for large-scale, NP-hard JSS instances
• Does not require gradient information or convexity
• Risk of premature convergence to local optima; requires parameter tuning

A probabilistic optimization technique that escapes local optima by occasionally accepting worse solutions. It mimics the controlled cooling of metal, where the temperature parameter governs the probability of accepting uphill moves.

• Starts with high 'temperature' for broad exploration, then cools for exploitation
• Uses neighborhood structures like swapping operations on a critical path
• Theoretically converges to the global optimum given infinite cooling time

An exact algorithm that systematically partitions the solution space into a tree. It computes lower bounds for each node (e.g., via linear relaxation or the length of the longest path) and prunes branches that cannot beat the current best solution.

• Guarantees finding the optimal makespan
• Performance heavily depends on the tightness of the bounding function
• Often combined with heuristics to find a good incumbent solution early

The standard modeling framework for Job Shop Scheduling. The problem is represented as a graph where nodes are operations, conjunctive arcs define job precedence, and disjunctive edges connect operations on the same machine. Solving the problem means selecting one direction for each disjunctive edge to create an acyclic, minimal-makespan graph.

• The critical path in the directed graph determines the makespan
• Neighborhood search algorithms operate by reversing critical arcs
• Provides an intuitive visual model for understanding schedule feasibility