An alternative proof of the Kawaguchi-Kyan bound for the largest-ratio-first rule

DOI10.1016/j.orl.2011.06.007zbMath1242.90080OpenAlexW1993301069MaRDI QIDQ433121

Uwe Schwiegelshohn

Publication date: 13 July 2012

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2011.06.007

zbMATH Keywords

worst case analysisperformance guaranteetotal weighted completion time scheduling

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

Unnamed Item, The largest-Z-ratio-first algorithm is 0.8531-approximate for scheduling unreliable jobs on \(m\) parallel machines, Improved analysis of two algorithms for min-weighted sum bin packing, On the Integration of Theoretical Single-Objective Scheduling Results for Multi-objective Problems

Cites Work

• Structure of a simple scheduling polyhedron
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem