Introduction

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.

Shrink the Makespan

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">Three jobs, each a chain of operations on machines M1, M2, M3. Each machine processes its operations in some order. Reorder a machine’s queue and watch the <b>Gantt chart</b> and the <b>makespan</b> (total finish time) change. Evaluating an order is instant; finding the best one is the hard part.</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">Find best (brute force)</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Job-shop scheduling: each job is an ordered list of operations [machine, duration].
// A "schedule" picks, for each machine, the ORDER it runs its operations.
// We simulate respecting (a) job order (op k waits for op k-1 of same job) and (b) machine order (a machine runs one op at a time, in its chosen order).
// Makespan = time the last operation finishes. Minimizing it is NP-hard.
const JOBS = [
  [[0,3],[1,2],[2,2]],   // Job 1: M1(3) -> M2(2) -> M3(2)
  [[1,2],[0,3],[2,1]],   // Job 2: M2(2) -> M1(3) -> M3(1)
  [[2,4],[1,1],[0,2]]    // Job 3: M3(4) -> M2(1) -> M1(2)
];
const M = 3;
// ops on each machine as [job, opIndex]; machineQueue[m] is an array we can reorder.
function defaultQueues(){
  const q = [[],[],[]];
  JOBS.forEach((job,j)=> job.forEach((op,k)=> q[op[0]].push([j,k]) ));
  return q;
}
let queues = defaultQueues();

// Simulate one set of machine queues -> per-op start/end + makespan, or null if the
// chosen orders create a deadlock (cyclic wait). Returns {sched, makespan}.
function simulate(qs){
  const start = JOBS.map(job=>job.map(()=>-1));
  const end   = JOBS.map(job=>job.map(()=>-1));
  const qpos  = [0,0,0];                 // next op to place on each machine
  const jpos  = JOBS.map(()=>0);         // next op ready in each job
  let placed = 0; const total = JOBS.reduce((s,j)=>s+j.length,0);
  let guard = 0;
  while(placed < total){
    let progressed = false;
    for(let m=0;m<M;m++){
      if(qpos[m] >= qs[m].length) continue;
      const [j,k] = qs[m][qpos[m]];
      if(jpos[j] !== k) continue;        // this job isn't ready for op k yet
      // earliest start: after job's previous op AND after machine's previous op
      const jReady = k>0 ? end[j][k-1] : 0;
      const mReady = qpos[m]>0 ? end[ qs[m][qpos[m]-1][0] ][ qs[m][qpos[m]-1][1] ] : 0;
      const s = Math.max(jReady, mReady);
      start[j][k] = s; end[j][k] = s + JOBS[j][k][1];
      qpos[m]++; jpos[j]++; placed++; progressed = true;
    }
    if(!progressed) return null;         // deadlock from the chosen machine orders
    if(++guard > 10000) return null;
  }
  let mk = 0; end.forEach(r=>r.forEach(e=> mk = Math.max(mk,e)));
  return { start, end, makespan: mk };
}

// All permutations of an array.
function perms(a){
  if(a.length<=1) return [a.slice()];
  const out=[];
  for(let i=0;i<a.length;i++){ const rest=a.slice(0,i).concat(a.slice(i+1));
    for(const p of perms(rest)) out.push([a[i]].concat(p)); }
  return out;
}
// Brute force every combination of machine orderings; keep the min-makespan one.
function bestSchedule(){
  const opts = queues.map(q=>perms(q));
  let best=null, bestQ=null;
  for(const a of opts[0]) for(const b of opts[1]) for(const c of opts[2]){
    const r = simulate([a,b,c]);
    if(r && (best===null || r.makespan < best)){ best=r.makespan; bestQ=[a,b,c]; }
  }
  return { makespan: best, queues: bestQ };
}

function jclass(j){ return 'j'+j; }
function render(){
  const r = simulate(queues);
  const gantt = document.getElementById('gantt'); gantt.innerHTML='';
  const optimal = bestSchedule().makespan;
  const mk = r ? r.makespan : null;
  // scale: width of track maps to max(makespan, optimal-ish)
  const span = Math.max(mk||1, 12);
  for(let m=0;m<M;m++){
    const row=document.createElement('div'); row.className='row';
    const lab=document.createElement('div'); lab.className='rlabel'; lab.textContent='M'+(m+1);
    const track=document.createElement('div'); track.className='track';
    if(r){
      queues[m].forEach(([j,k])=>{
        const op=document.createElement('div'); op.className='op '+jclass(j);
        const s=r.start[j][k], e=r.end[j][k];
        op.style.left=(100*s/span)+'%'; op.style.width=(100*(e-s)/span)+'%';
        op.textContent='J'+(j+1); op.title=fmt('Job %j%%v% op %k%%v%  [%s%–%e%]', { j: j, v: 1, k: k, s: s, e: e });
        track.appendChild(op);
      });
    }
    row.appendChild(lab); row.appendChild(track); gantt.appendChild(row);
  }
  const md=document.getElementById('makespan');
  if(r){
    const isBest = mk===optimal;
    md.className='makespan'+(isBest?' best':'');
    md.innerHTML=fmt('Makespan: <span>%mk%</span> time units%v%', { mk: mk, v: isBest?' — optimal! ✓':' (best possible: '+optimal+')' });
  } else { md.className='makespan'; md.innerHTML='<span>Deadlock</span> — these machine orders cannot all be satisfied.'; }
  renderQueues();
}
function renderQueues(){
  const box=document.getElementById('queues'); box.innerHTML='';
  for(let m=0;m<M;m++){
    const row=document.createElement('div'); row.className='qrow';
    const b=document.createElement('b'); b.textContent='M'+(m+1); row.appendChild(b);
    queues[m].forEach(([j,k],i)=>{
      const c=document.createElement('span'); c.className='chip '+jclass(j);
      c.textContent='J'+(j+1); row.appendChild(c);
      if(i < queues[m].length-1){
        const sw=document.createElement('button'); sw.className='swap'; sw.textContent='⇄';
        sw.title=fmt('Swap order on M%m%%v%', { m: m, v: 1 });
        sw.addEventListener('click',()=>{ const q=queues[m];
          [q[i],q[i+1]]=[q[i+1],q[i]]; render(); });
        row.appendChild(sw);
      }
    });
    box.appendChild(row);
  }
}
document.getElementById('find').addEventListener('click',()=>{
  const b=bestSchedule(); if(b.queues){ queues=b.queues; render();
    console.log('Best makespan:', b.makespan); }
});
document.getElementById('reset').addEventListener('click',()=>{ queues=defaultQueues(); render(); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/job-shop-scheduling/Content licensed under CC BY-NC 4.0.