Job-Shop Scheduling
- Also called: JSSP, JSP, job-shop problem
- Category: Planning & manipulation › Task-level
- Tags: scheduling, combinatorial-optimization, multi-robot, manufacturing, task-planning
A combinatorial optimization problem of ordering operations on shared machines, where each job follows its own fixed machine route, usually to minimize the time until all jobs finish (makespan).
Definition
Job-shop scheduling is the problem of deciding when each operation runs on a set of shared machines. There are n jobs and m machines. Each job is a sequence of operations that must be done in a given order, and each operation needs one specific machine for a known processing time. A machine can work on only one operation at a time, and in the classical version an operation cannot be interrupted once started. The task is to choose the order of operations on every machine so that an objective is minimized, most often the makespan, the time at which the last job finishes. Other objectives include total tardiness against due dates and total flow time.
The problem is NP-hard in general, and even small instances can be hard to solve to proven optimality. It has close relatives that differ in how much freedom there is: in a flow shop every job visits the machines in the same order, in an open shop the order of operations within a job is free, and in a flexible job shop each operation may run on any machine from an allowed set, so the solver must also assign machines. A standard way to model the problem is the disjunctive graph, in which fixed arcs encode the order within each job and pairs of undirected arcs encode the still-open choice of which operation goes first on a shared machine.
Solution methods range from simple dispatching rules, such as shortest processing time first, through exact methods based on mixed-integer programming, constraint programming and branch and bound, to metaheuristics such as tabu search, simulated annealing and genetic algorithms. More recent work trains dispatching policies with reinforcement learning, often using graph neural networks over the disjunctive graph. In robotics, job-shop formulations appear when several robots, machines and workstations in a cell must share time: robots act as machines or as resources, tasks become operations, and the resulting schedule is then turned into motion plans and robot programs.
Why it matters
Whenever several robots or machines share work with ordering constraints, the order of tasks decides throughput and idle time as much as the speed of any single robot does. Recognizing a planning problem as a job-shop or flexible job-shop instance gives access to mature solvers, benchmark instances and known bounds, instead of hand-built heuristics that are hard to evaluate.
Key applications
- Sequencing tasks across multiple robots and machines in manufacturing cells
- Allocating shared workstations and fixtures among robot arms
- Production planning for machining, assembly and test lines
- Benchmarking task planners, including learned and language-model planners, against optimal schedules
- Scheduling mobile robots that serve several machines in a factory
In practice
An assembly cell has two robot arms, a CNC machine and a fixture station. Each product needs a fixed sequence of steps: load the blank into the CNC, machine it, move it to the fixture, then insert two parts. An engineer models each product as a job, each step as an operation tied to the robot or machine that performs it, and adds the processing times measured on the line. A constraint-programming solver with interval variables and no-overlap constraints per resource returns a schedule that minimizes makespan. The engineer then checks that the schedule is physically feasible, adding travel times between stations and keep-out rules so that the two arms are never scheduled into the shared fixture area at the same time, and the schedule is turned into a program for each robot.
Common misconceptions
- Job-shop scheduling is the same as task allocation — allocation decides who does a task, while job-shop scheduling also fixes the order and timing of operations on each shared resource
- Every job visits the machines in the same order — that is a flow shop; in a job shop each job has its own route
- A valid schedule is ready for the robots — the classical model ignores travel, setup and collision between robots unless they are added as extra constraints
- Optimal schedules are always out of reach — constraint-programming and mixed-integer solvers often find optimal or near-optimal schedules for practical instances; proving optimality is hard mainly for large or tightly constrained ones
Who should know this
- Manufacturing and automation engineers designing multi-robot cells
- Robotics researchers working on task planning and multi-robot coordination
- Operations research engineers building production schedulers
- Developers of language-model or learned planners for industrial robots
Related technologies
- Constraint Programming
- Google OR-Tools CP-SAT
- Mixed-Integer Linear Programming
- Dispatching Rules
- Tabu Search
- Flexible Job-Shop Scheduling
Related terms
Related projects
- BehaviorTree.CPP: C++ behavior tree library for robot task planning, powering Nav2 and ROS 2 systems
- Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
- IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
- X-VLA: Cross-embodiment VLA model with soft-prompted scaling
- Swarm-SLAM: Decentralized collaborative SLAM for robot swarms with bandwidth-aware loop closing
- PlanSys2: The PDDL-based task planning system for ROS 2 — symbolic AI planning on real robots
Videos
- Operations Research 09D: Job Shop Scheduling Problem: Yong Wang
- Mod-07 Lec-28 Job shop scheduling -- Gantt chart, Different dispatching rules: nptelhrd