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

Mertzios, G.B.; Unger, W.

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, July). A parameterized algorithm for the preemptive scheduling of equal-length jobs. Presented at International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-09), Orlando, Florida

• Presentation Conference Type: Conference Paper (published)
• Conference Name: International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-09)
• Start Date: Jul 16, 2009
• End Date: Jul 19, 2009
• Publication Date: Jul 1, 2009
• Deposit Date: Dec 8, 2011
• Pages: 20-27
• Public URL: https://durham-repository.worktribe.com/output/1158169
• Publisher URL: http://www.promoteresearch.org/2009/proceedings-listing-2009/tmfcs09.html
• Additional Information: Conference dates: July 13-16, 2009