7 Mai
2008
7 Mai
'08
19:16
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}})$.