A PTAS for the average weighted completion time problem on unrelated machines
Lists
Only you see this
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...