JobShopScheduling

JobShopScheduling, commonly known as the Job Shop Scheduling Problem (JSSP), is a foundational optimization problem in operations research and combinatorial optimization. It models a manufacturing setting where a set of jobs must be processed on a set of machines, with each job comprising a fixed sequence of operations, each assigned to a specific machine and with a known processing time. A machine can handle at most one operation at a time, and operations within a job must follow their prescribed order.

The typical objective is to minimize the makespan, the time by which all jobs complete. Other common goals include minimizing total completion time, maximum lateness, or tardiness, depending on the production environment. A standard model uses a disjunctive graph or a mixed-integer programming/constraint programming formulation. Decision variables capture operation start times and the on-machine sequencing of concurrent operations. Constraints enforce job precedence and non-overlapping on each machine, while the objective targets makespan.

JSSP is NP-hard in the strong sense for instances with three or more machines and jobs. Several restricted cases are solvable in polynomial time, such as the two-machine flow shop. Variants include flexible job shop and open shop.

Solution methods combine exact approaches—MILP, constraint programming, and branch-and-bound—with heuristics and metaheuristics such as priority dispatch rules, local search, tabu search, simulated annealing, genetic algorithms, and ant colony optimization. Hybrid methods and large-neighborhood search are common in practice.

Applications appear in manufacturing and assembly settings where machine capacity and job precedence drive throughput, lead times, and resource utilization.