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:

Preemptive scheduling of equal-length jobs in polynomial time.

Mertzios, G.B. and Unger, W. (2010) 'Preemptive scheduling of equal-length jobs in polynomial time.', Mathematics in computer science., 3 (1). pp. 73-84.


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 åi=1nwiCini=1wiCi 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((\fracnk+1)kn8)Okn+1kn8 and hence, the problem is polynomially solvable for any fixed number k of different weights.

Item Type:Article
Additional Information:Issue title: 'Advances in combinatorial algorithms I'.
Keywords:Machine scheduling, Preemptive scheduling, Equal-length jobs, Parameterized algorithm, Polynomial algorithm.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:10 January 2012
Date of first online publication:March 2010
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar