Document Open Access Logo

Online Makespan Minimization: The Power of Restart

Authors Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.14.pdf
  • Filesize: 0.55 MB
  • 19 pages

Document Identifiers

Author Details

Zhiyi Huang
  • Department of Computer Sicence, The University of Hong Kong, Hong Kong
Ning Kang
  • Department of Computer Sicence, The University of Hong Kong, Hong Kong
Zhihao Gavin Tang
  • Department of Computer Sicence, The University of Hong Kong, Hong Kong
Xiaowei Wu
  • Department of Computing, The Hong Kong Polytechnic University, Hong Kong
Yuhao Zhang
  • Department of Computer Sicence, The University of Hong Kong, Hong Kong

Funding

  • Huang, Zhiyi: Partially supported by the Hong Kong RGC under the grant HKU17202115E.
  • Wu, Xiaowei: Part of the work was done when the author was a postdoc at the University of Hong Kong.

Cite As Get BibTex

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online Makespan Minimization: The Power of Restart. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.14

Abstract

We consider the online makespan minimization problem on identical machines. Chen and Vestjens (ORL 1997) show that the largest processing time first (LPT) algorithm is 1.5-competitive. For the special case of two machines, Noga and Seiden (TCS 2001) introduce the SLEEPY algorithm that achieves a competitive ratio of (5 - sqrt{5})/2 ~~ 1.382, matching the lower bound by Chen and Vestjens (ORL 1997). Furthermore, Noga and Seiden note that in many applications one can kill a job and restart it later, and they leave an open problem whether algorithms with restart can obtain better competitive ratios.
We resolve this long-standing open problem on the positive end. Our algorithm has a natural rule for killing a processing job: a newly-arrived job replaces the smallest processing job if 1) the new job is larger than other pending jobs, 2) the new job is much larger than the processing one, and 3) the processed portion is small relative to the size of the new job. With appropriate choice of parameters, we show that our algorithm improves the 1.5 competitive ratio for the general case, and the 1.382 competitive ratio for the two-machine case.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Online algorithms
Keywords
  • Online Scheduling
  • Makespan Minimization
  • Identical Machines

Metrics

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

Related Versions

References

  1. Susanne Albers. Better bounds for online scheduling. SIAM Journal on Computing, 29(2):459-473, 1999. Google Scholar
  2. Nir Avrahami and Yossi Azar. Minimizing total flow time and total completion time with immediate dispatching. Algorithmica, 47(3):253-268, 2007. Google Scholar
  3. Y. Bartal, A. Fiat, H. Karloff, and R. Vohra. New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences, 51(3):359-366, 1995. Google Scholar
  4. Piotr Berman, Moses Charikar, and Marek Karpinski. On-line load balancing for related machines. Journal of Algorithms, 35(1):108-121, 2000. Google Scholar
  5. Bo Chen, André van Vliet, and Gerhard J. Woeginger. A lower bound for randomized on-line scheduling algorithms. Information Processing Letters, 51(5):219-222, 1994. Google Scholar
  6. Bo Chen, André van Vliet, and Gerhard J. Woeginger. An optimal algorithm for preemptive on-line scheduling. Operations Research Letters, 18(3):127-131, 1995. 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. Bo Chen and Arjen P. A. Vestjens. Scheduling on identical machines: How good is LPT in an on-line setting? Operations Research Letters, 21(4):165-169, 1997. Google Scholar
  9. Marek Chrobak, Wojciech Jawor, Jirí Sgall, and Tomás Tichý. Online scheduling of equal-length jobs: Randomization and restarts help. SIAM Journal on Computing, 36(6):1709-1728, 2007. 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. Tomás Ebenlendr, Wojciech Jawor, and Jirí Sgall. Preemptive online scheduling: Optimal algorithms for all speeds. Algorithmica, 53(4):504-522, 2009. Google Scholar
  13. 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
  14. Leah Epstein, John Noga, Steven S. Seiden, Jirí Sgall, and Gerhard J. Woeginger. Randomized online scheduling on two uniform machines. In SODA, pages 317-326. ACM/SIAM, 1999. Google Scholar
  15. Leah Epstein and Jirí Sgall. A lower bound for on-line scheduling on uniformly related machines. Operations Research Letters, 26(1):17-22, 2000. Google Scholar
  16. Rudolf Fleischer and Michaela Wahl. On-line scheduling revisited. Journal of Scheduling, 3(6):343-353, 2000. Google Scholar
  17. Ronald L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics, 17(2):416-429, 1969. Google Scholar
  18. Han Hoogeveen, Chris N Potts, and Gerhard J Woeginger. On-line scheduling on a single machine: maximizing the number of early jobs. Operations Research Letters, 27(5):193-197, 2000. Google Scholar
  19. Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online makespan minimization: The power of restart. CoRR (to appear in APPROX 2018), abs/1806.02207, 2018. Google Scholar
  20. J. F. Rudin III. Improved Bound for the Online Scheduling Problem. PhD thesis, University of Texas at Dallas, 2001. Google Scholar
  21. J. F. Rudin III and R. Chandrasekaran. Improved bounds for the online scheduling problem. SIAM Journal on Computing, 32(3):717-735, 2003. URL: http://arxiv.org/abs/http://dx.doi.org/10.1137/S0097539702403438.
  22. 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
  23. 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
  24. Shisheng Li, Yinghua Zhou, Guangzhong Sun, and Guoliang Chen. Study on parallel machine scheduling problem with buffer. In IMSCCS, pages 278-273. IEEE Computer Society, 2007. Google Scholar
  25. John Noga and Steven S. Seiden. An optimal online algorithm for scheduling two machines with release times. Theoretical Computer Science, 268(1):133-143, 2001. Google Scholar
  26. Jianjun Wen and Donglei Du. Preemptive on-line scheduling for two uniform processors. Operations Research Letters, 23(3-5):113-116, 1998. Google Scholar
  27. Guochuan Zhang. A simple semi on-line algorithm for p2//c_maxwith a buffer. Information Processing Letters, 61(3):145-148, 1997. 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