Job-Shop Scheduling

Picture a small workshop. Several jobs must be built, and each job is a fixed sequence of operations — drill, then polish, then paint. Each operation needs a specific machine for a specific length of time, and a machine can do only one thing at a time.

The question sounds innocent: in what order should each machine take its waiting operations so that the whole batch finishes as early as possible? That finish time — the moment the last job rolls off the last machine — is called the makespan, and shaving it down is worth real money: less overtime, fewer idle machines, faster delivery.

Reorder the queue on one machine and you ripple delays through every job that depends on it. With just a few jobs and machines the number of possible orderings already runs into the millions. This is job-shop scheduling, and it is famous among engineers as one of the most stubborn optimization problems there is.

Below are three jobs, each a chain of operations on different machines. Click the buttons to swap the order in which a machine handles its operations, and watch the Gantt chart redraw and the makespan update live.

<p class="hint">{{hint}}</p>
<div id="gantt" class="gantt"></div>
<div class="makespan" id="makespan"></div>
<div id="queues" class="queues"></div>
<div class="btns">
  <button id="find" type="button">{{btn_find}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.gantt { display: flex; flex-direction: column; gap: 6px; margin: .4rem 0; }
.row { display: flex; align-items: center; gap: 6px; }
.rlabel { width: 34px; font: 700 13px ui-monospace, monospace; color: #1d3557; }
.track { position: relative; flex: 1; height: 30px; background: #eef2f6;
         border-radius: 6px; overflow: hidden; }
.op { position: absolute; top: 2px; height: 26px; border-radius: 5px; color: #fff;
      font: 700 12px system-ui, sans-serif; display: flex; align-items: center;
      justify-content: center; transition: left .25s, width .25s; }
.j0 { background: #1d3557; } .j1 { background: #e76f51; } .j2 { background: #2a9d8f; }
.makespan { font-size: 1.05rem; font-weight: 700; margin: .6rem 0; }
.makespan span { color: #c92f3c; }
.makespan.best span { color: #0a7d33; }
.queues { display: flex; flex-direction: column; gap: 6px; margin: .4rem 0 .8rem; }
.qrow { display: flex; align-items: center; gap: 6px; font-size: .9rem; }
.qrow b { width: 34px; color: #1d3557; }
.chip { padding: 2px 8px; border-radius: 12px; color: #fff; font: 600 12px system-ui; }
.swap { font: 600 12px system-ui; padding: 2px 8px; border: 1px solid #1d3557;
        background: #fff; color: #1d3557; border-radius: 6px; cursor: pointer; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Evaluating a given ordering is quick — simulate the machines and read off when the last job finishes. Finding the ordering with the smallest makespan is the hard part: press Find best (brute force) and the computer tries every legal sequencing. With three short jobs that is already dozens of combinations; add a few more jobs and machines and the count explodes far beyond what any computer can enumerate.

How hard is job-shop scheduling, really? Not running the schedule — finding the best one.

• Checking a schedule is easy: simulate each machine in the chosen order, respect the job sequences, and read off the makespan. This is fast (polynomial time).
• Brute force tries every legal ordering of operations on every machine. The number of combinations grows faster than exponentially, so it becomes hopeless after only a handful of jobs.
• It's NP-hard. Minimizing the makespan is NP-hard, and the result is sharp: even with just three machines the problem is NP-hard, shown by Garey, Johnson and Sethi in 1976. The famous 10×10 instance posed by Fisher and Thompson in 1963 took over 20 years to solve to proven optimality.
• No efficient exact algorithm is known, and if one existed it would solve every problem in NP — so this is intertwined with the great open question of P vs NP.

That is the punchline: job-shop scheduling is one of the cleanest real-world faces of intractability. It is a close cousin of the traveling salesman problem — both ask for the best ordering among astronomically many, and for both we have no shortcut, only clever search and approximation.

"Order these tasks on shared resources to finish as soon as possible" is one of the most valuable problems in the economy, and the job-shop is its purest form:

• Manufacturing: the original setting — sequencing parts through drills, lathes, ovens and paint booths to keep an expensive factory busy.
• Cloud and HPC: scheduling jobs onto a cluster of servers or GPUs is the same problem with electricity bills attached.
• Healthcare: routing patients through operating rooms, scanners and recovery beds is job-shop scheduling with lives on the line.
• Logistics and projects: airport gate assignment, dock loading and construction timelines all reduce to ordering operations on scarce resources.

Because exact solutions are out of reach, the real world leans on heuristics, local search, genetic algorithms and constraint solvers — the same toolkit used for the traveling salesman problem and other NP-hard optimization.

Job-shop scheduling hides a humbling truth: a problem you can explain in one sentence — order the operations so everything finishes fast — is NP-hard, intractable even with three machines, and entangled with P vs NP. Evaluating any schedule stays instant; proving you have the best one can take decades, as the legendary 10×10 instance showed.

So when a planner ships a schedule that is merely "very good" rather than provably perfect, that is not laziness — it is the rational response to a genuinely hard problem. Like the traveling salesman, the job-shop teaches us that sometimes the smartest move is to search well and accept that perfection may be forever out of reach.