Lesson · Scheduling · More than one machine

Machines in Parallel, and What LPT Guarantees

m identical machines, each job on exactly one of them, minimise the time the last machine finishes. No exchange argument reaches this: the decision is an assignment rather than an order. What is available is a heuristic with a guarantee, and two lower bounds — the average load and the longest single job — that the guarantee is proved from. On the lab's instance longest-first finishes at 13 where 12 is possible, and the binding lower bound is 34/3, which no schedule attains.

Open the interactive lesson Practice

m identical machines, each job on one machine, minimise the last finish LPT: longest job first, onto whichever machine is free soonest bound 1 sum p / m some machine does at least its share bound 2 max p that job runs on one machine without a break neither implies the other, and the OPTIMUM can be above both A 7, B 6, C 5, D 4, E 4, F 4, G 4 on 3: LPT 13, optimum 12, bounds 34/3 and 7

One heuristic, two bounds, and a gap above both of them

Core ideas

What this lesson establishes

Three ideas: why the exchange argument is not available, what the two bounds each see, and what a guarantee is when an optimum is not.

The decision is an assignment, so there is nothing adjacent to swap

On one machine a schedule was an order and two jobs could be neighbours. Here a schedule says which machine each job runs on, and the order within a machine does not affect when that machine finishes at all. Swapping two jobs between machines changes two loads by different amounts and changes the makespan only if one of them was the last to finish — so there is no local identity and no exchange proof, and the problem is hard in the sense “Algorithms and Complexity” gives the word.

Two lower bounds, and neither implies the other

The total work divided by the number of machines is a lower bound, because some machine must do at least the average. The longest single job is a lower bound, because that job runs on one machine without a break. On the lab's instance they are 34/3 and 7 and the first binds; on its one-big-job preset they are 7 and 11 and the second binds. A schedule cannot beat the larger of them, and the lab prints both so it is clear which one is doing the work.

A guarantee is not an optimum, and a bound is not a schedule

Longest-first is proved to finish within 4/3 − 1/(3m) of the best possible. On the lab's instance that allows 11/9 and the measured ratio is 13/12, so the guarantee holds with room to spare and is not tight. More important is what happens underneath: the optimum is 12 and the binding lower bound is 34/3, which is less than 12. A reader who stopped at the bound would believe in a schedule finishing at 34/3 that does not exist.

The material

Identical machines, a greedy rule, and the two numbers underneath it

The model, the rule, the two bounds it is measured against, and a worked instance where the optimum sits strictly above both of them.

Definition · Identical machines in parallel

m machines, all the same speed. Each job runs on exactly one machine, without interruption, and a machine runs one job at a time. The load of a machine is the total processing time assigned to it, and the makespan is the largest load. The order within a machine does not matter, so a schedule is just a partition of the jobs into m groups.

Definition · The LPT rule

Longest processing time: sort the jobs by p descending and place each one, in turn, on whichever machine is currently free soonest. It is a list-scheduling rule — one pass, no backtracking — and it does not in general find the optimum.

Theorem · The two lower bounds

For every assignment of jobs to m identical machines, the makespan is at least sum p / m and at least max p.

The m loads add to sum p, so the largest of them is at least the average sum p / m. A maximum is never below a mean of the same numbers.

The longest job runs on one machine without a break, so that machine's load is at least max p, and the makespan is at least that machine's load.

□

Neither bound implies the other, and the lab has a preset for each direction. With seven jobs adding to 34 on three machines the average is 34/3 and the longest job is 7, so the average binds. With one eleven-hour job and four small ones adding to 21 the average is 7 and the longest job is 11, so the longest binds — and there the bound is tight, because the optimum really is 11.

Seven jobs, three machines, and one hour that cannot be recovered

jobs A 7, B 6, C 5, D 4, E 4, F 4, G 4 total 34, m = 3 bound 1 34/3 the average load bound 2 7 the longest single job the binding bound is 34/3, which is about 11.33 and is not attainable LPT, placing 7, 6, 5, 4, 4, 4, 4 in turn on the machine free soonest M1 A 7, F 4 load 11 M2 B 6, E 4 load 10 M3 C 5, D 4, G 4 load 13 makespan 13 THE BEST OF ALL 2187 ASSIGNMENTS M1 A 7, C 5 load 12 M2 B 6, D 4 load 10 M3 E 4, F 4, G 4 load 12 makespan 12 ratio 13/12, inside the guarantee of 4/3 − 1/9 = 11/9 and 12 > 34/3: the optimum is strictly above the binding bound

Follow the rule's placements and the failure is visible. It puts the seven-hour job on the first machine, the six on the second, the five on the third, and then has four four-hour jobs to place onto loads of 7, 6 and 5. They go to the third, the second, the first and the third again, which leaves the third machine carrying 5 + 4 + 4 = 13. The optimum instead pairs the seven with the five and puts three fours together, which nothing in a one-pass rule would find.

Example · The optimum above the bound, which is the part worth keeping

The binding lower bound here is 34/3, and 34 is not divisible by 3. Every load is a whole number, so no assignment has all three loads equal to 34/3, and in fact no assignment gets below 12.

So the bound is 34/3, the optimum is 12 and the heuristic is 13. The gap between the heuristic and the optimum is a failure of the heuristic; the gap between the optimum and the bound is not a failure of anything. A report that treats the bound as a target to be chased has confused the two, and the target it is chasing does not exist.

When the bound is tight, and when the rule is exact

The lab's other two presets are the easy cases and they are worth running. With one eleven-hour job and four small ones the longest-job bound is 11, longest-first finishes at 11, and the enumeration confirms 11: bound, heuristic and optimum all agree, and the average-load bound of 7 is simply blind to why. With six four-hour jobs on three machines the average-load bound is 8, longest-first finishes at 8 and the optimum is 8; the longest-job bound is only 4 and contributes nothing, which is the same asymmetry the other way round.

Neither of those is evidence about the rule. They are instances where the bound happens to be attainable, and that is a property of the data rather than of the method. The useful habit is to compute both bounds first: when they meet the optimum the work is over before any schedule is built, and when they do not, the size of the remaining gap is what you have actually proved.

What the guarantee is and is not

The 4/3 − 1/(3m) guarantee is a worst-case statement about every instance, and it is proved from the two bounds rather than from any property of a particular schedule. On three machines it allows 11/9; the measured ratio on the lab's instance is 13/12, comfortably inside it. A measured ratio on one instance is not evidence about the bound in either direction, and the lab reports both numbers separately for that reason.

Shortest-first is the natural rival and it is much worse: on the same seven jobs it finishes at 15 against the optimum of 12, because it spends the small jobs early and is left placing the seven-hour job onto a machine that is already loaded. The lab offers both rules on the same data, and the contrast is the argument for sorting descending rather than an appeal to intuition.

Interactive

Identical machines in parallel

LPT against the exhaustive optimum, and against both of the bounds its guarantee is proved from

Place the jobs greedily, then look at both bounds and at the best assignment there is

The rule's assignment is drawn as one track per machine and its loads are added up again from the assignment rather than taken from the rule. Beside it is the best of every assignment, found by enumeration, and both lower bounds — the average load and the longest job — so it is visible which one binds and whether the optimum sits above it.

Worked example

Jobs, as name time

Machines3

The rule to place them by

The heuristic's makespan—

The best there is—

The ratio between them—

Total work over m—

The longest single job—

The better lower bound—

Two things bound every schedule from below and neither implies the other: the total work divided by the number of machines, because some machine must do at least its share, and the longest single job, because that job runs on one machine without a break. The 4/3 guarantee for LPT is proved against them, so the lab prints both.

Method

Splitting work across identical machines

Four steps, and the first one is done before any schedule exists.

Compute both lower bounds before scheduling anything

sum p / m exactly, as a fraction, and max p. The larger of the two is what no schedule can beat. On the lab's instance that is 34/3 against 7, and knowing it before you start is what makes the answer interpretable when it arrives.

Sort the jobs descending and place them one at a time

Each job goes on the machine that is free soonest, which at this point is the machine with the smallest load so far. Ties can be broken any way; the loads are what matter, not which physical machine is which.

Add the loads up again from the assignment

Do not take the makespan from the placement loop. Recompute each machine's load from the list of jobs on it, check that the loads add to sum p, and take the largest. The lab does exactly this, because a placement loop with an off-by-one in it reports a plausible number.

Report the makespan with the bound beside it

13, against a lower bound of 34/3 is a result. 13 on its own is a number. If the two are equal you have proved optimality and can stop; if they are not, the difference is the most you could still gain, and on this instance most of it is not gainable at all.

Bounds, guarantees and what a heuristic proves

Score 0 / 0

Choose the answer you can justify.

Seven jobs on three machines, greedily and then exactly

The lab's opening preset, placed one job at a time. Every figure is what the panel reports as the rule selector is moved between longest-first and shortest-first.

jobs A 7, B 6, C 5, D 4, E 4, F 4, G 4 total 34, three machines THE BOUNDS, BEFORE ANY SCHEDULE average load 34/3 longest job 7 binding 34/3 no schedule finishes earlier than this LPT, PLACING IN DESCENDING ORDER A 7 → M1 (0) loads 7 0 0 B 6 → M2 (0) loads 7 6 0 C 5 → M3 (0) loads 7 6 5 D 4 → M3 (5) loads 7 6 9 E 4 → M2 (6) loads 7 10 9 F 4 → M1 (7) loads 11 10 9 G 4 → M3 (9) loads 11 10 13 makespan 13 M1 A F, M2 B E, M3 C D G THE BEST OF ALL 2187 ASSIGNMENTS M1 A C 12 M2 B D 10 M3 E F G 12 makespan 12 ratio 13/12 guarantee on three machines 4/3 − 1/9 = 11/9 optimum 12 > binding bound 34/3 SHORTEST FIRST, ON THE SAME JOBS M1 A D G 15 M2 C E 9 M3 B F 10 makespan 15

The placement of G, the last job, is where the thirteen comes from. At that moment the loads are 11, 10 and 9, so G goes to the third machine and takes it to 13. Nothing at that point can be undone, and the rule has no mechanism for undoing it — which is what a one-pass heuristic is.

Three numbers, three meanings. 34/3 is proved and unattainable. 12 is attainable and was found by trying all 3⁷ = 2187 assignments. 13 is what the rule produced. Only the middle one is the answer to the question as asked, and on any instance large enough to matter it is the one you will not have.

For a rehearsal, switch to the one-big-job preset: A 11, B 3, C 3, D 2, E 2 on three machines. Compute both bounds before running it. The supplied first move is that the total is 21, so the average bound is 7 and the longest-job bound is 11. Say which binds, predict the optimum, and say why the average-load bound could never have seen it.

Common mistakes

Reading the average-load bound as a reachable target34/3 is a proof that nothing finishes sooner. On this instance the true optimum is 12, which is more than half an hour above it, and no rearrangement will ever close that part of the gap. The distance from a heuristic to the bound is not the distance from the heuristic to the answer.

Sorting the jobs ascendingPlacing the small jobs first leaves the large ones to land on machines that are already loaded: on the lab's instance shortest-first finishes at 15 against longest-first's 13 and an optimum of 12. The rule sorts descending for that reason, and the lab runs both so the difference is measured rather than argued.

Reporting a heuristic value without the bound13 alone says nothing about how good it is. 13, against a lower bound of 34/3 and an enumerated optimum of 12 says three separate things, only one of which survives to a larger instance. A number with no bound attached is the thing this path's last courses exist to stop.

Check your understanding

✓

Finish when you can compute both bounds first and say what a heuristic value means against them.

You should be able to compute sum p / m exactly and max p, say which binds and why neither implies the other, run longest-first placement by hand recording the loads after each job, recompute the loads from the finished assignment rather than from the loop, and state the result as a makespan with a lower bound beside it, distinguishing the part of the gap that is the heuristic's fault from the part that is not.

Note: That is the first result on this course that is not exact, and it is the first that arrives with a guarantee instead. Two of the three objectives left on the path work this way. The remaining machine model is worse again: let each job visit the machines in its own order and there is not even a sequence to choose — there is one binary decision per pair of operations sharing a machine, and some combinations of those decisions describe a schedule that cannot be run at all.