Document Open Access Logo

The Power of Migration for Online Slack Scheduling

Authors Chris Schwiegelshohn, Uwe Schwiegelshohn

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.75.pdf
  • Filesize: 0.53 MB
  • 17 pages

Document Identifiers

Author Details

Chris Schwiegelshohn
Uwe Schwiegelshohn

Cite As Get BibTex

Chris Schwiegelshohn and Uwe Schwiegelshohn. The Power of Migration for Online Slack Scheduling. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 75:1-75:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.75

Abstract

We investigate the power of migration in online scheduling for parallel identical machines. Our objective is to maximize the total processing time of accepted jobs. Once we decide to accept a job, we have to complete it before its deadline d that satisfies d >= (1+epsilon)p + r, where p is the processing time, r the submission time and the slack epsilon > 0 a system parameter. Typically, the hard case arises for small slack epsilon << 1, i.e. for near-tight deadlines. Without migration, a greedy acceptance policy is known to be an optimal deterministic online algorithm with a competitive factor of (1+epsilon)/epsilon (DasGupta and Palis, APPROX 2000). Our first contribution is to show that migrations do not improve the competitive ratio of the greedy acceptance policy, i.e. the competitive ratio remains (1+epsilon)/epsilon for any number of machines.

Our main contribution is a deterministic online algorithm with almost tight competitive ratio on any number of machines. For a single machine, the competitive factor matches the optimal bound of (1+epsilon)/epsilon of the greedy acceptance policy. The competitive ratio improves with an increasing number of machines. It approaches (1+epsilon) ln((1+epsilon)/epsilon) as the number of machines converges to infinity. This is an exponential improvement over the greedy acceptance policy for small epsilon. Moreover, we show a matching lower bound on the competitive ratio for deterministic algorithms on any number of machines.

Subject Classification

Keywords
  • Online scheduling
  • deadlines
  • preemption with migration
  • competitive analysis

Metrics

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

References

  1. S. Albers and M. Hellwig. On the value of job migration in online makespan minimization. In Proc. of ESA, pages 84-95, 2012. Google Scholar
  2. J. H. Anderson, V. Bud, and U. C. Devi. An EDF-based restricted-migration scheduling algorithm for multiprocessor soft real-time systems. Real-Time Systems, 38(2):85-131, 2008. Google Scholar
  3. S. K. Baruah, G. Koren, D. Mao, B. Mishra, A. Raghunathan, L. E. Rosier, D. Shasha, and F. Wang. On the competitiveness of on-line real-time task scheduling. Real-Time Systems, 4(2):125-144, 1992. Google Scholar
  4. S.K. Baruah and J.R. Haritsa. Scheduling for overload in real-time systems. IEEE Trans. Computers, 46(9):1034-1039, 1997. Google Scholar
  5. P. Brucker and S. Knust. Complexity results for scheduling problems. http://www2.informatik.uni-osnabrueck.de/knust/class/, 2009. [Online; accessed 11-April-2016].
  6. B. Chen, A. van Vliet, and G. J. Woeginger. An optimal algorithm for preemptive on-line scheduling. Oper. Res. Lett., 18(3):127-131, 1995. Google Scholar
  7. B. DasGupta and M.A. Palis. Online real-time preemptive scheduling of jobs with deadlines on multiple machines. Journal of Scheduling, 4(6):297-312, 2001. Google Scholar
  8. R. I. Davis and A. Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35, 2011. Google Scholar
  9. L. Epstein and A. Levin. Robust algorithms for preemptive scheduling. Algorithmica, 69(1):26-57, 2014. Google Scholar
  10. S.A. Goldman, J. Parwatikar, and S. Suri. Online scheduling with hard deadlines. Journal of Algorithms, 34(2):370-389, 2000. Google Scholar
  11. M.H. Goldwasser. Patience is a virtue: the effect of slack on competitiveness for admission control. In Proc. of SODA, pages 396-405, 1999. Google Scholar
  12. M.E. Hussein and U. Schwiegelshohn. Utilization of nonclairvoyant online schedules. Theor. Comput. Sci., 362(1-3):238-247, 2006. Google Scholar
  13. B. Kalyanasundaram and K. Pruhs. Eliminating migration in multi-processor scheduling. J. Algorithms, 38(1):2-24, 2001. Google Scholar
  14. B. Kalyanasundaram and K. Pruhs. Maximizing job completions online. J. Algorithms, 49(1):63-85, 2003. Google Scholar
  15. T. Kawaguchi and S. Kyan. Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM Journal on Computing, 15(4):1119-1129, 1986. Google Scholar
  16. J.H. Kim and K.Y. Chwa. On-line deadline scheduling on multiple resources. In Proc. of COCOON, pages 443-452, 2001. Google Scholar
  17. G. Koren and D. Shasha. MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling. Theor. Comput. Sci., 128(1&2):75-97, 1994. Google Scholar
  18. E. L. Lawler. A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Annals of Operations Research, 26(1):125-133, 1990. Google Scholar
  19. J. Lee. Online deadline scheduling: multiple machines and randomization. In Proc. of SPAA, pages 19-23, 2003. Google Scholar
  20. R.J. Lipton and A. Tomkins. Online interval scheduling. In Proc. of SODA, pages 302-311, 1994. Google Scholar
  21. M.L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer Science+Business Media, forth edition, 2010. Google Scholar
  22. P. Sanders, N. Sivadasan, and M. Skutella. Online scheduling with bounded migration. Math. Oper. Res., 34(2):481-498, 2009. Google Scholar
  23. U. Schwiegelshohn. An alternative proof of the Kawaguchi-Kyan bound for the Largest-Ratio-First rule. Oper. Res. Lett., 39(4):255-259, 2011. URL: http://dx.doi.org/10.1016/j.orl.2011.06.007.
  24. M. Skutella and J. Verschae. A robust PTAS for machine covering and packing. In Proc. of ESA, pages 36-47, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15775-2_4.
  25. B. Sotomayor, R. S. Montero, I. M. Llorente, and I. T. Foster. Virtual infrastructure management in private and hybrid clouds. IEEE Internet Computing, 13(5):14-22, 2009. Google Scholar
  26. P. Valente and G. Lipari. An upper bound to the lateness of soft real-time tasks scheduled by EDF on multiprocessors. In Proc. of RTSS, pages 311-320, 2005. Google Scholar
  27. G. J. Woeginger. On-line scheduling of jobs with fixed start and end times. Theor. Comput. Sci., 130(1):5-16, 1994. 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