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: | (AM) Accepted Manuscript Download PDF (205Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1007/s11786-009-0003-z |
| Publisher statement: | The final publication is available at Springer via http://dx.doi.org/10.1007/s11786-009-0003-z. |
| 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
| Export: | |
| Look up in GoogleScholar |
