Preemptive Scheduling of Equal-Length Jobs in Polynomial Time

George B. Mertzios, Walter Unger

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
$\sum_{i=1}^{n}w_{i}C_{i}$ 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((\frac{n}{k}+1)^{k}n^{8})$
and hence, the problem is polynomially solvable for any fixed number $k$
of different weights.