List scheduling

List scheduling is a greedy algorithm for Identical-machines scheduling. The input to this algorithm is a list of jobs that should be executed on a set of m machines. The list is ordered in a fixed order, which can be determined e.g. by the priority of executing the jobs, or by their order of arrival. The algorithm repeatedly executes the following steps until a valid schedule is obtained:

• Take the first job in the list (the one with the highest priority).
• Find a machine that is available for executing this job.
  • If a machine is found, schedule this job on that machine.
  • Otherwise (no suitable machine is available), select the next job in the list.

Example

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.

Performance guarantee

The algorithm runs in time ${\displaystyle O(n)}$, where n is the number of jobs. The algorithm always returns a partition of the jobs whose makespan is at most ${\displaystyle 2-1/m}$ times the optimal makespan. ^[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 algorithm can be used as an online algorithm, when the order in which the items arrive cannot be controlled.

Ordering 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: ^[2]

• Highest level first algorithm, or HLF;
• Longest path algorithm or LP;
• Longest-processing-time-first scheduling, or LPT; this variant decreases the approximation ratio to ${\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}}$.
• Critical path method.
• Heterogeneous Earliest Finish Time or HEFT. For the case heterogeneous workers.

Anomalies

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:

• 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, [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₁ machines and the makespan was t₁. Now, we have m₂ 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: ^{[1] [3]}

${\displaystyle {\frac {t_{2}}{t_{1}}}\leq 1+{\frac {m_{1}-1}{m_{2}}}}$.

In particular, with the same number of machines, the ratio is ${\displaystyle 2-{\frac {1}{m}}}$. A special case is when the original schedule is optimal; this yields the bound ${\displaystyle 2-{\frac {1}{m}}}$ on the approximation ratio.

References

1. Graham, Ron L. (1969-03-01). "Bounds on Multiprocessing Timing Anomalies" . SIAM Journal on Applied Mathematics. 17 (2): 416–429. doi:10.1137/0117039. ISSN   0036-1399.
2. Micheli, Giovanni De (1994). Synthesis and optimization of digital circuits. New York: McGraw-Hill. ISBN   978-0070163331.
3. Graham, Ron L. (1966). "Bounds for Certain Multiprocessing Anomalies". Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x. ISSN   1538-7305.