LIPIcs.STACS.2011.380.pdf
- Filesize: 0.77 MB
- 12 pages
Document
A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times
Authors
-
Part of:
Volume:
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2011-03-11
Cite As Get BibTex
Alejandro Lopez-Ortiz and Claude-Guy Quimper. A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 380-391, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.STACS.2011.380
Abstract
Consider the problem of scheduling a set of tasks of length p without preemption on $m$ identical machines with given release and deadline times. We present a new algorithm for computing the schedule with minimal completion times and makespan. The algorithm has time complexity O(min(1,p/m)n^2) which improves substantially over the best known algorithm with complexity O(mn^2).
Subject Classification
Keywords
- Scheduling
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads