{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:12:23Z","timestamp":1750219943903,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Netherlands Organisation for Scientific Research (NWO) through a VIDI","award":["016.Vidi.189.087"],"award-info":[{"award-number":["016.Vidi.189.087"]}]},{"name":"German Science Foundation","award":["ME 3825\/1"],"award-info":[{"award-number":["ME 3825\/1"]}]},{"name":"Independent Research Fund Denmark, Natural Sciences","award":["DFF-0135-00018B"],"award-info":[{"award-number":["DFF-0135-00018B"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>\n            We consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a single or multiple possibly unrelated machines that maximizes the number of jobs that complete before their deadline. Due to strong impossibility results for competitive analysis on a single machine, we require that jobs contain some\n            <jats:italic>slack<\/jats:italic>\n            \u025b &gt; 0, which means that the feasible time window for scheduling a job is at least 1+\u025b times its processing time on each eligible machine. Our contribution is two-fold: (i) We give the first non-trivial online algorithms for throughput maximization on unrelated machines, and (ii), this is the main focus of our paper, we answer the question on how to handle commitment requirements which enforce that a scheduler has to guarantee at a certain point in time the completion of admitted jobs. This is very relevant, e.g., in providing cloud-computing services, and disallows last-minute rejections of critical tasks. We present an algorithm for unrelated machines that is\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Theta (\\frac{1}{\\varepsilon })\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -competitive when the scheduler must commit upon starting a job. Somewhat surprisingly, this is the same optimal performance bound (up to constants) as for scheduling without commitment on a single machine. If commitment decisions must be made before a job\u2019s slack becomes less than a \u03b4-fraction of its size, we prove a competitive ratio of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {O}(\\frac{1}{\\varepsilon - \\delta })\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for 0 &lt; \u03b4 &lt; \u025b. This result nicely interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithm admits any bounded competitive ratio. While we mainly focus on scheduling without migration, our results also hold when comparing against a migratory optimal solution in case of identical machines.\n          <\/jats:p>","DOI":"10.1145\/3569582","type":"journal-article","created":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T12:15:47Z","timestamp":1671020147000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Throughput Maximization on Unrelated Machines: Commitment is No Burden"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8636-9711","authenticated-orcid":false,"given":"Franziska","family":"Eberle","sequence":"first","affiliation":[{"name":"Department of Mathematics, London School of Economics and Political Science, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3531-7644","authenticated-orcid":false,"given":"Nicole","family":"Megow","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computer Science, University of Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2236-0210","authenticated-orcid":false,"given":"Kevin","family":"Schewior","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,20]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_55"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764535"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9321-4"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799354138"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.620484"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.1994.342713"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00365406"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185354"},{"key":"e_1_3_1_10_2","doi-asserted-by":"crossref","first-page":"680","DOI":"10.1145\/335305.335401","volume-title":"STOC","author":"Berman Piotr","year":"2000","unstructured":"Piotr Berman and Bhaskar DasGupta. 2000. Improvements in throughout maximization for real-time scheduling. In STOC. ACM, 680\u2013687."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01469-2"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_11"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.58762"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210384"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90032-K"},{"key":"e_1_3_1_16_2","volume-title":"ESA (LIPIcs)","author":"Eberle Franziska","year":"2020","unstructured":"Franziska Eberle, Nicole Megow, and Kevin Schewior. 2020. Optimally handling commitment issues in online throughput maximization. In ESA (LIPIcs), Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168847"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2002.1019250"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022994010777"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022956425198"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_24"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1148438"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_55"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400271"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1128"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00074-9"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90165-1"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236882"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02248588"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68874-4_9"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486187"},{"key":"e_1_3_1_33_2","first-page":"402","volume-title":"IPCO (Lecture Notes in Computer Science)","author":"Moseley Benjamin","year":"2022","unstructured":"Benjamin Moseley, Kirk Pruhs, Clifford Stein, and Rudy Zhou. 2022. A competitive algorithm for throughput maximization on identical machines. In IPCO (Lecture Notes in Computer Science), Vol. 13265. Springer, 402\u2013414."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15369-3_27"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.03.006"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2016.75"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.06.011"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569582","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3569582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:57Z","timestamp":1750182537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,31]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3569582"],"URL":"https:\/\/doi.org\/10.1145\/3569582","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2023,1,31]]},"assertion":[{"value":"2021-06-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}