Document Open Access Logo

Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines

Authors Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, Denis Trystram

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.24.pdf
  • Filesize: 426 kB
  • 12 pages

Document Identifiers

Author Details

Giorgio Lucarelli
  • LCOMS, University of Lorraine, Metz, France
Benjamin Moseley
  • Tepper School of Business, Carnegie Mellon University, USA
Nguyen Kim Thang
  • IBISC, Univ. Paris-Saclay, France
Abhinav Srivastav
  • IBISC, Univ. Paris-Saclay, France
Denis Trystram
  • Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, France

Funding

  • Moseley, Benjamin: Google Research Award and NSF grants CCF-1830711, CCF-1824303, and CCF-1733873
  • Thang, Nguyen Kim: OATA ANR-15-CE40-0015-01
  • Srivastav, Abhinav: OATA ANR-15-CE40-0015-01

Cite As Get BibTex

Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.FSTTCS.2019.24

Abstract

We consider the problem of scheduling jobs to minimize the maximum weighted flow-time on a set of related machines. When jobs can be preempted this problem is well-understood; for example, there exists a constant competitive algorithm using speed augmentation. When jobs must be scheduled non-preemptively, only hardness results are known. In this paper, we present the first online guarantees for the non-preemptive variant. We present the first constant competitive algorithm for minimizing the maximum weighted flow-time on related machines by relaxing the problem and assuming that the online algorithm can reject a small fraction of the total weight of jobs. This is essentially the best result possible given the strong lower bounds on the non-preemptive problem without rejection.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • Online Algorithms
  • Scheduling
  • Resource Augmentation

Metrics

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

References

  1. C. Ambühl and M. Mastrolilli. On-line scheduling to minimize max flow time: an optimal preemptive algorithm. Oper. Res. Lett., 33(6):597-602, 2005. Google Scholar
  2. S. Anand, K. Bringmann, T. Friedrich, N. Garg, and A. Kumar. Minimizing Maximum (Weighted) Flow-time on Related and Unrelated Machines. In Proceedings of International Colloquium on Automata, Languages and Programming, pages 13-24, 2013. Google Scholar
  3. S. Anand, N. Garg, and A. Kumar. Resource augmentation for weighted flow-time explained by dual fitting. In Proceedings of Symposium on Discrete Algorithms, pages 1228-1241, 2012. Google Scholar
  4. N. Bansal and E. Cloostermans. Minimizing Maximum Flow-Time on Related Machines. In Proceedings of Workshop on Approximation Algorithms for Combinatorial Problems, pages 1-14, 2015. Google Scholar
  5. N. Bansal and K. Pruhs. Server Scheduling in the Weighted 𝓁p Norm. In Proceedings of Latin American Symposium on Theoretical Informatics, pages 434-443, 2004. Google Scholar
  6. Chandra Chekuri, Sungjin Im, and Benjamin Moseley. Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor. Theory of Computing, 8(1):165-195, 2012. Google Scholar
  7. A.R. Choudhury, S. Das, N. Garg, and A .Kumar. Rejecting jobs to Minimize Load and Maximum Flow-time. In Proceedings of Symposium on Discrete Algorithms, pages 1114-1133, 2015. Google Scholar
  8. A.R. Choudhury, S. Das, A. Kumar, P. Harsha, and G. Ramalingam. Minimizing weighted 𝓁_p-norm of flow-time in the rejection model. In Proceedings on the Conference on Foundations of Software Technology and Theoretical Computer Science, volume 45, pages 25-37, 2015. Google Scholar
  9. P.F. Dutot, E. Saule, A. Srivastav, and Denis D. Trystram. Online Non-preemptive Scheduling to Optimize Max Stretch on a Single Machine. In Proceedings of nternational Conference on Computing and Combinatorics, pages 483-495, 2016. Google Scholar
  10. K. Fox, S. Im, and B. Moseley. Energy efficient scheduling of parallelizable jobs. In Proceedings of Symposium on Discrete Algorithms, pages 948-957, 2013. Google Scholar
  11. A. Gupta, S. Im, R. Krishnaswamy, B. Moseley, and K. Pruhs. Scheduling heterogeneous processors isn't as easy as you think. In Proceedings of Symposium on Discrete Algorithms, pages 1242-1253, 2012. Google Scholar
  12. B. Kalyanasundaram and K. Pruhs. Speed is as powerful as clairvoyance. Journal of ACM, 47(4):617-643, 2000. Google Scholar
  13. Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality. In European Symposium on Algorithms (ESA, 2016), volume 57, pages 1-17, 2016. Google Scholar
  14. B.A. Michael, S. Chakrabarti, and S. Muthukrishnan. Flow and Stretch Metrics for Scheduling Continuous Job Streams. In Proceedings of the Annual Symposium on Discrete Algorithms, pages 270-279, 1998. Google Scholar
  15. C.A. Phillips, C. Stein, and E. Torng andJ. Wein. Optimal time-critical scheduling via resource augmentation. Algorithmica, 32(2):163-200, 2002. Google Scholar
  16. Im S, B. Moseley, K. Pruhs, and C. Stein. Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pages 51:1-51:10, 2017. Google Scholar
  17. N.K. Thang. Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling. In Proceedings of European Symposium on Algorithms, pages 755-766, 2013. 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