{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T06:53:58Z","timestamp":1773471238176,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T00:00:00Z","timestamp":1702512000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-1617653, CCF-1844939, CCF-2121745"],"award-info":[{"award-number":["CCF-1617653, CCF-1844939, CCF-2121745"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            In the single-machine\n            <jats:italic>non-clairvoyant<\/jats:italic>\n            scheduling problem, the goal is to minimize the total completion time of jobs whose processing times are\n            <jats:italic>unknown<\/jats:italic>\n            <jats:italic>a priori<\/jats:italic>\n            . We revisit this well-studied problem and consider the question of how to effectively use (possibly erroneous) predictions of the processing times. We study this question from ground zero by first asking what constitutes a good prediction; we then propose a new measure to gauge prediction quality and design scheduling algorithms with strong guarantees under this measure. Our approach to derive a prediction error measure based on natural desiderata could find applications for other online problems.\n          <\/jats:p>","DOI":"10.1145\/3593969","type":"journal-article","created":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T12:38:25Z","timestamp":1683031105000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Non-clairvoyant Scheduling with Predictions"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5994-7280","authenticated-orcid":false,"given":"Sungjin","family":"Im","sequence":"first","affiliation":[{"name":"University of California, Merced, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2203-2586","authenticated-orcid":false,"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Google Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-4302-0751","authenticated-orcid":false,"given":"Mahshid Montazer","family":"Qaem","sequence":"additional","affiliation":[{"name":"University of California, Merced, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8650-2022","authenticated-orcid":false,"given":"Manish","family":"Purohit","sequence":"additional","affiliation":[{"name":"Google Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,14]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Anders Aamand Piotr Indyk and Ali Vakilian. 2019. (Learned) frequency estimation algorithms under Zipfian distribution. (2019). arXiv:1908.05198"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnca.2017.01.016"},{"key":"e_1_3_3_4_2","first-page":"303","volume-title":"ICML","author":"Anand Keerti","year":"2020","unstructured":"Keerti Anand, Rong Ge, and Debmalya Panigrahi. 2020. Customizing ML predictions for online algorithms. In ICML. PMLR, 303\u2013313."},{"key":"e_1_3_3_5_2","first-page":"345","volume-title":"ICML","author":"Antoniadis Antonios","year":"2020","unstructured":"Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. 2020. Online metric algorithms with untrusted predictions. In ICML. 345\u2013355."},{"key":"e_1_3_3_6_2","first-page":"7933","volume-title":"NeurIPS","author":"Antoniadis Antonios","year":"2020","unstructured":"Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. 2020. Secretary and online matching problems with machine learned advice. In NeurIPS. 7933\u20137944."},{"key":"e_1_3_3_7_2","first-page":"1070","volume-title":"STOC","author":"Azar Yossi","year":"2021","unstructured":"Yossi Azar, Stefano Leonardi, and Noam Touitou. 2021. Flow time scheduling with uncertain processing time. In STOC. 1070\u20131080."},{"key":"e_1_3_3_8_2","first-page":"252","volume-title":"SODA","author":"Azar Yossi","year":"2022","unstructured":"Yossi Azar, Stefano Leonardi, and Noam Touitou. 2022. Distortion-oblivious algorithms for minimizing flow time. In SODA. 252\u2013274."},{"key":"e_1_3_3_9_2","first-page":"15350","volume-title":"NeurIPS","author":"Bamas \u00c9tienne","year":"2020","unstructured":"\u00c9tienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. 2020. Learning augmented energy minimization via speed scaling. In NeurIPS. 15350\u201315359."},{"key":"e_1_3_3_10_2","volume-title":"NeurIPS","author":"Bamas \u00c9tienne","year":"2020","unstructured":"\u00c9tienne Bamas, Andreas Maggiori, and Ola Svensson. 2020. The primal-dual method for learning augmented algorithms. In NeurIPS."},{"key":"e_1_3_3_11_2","first-page":"822","volume-title":"ICML","author":"Bhaskara Aditya","year":"2020","unstructured":"Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. 2020. Online learning with imperfect hints. In ICML. 822\u2013831."},{"key":"e_1_3_3_12_2","volume-title":"ICML","author":"Cohen Edith","year":"2020","unstructured":"Edith Cohen, Ofir Geri, and Rasmus Pagh. 2020. Composable sketches for functions of frequencies: Beyond the worst case. In ICML."},{"key":"e_1_3_3_13_2","first-page":"10393","volume-title":"NeurIPS","author":"Dinitz Michael","year":"2021","unstructured":"Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. 2021. Faster matchings via learned duals. In NeurIPS. 10393\u201310406."},{"key":"e_1_3_3_14_2","first-page":"2319","volume-title":"ICML","author":"Gollapudi Sreenivas","year":"2019","unstructured":"Sreenivas Gollapudi and Debmalya Panigrahi. 2019. Online algorithms for rent-or-buy with expert advice. In ICML. 2319\u20132327."},{"key":"e_1_3_3_15_2","volume-title":"ICLR","author":"Hsu Chen-Yu","year":"2019","unstructured":"Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. 2019. Learning-based frequency estimation algorithms. In ICLR."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3136754"},{"key":"e_1_3_3_17_2","first-page":"2733","volume-title":"NeurIPS","author":"Im Sungjin","year":"2021","unstructured":"Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. 2021. Online knapsack with frequency predictions. In NeurIPS. 2733\u20132743."},{"key":"e_1_3_3_18_2","volume-title":"ICALP","author":"Jiang Zhihao","year":"2020","unstructured":"Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. 2020. Online algorithms for weighted paging with predictions. In ICALP. 69:1\u201369:18."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_3_3_20_2","first-page":"489","volume-title":"SIGMOD","author":"Kraska Tim","year":"2018","unstructured":"Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The case for learned index structures. In SIGMOD. 489\u2013504."},{"key":"e_1_3_3_21_2","first-page":"9661","volume-title":"NeurIPS","author":"Kumar Ravi","year":"2018","unstructured":"Ravi Kumar, Manish Purohit, and Zoya Svitkina. 2018. Improving online algorithms using ML predictions. In NeurIPS. 9661\u20139670."},{"key":"e_1_3_3_22_2","first-page":"1859","volume-title":"SODA","author":"Lattanzi Silvio","year":"2020","unstructured":"Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. 2020. Online scheduling via learned weights. In SODA. 1859\u20131877."},{"key":"e_1_3_3_23_2","volume-title":"ESA","author":"Lavastida Thomas","year":"2021","unstructured":"Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. 2021. Learnable and instance-robust predictions for online matching, flows and load balancing. In ESA. 59:1\u201359:17."},{"key":"e_1_3_3_24_2","first-page":"6523","volume-title":"ICML","author":"Li Shi","year":"2021","unstructured":"Shi Li and Jiayi Xian. 2021. Online unrelated machine load balancing with predictions revisited. In ICML. 6523\u20136532."},{"key":"e_1_3_3_25_2","first-page":"357","volume-title":"SPAA","author":"Lindermayr Alexander","year":"2022","unstructured":"Alexander Lindermayr and Nicole Megow. 2022. Permutation predictions for non-clairvoyant scheduling. In SPAA. 357\u2013368."},{"key":"e_1_3_3_26_2","first-page":"3296","volume-title":"ICML","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvtiskii. 2018. Competitive caching with machine learned advice. In ICML. 3296\u20133305."},{"key":"e_1_3_3_27_2","first-page":"495","volume-title":"CCGRID","author":"Matsunaga Andr\u00e9a","year":"2010","unstructured":"Andr\u00e9a Matsunaga and Jos\u00e9 A. B. Fortes. 2010. On the use of machine learning to predict the time and resources consumed by applications. In CCGRID. 495\u2013504."},{"key":"e_1_3_3_28_2","first-page":"464","volume-title":"NeurIPS","author":"Mitzenmacher Michael","year":"2018","unstructured":"Michael Mitzenmacher. 2018. A model for learned Bloom filters and optimizing by sandwiching. In NeurIPS. 464\u2013473."},{"key":"e_1_3_3_29_2","volume-title":"ITCS","author":"Mitzenmacher Michael","year":"2020","unstructured":"Michael Mitzenmacher. 2020. Scheduling with predictions and the price of misprediction. In ITCS. 14:1\u201314:18."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90151-1"},{"key":"e_1_3_3_31_2","first-page":"11","volume-title":"Workshop on Workflows in Support of Large-Scale Science","author":"Pietri Ilia","year":"2014","unstructured":"Ilia Pietri, Gideon Juve, Ewa Deelman, and Rizos Sakellariou. 2014. A performance model to estimate execution time of scientific workflows on the Cloud. In Workshop on Workflows in Support of Large-Scale Science. 11\u201319."},{"key":"e_1_3_3_32_2","volume-title":"Handbook of Scheduling - Algorithms, Models, and Performance Analysis","author":"Pruhs Kirk","year":"2004","unstructured":"Kirk Pruhs, Jir\u00ed Sgall, and Eric Torng. 2004. Online scheduling. In Handbook of Scheduling - Algorithms, Models, and Performance Analysis, Joseph Y.-T. Leung (Ed.). Chapman and Hall\/CRC."},{"key":"e_1_3_3_33_2","first-page":"1834","volume-title":"SODA","author":"Rohatgi Dhruv","year":"2020","unstructured":"Dhruv Rohatgi. 2020. Near-optimal bounds for online caching with machine learned advice. In SODA. 1834\u20131845."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108637435"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428336"},{"key":"e_1_3_3_36_2","volume-title":"ICLR","author":"Vaidya Kapil","year":"2021","unstructured":"Kapil Vaidya, Eric Knorr, Tim Kraska, and Michael Mitzenmacher. 2021. Partitioned learned Bloom filter. In ICLR."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3593969","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3593969","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:51Z","timestamp":1750178871000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3593969"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,14]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3593969"],"URL":"https:\/\/doi.org\/10.1145\/3593969","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,14]]},"assertion":[{"value":"2022-01-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}