A PTAS for the average weighted completion time problem on unrelated machines

Foto Afrati, Evripidis Bampis, Claire Kenyon, Ioannis MilisJournal of Scheduling 2000 · DOI

Abstract

We study the problem of scheduling n independent weighted jobs on a constant number of unrelated parallel machines so as to minimize the weighted sum of job completion times Rm∣∣∑wjCj. We present an O(n log n) time approximation scheme for the non-preemptive case of this problem. Notice that when the number of machines is not a constant (i.e. R∣∣∑wjCj) then no PTAS is possible, unless 𝒫=𝒩𝒫. Copyright © 2000 John Wiley & Sons, Ltd.
BibTeX
@article{afrati2000ptas,
  author = {Foto Afrati and Evripidis Bampis and Claire Kenyon and Ioannis Milis},
  title = {{A PTAS for the average weighted completion time problem on unrelated machines}},
  journal = {Journal of Scheduling},
  year = {2000},
  doi = {10.1002/1099-1425(200011/12)3:6<323::aid-jos52>3.0.co;2-e},
}

Loading related content...

Figure