LPT sequencing

largest-processing-time-first sequencing

A sequencing rule in scheduling theory that prioritizes jobs (or tasks) to be scheduled according to an order of their non-increasing processing times.

One of the fundamental problems in scheduling is to schedule $n$ independent jobs (tasks) non-pre-emptively on $m\geq2$ parallel machines (processors) so as to minimize the schedule makespan, i.e., the overall completion time. For this strongly $\mathcal N\mathcal P$-hard problem [a5] (cf. also $\mathcal N\mathcal P$), R.L. Graham has proposed a very simple heuristic or approximation algorithm, known as list scheduling, usually abbreviated LS, which first puts the jobs in any priority list and then always assigns the first job in the remaining list to the first available machine. He has proved that such a heuristic has a worst-case performance ratio of $2-1/m$, where the worst-case performance ratio of a heuristic $H$ is the infimum of all those $\rho$ such that, for any problem instance, the makespan of the schedule generated by $H$ is no more than $\rho$ times the minimum one, and hence it indicates a performance guarantee of $H$.

Based on an observation on list scheduling that the worst situation occurs when the job that terminates the schedule is long, R.L. Graham [a6] has improved list scheduling by choosing a particular initial priority list — LPT sequence, which ends with shortest jobs. He shows that the LPT heuristic has a worst-case performance ratio of $4/3-1/(3m)$. However, empirical experiments show that the LPT heuristic performs much better in practice than its worst-case performance ratio can indicate, especially as the number of jobs becomes large. Consequently, E.G. Coffman and R. Sethi [a3] have generalized Graham's LPT bound so as to include a parameter characterizing the numbers of jobs assigned to machines by LPT. They show that, if an LPT schedule has a last-finishing job that runs on a machine with at least $k-1$ other jobs ($k\geq3$), then the worst-case performance ratio of LPT is actually $(k+1)/k-1/(km)$. J.D. Blocher and S. Chand [a1] and B. Chen [a2] have further strengthened the bound a posteriori by providing a stronger lower bound on the optimal makespan. These results show that the LPT heuristic is actually asymptotically optimal.

In terms of average-case performance, under mild conditions on the probability distribution, J.B.G. Frenk and A.H.G. Rinnooy Kan [a4] have proved that LPT is asymptotically absolutely as well as relatively optimal in expectation, even if the machines have different speeds.

With such a good performance, the LPT heuristic has been successfully applied to various scheduling environments in delivering a near minimum-makespan schedule. For example, in multi-stage scheduling with parallel machines, where each job has to be processed in some stages at different time periods and each stage consists of a number of parallel machines, LPT scheduling is applied at each individual stage. In on-line parallel scheduling, where jobs arrive over time and the existence and processing time of each job is unknown until its arrival, LPT scheduling is used between any two consecutive arrival times.

More importantly, with its excellent balance between efficiency and effectiveness as a heuristic, LPT has become a touchstone for the design of heuristic scheduling algorithms of high quality.

References

[a1]	J.D. Blocher, S. Chand, "Scheduling of parallel processors: A posterior bound on LPT sequencing and a two-step algorithm" Naval Research Logistics , 38 (1991) pp. 273–287
[a2]	B. Chen, "A note on LPT scheduling" Oper. Res. Lett. , 14 (1993) pp. 139–142
[a3]	E.G. Coffman Jr., R. Sethi, "A generalized bound on LPT sequencing" Revue Française d'Automatique Informatique: Recherche Operationnelle , S10 (1976) pp. 17–25
[a4]	J.B.G. Frenk, A.H.G. Rinnooy Kan, "The asymptotic optimality of the LPT rule" Math. Operations Res. , 12 (1987) pp. 241–254
[a5]	M.R. Garey, D.S. Johnson, "Strong NP-completeness results: Motivation, examples and implications" J. Assoc. Comput. Mach. , 25 (1978) pp. 499–508
[a6]	R.L. Graham, "Bounds on multiprocessor timing anomalies" SIAM J. Appl. Math. , 17 (1969) pp. 416–429