Preemptive scheduling of equal-length jobs in polynomial time.

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.