Answer to Question #187541 in Algorithms for tejaswini

Question

 Consider the following instance of load balancing problem. There are m machines and n=2m+1 jobs, 3 jobs are of length m and 2 jobs of m+i for each 1<= i <= m-1. Show that on this instance the list-scheduling algorithm with the LPT rule achieves the approximation ratio 4/3-1/3m.  

Answer 1

FOR i = 1TO m 
L[i]<-0. 
S[i]<-∅.
FOR j = 1TO (2m +1)
i <-argmin k L[k]. 
S[i]<- S[i] ∪ {j}. L[i]<- L[i] + tj.
RETURN S[1], S[2], ..., S[m]