@techreport{TR-IC-03-11,
  number = {IC-03-11},
  author = {E. C. Xavier and F. K. Miyazawa},
  title = {Practical Comparison of Approximation Algorithms
           for Scheduling Problems},
  month = {April},
  year = {2003}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 17 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       In   this  paper   we   consider  an   experimental  study   of
       approximation  algorithms for  scheduling problems  in parallel
       machines minimizing  the average weighted  completion time.  We
       implemented   approximation   algorithms   for  the   following
       problems: $P | r_j| \sum C_j$ , $P||\sum w_j C_j$ , $P|r_j|\sum
       w_j  C_j$, $R||\sum  w_j  C_j$ and  $R|r_j|\sum  w_j C_j$.   We
       generated  about  900  tests   over  more  than  190  different
       instances and present some practical aspects of the implemented
       algorithms.   We also  made an  experimental comparison  on two
       lower bounds based in  the formulations used by the algorithms.
       The  first one is  a semidefinite  formulation for  the problem
       $R||\sum w_j C_j$ and the other is a linear formulation for the
       problem  $R|r_j|\sum w_j  C_j$. For  all tests,  the algorithms
       obtained very good results.  We note that algorithms using more
       refined  techniques, when  compared to  algorithms  with simple
       strategies,  does not  necessary leads  to better  results.  We
       also present two heuristics, based in approximation algorithms,
       that  generates solutions  with  better quality  in almost  all
       instances considered.
  }
}