A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines

DOI10.1287/OPRE.45.1.116MaRDI QIDQ4367269zbMATH OpenOpenAlexFDO

Authors Paul Mireault, James B. Orlin, Rakesh V. Vohra

Publication date 25 November 1997

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/459a059f827b73ead464f7f77c1b7d9e7329975d

zbMATH Keywords

makespanuniform parallel machineslargest processing time first

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Scheduling Independent Tasks on Uniform Processors
• A note on LPT scheduling
• Parametric bounds for LPT scheduling on uniform processors
• A modified LPT algorithm for the two uniform parallel machine makespan minimization problem
• A note on LPT scheduling

Cited in

(23)

• A survey on makespan minimization in semi-online environments
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• A modified LPT algorithm for the two uniform parallel machine makespan minimization problem
• Semi-online machine covering for two uniform machines
• Parametric analysis of the quality of single preemption schedules on three uniform parallel machines
• A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem
• The rate of convergence to optimality of the LPT rule
• New approximation bounds for LPT scheduling
• The longest processing time rule for identical parallel machines revisited
• Tighter approximation bounds for LPT scheduling in two special cases
• scientific article; zbMATH DE number 1094170 (Why is no real title available?)
• Approximate strong equilibria in job scheduling games with two uniformly related machines
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• Online makespan scheduling with job migration on uniform machines
• Semi-online scheduling with known maximum job size on two uniform machines
• A linear compound algorithm for uniform machine scheduling
• Single parameter analysis of power of preemption on two and three uniform machines
• Semi-online scheduling with bounded job sizes on two uniform machines
• Optimal and online preemptive scheduling on uniformly related machines
• Scheduling Independent Tasks on Uniform Processors
• A note on MULTIFIT scheduling for uniform machines
• Optimal on-line algorithms to minimize makespan on two machines with resource augmentation
• Online Makespan Scheduling with Job Migration on Uniform Machines

This page was built for publication: A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines

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