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 list scheduling algorithm has several anomalies.[1] Suppose there are m=3 machines, and the job lengths are:
3, 2, 2, 2, 4, 4, 4, 4, 9
Further, suppose that all the "4" jobs must be executed after the fourth "2" job. Then, list scheduling returns the following schedule:
- 3, 9
- 2, 2, 4, 4
- 2, [2 idle], 4, 4
and the makespan is 12.
Anomaly 1. If the "4" jobs do not depend on previous jobs anymore, then the list schedule is:
and the makespan is 16. Removing dependencies has enlarged the makespan.
Anomaly 2. Suppose the job lengths decrease by 1, to 2, 1, 1, 1, 3, 3, 3, 3, 8 (with the original dependencies). Then, the list schedule is:
- 2, 3, 3
- 1, 1, 3, 8
- 1, [1 idle], 3
and the makespan is 13. Shortening all jobs has enlarged the makespan.
Anomaly 3. Suppose there is one more machine (with the original lengths, with or without dependencies). Then, the list schedule is:
and the makespan is 15. Adding a machine has enlarged the makespan.
The anomalies are bounded as follows. Suppose initially we had m1 machines and the makespan was t1. 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. Then:[1][3]
.
In particular, with the same number of machines, the ratio is . A special case is when the original schedule is optimal; this yields the bound on the approximation ratio.