Cookies

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.

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 å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:PDF - Accepted Version (205Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/s11786-009-0003-z
Publisher statement:The original publication is available at www.springerlink.com
Record Created:15 Dec 2011 12:35
Last Modified:10 Jan 2012 15:16

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