{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T09:03:38Z","timestamp":1776071018558,"version":"3.50.1"},"reference-count":27,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>This paper studies a scheduling problem with machine calibrations for multi-interval jobs. More exactly, there are n (possibly weighted) jobs of unit size that must be scheduled on a single initially uncalibrated machine. The machine can process jobs only when calibrated, and such a calibration lasts for T time slots. The standard model by Bender et al. [Bender MA, Bunde DP, Leung VJ, McCauley S, Phillips CA (2013) Efficient scheduling to minimize calibrations. Blelloch GE, V\u00f6cking B, eds. 25th ACM Sympos. Parallelism Algorithms Architectures SPAA \u201813 (ACM, New York), 280\u2013287] assumes that each job has a release time and deadline between which it must be processed. We study a generalization in which each job must be processed during one of possibly many job-dependent time intervals. We consider two objectives: In the minimization version, our goal is to minimize the number of calibrations while scheduling all jobs. In the maximization version, our goal is to maximize the total weight of scheduled jobs while using at most B calibrations. For the minimization version, we present a logarithmic approximation algorithm. We also prove that the problem is set-cover hard, implying that our algorithm is optimal up to a constant factor unless P = NP. The special case when each job may be scheduled in at most two time slots is shown to be vertex-cover hard, implying that there is no [Formula: see text]-approximation algorithm based on the unique game conjecture. For the maximization version, we give an algorithm with approximation ratio [Formula: see text]. This improves upon the previously best-known algorithm, which has an approximation ratio of 1\/3 [Chau V, Feng S, Li M, Wang Y, Zhang G, Zhang Y (2019) Weighted throughput maximization with calibrations. Friggstad Z, Sack JR, Salavatipour MR, eds. Algorithms Data Structures 16th Internat. Sympos. WADS 2019 Proc., Lecture Notes in Computer Science, vol. 11646 (Springer, New York), 311\u2013324]. Moreover, we also prove that our bound on the approximation ratio is tight. Although all hardness results mentioned above hold for any [Formula: see text], we provide optimal polynomial-time algorithms for T = 2 in both the minimization version and the maximization version. Finally, we show that our methods can be extended into the m identical machines case by losing some running time, whereas all algorithmic results remain the same in both versions.<\/jats:p>\n                  <jats:p>History: Accepted by Erwin Pesch, Area Editor for Heuristic Search &amp; Approximation Algorithms.<\/jats:p>\n                  <jats:p>Supplemental Material: The online appendix is available at https:\/\/doi.org\/10.1287\/ijoc.2023.0430 .<\/jats:p>","DOI":"10.1287\/ijoc.2023.0430","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T10:43:39Z","timestamp":1743677019000},"page":"377-396","source":"Crossref","is-referenced-by-count":0,"title":["Scheduling with Calibrations for Multi-Interval Jobs"],"prefix":"10.1287","volume":"38","author":[{"given":"Vincent","family":"Chau","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Southeast University, Nanjing 211189, China"}]},{"given":"Christoph","family":"Damerius","sequence":"additional","affiliation":[{"name":"Department of Informatics, Universit\u00e4t Hamburg, 22527 Hamburg, Germany"}]},{"given":"Peter","family":"Kling","sequence":"additional","affiliation":[{"name":"Department of Informatics, Universit\u00e4t Hamburg, 22527 Hamburg, Germany"}]},{"given":"Minming","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong"}]},{"given":"Florian","family":"Schneider","sequence":"additional","affiliation":[{"name":"Department of Informatics, Universit\u00e4t Hamburg, 22527 Hamburg, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4859-2661","authenticated-orcid":false,"given":"Ruilong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong"}]}],"member":"109","reference":[{"key":"B1","volume-title":"Network Flows\u2014Theory, Algorithms and Applications","author":"Ahuja RK","year":"1993"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-021-00688-5"},{"issue":"1","key":"B3","first-page":"E22","volume":"5","author":"Bansal SK","year":"2004","journal-title":"AAPS PharmSciTech"},{"key":"B4","doi-asserted-by":"crossref","unstructured":"Bender MA, Bunde DP, Leung VJ, McCauley S, Phillips CA (2013) Efficient scheduling to minimize calibrations. Blelloch GE, V\u00f6cking B, eds.\n                      25th ACM Sympos. Parallelism Algorithms Architectures SPAA \u201813\n                      (ACM, New York), 280\u2013287.","DOI":"10.1145\/2486159.2486193"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1016\/S0007-8506(07)60147-4"},{"key":"B6","doi-asserted-by":"crossref","unstructured":"Chang J, Gabow HN, Khuller S (2012) A model for minimizing active processor time. Epstein L, Ferragina P, eds.\n                      Algorithms ESA 2012 20th Annual Eur. Sympos. Proc.\n                      , Lecture Notes in Computer Science, vol. 7501 (Springer, New York), 289\u2013300.","DOI":"10.1007\/978-3-642-33090-2_26"},{"key":"B7","doi-asserted-by":"crossref","unstructured":"Chau V, Li M, McCauley S, Wang K (2017) Minimizing total weighted flow time with calibrations. Scheideler C, Hajiaghayi MT, eds.\n                      Proc. 29th ACM Sympos. Parallelism Algorithms Architectures SPAA 2017\n                      (ACM, New York), 67\u201376.","DOI":"10.1145\/3087556.3087573"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.04.020"},{"key":"B9","doi-asserted-by":"crossref","unstructured":"Chau V, Feng S, Li M, Wang Y, Zhang G, Zhang Y (2019) Weighted throughput maximization with calibrations. Friggstad Z, Sack JR, Salavatipour MR, eds.\n                      Algorithms Data Structures 16th Internat. Sympos. WADS 2019 Proc.\n                      , Lecture Notes in Computer Science, vol. 11646 (Springer, New York), 311\u2013324.","DOI":"10.1007\/978-3-030-24766-9_23"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.07.021"},{"key":"B11","doi-asserted-by":"crossref","unstructured":"Chen L, Li M, Lin G, Wang K (2019) Approximation of scheduling with calibrations on multiple machines (brief announcement). Scheideler C, Berenbrink P, eds.\n                      31st ACM Sympos. Parallelism Algorithms Architectures SPAA 2019\n                      (ACM, New York), 237\u2013239.","DOI":"10.1145\/3323165.3323173"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703422479"},{"key":"B13","doi-asserted-by":"crossref","unstructured":"Demaine ED, Ghodsi M, Hajiaghayi MT, Sayedi-Roshkhar AS, Zadimoghaddam M (2007) Scheduling to minimize gaps and power consumption. Gibbons PB, Scheideler C, eds.\n                      SPAA 2007 Proc. 19th Annual ACM Sympos. Parallelism Algorithms Architectures\n                      (ACM, New York), 46\u201354.","DOI":"10.1145\/1248377.1248385"},{"key":"B14","doi-asserted-by":"crossref","unstructured":"Feng Q, Jiang X, Wang J (2016) Improved algorithms for several parameterized problems based on random methods. Zhu D, Bereg S, eds.\n                      Frontiers Algorithmics 10th Internat. Workshop FAW 2016 Proc.\n                      , Lecture Notes in Computer Science, vol. 9711 (Springer, New York), 65\u201374.","DOI":"10.1007\/978-3-319-39817-4_7"},{"key":"B15","doi-asserted-by":"crossref","unstructured":"Fineman JT, Sheridan B (2015) Scheduling non-unit jobs to minimize calibrations. Blelloch GE, Agrawal K, eds.\n                      Proc. 27th ACM Sympos. Parallelism Algorithms Architectures SPAA 2015\n                      (ACM, New York), 161\u2013170.","DOI":"10.1145\/2755573.2755605"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1801"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2041"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2022.0128"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.3390\/s130709132"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.1.80"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.11.002"},{"key":"B23","doi-asserted-by":"crossref","unstructured":"Trevisan L (2001) Non-approximability results for optimization problems on bounded degree instances. Scott Vitter J, Spirakis PG, Yannakakis M, eds.\n                      Proc. 33rd Annual ACM Sympos. Theory Comput.\n                      (ACM, New York), 453\u2013461.","DOI":"10.1145\/380752.380839"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.03.018"},{"key":"B25","unstructured":"WebLink (2016) Maximum weight matching and submodular functions. Accessed July 19, 2016, https:\/\/cstheory.stackexchange.com\/a\/36209\/34178."},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579435"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1109\/34.888718"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.2023.0430","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T08:19:48Z","timestamp":1776068388000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.2023.0430"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/ijoc.2023.0430"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.2023.0430","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}