Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430641 | Journal of Discrete Algorithms | 2009 | 14 Pages |
Q||CmaxQ||Cmax 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||CmaxQ||Cmax are considered: case I, when m−1m−1 machine speeds are equal, and there is only one faster machine; and case II, when machine speeds are all powers of 2 (2-divisible machines). 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 ‘Largest Processing Time (LPT)’. We provide an analysis of this ratio Lpt/OptLpt/Opt for both special cases: For ‘one fast machine’, a tight bound of (3+1)/2≈1.3660 is given. For 2-divisible machines, we show that in the worst case 1.3673