Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Preemptive scheduling of equal-length jobs in polynomial time
Mertzios, G.B.; Unger, W.
Authors
W. Unger
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.
Citation
Mertzios, G., & Unger, W. (2010). Preemptive scheduling of equal-length jobs in polynomial time. Mathematics in Computer Science, 3(1), 73-84. https://doi.org/10.1007/s11786-009-0003-z
Journal Article Type | Article |
---|---|
Publication Date | Mar 1, 2010 |
Deposit Date | Dec 8, 2011 |
Publicly Available Date | Mar 28, 2024 |
Journal | Mathematics in Computer Science |
Print ISSN | 1661-8270 |
Electronic ISSN | 1661-8289 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 3 |
Issue | 1 |
Pages | 73-84 |
DOI | https://doi.org/10.1007/s11786-009-0003-z |
Keywords | Machine scheduling, Preemptive scheduling, Equal-length jobs, Parameterized algorithm, Polynomial algorithm. |
Files
Accepted Journal Article
(210 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/s11786-009-0003-z.
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search