Preemptive scheduling of equal-length jobs in polynomial time

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 åi=1nwiCini=1wiCi 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((\fracnk+1)kn8)Okn+1kn8 and hence, the problem is polynomially solvable for any fixed number k of different weights.

Citation

Mertzios, G., & Unger, W. (2010). Preemptive scheduling of equal-length jobs in polynomial time. Mathematics in Computer Science, 3(1), 73-84. https://doi.org/10.1007/s11786-009-0003-z

• Journal Article Type: Article
• Publication Date: Mar 1, 2010
• Deposit Date: Dec 8, 2011
• Publicly Available Date: Jan 10, 2012
• Journal: Mathematics in Computer Science
• Print ISSN: 1661-8270
• Electronic ISSN: 1661-8289
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 3
• Issue: 1
• Pages: 73-84
• DOI: https://doi.org/10.1007/s11786-009-0003-z
• Keywords: Machine scheduling, Preemptive scheduling, Equal-length jobs, Parameterized algorithm, Polynomial algorithm.
• Public URL: https://durham-repository.worktribe.com/output/1524682