How does a job shop differ from a flow shop?

In a flow shop, jobs follow a common machine order; job-shop routes can differ between jobs.

What is the flexible job-shop variant?

Operations can have a choice among eligible machines, adding assignment decisions to sequencing and timing.

Is machine workload always enough to prove the optimum?

No. It gives a lower bound, but precedence interactions can force a makespan above that bound. The worked example happens to attain it.

AI Glossary / Graphs and symbolic AI / Intermediate

Job-shop scheduling problem

Definition

A job-shop scheduling problem asks when to perform the operations of several jobs on shared machines while respecting each job's required operation order and each machine's capacity. A common objective is to minimize the makespan: the time by which all jobs have finished.

What it means

A job is a sequence of operations, not necessarily one uninterrupted block of work. Each operation requires a specified machine for a specified processing duration. Different jobs can visit machines in different orders, creating competition for resources.

The schedule assigns start times and, implicitly, an order for operations that share a machine. It must preserve the technical sequence within each job while avoiding machine conflicts.

The classical version assumes an operation runs without interruption once started and a machine handles one operation at a time. Real applications often add release dates, setup times, maintenance, alternative machines or staffing requirements. These extensions require explicit modeling.

How it works

Represent each operation with a start time, duration and end time. For successive operations within a job, require the later start to be at least the earlier end. For operations on the same machine, require their time intervals not to overlap.

Define an objective separately from these feasibility constraints. Minimizing the final completion time is different from minimizing lateness, total waiting time or the number of schedule changes. The solver optimizes what the model specifies.

Constraint programming, mathematical optimization and heuristic methods can search possible schedules. A feasible result satisfies the modeled constraints, but is not necessarily proven optimal. Solver status, bounds and stopping conditions should accompany any claim about solution quality. A time limit without a solution is also different from a proof that no feasible schedule exists.

Three practical examples

A small workshop schedules jobs that need different sequences of cutting, drilling and finishing equipment.
A laboratory planning model allocates sample-processing operations to shared instruments while preserving required processing order.
A simulation compares a proposed machine addition with the current resource configuration using the same jobs, durations and objective.

Think of it this way

Think of several meals whose preparation steps require shared appliances. One meal needs the oven before the mixer, while another needs the mixer before the oven. The steps must be arranged so that no appliance is promised to two steps simultaneously.

The analogy captures sequencing and capacity. A formal job-shop model needs precise durations and assumptions; it does not automatically include every uncertainty or human decision present in a real kitchen or workshop.

Worked example

A seven-hour schedule with a simple optimality certificate

Suppose two jobs are available at time zero. Job A requires three hours on machine M1, then two hours on M2. Job B requires two hours on M2, then four hours on M1. Operations cannot be interrupted, and each machine handles one operation at a time. There are no setup times or other constraints.

Schedule A's first operation on M1 from time 0 to 3. Simultaneously, schedule B's first operation on M2 from 0 to 2. M2 then waits from 2 to 3 because A's first operation has not finished.

At time 3, start A's second operation on M2, finishing at 5. Also start B's second operation on M1, finishing at 7. Both job sequences are respected, and neither machine has overlapping operations. The makespan is 7 hours.

M1 must perform three plus four hours of processing, totaling 7. Because it cannot process two operations simultaneously and no work starts before zero, every feasible schedule has makespan at least 7. The proposed schedule reaches that lower bound, so it is optimal for this small model.

Processing all of A before starting B would instead finish at 11. This comparison demonstrates the benefit of coordinating shared resources, but the seven-hour proof depends on the exact assumptions. Adding setup or transport time requires a revised schedule and bound.

Illustrative case study

The fictional Cedar Workshop team creates a scheduling model from job routes and machine durations. An initial schedule is feasible in the model, but operators point out that switching between certain materials requires additional setup.

The team adds these requirements and compares schedules under the same objective. It also distinguishes schedules found within the search time limit from schedules whose optimality has been established.

Cedar reviews each machine's timeline and each job's operation order before using the result as a planning proposal. This fictional case illustrates model validation and truthful reporting, without claiming productivity gains or complete operational coverage.

Common misconceptions and mistakes

A job must occupy one machine continuously until complete. It can contain operations on several machines and wait between them.
Machines being busy all the time guarantees the best schedule. Precedence interactions and the chosen objective matter.
A solver-produced schedule is automatically optimal. A feasible solution may lack an optimality proof.
A short makespan guarantees all due dates are met. Due dates and their penalties must be represented if they matter.

Business use

Job-shop models help make resource conflicts visible and compare proposed sequencing decisions. Their value depends on accurate routes, durations and constraints, particularly when operational practice differs from the simplified model.

Agree on the objective before optimizing. A plan that finishes the last job early may be undesirable if it delays an urgent job or changes too many committed start times. Keep assumptions and solver status alongside the schedule, and use scenarios when durations are uncertain. The model still needs review against actual work and priorities.

Check your understanding

Why can no schedule in the worked example finish before time 7?

Answer: M1 has seven hours of required processing and can perform only one operation at a time. The proposed schedule attains that unavoidable machine-workload bound.

Related terms

Scheduling
Precedence constraints
Makespan
precedence constraint
resource capacity
constraint programming
feasible solution
optimality bound
flow shop

Learn next

Add a one-hour unavailability interval on M1 from time 3 to 4. Construct a revised feasible schedule, compute its makespan and explain whether the original seven-hour workload bound is still sufficient to prove optimality.

Makespan

Sources

Google's OR-Tools documentation defines the job-shop model and its precedence and machine constraints: https://developers.google.com/optimization/scheduling/job_shop

The CP-SAT documentation distinguishes feasible, optimal, infeasible and unknown outcomes: https://developers.google.com/optimization/cp/cp_solver

The two-job schedule, lower-bound proof and Cedar Workshop case are original illustrations. Their assumptions are explicit.

Previous: Jensen bound integration Next: Johnson's algorithm