Document Open Access Logo

Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling

Authors Sven Jäger, Martin Skutella

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2018.43.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • Stochastic Scheduling
  • Parallel Machines
  • Approximation Algorithm
  • List Scheduling
  • Weighted Shortest (Expected) Processing Time Rule

Metrics

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

Abstract

Minimizing the sum of weighted completion times on m identical
parallel machines is one of the most important and classical
scheduling problems. For the stochastic variant where processing
times of jobs are random variables, Möhring, Schulz, and Uetz (1999) presented the first and still best known approximation result,
achieving, for arbitrarily many machines, performance
ratio 1+1/2(1+Delta), where Delta is an upper bound on the
squared coefficient of variation of the processing times. We prove
performance ratio 1+1/2(sqrt(2)-1)(1+Delta)
for the same
underlying algorithm---the Weighted Shortest Expected Processing
Time (WSEPT) rule. For the special case of deterministic scheduling
(i.e., Delta=0), our bound matches the tight performance
ratio 1/2(1+sqrt(2)) of this algorithm (WSPT rule), derived by
Kawaguchi and Kyan in a 1986 landmark paper. We present several
further improvements for WSEPT's performance ratio, one of them
relying on a carefully refined analysis of WSPT yielding, for every
fixed number of machines m, WSPT's exact performance ratio of
order 1/2(1+sqrt(2))-O(1/m^2).

Cite As Get BibTex

Sven Jäger and Martin Skutella. Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.43

Author Details

Sven Jäger
Martin Skutella

References

  1. Adi Avidor, Yossi Azar, and Jirí Sgall. Ancient and new algorithms for load balancing in the l_p norm. Algorithmica, 29(3):422-441, 2001. URL: http://dx.doi.org/10.1007/s004530010051.
  2. Chandra Chekuri, Rajeev Motwani, Balas Natarajan, and Clifford Stein. Approximation techniques for average completion time scheduling. SIAM Journal on Computing, 31(1):146-166, 2001. URL: http://dx.doi.org/10.1137/s0097539797327180.
  3. Wang Chi Cheung, Felix Fischer, Jannik Matuschke, and Nicole Megow. A Ω(Δ^1/2) gap example for the WSEPT policy. Cited as personal communication in Uetz: MDS Autumn School Approximation Algorithms for Stochastic Optimization, 2014. URL: http://www3.math.tu-berlin.de/MDS/summerschool14-material/Uetz-Exercises.pdf.
  4. Willard L. Eastman, Shimon Even, and I. Martin Isaacs. Bounds for the optimal scheduling of n jobs on m processors. Management Science, 11(2):268-279, 1964. URL: http://dx.doi.org/10.1287/mnsc.11.2.268.
  5. Michel X. Goemans. Improved approximation algorithms for scheduling with release dates. In Michael Saks, editor, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 591-598. Society for Industrial and Applied Mathematics, 1997. URL: http://dl.acm.org/citation.cfm?id=314394.
  6. Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella, and Yaoguang Wang. Single machine scheduling with release dates. SIAM J. Discrete Math., 15(2):165-192, 2002. URL: http://dx.doi.org/10.1137/S089548019936223X.
  7. Ronald L. Graham, Eugene L. Lawler, Jan Karel Lenstra, and Alexander H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. In Peter L. Hammer, Ellis L. Johnson, and Bernhard H. Korte, editors, Discrete Optimization II, volume 5 of Annals of Discrete Mathematics, pages 287-326. Elsevier, 1979. URL: http://dx.doi.org/10.1016/S0167-5060(08)70356-X.
  8. Varun Gupta, Benjamin Moseley, Marc Uetz, and Qiaomin Xie. Stochastic online scheduling on unrelated machines. In Friedrich Eisenbrand and Jochen Könemann, editors, Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, volume 10328 of Lecture Notes in Computer Science, pages 228-240. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-59250-3_19.
  9. Leslie A. Hall, David B. Shmoys, and Joel Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. In Éva Tardos, editor, Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 142-151, Philadelphia, PA, USA, 1996. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=313852.313907.
  10. Sungjin Im, Benjamin Moseley, and Kirk Pruhs. Stochastic scheduling of heavy-tailed jobs. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 474-486. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.474.
  11. S. Jäger and M. Skutella. Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling. ArXiv e-prints, jan 2018. URL: http://arxiv.org/abs/1801.01105.
  12. Caroline Jagtenberg, Uwe Schwiegelshohn, and Marc Uetz. Analysis of smith’s rule in stochastic machine scheduling. Oper. Res. Lett., 41(6):570-575, 2013. URL: http://dx.doi.org/10.1016/j.orl.2013.08.001.
  13. Christos Kalaitzis, Ola Svensson, and Jakub Tarnawski. Unrelated machine scheduling of jobs with uniform Smith ratios. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2654-2669, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. URL: http://arxiv.org/abs/1607.07631.
  14. Tsuyoshi Kawaguchi and Seiki Kyan. Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM J. Comput., 15(4):1119-1129, 1986. URL: http://dx.doi.org/10.1137/0215081.
  15. Nicole Megow, Marc Uetz, and Tjark Vredeveld. Models and algorithms for stochastic online scheduling. Math. Oper. Res., 31(3):513-525, 2006. URL: http://dx.doi.org/10.1287/moor.1060.0201.
  16. Rolf H. Möhring, Franz Josef Radermacher, and Gideon Weiss. Stochastic scheduling problems I - general strategies. Zeitschr. für OR, 28(7):193-260, 1984. URL: http://dx.doi.org/10.1007/BF01919323.
  17. Rolf H. Möhring, Andreas S. Schulz, and Marc Uetz. Approximation in stochastic scheduling: the power of lp-based priority policies. J. ACM, 46(6):924-942, 1999. URL: http://dx.doi.org/10.1145/331524.331530.
  18. Michael H. Rothkopf. Scheduling with random service times. Management Science, 12(9):707-713, may 1966. URL: http://dx.doi.org/10.1287/mnsc.12.9.707.
  19. Andreas S. Schulz. Stochastic online scheduling revisited. In Boting Yang, Ding-Zhu Du, and Cao An Wang, editors, Combinatorial Optimization and Applications, Second International Conference, COCOA 2008, St. John’s, NL, Canada, August 21-24, 2008. Proceedings, volume 5165 of Lecture Notes in Computer Science, pages 448-457. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-85097-7_42.
  20. Uwe 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.
  21. Martin Skutella. A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective. Oper. Res. Lett., 44(5):676-679, 2016. URL: http://dx.doi.org/10.1016/j.orl.2016.07.016.
  22. Martin Skutella, Maxim Sviridenko, and Marc Uetz. Unrelated machine scheduling with stochastic processing times. Math. Oper. Res., 41(3):851-864, 2016. URL: http://dx.doi.org/10.1287/moor.2015.0757.
  23. Martin Skutella and Gerhard J. Woeginger. A PTAS for minimizing the total weighted completion time on identical parallel machines. Math. Oper. Res., 25(1):63-75, 2000. URL: http://dx.doi.org/10.1287/moor.25.1.63.15212.
  24. Wayne E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1-2):59-66, mar 1956. URL: http://dx.doi.org/10.1002/nav.3800030106.
  25. Richard R. Weber, Pravin Varaiya, and Jean Walrand. Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime. Journal of Applied Probability, 23(3):841-847, sep 1986. URL: http://dx.doi.org/10.2307/3214023.
  26. Gideon Weiss. Approximation results in parallel machnies stochastic scheduling. Annals of Operations Research, 26(1):195-242, 1990. URL: http://dx.doi.org/10.1007/BF02248591.
  27. Gideon Weiss. Turnpike optimality of smith’s rule in parallel machines stochastic scheduling. Math. Oper. Res., 17(2):255-270, 1992. URL: http://dx.doi.org/10.1287/moor.17.2.255.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact