{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T21:12:15Z","timestamp":1762809135617,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T00:00:00Z","timestamp":1625788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Government of Spain through project ``BugBirth'","award":["RTI2018-101963-B-100"],"award-info":[{"award-number":["RTI2018-101963-B-100"]}]},{"name":"Regional Government of Madrid","award":["S2013\/ICE-2894"],"award-info":[{"award-number":["S2013\/ICE-2894"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            We consider the Windows Scheduling (WS) problem, which is a restricted version of Unit-Fractions Bin Packing, and it is also called Inventory Replenishment in the context of Supply Chain. In brief, WS problem is to schedule the use of communication channels to clients. Each client\n            <jats:italic>\n              c\n              <jats:sup>i<\/jats:sup>\n            <\/jats:italic>\n            is characterized by an active cycle and a window\n            <jats:italic>\n              w\n              <jats:sup>i<\/jats:sup>\n            <\/jats:italic>\n            . During the period of time that any given client\n            <jats:italic>\n              c\n              <jats:sup>i<\/jats:sup>\n            <\/jats:italic>\n            is active, there must be at least one transmission from\n            <jats:italic>\n              c\n              <jats:sup>i<\/jats:sup>\n            <\/jats:italic>\n            scheduled in any\n            <jats:italic>\n              w\n              <jats:sup>i<\/jats:sup>\n            <\/jats:italic>\n            consecutive time slots, but at most one transmission can be carried out in each channel per time slot. The goal is to minimize the number of channels used.\n          <\/jats:p>\n          <jats:p>We extend previous online models, where decisions are permanent, assuming that clients may be reallocated at some cost. We assume that such cost is a constant amount paid per reallocation. That is, we aim to minimize also the number of reallocations. We present three online reallocation algorithms for Windows Scheduling. We evaluate experimentally multiple variants of these protocols showing that, in practice, all three achieve constant amortized reallocations with close to optimal channel usage. Our simulations also expose interesting tradeoffs between reallocations and channel usage. We introduce a new objective function for WS with reallocations that can be also applied to models where reallocations are not possible. We analyze this metric for one of the algorithms that, to the best of our knowledge, is the first online WS protocol with theoretical guarantees that applies to scenarios where clients may leave and the analysis is against current load rather than peak load. Using previous results, we also observe bounds on channel usage for one of the algorithms.<\/jats:p>","DOI":"10.1145\/3462208","type":"journal-article","created":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T15:06:22Z","timestamp":1625843182000},"page":"1-19","source":"Crossref","is-referenced-by-count":2,"title":["Dynamic Windows Scheduling with Reallocation"],"prefix":"10.1145","volume":"26","author":[{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rutgers University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katia","family":"Leal","sequence":"additional","affiliation":[{"name":"Depto. de Teor\u00eda de la Se\u00f1al, Comunicaciones, Sistemas Telem\u00e1ticos y Computaci\u00f3n,Universidad Rey Juan Carlos, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel A.","family":"Mosteiro","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Pace University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher Thraves","family":"Caro","sequence":"additional","affiliation":[{"name":"Depto. de Ingenier\u00eda Matem\u00e1tica, Universidad de Concepci\u00f3n,Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10100-012-0266-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-012-9489-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2786397.2786403"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240447X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412234"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273344"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9930-4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.028"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 15th International Symposium on Algorithms and Computation (Lecture Notes in Computer Science)","volume":"3341","author":"Chan Wun-Tat","unstructured":"Wun-Tat Chan and Prudence W. H. Wong . 2005. On-line windows scheduling of temporary items . In Proceedings of the 15th International Symposium on Algorithms and Computation (Lecture Notes in Computer Science) , Vol. 3341 . Springer Berlin, 259\u2013270. DOI:https:\/\/doi.org\/10.1007\/978-3-540-30551-4_24 10.1007\/978-3-540-30551-4_24 Wun-Tat Chan and Prudence W. H. Wong. 2005. On-line windows scheduling of temporary items. In Proceedings of the 15th International Symposium on Algorithms and Computation (Lecture Notes in Computer Science), Vol. 3341. Springer Berlin, 259\u2013270. DOI:https:\/\/doi.org\/10.1007\/978-3-540-30551-4_24"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Martin Farach-Colton Katia Leal Miguel A. Mosteiro and Christopher Thraves. 2014. Dynamic Windows Scheduling with Reallocation. arXiv:cs.DS\/1404.1087.  Martin Farach-Colton Katia Leal Miguel A. Mosteiro and Christopher Thraves. 2014. Dynamic Windows Scheduling with Reallocation. arXiv:cs.DS\/1404.1087.","DOI":"10.1007\/978-3-319-07959-2_9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.09.002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00170-009-2190-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794276749"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOSH.0000031424.35504.c4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0381"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1171-0"},{"key":"e_1_2_1_17_1","unstructured":"SimJava 2006. SimJava. Retrieved from http:\/\/www.icsa.inf.ed.ac.uk\/research\/groups\/hase\/simjava\/.  SimJava 2006. SimJava. Retrieved from http:\/\/www.icsa.inf.ed.ac.uk\/research\/groups\/hase\/simjava\/."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1074"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.12.011"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3462208","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3462208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:53Z","timestamp":1750193333000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3462208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,9]]},"references-count":19,"alternative-id":["10.1145\/3462208"],"URL":"https:\/\/doi.org\/10.1145\/3462208","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2021,7,9]]}}}