Example
Suppose there are five jobs with processing-times , and ''m''=2 processors. Then, the resulting schedule is , , and thePerformance guarantee
The algorithm runs in time , where ''n'' is the number of jobs. The algorithm always returns a partition of the jobs whose makespan is at most times the optimal makespan. 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 algorithm can be used as anOrdering strategies
Instead of using an arbitrary order, one can pre-order the jobs in order to attain better guarantees. Some known list scheduling strategies are: * Highest level first algorithm, or HLF; *Anomalies
The list scheduling algorithm has several anomalies. Suppose there are ''m''=3 machines, and the job lengths are:3, 2, 2, 2, 4, 4, 4, 4, 9Further, 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, 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: * 3, 4, 9 * 2, 2, 4 * 2, 4, 4 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, 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: * 3, 4 * 2, 4, 9 * 2, 4 * 2, 4 and the makespan is 15. Adding a machine has enlarged the makespan. The anomalies are bounded as follows. Suppose initially we had ''m''1 machines and the makespan was ''t''1. Now, we have ''m''2 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 ''t''2. Then:
.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.
References
{{DEFAULTSORT:List Scheduling Scheduling algorithms