Publication details for Dr George MertziosMertzios, G.B. & Unger, W. (2010). Preemptive scheduling of equal-length jobs in polynomial time. Mathematics in Computer Science 3(1): 73-84.
- Publication type: Journal Article
- ISSN/ISBN: 1661-8270, 1661-8289
- DOI: 10.1007/s11786-009-0003-z
- Keywords: Machine scheduling, Preemptive scheduling, Equal-length jobs, Parameterized algorithm, Polynomial algorithm.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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 ∑
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((
+1)kn8) and hence, the problem is polynomially solvable for any fixed number k of different weights.