Two machines in series, every job visiting them in the same order. The first machine never stops, so the makespan is the work on the second machine plus the idle time in between — and the work does not depend on the order, so minimising the makespan is minimising idle time on the second machine. Johnson's rule does it exactly: jobs quicker on the first machine go to the front, shortest first, and the rest go to the back, longest on the second machine first.
Core ideas
Three ideas: what the second machine is waiting for, why that turns the makespan into an idle-time problem, and what the rule's two halves are each doing.
Machine one runs the jobs back to back from time zero, so its timeline has no gaps and its finish times do not depend on anything but the order. Machine two can only start a job once machine one has released it and machine two is free, so its timeline has gaps in it. Every interesting quantity here is about those gaps.
The project ends when machine two finishes its last job, and machine two's timeline is made of exactly two things: the processing it does, which is sum p2 whatever the order, and the time it spends waiting. So makespan = sum p2 + idle, the first term is a constant, and the whole of the optimisation is the second. On the lab's five jobs the work is 27 in every order and the idle time is 3 under the rule and 7 in the typed order — which is the whole of the difference between 30 and 34.
A job quicker on machine one is a job that gets machine two started early, so those jobs go to the front, shortest on machine one first, to start machine two as soon as possible. A job quicker on machine two leaves machine one free early, so those go to the back, longest on machine two first, so that the longest tail is not the thing left at the end. Both halves are minimising idle time, at the two ends where idle time happens.
The material
The model, the recursion that builds the schedule, the rule in two halves, and it measured against every one of the 120 orders.
n jobs; job j needs p1_j on machine one and then p2_j on machine two, in that order. Both machines run one job at a time, nothing is interrupted, everything is available at time zero, and every job visits the machines in the same order — which is what makes it a flow shop.
The same order is used on both machines. A schedule that resequenced between the machines could in principle do better on more than two machines; on two it cannot, which is why one permutation is the whole decision here.
Write the order as k = 1, 2, …, n. Machine one finishes job k at C1(k) = C1(k−1) + p1(k), with C1(0) = 0, so it is the running total. Machine two cannot start job k until both that job has left machine one and machine two has finished job k−1:
The max is where the whole problem lives. When C1(k) wins, machine two was idle waiting for the job; when C2(k−1) wins, machine two was busy and the job waited instead. Waiting jobs cost nothing in this objective; a waiting machine costs the makespan.
Split the jobs. Those with p1 < p2 form the front group and are ordered by p1 ascending. The rest, with p1 ≥ p2, form the back group and are ordered by p2 descending. The schedule is the front group followed by the back group, and it minimises the makespan.
The two schedules do the same 27 hours of work on machine two and differ only in how long that machine spent waiting. In the typed order it waits five hours at the start, because A occupies machine one for five hours before anything can be handed over. Johnson puts B first, which occupies machine one for one hour, and machine two starts at 1 instead of at 5.
The lab has a preset built to make this visible: four jobs where the typed order begins with an eight-hour job on machine one that needs one hour on machine two. Machine two stands idle for the whole eight hours, and the typed order finishes at 35 with 18 hours of idle time against 17 hours of work.
Johnson's rule turns it round completely: D C B A, finishing at 24 with 7 hours of idle. Same jobs, same work, eleven hours saved, and the enumeration confirms that 24 is the best any of the twenty-four orders can do.
A recursion that produces a number is easy to get subtly wrong, so the lab reads the drawing back. It checks that machine one runs with no gaps, that machine two never overlaps itself, that no job reaches machine two before it has left machine one, and that the makespan taken off the last bar is the makespan the recursion reported. Then it checks work + idle = makespan exactly, which is the identity the rule is built on.
It also runs every one of the n! orders through the same two-machine clock and reports the best, the count and how many orders tie for it. On the lab's instance two orders attain 30, and Johnson's is one of them. Reporting the tie count matters: naming a single order and implying it is the unique optimum is a claim nobody made.
Three machines in series is a different problem and this rule does not extend to it. There is a special case — when the middle machine is dominated by one of the others — in which a two-machine reduction works, and the general case is hard in the sense “Algorithms and Complexity” gave the word. The lab offers two machines and says so rather than offering a third with a rule that is not a theorem.
The tie case is worth one line. When p1 = p2 for every job, as in the lab's third preset, the front group is empty and the rule sorts everything into the back group by p2 descending. That order attains the optimum, and so does every other order: all twenty-four tie at 21. The rule is not doing any work there, and the panel's tie count says so.
Interactive
Machine 2's idle time is the whole of the difference between one order and another
Method
Four steps, and the second is the one that decides which half a job belongs to.
p1:p2, machine one first. Getting the two columns the wrong way round produces a valid schedule for a problem you do not have, and nothing in the output looks wrong — the makespan will simply be larger than it should be.
Strictly quicker on machine one goes to the front group; everything else, including the ties, goes to the back group. The split is the decision; the two sorts that follow are bookkeeping.
Two different keys for the two groups, and they are not the same sort run twice. The front wants the smallest first-machine time first, to start machine two as early as possible; the back wants the largest second-machine time first, so the tail at the end is short.
Run the recursion, then add up the second machine's processing and its idle time and check that they come to the makespan. If they do not, the recursion has a gap in it that the drawing will show at once, and the lab refuses the schedule rather than printing the number.
The lab's opening preset, with both timelines written out. Every figure is what the panel reports when the comparison order is left as typed.
The two idle blocks in the typed order are the whole of the four-hour gap, and they have different causes. The five hours at the start are machine two waiting for the first job to exist; the two hours in the middle are machine two having finished B at 13 while C is still on machine one until 15. Johnson's split attacks the first with the front group and the second with the back group.
Machine one is worth checking too. In both schedules it runs from 0 to 28 without a break and finishes before machine two does. That is always true here, and it is why no amount of cleverness about machine one helps: its timeline is fixed up to the order and it is never the thing that ends the schedule.
For a rehearsal, use the preset where every job takes the same time on both machines. The supplied first move is that no job satisfies p1 < p2, so the front group is empty. Predict what the rule returns and what the enumeration says about how many orders tie for the best makespan, before the panel tells you. The answer is that all twenty-four tie, which means the rule is choosing arbitrarily and the tie count is the only honest way to say so.
You should be able to run the two-machine recursion with its max, split the jobs on p1 < p2, sort the two groups on their own keys, draw both machines' timelines, list the idle intervals on machine two, check that the idle time plus sum p2 equals the makespan, and compare the rule against a typed order on the same jobs.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.