Document Open Access Logo

Approximations for Throughput Maximization

Authors Dylan Hyatt-Denesik, Mirmahdi Rahgoshay, Mohammad R. Salavatipour

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.11.pdf
  • Filesize: 0.53 MB
  • 17 pages

Document Identifiers

Author Details

Dylan Hyatt-Denesik
  • Department of Combinatorcs and Optimization, University of Waterloo, Canada
Mirmahdi Rahgoshay
  • Department of Computing Science, University of Alberta, Edmonton, Canada
Mohammad R. Salavatipour
  • Department of Computing Science, University of Alberta, Edmonton, Canada

Funding

  • Salavatipour, Mohammad R.: Supported by NSERC.

Cite As Get BibTex

Dylan Hyatt-Denesik, Mirmahdi Rahgoshay, and Mohammad R. Salavatipour. Approximations for Throughput Maximization. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.11

Abstract

In this paper we study the classical problem of throughput maximization. In this problem we have a collection J of n jobs, each having a release time r_j, deadline d_j, and processing time p_j. They have to be scheduled non-preemptively on m identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their [r_j,d_j] window. This problem has been studied extensively (even for the case of m = 1). Several special cases of the problem remain open. Bar-Noy et al. [STOC1999] presented an algorithm with ratio 1-1/(1+1/m)^m for m machines, which approaches 1-1/e as m increases. For m = 1, Chuzhoy-Ostrovsky-Rabani [FOCS2001] presented an algorithm with approximation with ratio 1-1/e-ε (for any ε > 0). Recently Im-Li-Moseley [IPCO2017] presented an algorithm with ratio 1-1/e+ε₀ for some absolute constant ε₀ > 0 for any fixed m. They also presented an algorithm with ratio 1-O(√(log m/m))-ε for general m which approaches 1 as m grows. The approximability of the problem for m = O(1) remains a major open question. Even for the case of m = 1 and c = O(1) distinct processing times the problem is open (Sgall [ESA2012]). In this paper we study the case of m = O(1) and show that if there are c distinct processing times, i.e. p_j’s come from a set of size c, then there is a randomized (1-ε)-approximation that runs in time O(n^{mc⁷ε^(-6)}log T), where T is the largest deadline. Therefore, for constant m and constant c this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Scheduling
  • Approximation Algorithms
  • Throughput Maximization

Metrics

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

References

  1. Micah Adler, Arnold L. Rosenberg, Ramesh K. Sitaraman, and Walter Unger. Scheduling time-constrained communication in linear networks. Theory Comput. Syst., 35(6):599-623, 2002. URL: https://doi.org/10.1007/s00224-002-1001-6.
  2. Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Clifford Stein, and Baruch Schieber. Non-preemptive min-sum scheduling with resource augmentation. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 614-624, 2007. URL: https://doi.org/10.1109/FOCS.2007.46.
  3. Philippe Baptiste. On minimizing the weighted number of late jobs in unit execution time open-shops. European Journal of Operational Research, 149(2):344-354, 2003. URL: https://doi.org/10.1016/S0377-2217(02)00759-2.
  4. Philippe Baptiste, Peter Brucker, Sigrid Knust, and Vadim G. Timkovsky. Ten notes on equal-processing-time scheduling. 4OR, 2(2):111-127, 2004. URL: https://doi.org/10.1007/s10288-003-0024-4.
  5. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. J. ACM, 48(5):1069-1090, 2001. URL: https://doi.org/10.1145/502102.502107.
  6. Amotz Bar-Noy, Sudipto Guha, Joseph Naor, and Baruch Schieber. Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput., 31(2):331-352, 2001. URL: https://doi.org/10.1137/S0097539799354138.
  7. Sanjoy K. Baruah, Gilad Koren, Decao Mao, Bhubaneswar Mishra, Arvind Raghunathan, Louis E. Rosier, Dennis E. Shasha, and Fuxing Wang. On the competitiveness of on-line real-time task scheduling. Real-Time Systems, 4(2):125-144, 1992. URL: https://doi.org/10.1007/BF00365406.
  8. Piotr Berman and Bhaskar DasGupta. Improvements in throughout maximization for real-time scheduling. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 680-687, 2000. URL: https://doi.org/10.1145/335305.335401.
  9. Chandra Chekuri and Sanjeev Khanna. A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput., 35(3):713-728, 2005. URL: https://doi.org/10.1137/S0097539700382820.
  10. Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, and Joseph Naor. Machine minimization for scheduling jobs with interval constraints. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 81-90, 2004. URL: https://doi.org/10.1109/FOCS.2004.38.
  11. Julia Chuzhoy and Joseph Naor. New hardness results for congestion minimization and machine scheduling. J. ACM, 53(5):707-721, 2006. URL: https://doi.org/10.1145/1183907.1183908.
  12. Julia Chuzhoy, Rafail Ostrovsky, and Yuval Rabani. Approximation algorithms for the job interval selection problem and related scheduling problems. Math. Oper. Res., 31(4):730-738, 2006. URL: https://doi.org/10.1287/moor.1060.0218.
  13. Mitre Dourado, Rosiane Rodrigues, and Jayme Szwarcfiter. Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs. Annals of Operations Research, 169(1):81-91, 2009. URL: https://EconPapers.repec.org/RePEc:spr:annopr:v:169:y:2009:i:1:p:81-91:10.1007/s10479-008-0479-y.
  14. Jan Elffers and Mathijs de Weerdt. Scheduling with two non-unit task lengths is np-complete. CoRR, abs/1412.3095, 2014. URL: http://arxiv.org/abs/1412.3095.
  15. Ulrich Faigle and Willem M. Nawijn. Note on scheduling intervals on-line. Discrete Applied Mathematics, 58(1):13-17, 1995. URL: https://doi.org/10.1016/0166-218X(95)00112-5.
  16. Matteo Fischetti, Silvano Martello, and Paolo Toth. The fixed job schedule problem with working-time constraints. Operations Research, 37(3):395-403, 1989. URL: https://doi.org/10.1287/opre.37.3.395.
  17. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  18. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. North-Holland Publishing Co. Amsterdam, The Netherlands, 2004. Google Scholar
  19. Roshdy H. M. Hafez and G. R. Rajugopal. Adaptive rate controlled, robust video communication over packet wireless networks. MONET, 3(1):33-47, 1998. URL: https://doi.org/10.1023/A:1019156211458.
  20. Sungjin Im, Shi Li, and Benjamin Moseley. Breaking 1 - 1/e barrier for non-preemptive throughput maximization. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 292-304, 2017. URL: https://doi.org/10.1007/978-3-319-59250-3_24.
  21. Sungjin Im, Shi Li, Benjamin Moseley, and Eric Torng. A dynamic programming framework for non-preemptive scheduling problems on multiple machines [extended abstract]. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1070-1086. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.72.
  22. Klaus Jansen. A fast approximation scheme for the multiple knapsack problem. In SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012. Proceedings, pages 313-324, 2012. URL: https://doi.org/10.1007/978-3-642-27660-6_26.
  23. Gilad Koren and Dennis E. Shasha. D^over; an optimal on-line scheduling algorithm for overloaded real-time systems. In Proceedings of the Real-Time Systems Symposium - 1992, Phoenix, Arizona, USA, December 1992, pages 290-299, 1992. URL: https://doi.org/10.1109/REAL.1992.242650.
  24. Richard J. Lipton and Andrew Tomkins. Online interval scheduling. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA., pages 302-311, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314506.
  25. Hang Liu and Magda El Zarki. Adaptive source rate control for real-time wireless video transmission. MONET, 3(1):49-60, 1998. URL: https://doi.org/10.1023/A:1019108328296.
  26. Chris N. Potts and Vitaly A. Strusevich. Fifty years of scheduling: a survey of milestones. JORS, 60(S1), 2009. URL: https://doi.org/10.1057/jors.2009.2.
  27. Kirk Pruhs, Jirí Sgall, and Eric Torng. Online scheduling. In Handbook of Scheduling - Algorithms, Models, and Performance Analysis. Chapman and Hall/CRC, 2004. URL: http://www.crcnetbase.com/doi/abs/10.1201/9780203489802.ch15.
  28. Prabhakar Raghavan and Clark D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987. URL: https://doi.org/10.1007/BF02579324.
  29. Petra Schuurman and Gerhard J. Woeginger. Polynomial time approximation algorithms for machine scheduling: ten open problems. Journal of Scheduling, 2(5):203-213, 1999. Google Scholar
  30. Jirí Sgall. Open problems in throughput scheduling. In Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, pages 2-11, 2012. URL: https://doi.org/10.1007/978-3-642-33090-2_2.
  31. Frits C. R. Spieksma. Approximating an interval scheduling problem. In Approximation Algorithms for Combinatorial Optimization, International Workshop APPROX'98, Aalborg, Denmark, July 18-19, 1998, Proceedings, pages 169-180, 1998. URL: https://doi.org/10.1007/BFb0053973.
  32. David K. Y. Yau and Simon S. Lam. Adaptive rate-controlled scheduling for multimedia applications. IEEE/ACM Trans. Netw., 5(4):475-488, 1997. URL: https://doi.org/10.1109/90.649461.
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