Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Approximations for Throughput Maximization

  • Published:
Algorithmica Aims and scope Submit manuscript

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. (Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1–4, 1999, Atlanta, Georgia, USA, pp. 622–631. ACM, 1999, https://doi.org/10.1145/301250.301420) 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 et al. (42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001, 14–17 October 2001, Las Vegas, Nevada, USA, pp. 348–356. IEEE Computer Society, 2001) presented an algorithm with approximation with ratio \(1-\frac{1}{e}-\varepsilon \) (for any \(\varepsilon >0\)). Recently Im et al. (SIAM J Discrete Math 34(3):1649–1669, 2020) presented an algorithm with ratio \(1-1/e+\varepsilon _0\) for some absolute constant \(\varepsilon _0>0\) for any fixed m. They also presented an algorithm with ratio \(1-O(\sqrt{\log m/m})-\varepsilon \) 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 in: Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceedings, pp 2–11, 2012). 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-{\varepsilon })\)-approximation that runs in time \(O(n^{mc^7{\varepsilon }^{-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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2

Similar content being viewed by others

References

  1. Adler, M., Rosenberg, A.L., Sitaraman, R.K., Unger, W.: Scheduling time-constrained communication in linear networks. Theory Comput. Syst. 35(6), 599–623 (2002)

    Article  MathSciNet  Google Scholar 

  2. Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753–782 (1998)

    Article  MathSciNet  Google Scholar 

  3. Bansal, N., Chan, H.-L., Khandekar, R., Pruhs, K., Stein, C., Schieber, B.: 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, pp. 614–624 (2007)

  4. Baptiste, P.: On minimizing the weighted number of late jobs in unit execution time open-shops. Eur. J. Oper. Res. 149(2), 344–354 (2003)

    Article  MathSciNet  Google Scholar 

  5. Baptiste, P., Brucker, P., Knust, S., Timkovsky, V.G.: Ten notes on equal-processing-time scheduling. 4OR 2(2), 111–127 (2004)

    Article  MathSciNet  Google Scholar 

  6. Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069–1090 (2001)

    Article  MathSciNet  Google Scholar 

  7. Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Approximating the throughput of multiple machines under real-time scheduling. In: Vitter, J.S., Larmore, L.L., Leighton, F.T. (eds.) Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1–4, 1999, Atlanta, Georgia, USA, pp. 622-631. ACM (1999). https://doi.org/10.1145/301250.301420

  8. Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput. 31(2), 331–352 (2001)

    Article  MathSciNet  Google Scholar 

  9. Baruah, S.K., Koren, G., Mao, D., Mishra, B., Raghunathan, A., Rosier, L.E., Shasha, D.E., Wang, F.: On the competitiveness of on-line real-time task scheduling. Real-Time Syst. 4(2), 125–144 (1992)

    Article  Google Scholar 

  10. Berman, P., DasGupta, B.: 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, pp. 680–687 (2000)

  11. Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3), 713–728 (2005)

    Article  MathSciNet  Google Scholar 

  12. Chuzhoy, J., Guha, S., Khanna, S., Naor, J.: 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, pp. 81–90 (2004)

  13. Chuzhoy, J., Naor, J.: New hardness results for congestion minimization and machine scheduling. J. ACM 53(5), 707–721 (2006)

    Article  MathSciNet  Google Scholar 

  14. Chuzhoy, J., Ostrovsky, R., Rabani, Y.: Approximation algorithms for the job interval selection problem and related scheduling problems. In: 42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001, 14–17 October 2001, Las Vegas, Nevada, USA, pp. 348–356. IEEE Computer Society (2001). https://doi.org/10.1109/SFCS.2001.959909

  15. Chuzhoy, J., Ostrovsky, R., Rabani, Y.: Approximation algorithms for the job interval selection problem and related scheduling problems. Math. Oper. Res. 31(4), 730–738 (2006)

    Article  MathSciNet  Google Scholar 

  16. Dourado, M., Rodrigues, R., Szwarcfiter, J.: Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs. Ann. Oper. Res. 169(1), 81–91 (2009)

    Article  MathSciNet  Google Scholar 

  17. Elffers, J., de Weerdt, M.: Scheduling with two non-unit task lengths is np-complete. arXiv:1412.3095 (2014)

  18. Fischetti, M., Martello, S., Toth, P.: The fixed job schedule problem with working-time constraints. Oper. Res. 37(3), 395–403 (1989)

    Article  MathSciNet  Google Scholar 

  19. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)

  20. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. North-Holland Publishing Co., Amsterdam (2004)

  21. Grandoni, F., Rothvoß, T.: Pricing on paths: a PTAS for the highway problem. SIAM J. Comput. 45(2), 216–231 (2016)

    Article  MathSciNet  Google Scholar 

  22. Hafez, R.H.M., Rajugopal, G.R.: Adaptive rate controlled, robust video communication over packet wireless networks. MONET 3(1), 33–47 (1998)

    Google Scholar 

  23. Im, S., Li, S., Moseley, B.: Breaking 1–1/e barrier for nonpreemptive throughput maximization. SIAM J. Discrete Math. 34(3), 1649–1669 (2020)

    Article  MathSciNet  Google Scholar 

  24. Im, S., Li, S., Moseley, B., Torng, E.: A dynamic programming framework for non-preemptive scheduling problems on multiple machines [extended abstract]. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4–6, 2015, pp. 1070–1086. SIAM (2015)

  25. Jansen, K.: 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, pp. 313–324 (2012)

  26. Liu, H., El Zarki, M.: Adaptive source rate control for real-time wireless video transmission. MONET 3(1), 49–60 (1998)

    Google Scholar 

  27. Nonner, T., Sviridenko, M.: An efficient polynomial-time approximation scheme for the joint replenishment problem. In: Goemans, M.X., Correa, J.R. (eds.), Integer Programming and Combinatorial Optimization—16th International Conference, IPCO 2013, Valparaíso, Chile, March 18–20, 2013. Proceedings, volume 7801 of Lecture Notes in Computer Science, pp. 314–323. Springer (2013)

  28. Potts, C.N., Strusevich, V.A.: Fifty years of scheduling: a survey of milestones. JORS, 60(S1) (2009)

  29. Pruhs, K., Sgall, J., Torng, E.: Online Scheduling. Models, and Performance Analysis, In Handbook of Scheduling - Algorithms (2004)

  30. Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365–374 (1987)

    Article  MathSciNet  Google Scholar 

  31. Schuurman, P., Woeginger, G.J.: Polynomial time approximation algorithms for machine scheduling: ten open problems. J. Sched. 2(5), 203–213 (1999)

    Article  MathSciNet  Google Scholar 

  32. Sgall, J.: Open problems in throughput scheduling. In: Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceedings, pp. 2–11 (2012)

  33. Spieksma, F.C.R.: Approximating an interval scheduling problem. In: Approximation Algorithms for Combinatorial Optimization, International Workshop APPROX’98, Aalborg, Denmark, July 18–19, 1998, Proceedings, pp. 169–180 (1998)

  34. Yau, D.K.Y., Lam, S.S.: Adaptive rate-controlled scheduling for multimedia applications. IEEE/ACM Trans. Netw. 5(4):475–488 (1997)

Download references

Acknowledgements

The authors have no competing interests as defined by Springer, or other interests that might be perceived to influence the results and/or discussion reported in this paper. Other than the preliminary version of this article that is published as extended abstract in Proceedings of ISAAC2020, the results/data/figures in this manuscript have not been published elsewhere, nor are they under consideration (from you or one of your Contributing Authors) by another publisher.

Author information

Authors and Affiliations

  1. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada

    Dylan Hyatt-Denesik

  2. Department of Computing Science, University of Alberta, Edmonton, Canada

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

  3. Eindhoven University of Technology, Eindhoven, The Netherlands

    Dylan Hyatt-Denesik

Authors
  1. Dylan Hyatt-Denesik
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mirmahdi Rahgoshay
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mohammad R. Salavatipour
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors have contributed to the preparation of this manuscript.

Corresponding author

Correspondence to Mohammad R. Salavatipour.

Ethics declarations

Competing interests

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Mohammad R. Salavatipour: Supported by organization NSERC. A preliminary version of this article appeared in Proceedings of ISAAC2020.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hyatt-Denesik, D., Rahgoshay, M. & Salavatipour, M.R. Approximations for Throughput Maximization. Algorithmica 86, 1545–1577 (2024). https://doi.org/10.1007/s00453-023-01201-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-023-01201-4

Keywords

Search

Navigation