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

DOI10.1287/OPRE.45.1.116zbMATH Open0899.90112OpenAlexW2160030032MaRDI QIDQ4367269FDOQ4367269

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

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

zbMATH Keywords

makespanuniform parallel machineslargest processing time first

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cited In (23)

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

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)