Document Open Access Logo

Online Makespan Scheduling with Job Migration on Uniform Machines

Authors Matthias Englert, David Mezlaf, Matthias Westermann

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.26.pdf
  • Filesize: 382 kB
  • 14 pages

Document Identifiers

Author Details

Matthias Englert
  • DIMAP and Department of Computer Science, University of Warwick, Coventry, UK
David Mezlaf
  • Department of Computer Science, TU Dortmund, Dortmund, Germany
Matthias Westermann
  • Department of Computer Science, TU Dortmund, Dortmund, Germany

Cite As Get BibTex

Matthias Englert, David Mezlaf, and Matthias Westermann. Online Makespan Scheduling with Job Migration on Uniform Machines. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.26

Abstract

In the classic minimum makespan scheduling problem, we are given an input sequence of n jobs with sizes. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we allow the online algorithm to reassign up to k jobs to different machines in the final assignment.
For m identical machines, Albers and Hellwig (Algorithmica, 2017) give tight bounds on the competitive ratio in this model. The precise ratio depends on, and increases with, m. It lies between 4/3 and ~~ 1.4659. They show that k = O(m) is sufficient to achieve this bound and no k = o(n) can result in a better bound.
We study m uniform machines, i.e., machines with different speeds, and show that this setting is strictly harder. For sufficiently large m, there is a delta = Theta(1) such that, for m machines with only two different machine speeds, no online algorithm can achieve a competitive ratio of less than 1.4659 + delta with k = o(n).
We present a new algorithm for the uniform machine setting. Depending on the speeds of the machines, our scheduling algorithm achieves a competitive ratio that lies between 4/3 and ~~ 1.7992 with k = O(m). We also show that k = Omega(m) is necessary to achieve a competitive ratio below 2.
Our algorithm is based on a subtle imbalance with respect to the completion times of the machines, complemented by a bicriteria approximation algorithm that minimizes the makespan and maximizes the average completion time for certain sets of machines.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • online algorithms
  • competitive analysis
  • minimum makespan scheduling
  • job migration

Metrics

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

References

  1. Susanne Albers. Better bounds for online scheduling. SIAM Journal on Computing, 29(2):459-473, 1999. Google Scholar
  2. Susanne Albers and Matthias Hellwig. On the value of job migration in online makespan minimization. Algorithmica, 79(2):598-623, 2017. Google Scholar
  3. James Aspnes, Yossi Azar, Amos Fiat, Serge A. Plotkin, and Orli Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM, 44(3):486-504, 1997. Google Scholar
  4. Yair Bartal, Amos Fiat, Howard J. Karloff, and Rakesh Vohra. New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences, 51(3):359-366, 1995. Google Scholar
  5. Yair Bartal, Howard J. Karloff, and Yuval Rabani. A better lower bound for on-line scheduling. Information Processing Letters, 50(3):113-116, 1994. Google Scholar
  6. Piotr Berman, Moses Charikar, and Marek Karpinski. On-line load balancing for related machines. Journal of Algorithms, 35(1):108-121, 2000. Google Scholar
  7. Bo Chen, André van Vliet, and Gerhard J. Woeginger. New lower and upper bounds for on-line scheduling. Operations Research Letters, 16(4):221-230, 1994. Google Scholar
  8. Xin Chen, Yan Lan, Attila Benko, György Dósa, and Xin Han. Optimal algorithms for online scheduling with bounded rearrangement at the end. Theoretical Computer Science, 412(45):6269-6278, 2011. Google Scholar
  9. Ning Ding, Yan Lan, Xin Chen, György Dósa, He Guo, and Xin Han. Online minimum makespan scheduling with a buffer. International Journal of Foundations of Computer Science, 25(5):525-536, 2014. Google Scholar
  10. György Dósa and Leah Epstein. Online scheduling with a buffer on related machines. Journal of Combinatorial Optimization, 20(2):161-179, 2010. Google Scholar
  11. György Dósa and Leah Epstein. Preemptive online scheduling with reordering. SIAM Journal on Discrete Mathematics, 25(1):21-49, 2011. Google Scholar
  12. György Dósa, Yuxin Wang, Xin Han, and He Guo. Online scheduling with rearrangement on two related machines. Theoretical Computer Science, 412(8-10):642-653, 2011. Google Scholar
  13. Tomás Ebenlendr and Jirí Sgall. A lower bound on deterministic online algorithms for scheduling on related machines without preemption. Theory of Computing Systems, 56(1):73-81, 2015. Google Scholar
  14. Matthias Englert, Deniz Özmen, and Matthias Westermann. The power of reordering for online minimum makespan scheduling. SIAM Journal on Computing, 43(3):1220-1237, 2014. Google Scholar
  15. Leah Epstein and Lene M. Favrholdt. Optimal preemptive semi-online scheduling to minimize makespan on two related machines. Operations Research Letters, 30(4):269-275, 2002. Google Scholar
  16. Leah Epstein, Asaf Levin, and Rob van Stee. Max-min online allocations with a reordering buffer. SIAM Journal on Discrete Mathematics, 25(3):1230-1250, 2011. Google Scholar
  17. Ulrich Faigle, Walter Kern, and György Turán. On the performance of on-line algorithms for partition problems. Acta Cybernetica, 9(2):107-119, 1989. Google Scholar
  18. Rudolph Fleischer and Michaela Wahl. On-line scheduling revisited. Journal of Scheduling, 3(6):343-353, 2000. Google Scholar
  19. Donald K. Friesen. Tighter bounds for LPT scheduling on uniform processors. SIAM Journal on Computing, 16(3):554-560, 1987. Google Scholar
  20. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  21. Todd Gormley, Nick Reingold, Eric Torng, and Jeffery Westbrook. Generating adversaries for request-answer games. In Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 564-565, 2000. Google Scholar
  22. Ronald L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45(1):1563-1581, 1966. Google Scholar
  23. Ronald L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics, 17(2):416-429, 1969. Google Scholar
  24. Dorit S. Hochbaum and David B. Shmoys. A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM Journal on Computing, 17(3):539-551, 1988. Google Scholar
  25. David R. Karger, Steven J. Phillips, and Eric Torng. A better algorithm for an ancient scheduling problem. Journal of Algorithms, 20(2):400-430, 1996. Google Scholar
  26. Hans Kellerer, Vladimir Kotov, Maria Grazia Speranza, and Zsolt Tuza. Semi on-line algorithms for the partition problem. Operations Research Letters, 21(5):235-242, 1997. Google Scholar
  27. Ming Liu, Yinfeng Xu, Chengbin Chu, and Feifeng Zheng. Online scheduling on two uniform machines to minimize the makespan. Theoretical Computer Science, 410(21-23):2099-2109, 2009. Google Scholar
  28. Paul Mireault, James B. Orlin, and Rakesh V. Vohra. A parametric worst case analysis of the LPT heuristic for two uniform machines. Operations Research, 45(1):116-125, 1997. Google Scholar
  29. Kirk Pruhs, Jiri Sgall, and Eric Torng. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter Online Scheduling. CRC Press, 2004. Google Scholar
  30. John F. Rudin III. Improved Bound for the Online Scheduling Problem. PhD thesis, University of Texas at Dallas, 2001. Google Scholar
  31. John F. Rudin III and R. Chandrasekaran. Improved bound for the online scheduling problem. SIAM Journal on Computing, 32(3):717-735, 2003. Google Scholar
  32. Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online scheduling with bounded migration. Mathematics of Operations Research, 34(2):481-498, 2009. Google Scholar
  33. Zhiyi Tan and Shaohua Yu. Online scheduling with reassignment. Operations Research Letters, 36(2):250-254, 2008. Google Scholar
  34. Yuxin Wang, Attila Benko, Xin Chen, György Dósa, He Guo, Xin Han, and Cecilia Sik-Lányi. Online scheduling with one rearrangement at the end: Revisited. Information Processing Letters, 112(16):641-645, 2012. 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