A polynomial time approximation scheme for the average weighted completion time problem on unrelated machines

A polynomial time approximation scheme for the average weighted completion time problem on unrelated machines

0.00 Avg rating—0 Votes
Article ID: iaor20012779
Country: United Kingdom
Volume: 3
Issue: 6
Start Page Number: 323
End Page Number: 332
Publication Date: Nov 2000
Journal: Journal of Scheduling
Authors: , , ,
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 𝒫 = NP.

Reviews

Required fields are marked *. Your email address will not be published.