Sequence n jobs through two machines in series to minimize the total completion time (makespan) using Johnson's rule. Enter each job's time on Machine 1 and Machine 2 to get the optimal order, the makespan, a Gantt-style timeline, and the idle time on Machine 2. Everything recomputes live in your browser.
| Job | M1 start | M1 finish | M2 start | M2 finish |
|---|---|---|---|---|
| B | 0 | 1 | 1 | 7 |
| D | 1 | 4 | 7 | 15 |
| C | 4 | 13 | 15 | 22 |
| E | 13 | 23 | 23 | 27 |
| A | 23 | 28 | 28 | 30 |
Johnson's rule is a classic scheduling algorithm that finds the job sequence which minimizes the makespan — the total time to complete all jobs — when every job must pass through two machines in the same order (Machine 1 then Machine 2). Published by S. M. Johnson in 1954, it is one of the few scheduling problems with a simple, provably optimal solution. This tool applies the rule to your jobs, returns the optimal sequence and makespan, and draws a Gantt-style timeline showing exactly when each job runs on each machine, including the idle time on Machine 2.
List every job with its processing time on Machine 1 and Machine 2. Find the single smallest time among all of these. If that smallest time is on Machine 1, place the job as early as possible — at the front of the unfilled sequence. If it is on Machine 2, place the job as late as possible — at the back. Remove that job and repeat with the remaining jobs, filling positions inward from both ends, until every job is placed. Ties can be broken arbitrarily (this tool resolves them deterministically). The intuition: jobs that are quick on Machine 1 go first so Machine 2 starts working sooner, and jobs that are quick on Machine 2 go last so they do not leave Machine 2 idle while waiting.
The makespan is the moment the last job finishes on Machine 2. Because the two machines run in series, Machine 2 cannot start a job until that job has finished on Machine 1 AND Machine 2 has finished its previous job — so Machine 2 may sit idle, especially at the start while the first job is still on Machine 1. Johnson’s rule minimizes the makespan, which is equivalent to minimizing the total idle time on Machine 2. This calculator reports the optimal sequence, the makespan, and the accumulated idle time on Machine 2 so you can see the gaps the schedule could not avoid.
The Gantt chart shows two rows — Machine 1 on top, Machine 2 below — with each job drawn as a bar spanning its start and finish times. Machine 1 processes jobs back-to-back in the optimal order with no gaps (it never waits). Machine 2 follows: each job’s M2 bar begins at the later of (a) when that job finished on M1 and (b) when M2 finished the previous job. Any blank space before an M2 bar is idle time. The detailed table beneath the chart lists the exact M1 and M2 start/finish times for each job in sequence.
Johnson’s rule is optimal only under specific conditions: there are exactly two machines, every job visits Machine 1 then Machine 2 in that order (a flow shop), processing times are known and fixed, no preemption (a job runs to completion once started), and all jobs are available at time zero. It does not handle setup-dependent sequencing, due-date or tardiness objectives, or jobs that skip a machine in a complex way. The rule extends to certain three-machine flow shops when the middle machine is dominated (its max time ≤ the min time on machine 1 or 3), by combining M1+M2 and M2+M3 into two pseudo-machines. For general multi-machine or multi-objective scheduling, heuristics and mixed-integer programming are used instead.
It minimizes the makespan — the total elapsed time from when the first job starts on Machine 1 to when the last job finishes on Machine 2 — for n jobs flowing through two machines in series. Minimizing the makespan is equivalent to minimizing the idle time on the second machine.
It repeatedly finds the smallest processing time across all remaining jobs and both machines. If that minimum is on Machine 1, the job is scheduled as early as possible (toward the front); if it is on Machine 2, the job is scheduled as late as possible (toward the back). The job is then removed and the process repeats until the full sequence is built.
Machine 2 can only work on a job after that job has finished on Machine 1, so at the very start it must wait for the first job to clear Machine 1. Later gaps appear whenever Machine 2 finishes a job before the next one is ready from Machine 1. Johnson’s rule arranges jobs to make this total idle time as small as possible, but it usually cannot eliminate it entirely.
Not in general. It is provably optimal only for the two-machine flow shop. It can be applied to a three-machine flow shop in the special case where the middle machine is dominated — when its maximum time is no greater than the minimum time on machine 1 or machine 3 — by forming two combined pseudo-machines. For broader cases, scheduling heuristics or optimization solvers are required.
Ties can be broken arbitrarily without affecting the optimal makespan — any consistent tie-breaking rule yields an optimal (though possibly different) sequence. This calculator breaks ties deterministically, so you may see a particular valid ordering among several that share the same minimum makespan.