Document Open Access Logo

Minimizing Maximum Flow-time on Related Machines

Authors Nikhil Bansal, Bouke Cloostermans

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.85.pdf
  • Filesize: 427 kB
  • 11 pages

Document Identifiers

Author Details

Nikhil Bansal
Bouke Cloostermans

Cite As Get BibTex

Nikhil Bansal and Bouke Cloostermans. Minimizing Maximum Flow-time on Related Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 85-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.85

Abstract

We consider the online problem of minimizing the maximum flow-time on related machines. This is a natural generalization of the extensively studied makespan minimization problem to the setting where jobs arrive over time. Interestingly, natural algorithms such as Greedy or Slow-fit that work for the simpler identical machines case or for makespan minimization on related machines, are not O(1)-competitive. Our main result is a new O(1)-competitive algorithm for the problem. Previously, O(1)-competitive algorithms were known only with resource augmentation, and in fact no O(1) approximation was known even in the offline case.

Subject Classification

Keywords
  • Related machines scheduling
  • Maximum flow-time minimization
  • On-line algorithm
  • Approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Susanne Albers. Introduction to scheduling, chapter Online scheduling, pages 51-73. Chapman and Hall/CRC, 2010. Google Scholar
  2. Christoph Ambühl and Monaldo Mastrolilli. On-line scheduling to minimize max flow time: an optimal preemptive algorithm. Oper. Res. Lett., 33(6):597-602, 2005. Google Scholar
  3. S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, and Amit Kumar. Minimizing maximum (weighted) flow-time on related and unrelated machines. In ICALP (1), pages 13-24, 2013. Google Scholar
  4. S. Anand, Naveen Garg, and Amit Kumar. Resource augmentation for weighted flow-time explained by dual fitting. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1228-1241, 2012. Google Scholar
  5. Yossi Azar. On-line load balancing. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms, volume 1442 of Lecture Notes in Computer Science, pages 178-195. Springer, 1998. Google Scholar
  6. Yossi Azar, Bala Kalyanasundaram, Serge A. Plotkin, Kirk Pruhs, and Orli Waarts. On-line load balancing of temporary tasks. J. Algorithms, 22(1):93-110, 1997. Google Scholar
  7. Nikhil Bansal and Janardhan Kulkarni. Minimizing flow-time on unrelated machines. In Symposium on Theory of Computing, STOC, 2015, to appear. Google Scholar
  8. Michael A. Bender, Soumen Chakrabarti, and S. Muthukrishnan. Flow and stretch metrics for scheduling continuous job streams. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 270-279, 1998. Google Scholar
  9. Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science, 3(2-3):93-263, 2009. Google Scholar
  10. Chandra Chekuri and Benjamin Moseley. Online scheduling to minimize the maximum delay factor. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1116-1125. Society for Industrial and Applied Mathematics, 2009. Google Scholar
  11. Yookun Cho and Sartaj Sahni. Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9(1):91-103, 1980. Google Scholar
  12. Naveen Garg. Minimizing average flow-time. In Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, pages 187-198, 2009. Google Scholar
  13. Sungjin Im, Benjamin Moseley, and Kirk Pruhs. A tutorial on amortized local competitiveness in online scheduling. SIGACT News, 42(2):83-97, 2011. Google Scholar
  14. Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. J. ACM, 47(4):617-643, 2000. Google Scholar
  15. Kirk Pruhs, Jiri Sgall, and Eric Torng. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter Online Scheduling. CRC Press, 2004. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact