The input to this algorithm is a list of jobs that should be executed on a set of m machines.
The algorithm repeatedly executes the following steps until a valid schedule is obtained: Suppose there are five jobs with processing-times {4,5,6,7,8}, and m=2 processors.
Then, the resulting schedule is {4,6,8}, {5,7}, and the makespan is max(18,12)=18; if m=3, then the resulting schedule is {4,7}, {5,8}, {6}, and the makespan is max(11,13,6)=13.
The algorithm always returns a partition of the jobs whose makespan is at most
[1] This is due to the fact that both the length of the longest job and the average length of all jobs are lower bounds for the optimal makespan.
The list scheduling algorithm has several anomalies.
Suppose the job lengths decrease by 1, to 2, 1, 1, 1, 3, 3, 3, 3, 8 (with the original dependencies).
Shortening all jobs has enlarged the makespan.
Suppose there is one more machine (with the original lengths, with or without dependencies).
Now, we have m2 machines, the dependencies are the same or relaxed, the job lengths are the same or shorter, the list is the same or different, and the makespan is t2.
A special case is when the original schedule is optimal; this yields the bound