The Asymptotic Optimality of the LPT Rule

DOI10.1287/moor.12.2.241zbMath0632.90031OpenAlexW1978788704MaRDI QIDQ3770267

Alexander H. G. Rinnooy Kan, J. B. G. Frenk

Publication date: 1987

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/5ca82a5e53628b56a1287344283f8fd1f870cbae

zbMATH Keywords

probabilistic analysisminimizing makespanLongest Processing Timeparallel machines of different speedstrong asymptotic optimality results

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

An introduction to the analysis of approximation algorithms ⋮ Sensitivity analysis of list scheduling heuristics ⋮ Effective on-line algorithms for reliable due date quotation and large-scale scheduling ⋮ List scheduling algorithms to minimize the makespan on identical parallel machines ⋮ Minmax scheduling with job-classes and earliness-tardiness costs ⋮ Approximate algorithms for the \(P\parallel C_{\max}\) problem ⋮ The longest processing time rule for identical parallel machines revisited ⋮ A note on posterior tight worst-case bounds for longest processing time schedules ⋮ The LPT heuristic for minimizing total load on a proportionate openshop ⋮ Concurrent stochastic methods for global optimization ⋮ On the asymptotic probabilistic analysis of scheduling problems in the presence of precedence constraints ⋮ A state-of-the-art review of parallel-machine scheduling research ⋮ Approximation results in parallel machines stochastic scheduling ⋮ Scheduling and due‐date quotation in a make‐to‐order supply chain ⋮ An algorithm for flow time minimization and its asymptotic makespan properties ⋮ Scheduling job classes on uniform machines ⋮ A common due-data assignment problem on parallel identical machines ⋮ A general lower bound for the makespan problem ⋮ Parallel machines scheduling with nonsimultaneous machine available time ⋮ New directions in scheduling theory ⋮ Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs ⋮ Bounds and asymptotic results for the uniform parallel processor weighted flow time problem ⋮ An analysis of the LPT algorithm for the max-min and the min-ratio partition problems