Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Publication details for Dr George Mertzios

Mertzios, G.B. & Unger, W. (2009), A parameterized algorithm for the preemptive scheduling of equal-length jobs, International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-09). Orlando, Florida, ISRST, Orlando FL, 20-27.

Author(s) from Durham

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
n
i=1 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((n
k +1)kn8) and hence, this is the first polynomial
algorithm for any fixed number k of different weights

Notes

Conference dates: July 13-16, 2009