AIB 2008-10: Preemptive Scheduling of Equal-Length Jobs in Polynomial Time

The following technical report is available from http://aib.informatik.rwth-aachen.de: Preemptive Scheduling of Equal-Length Jobs in Polynomial Time George B. Mertzios, Walter Unger AIB 2008-10 We study the preemptive scheduling problem of a set of $n$ jobs with release times and equal processing time 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, where the number $k$ of different weights is constant. We provide for this problem a first polynomial algorithm with runtime $O(\frac{n^{k+8}}{k^{k}})$.