An update on the asymptotic optimality of the longest processing time heuristic

DOI10.1007/S10951-025-00862-ZMaRDI QIDQ7288389zbMATH OpenFDO

Authors Anne Benoit, Louis-Claude Canon, Pierre-Cyrille Héam

Publication date 30 June 2026

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10951-025-00862-Z

Mathematics Subject Classification ID

Mathematical modeling or simulation for problems pertaining to operations research and mathematical programming (90-10) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Cites work

• A calculus for the random generation of labelled combinatorial structures
• An Application of Bin-Packing to Multiprocessor Scheduling
• Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
• Analytic combinatorics
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Bounds on Multiprocessing Timing Anomalies
• scientific article; zbMATH DE number 3768966 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 947476 (Why is no real title available?)
• scientific article; zbMATH DE number 2230249 (Why is no real title available?)
• Multiprocessor scheduling: Combining LPT and MULTIFIT
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• The Asymptotic Optimality of the LPT Rule
• The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
• The longest processing time rule for identical parallel machines revisited
• The rate of convergence to optimality of the LPT rule
• Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling

This page was built for publication: An update on the asymptotic optimality of the longest processing time heuristic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7288389)