Scheduling to minimize the average completion time of dedicated tasks

Foto Afrati, Evripidis Bampis, Aleksei V. Fishkin, Klaus Jansen, Claire Kenyon

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


We propose a polynomial time approximation scheme for schedu\-ling a set of dedicated tasks on a constant number $m$ of processors in order to minimize the sum of completion times $Pm| \mbox{fix}_j |\sum C_j$. In addition we give a polynomial time approximation scheme for the weighted preemptive problem with release dates, $Pm| \mbox{fix}_j,pmtn,r_j |\sum w_j C_j$.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems