A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times

Authors Alejandro Lopez-Ortiz, Claude-Guy Quimper



PDF
Thumbnail PDF

File

LIPIcs.STACS.2011.380.pdf
  • Filesize: 0.77 MB
  • 12 pages

Document Identifiers

Author Details

Alejandro Lopez-Ortiz
Claude-Guy Quimper

Cite AsGet 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).
Keywords
  • Scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail