A 3/2 dual approximation for minimizing the makespan of independent tasks on heterogeneous processors
SpeakerMarin Bougeret
Co-authorsPierre-Francois Dutot, Erik Saule
We present an extension of the 2 approximation of Gonzalez, Ibarra and Sahni[SIAM 77] for the problem of minimizing makespan when scheduling independent tasks on heterogeneous processors (Q||Cmax).
We will first consider two classical list algorithms for this problem : Earliest Finish Time (EFT), and Earliest Finish Time with sorting tasks (EFT-LPT). After showing why EFT has an approximation ratio of Ω( log n), we will sketch the Gonzalez, Ibarra and Sahni analysis of ratio 2 for EFT-LPT.
Then we present our 3/2 dual approximation, with the proof of the bound and a worst case example which reaches the bound, proving its tightness.
slides(pdf)