{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T12:52:38Z","timestamp":1753275158848,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T00:00:00Z","timestamp":1698278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>For a single server system, Shortest Remaining Processing Time (SRPT) is an optimal size-based policy. In this article, we discuss scheduling a single-server system when exact information about the jobs\u2019 processing times is not available. When the SRPT policy uses estimated processing times, the underestimation of large jobs can significantly degrade performance. We propose an index-based policy with a single parameter, Size Estimate Hedging (SEH), that only uses estimated processing times for scheduling decisions. A job\u2019s priority is increased dynamically according to an SRPT rule until it is determined that it is underestimated, at which time the priority is frozen. Numerical results suggest that SEH has desirable performance for estimation error variance that is consistent with what is seen in practice.<\/jats:p>","DOI":"10.1145\/3580491","type":"journal-article","created":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T11:57:09Z","timestamp":1673956629000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["SEH: Size Estimate Hedging Scheduling of Queues"],"prefix":"10.1145","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9485-3394","authenticated-orcid":false,"given":"Maryam","family":"Akbari-Moghaddam","sequence":"first","affiliation":[{"name":"McMaster University, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0881-831X","authenticated-orcid":false,"given":"Douglas G.","family":"Down","sequence":"additional","affiliation":[{"name":"McMaster University, Canada"}]}],"member":"320","published-online":{"date-parts":[[2023,10,26]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2","DOI":"10.1007\/s11134-009-9141-x"},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/978-3-030-85172-9_9","volume-title":"International Conference on Quantitative Evaluation of Systems","author":"Akbari-Moghaddam Maryam","year":"2021","unstructured":"Maryam Akbari-Moghaddam and Douglas G. Down. 2021. SEH: Size estimate hedging for single-server queues. In International Conference on Quantitative Evaluation of Systems. Springer, 168\u2013185."},{"doi-asserted-by":"publisher","key":"e_1_3_2_4_2","DOI":"10.1016\/j.tcs.2004.05.023"},{"key":"e_1_3_2_5_2","first-page":"762","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Bender Michael A.","year":"2002","unstructured":"Michael A. Bender, Shanmugavelayutham Muthukrishnan, and Rajmohan Rajaraman. 2002. Improved algorithms for stretch scheduling. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 762\u2013771."},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"3074","DOI":"10.1109\/INFCOM.2011.5935152","volume-title":"Proceedings of the 2011 IEEE INFOCOM","author":"Chang Hyunseok","year":"2011","unstructured":"Hyunseok Chang, Murali Kodialam, Ramana Rao Kompella, T. V. Lakshman, Myungjin Lee, and Sarit Mukherjee. 2011. Scheduling in MapReduce-like systems for fast completion time. In Proceedings of the 2011 IEEE INFOCOM. 3074\u20133082."},{"key":"e_1_3_2_7_2","article-title":"Interactive analytical processing in big data systems: A cross-industry study of MapReduce workloads","author":"Chen Yanpei","year":"2012","unstructured":"Yanpei Chen, Sara Alspaugh, and Randy Katz. 2012. Interactive analytical processing in big data systems: A cross-industry study of MapReduce workloads. arXiv preprint arXiv:1208.4174 (2012).","journal-title":"arXiv preprint arXiv:1208.4174"},{"doi-asserted-by":"publisher","key":"e_1_3_2_8_2","DOI":"10.5555\/574894"},{"key":"e_1_3_2_9_2","first-page":"3","volume-title":"A Practical Guide to Heavy Tails: Statistical Techniques and Applications","author":"Crovella Mark E.","year":"1998","unstructured":"Mark E. Crovella, Murad S. Taqqu, and Azer Bestavros. 1998. Heavy-tailed probability distributions in the world wide web. In A Practical Guide to Heavy Tails: Statistical Techniques and Applications. Birkh\u00e4user, 3\u201325."},{"key":"e_1_3_2_10_2","article-title":"Scheduling with inexact job sizes: The merits of shortest processing time first","author":"Dell\u2019Amico Matteo","year":"2019","unstructured":"Matteo Dell\u2019Amico. 2019. Scheduling with inexact job sizes: The merits of shortest processing time first. arXiv preprint arXiv:1907.04824 (2019).","journal-title":"arXiv preprint arXiv:1907.04824"},{"issue":"7","key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"2199","DOI":"10.1109\/TC.2015.2468225","article-title":"PSBS: Practical size-based scheduling","volume":"65","author":"Dell\u2019Amico Matteo","year":"2015","unstructured":"Matteo Dell\u2019Amico, Damiano Carra, and Pietro Michiardi. 2015. PSBS: Practical size-based scheduling. IEEE Trans. Comput. 65, 7 (2015), 2199\u20132212.","journal-title":"IEEE Trans. Comput."},{"doi-asserted-by":"publisher","key":"e_1_3_2_12_2","DOI":"10.1111\/j.2517-6161.1979.tb01068.x"},{"doi-asserted-by":"publisher","key":"e_1_3_2_13_2","DOI":"10.1016\/j.peva.2018.10.001"},{"key":"e_1_3_2_14_2","volume-title":"Proceedings of the ASA-IMS Conference on Applications of Heavy Tailed Distributions in Economics, Engineering and Statistics","author":"Harchol-Balter Mor","year":"1999","unstructured":"Mor Harchol-Balter. 1999. The effect of heavy-tailed job size distributions on computer system design. In Proceedings of the ASA-IMS Conference on Applications of Heavy Tailed Distributions in Economics, Engineering and Statistics."},{"doi-asserted-by":"publisher","key":"e_1_3_2_15_2","DOI":"10.1145\/762483.762486"},{"key":"e_1_3_2_16_2","article-title":"Queueing systems: Theory, vol. 1","author":"Kleinrock Leonard","year":"1975","unstructured":"Leonard Kleinrock. 1975. Queueing systems: Theory, vol. 1. A Wiley-Interscience Publication (1975).","journal-title":"A Wiley-Interscience Publication"},{"key":"e_1_3_2_17_2","first-page":"31","volume-title":"Proceedings of the IEEE Computer Society\u2019s 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, 2004.(MASCOTS 2004).","author":"Lu Dong","year":"2004","unstructured":"Dong Lu, Huanyuan Sheng, and Peter Dinda. 2004. Size-based scheduling policies with inaccurate scheduling information. In Proceedings of the IEEE Computer Society\u2019s 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, 2004.(MASCOTS 2004). IEEE, 31\u201338."},{"key":"e_1_3_2_18_2","volume-title":"Robustness to Estimation Errors for Size-Aware Scheduling","author":"Mailach Rachel","year":"2017","unstructured":"Rachel Mailach. 2017. Robustness to Estimation Errors for Size-Aware Scheduling. Master\u2019s thesis. McMaster University, Department of Computing and Software, Canada."},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"10","DOI":"10.23919\/ITC.2017.8064334","volume-title":"Proceedings of the 2017 29th International Teletraffic Congress (ITC 29)","author":"Mailach Rachel","year":"2017","unstructured":"Rachel Mailach and Douglas G. Down. 2017. Scheduling jobs with estimation errors for multi-server systems. In Proceedings of the 2017 29th International Teletraffic Congress (ITC 29). IEEE, 10\u201318."},{"key":"e_1_3_2_20_2","article-title":"Scheduling with predictions and the price of misprediction","author":"Mitzenmacher Michael","year":"2019","unstructured":"Michael Mitzenmacher. 2019. Scheduling with predictions and the price of misprediction. arXiv preprint arXiv:1902.00732 (2019).","journal-title":"arXiv preprint arXiv:1902.00732"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1109\/BigData.2013.6691554","volume-title":"Proceedingsof the 2013 IEEE International Conference on Big Data","author":"Pastorelli Mario","year":"2013","unstructured":"Mario Pastorelli, Antonio Barbuzzi, Damiano Carra, Matteo Dell\u2019Amico, and Pietro Michiardi. 2013. HFSP: Size-based scheduling for Hadoop. In Proceedingsof the 2013 IEEE International Conference on Big Data. IEEE, 51\u201359."},{"key":"e_1_3_2_22_2","first-page":"9661","volume-title":"Advances in Neural Information Processing Systems","author":"Purohit Manish","year":"2018","unstructured":"Manish Purohit, Zoya Svitkina, and Ravi Kumar. 2018. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems. 9661\u20139670."},{"doi-asserted-by":"publisher","key":"e_1_3_2_23_2","DOI":"10.1145\/781027.781055"},{"doi-asserted-by":"publisher","key":"e_1_3_2_24_2","DOI":"10.1017\/S0269964800001194"},{"doi-asserted-by":"publisher","key":"e_1_3_2_25_2","DOI":"10.1287\/opre.16.3.687"},{"doi-asserted-by":"publisher","key":"e_1_3_2_26_2","DOI":"10.1287\/opre.14.4.670"},{"key":"e_1_3_2_27_2","series-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)","first-page":"114:1\u2013114:30","volume":"215","author":"Scully Ziv","year":"2022","unstructured":"Ziv Scully, Isaac Grosof, and Michael Mitzenmacher. 2022. Uniform bounds for scheduling with job size estimates. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 215), Mark Braverman (Ed.). 114:1\u2013114:30."},{"doi-asserted-by":"publisher","key":"e_1_3_2_28_2","DOI":"10.1145\/3179419"},{"doi-asserted-by":"publisher","key":"e_1_3_2_29_2","DOI":"10.1016\/j.sorms.2010.07.002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_30_2","DOI":"10.1145\/1375457.1375461"},{"doi-asserted-by":"publisher","key":"e_1_3_2_31_2","DOI":"10.1007\/BF01182931"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580491","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580491","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:42Z","timestamp":1750178262000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580491"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,26]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3580491"],"URL":"https:\/\/doi.org\/10.1145\/3580491","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"type":"print","value":"1049-3301"},{"type":"electronic","value":"1558-1195"}],"subject":[],"published":{"date-parts":[[2023,10,26]]},"assertion":[{"value":"2022-01-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}