Skip to main content

Research Repository

Advanced Search

A parameterized algorithm for the preemptive scheduling of equal-length jobs

Mertzios, G.B.; Unger, W.

Authors

W. Unger



Abstract

We study the preemptive scheduling problem of a set of n jobs with release times and equal processing times on a single machine. The objective is to minimize the sum of the weighted completion times n i=1 wiCi of the jobs. We propose for this problem the first parameterized algorithm on the number k of different weights. The runtime of the proposed algorithm is O((n k +1)kn8) and hence, this is the first polynomial algorithm for any fixed number k of different weights

Citation

Mertzios, G., & Unger, W. (2009). A parameterized algorithm for the preemptive scheduling of equal-length jobs.

Conference Name International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-09)
Conference Location Orlando, Florida
Start Date Jul 16, 2009
End Date Jul 19, 2009
Publication Date Jul 1, 2009
Deposit Date Dec 8, 2011
Pages 20-27
Publisher URL http://www.promoteresearch.org/2009/proceedings-listing-2009/tmfcs09.html
Additional Information Conference dates: July 13-16, 2009


You might also like



Downloadable Citations