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 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.

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

Item Type:Conference item (Paper)
Full text:PDF - Accepted Version
Publisher-imposed embargo
(87Kb)
Status:Peer-reviewed
Publisher Web site:http://www.promoteresearch.org/2009/proceedings-listing-2009/tmfcs09.html
Record Created:22 Feb 2012 16:05
Last Modified:08 Sep 2014 11:04

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