Motivation
A collection of jobs must be assigned to identical machines. The goal is to finish the last job as early as possible. A simple online rule assigns each arriving job to the machine with the least current load. It does not need to know future jobs, yet its final makespan is always within a factor of two of the optimum.
A sharper analysis gives the exact factor for machines and exhibits an instance attaining it. The proof identifies the job that finishes last and combines two different lower bounds on the optimal makespan.
Model and algorithm
Definition 7.6.1
(Scheduling instance and makespan)
Let be the number of identical machines. There are jobs with nonnegative processing times . Jobs are assigned in the given order and run nonpreemptively, with each machine processing its assigned jobs sequentially. The load of a machine is the sum of the processing times of its jobs; the makespan is the maximum load. Let and let be the smallest possible makespan among all assignments. For an empty job list, define .
Definition 7.6.2
(List scheduling)
List scheduling starts every load at zero. For each job in order, assign it to a machine with minimum current load, breaking ties arbitrarily. The rule can make its decision without seeing later jobs. If there are no jobs, return the empty schedule with makespan zero.
Theorems
Theorem 7.6.3
(List-scheduling approximation)
For every input,
where is the makespan produced by list scheduling.
Theorem 7.6.4
(Tightness of the factor)
For every integer , there is an ordered job list on which list scheduling has makespan , regardless of how it breaks ties among equally loaded machines.
If all processing times are zero, both sides of the guarantee are zero. The result is stated as an inequality and does not divide by .
Proofs
Two lower bounds on the optimum
Lemma 7.6.5
(Two lower bounds on the optimum)
For every instance, and .
Proof
(Average load and longest job)
Every assignment has total machine load , so its largest load is at least . Also, the machine containing job must process that entire job, so its makespan is at least . Therefore
The first bound is an average-load argument; the second is a single-job argument. They are both necessary for the proof below. A single job cannot be split among machines in this model.
Analyze the last-finishing job
Proof
(Charging the critical start time to earlier work)
Assume at least one job has positive processing time, and choose a job that finishes at the final makespan on its machine. Let be that machine's load immediately before was assigned. Then ; there cannot be a later positive-length job on the same machine without exceeding the final makespan. Zero-length jobs after it do not change the equality.
At the moment was assigned, list scheduling chose a minimum-load machine. Every machine therefore had load at least . The total processing time of jobs assigned before was at least . Since includes those jobs and job ,
Consequently,
The last step applies the average-load and single-job lower bounds separately. This proves the theorem. The argument is valid with zero-length jobs and arbitrary tie-breaking because it uses only the minimum-load property at the critical assignment.
Proof X-ray
Charge the critical start time to earlier work
When the last-finishing job was placed, all machines already had at least its starting load. Earlier jobs therefore account for at least total work. The final job's own length is bounded by the optimum independently of that average-load bound.
What the critical-job inequality says
The estimate is stronger than the final approximation factor for a particular instance. If the critical job is small compared with the average load, the schedule is close to the average-load lower bound. If the job is large, the longest-job lower bound pays for its contribution. Neither lower bound needs to be tight on its own; both hold for the same unknown optimum.
The proof is retrospective: it selects the job that finishes last after the schedule is built. The algorithm does not need to predict this job. When several jobs finish at the same maximum load, choose any one of them that is last among positive-length jobs on its machine. Its preceding load and the minimum-load property still give the inequality.
The same reasoning applies to every prefix of the job list. If the input stops after any particular assignment, regard that prefix as a complete instance and compare its schedule with the optimal schedule for that prefix. Thus the guarantee does not depend on knowing the final number of jobs in advance. The statement concerns online revelation of job lengths in an assignment list; it does not model arbitrary physical release times or machine-dependent processing speeds.
Why the tight example balances
Starting from equal loads, assigning one unit job to a least-loaded machine changes one of the smallest loads by one. After each block of unit jobs, every machine's load has increased by exactly one: until all machines at the current smaller load have received a job, any machine already increased has a larger load and cannot be chosen again. Induction over blocks gives the load vector before the long job. This argument is independent of tie-breaking within a block.
The offline schedule uses knowledge of the long job and reserves one machine for it. The lower bound from that job proves that no schedule can do better than makespan . Together with the constructed offline schedule, this establishes the optimum exactly, not just an upper bound on it. The list schedule's makespan therefore proves the claimed worst-case ratio.
A matching lower-bound example
Proof
(Unit jobs followed by one long job)
Fix . Give list scheduling unit-length jobs followed by one job of length . After the unit jobs, the loads are all : the minimum-load rule fills the machines evenly, and the number of unit jobs is a multiple of . The last job is assigned to any machine and raises its load to .
An optimal offline schedule puts the length- job alone on one machine and distributes the unit jobs evenly over the remaining machines, on each. Its makespan is . The longest-job lower bound also gives , so this schedule is optimal. The ratio is .
Every tie-breaking choice leads to the same balanced load vector after the unit jobs, so the example proves tightness for the stated rule rather than for one particular tie convention.
Complexity and implementation
A min-priority queue keyed by current machine load supports each assignment by extracting a least-loaded machine and reinserting it with the updated load. With a binary heap, the assignments take comparisons and machine entries, apart from storing the output schedule. Including time to build the initial heap gives total time .
If , assigning each job to a distinct machine is optimal, with makespan equal to the longest processing time. Handling this case directly avoids allocating an enormous number of empty machine records when is given in binary and exceeds the number of jobs. For the nontrivial case , the heap size is bounded by the explicit job count. Exact rational processing times require exact additions and comparisons; the operation count is not by itself a full bit-complexity bound.
The proof applies to the supplied job order. Sorting jobs before list scheduling can improve some schedules, but it changes the online behavior and requires a separate analysis for any claimed stronger factor. The result here does not assume sorted inputs.
Counterexample mode
A greedy schedule can be suboptimal
On two machines, process jobs in that order. The two unit jobs give loads ; the last job then produces loads . An offline schedule puts the length-two job on one machine and both unit jobs on the other, with makespan two. The greedy ratio is , exactly .
Boundary conventions and output
A schedule can be represented by listing the assigned jobs on each machine in their assignment order. Starting each machine's jobs consecutively with no idle time realizes the stated load as its completion time when all jobs are available. Deliberately inserted idle time cannot improve the maximum completion time in this model, so the load formulation captures the optimum.
Zero processing times cause no difficulty. They can be assigned without changing a load, and an instance consisting only of zero-length jobs has makespan zero. The proof separates that case before selecting a positive critical job. If , the factor becomes exactly one and the work lower bound is equality. These cases should not be handled by dividing by an optimum that may be zero.
Worked examples
Worked example 7.6.6
(Two machines)
For job lengths , list scheduling assigns and to different machines, then assigns to the machine of load . The final loads are , so the makespan is three. Since , the schedule is optimal.
Worked example 7.6.7
(One machine)
With , every job must run on the only machine, so both list scheduling and the optimum have makespan . The factor equals one.
Worked example 7.6.8
(The tight three-machine instance)
For , give six unit jobs followed by a job of length three. The six unit jobs produce loads , and the last job makes one load five. An optimum puts the long job alone and three unit jobs on each other machine, giving makespan three. The ratio is .
Worked example 7.6.9
(More machines than jobs)
For processing times and five machines, assign the two jobs to distinct machines. The makespan is four, which meets the longest-job lower bound and is therefore optimal. The other machines can remain idle.
Common mistakes
Common mistake
(Current load versus final load)
The machine receiving the critical job has the smallest current load when that job is assigned. Its final load need not remain smallest. The proof charges that start time to the work already assigned, then adds the critical job's length.
Common mistake
(The average-load bound alone does not control the last job)
The inequality alone is not enough to bound the last job's contribution. A single job can be much longer than the average load, so the separate lower bound is essential.
Common mistake
(The rule does not need the optimum)
Finally, the guarantee compares the result with an offline optimum that knows all jobs. The list rule itself does not need that optimum or future job lengths. An offline algorithm may do better on a particular input without contradicting the approximation bound.
Summary
List scheduling places each job on a least-loaded machine. At the last-finishing job's assignment, every machine has accumulated at least its start load. Combining this work bound with the longest-job lower bound yields a approximation, and a sequence of unit jobs followed by one long job shows the factor is tight.
Exercises
Quick check
(Give the two general lower bounds on in terms of total processing time and individual jobs.)
One bound is an average and the other concerns a single job.
Solution · Answer
because the maximum load is at least the average, and because a job cannot be split across machines.
Quick check
(Run list scheduling on two machines for jobs and compare with an optimal assignment.)
Run the rule job by job, then try putting the two unit jobs together.
Solution · Answer
The first two jobs give loads ; the last produces up to machine names. The optimum has loads by placing the two unit jobs together, so the ratio is .
Quick check
(Why is list scheduling optimal when ?)
There is only one possible assignment of jobs to machines.
Solution · Answer
All jobs must be assigned to the only machine, giving makespan for every schedule. List scheduling therefore matches the optimum.
Quick check
(For , describe a job list attaining ratio .)
Recall the tight instance: unit jobs first, then one long job.
Solution · Answer
Use six jobs of length one followed by one job of length three. List scheduling obtains makespan five; putting the long job alone and three unit jobs on each other machine gives optimum three.