{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T04:03:50Z","timestamp":1768968230409,"version":"3.49.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CF-1824303, CCF-1845146, CCF-1733873, CMMI-1938909 and ANR project OATA ANR-15- CE40-0015-01, Hadamard PGMO and DIM RFSI."],"award-info":[{"award-number":["CF-1824303, CCF-1845146, CCF-1733873, CMMI-1938909 and ANR project OATA ANR-15- CE40-0015-01, Hadamard PGMO and DIM RFSI."]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>When a computer system schedules jobs there is typically a significant cost associated with preempting a job during execution. This cost can be incurred from the expensive task of saving the memory\u2019s state or from loading data into and out of memory. Thus, it is desirable to schedule jobs non-preemptively to avoid the costs of preemption.<\/jats:p>\n          <jats:p>\n            There is a need for non-preemptive system schedulers for desktops, servers, and data centers. Despite this need, there is a gap between theory and practice. Indeed, few non-preemptive\n            <jats:italic>online<\/jats:italic>\n            schedulers are known to have strong theoretical guarantees. This gap is likely due to strong lower bounds on any online algorithm for popular objectives. Indeed, typical worst-case analysis approaches, and even resource-augmented approaches such as speed augmentation, result in all algorithms having poor performance guarantees.\n          <\/jats:p>\n          <jats:p>This article considers online non-preemptive scheduling problems in the worst-case rejection model where the algorithm is allowed to reject a small fraction of jobs. By rejecting only a few jobs, this article shows that the strong lower bounds can be circumvented. This approach can be used to discover algorithmic scheduling policies with desirable worst-case guarantees.<\/jats:p>\n          <jats:p>Specifically, the article presents algorithms for the following three objectives: minimizing the total flow-time, minimizing the total weighted flow-time plus energy where energy is a convex function, and minimizing the total energy under the deadline constraints. The algorithms for the first two problems have a small constant competitive ratio while rejecting only a constant fraction of jobs. For the last problem, we present a constant competitive ratio without rejection.<\/jats:p>\n          <jats:p>Beyond specific results, the article asserts that alternative models beyond speed augmentation should be explored to aid in the discovery of good schedulers in the face of the requirement of being online and non-preemptive.<\/jats:p>","DOI":"10.1145\/3460880","type":"journal-article","created":{"date-parts":[[2021,8,23]],"date-time":"2021-08-23T10:47:26Z","timestamp":1629715646000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Non-preemptive Scheduling on Unrelated Machines with Rejections"],"prefix":"10.1145","volume":"8","author":[{"given":"Giorgio","family":"Lucarelli","sequence":"first","affiliation":[{"name":"LCOMS, Univ. Lorraine, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nguyen Kim","family":"Thang","sequence":"additional","affiliation":[{"name":"IBISC, Univ \u00c9vry, Universit\u00e9 Paris-Saclay, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhinav","family":"Srivastav","sequence":"additional","affiliation":[{"name":"IBISC, Univ \u00c9vry, Universit\u00e9 Paris-Saclay, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis","family":"Trystram","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,8,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49529-2_4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.97"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems.","author":"Bansal Nikhil","year":"2017","unstructured":"Nikhil Bansal . 2017 . Some open problems in scheduling . In Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems. Nikhil Bansal. 2017. Some open problems in scheduling. In Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a009"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.76"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206038"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380778"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.75"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_26"},{"key":"e_1_2_1_10_1","volume-title":"Devanur and Zhiyi Huang","author":"Nikhil","year":"2014","unstructured":"Nikhil R. Devanur and Zhiyi Huang . 2014 . Primal dual gives almost optimal energy efficient online algorithms. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms. Nikhil R. Devanur and Zhiyi Huang. 2014. Primal dual gives almost optimal energy efficient online algorithms. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1141038.1705261"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/312173.312174"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 27th International Symposium on Algorithms and Computation. 53:1\u201353:13","author":"Liu Fu-Hong","unstructured":"Fu-Hong Liu , Hsiang Hsuan Liu , and Prudence W. H. Wong . 2016. Optimal nonpreemptive scheduling in a smart grid model . In Proceedings of the 27th International Symposium on Algorithms and Computation. 53:1\u201353:13 . Fu-Hong Liu, Hsiang Hsuan Liu, and Prudence W. H. Wong. 2016. Optimal nonpreemptive scheduling in a smart grid model. In Proceedings of the 27th International Symposium on Algorithms and Computation. 53:1\u201353:13."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201916)","volume":"57","author":"Lucarelli Giorgio","year":"2016","unstructured":"Giorgio Lucarelli , Nguyen Kim Thang , Abhinav Srivastav , and Denis Trystram . 2016 . Online non-preemptive scheduling in a resource augmentation model based on duality . In Proceedings of the European Symposium on Algorithms (ESA\u201916) , Vol. 57 . 1\u201317. Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. 2016. Online non-preemptive scheduling in a resource augmentation model based on duality. In Proceedings of the European Symposium on Algorithms (ESA\u201916), Vol. 57. 1\u201317."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0068-9"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 21st European Symposium on Algorithms. 755\u2013766","author":"Thang Nguyen Kim","year":"2013","unstructured":"Nguyen Kim Thang . 2013 . Lagrangian duality in online scheduling with resource augmentation and speed scaling . In Proceedings of the 21st European Symposium on Algorithms. 755\u2013766 . Nguyen Kim Thang. 2013. Lagrangian duality in online scheduling with resource augmentation and speed scaling. In Proceedings of the 21st European Symposium on Algorithms. 755\u2013766."},{"key":"e_1_2_1_18_1","volume-title":"Online primal-dual algorithms with configuration linear programs. arXiv:1708.04903","author":"Thang Nguyen Kim","year":"2017","unstructured":"Nguyen Kim Thang . 2017. Online primal-dual algorithms with configuration linear programs. arXiv:1708.04903 ( 2017 ). Nguyen Kim Thang. 2017. Online primal-dual algorithms with configuration linear programs. arXiv:1708.04903 (2017)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492493"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460880","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460880","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460880","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:29Z","timestamp":1750195469000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460880"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3460880"],"URL":"https:\/\/doi.org\/10.1145\/3460880","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}