HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Update on the Asymptotic Optimality of LPT

Abstract : When independent tasks are to be scheduled onto identical processors, the typical goal is to minimize the makespan. A simple and efficient heuristic consists in scheduling first the task with the longest processing time (LPT heuristic), and to plan its execution as soon as possible. While the performance of LPT has already been largely studied, in particular its asymptotic performance, we revisit results and propose a novel analysis for the case of tasks generated through uniform integer compositions. Also, we perform extensive simulations to empirically assess the asymptotic performance of LPT. Results demonstrate that the absolute error rapidly tends to zero for several distributions of task costs, including ones studied by theoretical models, and realistic distributions coming from benchmarks.
Complete list of metadata

https://hal.inria.fr/hal-03159022
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Thursday, March 4, 2021 - 11:45:35 AM
Last modification on : Monday, May 16, 2022 - 4:46:02 PM
Long-term archiving on: : Saturday, June 5, 2021 - 6:42:39 PM

File

RR-9397.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03159022, version 1

Citation

Anne Benoit, Louis-Claude Canon, Redouane Elghazi, Pierre-Cyrille Heam. Update on the Asymptotic Optimality of LPT. [Research Report] RR-9397, Inria Grenoble - Rhône-Alpes. 2021, pp.23. ⟨hal-03159022⟩

Share

Metrics

Record views

59

Files downloads

274