Operations Management and Strategic Management · Scheduling and Queuing Models

Johnson's Rule and Job Sequencing for n Jobs

Updated 10 October 2026 · Fact-checked

Johnson's rule gives the job order that minimises total elapsed time when n jobs pass through two machines in the same order. Pick the smallest time in the table. If it is on Machine 1, schedule that job as early as possible. If it is on Machine 2, schedule it as late as possible. Repeat. Three machines need a test first.

Understand Johnson's Rule and Job Sequencing

Job sequencing asks one question: in what order should n jobs go through a set of machines so the whole batch finishes as early as possible? Every job must visit the machines in the same order, say Machine 1 and then Machine 2. Each job has a known processing time on each machine.

The order matters because Machine 2 can start a job only after Machine 1 has finished it. If a job with a long Machine 1 time comes early, Machine 2 waits. That waiting is idle time. The total time from the start of the first job on Machine 1 to the finish of the last job on Machine 2 is the total elapsed time (also called makespan).

Johnson's rule fixes the idea above. Jobs that are quick on Machine 1 should go first, so Machine 2 gets work early. Jobs that are quick on Machine 2 should go last, so Machine 1 is not left holding long Machine 2 work at the end. The rule applies this by looking at the smallest time in the table each round.

For three machines, Johnson's rule does not work directly. It works only if the minimum time on M1 or the minimum time on M3 is at least the maximum time on M2. In that case you combine the three machines into two fictitious machines and apply the same rule.

The rule assumes: all jobs are available at time zero, processing times are known and fixed, every job follows the same machine order, no pre-emption, and each machine does one job at a time.

Key rules to remember

Johnson's rule (two machines): Smallest time on M1 → place job at the earliest free position; smallest time on M2 → place job at the latest free position; Remove the placed job and repeat until all jobs are placed. Ties can be broken arbitrarily, so more than one optimal sequence may exist.
Condition for three machines: Min (M1 times) ≥ Max (M2 times), or Min (M3 times) ≥ Max (M2 times); At least one condition must hold. If neither holds, this method is not valid and you should say so.
Fictitious machines: G = M1 + M2 and H = M2 + M3 for each job; Apply Johnson's rule to G and H as if they were two machines. Then compute actual times on all three real machines.
Total elapsed time: Finish time of the last job on the last machine; Find it from the in-out table, not from the G and H columns.
Idle time on a machine: Total elapsed time − Sum of processing times on that machine; Valid when you count idle time from time zero to the end of the whole schedule. State the period you use.

How to solve Johnson's Rule and Job Sequencing questions

Use this method for any sequencing question with two or three machines. Always finish with an in-out time table to confirm the answer.

1Write the data as a table: jobs in rows, machines in columns.
2For three machines, check the condition: Min M1 ≥ Max M2 or Min M3 ≥ Max M2. If it holds, form G = M1 + M2 and H = M2 + M3 and treat G and H as the two machines.
3Scan the whole table for the smallest time. If it is in the first machine column, put that job in the first free slot. If it is in the second column, put it in the last free slot.
4Strike out that job. Repeat step 3 on the remaining jobs until every slot is filled. If there is a tie, pick any one and note that other optimal sequences exist.
5Write the final sequence. Use the real machine times, not G and H, for the next step.
6Build the in-out table. A job starts on Machine 1 when the previous job leaves it. On each later machine it starts at the later of two times: when it finishes on the previous machine, and when that machine becomes free.
7Read the total elapsed time from the last finish time. Compute idle time of each machine as elapsed time minus the sum of its processing times.
8State the answer clearly: the sequence, the total elapsed time and the idle time asked for, with units (hours or minutes).

Quickest way: Fill-the-ends method

When to use it: Use it when the question asks only for the optimal sequence and elapsed time, and the table has five to eight jobs.

Draw a row of empty boxes, one for each job.
Circle the smallest number in the table. Left column means fill from the left end. Right column means fill from the right end.
Cross out the job and move to the next smallest number. Keep filling inward from the two ends.
Check the finished sequence by running one quick in-out table. Recompute Machine 2 as: start = larger of (Machine 1 finish, Machine 2 previous finish).
As a cross-check, elapsed time must be at least the sum of Machine 1 times plus the Machine 2 time of the last job, and at least the sum of Machine 2 times plus the Machine 1 time of the first job.

Common mistakes in Johnson's Rule and Job Sequencing

Placing a job at the front when the smallest time is on Machine 2 (or the reverse).
Students remember 'smallest time' but forget that the machine column decides which end of the sequence is used.
Fix: Say it aloud: Machine 1 → front, Machine 2 → back. Write 'F' or 'B' beside each pick.
Using Johnson's rule for three machines without checking the condition.
Students jump straight to adding columns.
Fix: Always write the test first: Min M1 ≥ Max M2 or Min M3 ≥ Max M2. Show the numbers. If it fails, say the method is not applicable.
Computing elapsed time from the G and H columns.
G and H are only tools for choosing the order, but they look like real times.
Fix: After deciding the sequence, build the in-out table with the original machine times only.
Starting a job on Machine 2 right after it ends on Machine 1 even when Machine 2 is still busy.
Students forget the machine may not be free.
Fix: Start on Machine 2 = larger of (finish on Machine 1, finish of the previous job on Machine 2).
Counting idle time incorrectly, for example leaving out the wait before the first job reaches Machine 2 or the time after a machine finishes its last job.
The question's wording on idle time is not read closely.
Fix: Use elapsed time minus total processing time, and state the period. Check it against the gaps shown in your table.
Declaring only one answer when a tie exists and getting a different sequence from the book.
Ties allow more than one optimal sequence.
Fix: Note the tie. Any sequence from the rule gives the same minimum elapsed time. Mention this in your answer.

Worked examples

Example 1

Five jobs go through two machines, M1 then M2. Processing times in hours (M1, M2): A (4, 7), B (8, 3), C (6, 5), D (2, 9), E (5, 6). Find the optimal sequence, total elapsed time and the idle time of each machine.

Show the solution

Smallest time is 2 (job D on M1), so D goes first.
Remaining jobs A, B, C, E. Smallest is 3 (job B on M2), so B goes last.
Remaining A, C, E. Smallest is 4 (job A on M1), so A goes second.
Remaining C (6, 5) and E (5, 6). Smallest is 5, which appears twice: E on M1 and C on M2. E goes to the earlier slot (third) and C goes to the later slot (fourth). Both choices give D-A-E-C-B.
Optimal sequence: D → A → E → C → B.
In-out table. D: M1 0–2, M2 2–11. A: M1 2–6, M2 11–18. E: M1 6–11, M2 18–24. C: M1 11–17, M2 24–29. B: M1 17–25, M2 29–32.
Total elapsed time = 32 hours.
Sum of M1 times = 4 + 8 + 6 + 2 + 5 = 25. Idle time of M1 = 32 − 25 = 7 hours (after 25).
Sum of M2 times = 7 + 3 + 5 + 9 + 6 = 30. Idle time of M2 = 32 − 30 = 2 hours (at the start, 0 to 2).

Answer: Sequence D–A–E–C–B; total elapsed time 32 hours; idle time M1 = 7 hours, M2 = 2 hours.

Example 2

Four jobs are processed on three machines M1, M2, M3 in that order. Times in hours (M1, M2, M3): Job 1 (8, 3, 5), Job 2 (6, 4, 9), Job 3 (7, 2, 7), Job 4 (9, 5, 6). Find the optimal sequence, the total elapsed time and the idle time of M3.

Show the solution

Check the condition. Min M1 = 6. Max M2 = 5. Since 6 ≥ 5, the method is valid.
Form G = M1 + M2 and H = M2 + M3. Job 1: G 11, H 8. Job 2: G 10, H 13. Job 3: G 9, H 9. Job 4: G 14, H 11.
Smallest value is 8 (Job 1 on H), so Job 1 goes last.
Remaining Jobs 2, 3, 4. Smallest is 9 (Job 3, in both G and H). Put Job 3 first.
Remaining Jobs 2 (10, 13) and 4 (14, 11). Smallest is 10 (Job 2 on G), so Job 2 goes second and Job 4 third.
Optimal sequence: Job 3 → Job 2 → Job 4 → Job 1.
In-out table using the real times. Job 3: M1 0–7, M2 7–9, M3 9–16. Job 2: M1 7–13, M2 13–17, M3 17–26. Job 4: M1 13–22, M2 22–27, M3 27–33. Job 1: M1 22–30, M2 30–33, M3 33–38.
Total elapsed time = 38 hours.
Sum of M3 times = 7 + 9 + 6 + 5 = 27. Idle time of M3 = 38 − 27 = 11 hours. Check: 9 hours at the start, 1 hour between 16 and 17, 1 hour between 26 and 27, total 11.

Answer: Sequence 3–2–4–1; total elapsed time 38 hours; idle time of M3 = 11 hours.

Exam tips

Show the condition test for three machines in a separate line. Examiners give a mark for it, and a wrong 'not applicable' call is easy to spot.
Always draw the in-out table. Step marks go to the table even if you slip in the sequence.
Write the final sequence in a clear line such as D → A → E → C → B, then state elapsed time and idle time with units.
In MCQs, the quickest check is to find the smallest number and decide front or back. Often only one option has the right first or last job.
If the question asks for idle time of a particular machine, read whether it means the whole schedule or only between jobs. State your assumption in one line.

Practice questions from Scheduling and Queuing Models

Johnson's Rule and Job Sequencing: frequently asked questions

What is Johnson's rule in job sequencing?

It is a rule to order n jobs through two machines so that the total elapsed time is the least. You pick the smallest processing time in the table. A Machine 1 time sends the job to the front, and a Machine 2 time sends it to the back.

Can Johnson's rule be used for three machines?

Yes, but only when the condition holds: the minimum time on M1 or on M3 is at least the maximum time on M2. Then you add M1 + M2 and M2 + M3 to form two fictitious machines and apply the rule as usual.

What if two jobs have the same smallest time?

Pick either one. If the tie is between a Machine 1 time and a Machine 2 time, place each job at its own end. Different choices can give different sequences, but the minimum elapsed time stays the same.

How do I calculate idle time in a sequencing problem?

Build the in-out table first. Idle time of a machine is the total elapsed time minus the sum of that machine's processing times. Check it against the visible gaps in the table.