Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Tighter Approximation Bounds for LPT Scheduling in Two Special Cases


Kovács,  Annamária
Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Kovács, A. (2006). Tighter Approximation Bounds for LPT Scheduling in Two Special Cases. In Algorithms and Complexity: 6th Italian Conference, CIAC 2006 (pp. 187-198). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2433-9
Q||C max denotes the problem of scheduling n jobs on m machines of different speeds such that the makespan is minimized. In the paper two special cases of Q||C max are considered: Case I, when m–1 machine speeds are equal, and there is only one faster machine; and Case II, when machine speeds are all powers of 2. Case I has been widely studied in the literature, while Case II is significant in an approach to design so called monotone algorithms for the scheduling problem. We deal with the worst case approximation ratio of the classic list scheduling algorithm ’Longest Processing Time (LPT)’. We provide an analysis of this ratio Lpt/Opt for both special cases: For one fast machine, a tight bound of is given. When machine speeds are powers of 2 (2-divisible machines), we show that in the worst case 41/30 <Lpt/Opt<42/30=1.4. To our knowledge, the best previous lower bound for both problems was 4/3–ε, whereas the best known upper bounds were 3/2–1/2m for Case I [6] resp. 3/2 for Case II [10]. For both the lower and the upper bound, the analysis of Case II is a refined version of that of Case I.