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:
Record Created:22 Feb 2012 16:05
Last Modified:08 Sep 2014 11:04

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Look up in GoogleScholar | Find in a UK Library