We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

A parameterized algorithm for the preemptive scheduling of equal-length jobs.

Mertzios, G.B. and 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, 16-19 July 2009.


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

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Publisher Web site:
Date accepted:No date available
Date deposited:08 September 2014
Date of first online publication:July 2009
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar