{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:31:30Z","timestamp":1772119890726,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider scheduling problems for unit jobs with release times, where the number or size of the gaps in the schedule is taken into consideration, either in the objective function or as a constraint. Except for several papers on minimum-energy scheduling, there is no work in the scheduling literature that uses performance metrics depending on the gap structure of a schedule. One of our objectives is to initiate the study of such scheduling problems. We focus on the model with unit-length jobs. First we examine scheduling problems with deadlines, where we consider two variants of minimum-gap scheduling: maximizing throughput with a budget for the number of gaps and minimizing the number of gaps with a throughput requirement. We then turn to other objective functions. For example, in some scenarios gaps in a schedule may be actually desirable, leading to the problem of maximizing the number of gaps. A related problem involves minimizing the maximum gap size. The second part of the paper examines the model without deadlines, where we focus on the tradeoff between the number of gaps and the total or maximum flow time. For all these problems we provide polynomial time algorithms, with running times ranging from <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for some problems to <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^7)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>7<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for other. The solutions involve a spectrum of algorithmic techniques, including different dynamic programming formulations, speed-up techniques based on searching Monge arrays, searching <jats:inline-formula><jats:alternatives><jats:tex-math>$$X+Y$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>X<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>Y<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> matrices, or implicit binary search. Throughout the paper, we also draw a connection between gap scheduling problems and their continuous analogues, namely hitting set problems for intervals of real numbers. As it turns out, for some problems the continuous variants provide insights leading to efficient algorithms for the corresponding discrete versions, while for other problems completely new techniques are needed to solve the discrete version.<\/jats:p>","DOI":"10.1007\/s10951-021-00691-w","type":"journal-article","created":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T13:05:25Z","timestamp":1626872725000},"page":"381-403","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Scheduling with gaps: new models and algorithms"],"prefix":"10.1007","volume":"24","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mordecai","family":"Golin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tak-Wah","family":"Lam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dorian","family":"Nogneng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,21]]},"reference":[{"key":"691_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M., Moran, S., Shor, P., & Wilber, R. (1987). Geometric applications of a matrix-searching algorithm. Algorithmica, 2, 195\u2013208.","journal-title":"Algorithmica"},{"key":"691_CR2","doi-asserted-by":"crossref","unstructured":"Angel, E., Bampis, E. & Chau, V. (2012). Low complexity scheduling algorithm minimizing the energy for tasks with agreeable deadlines. In 10th Latin American theoretical informatics symposium (LATIN\u201912) (pp. 13\u201324).","DOI":"10.1007\/978-3-642-29344-3_2"},{"key":"691_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2014.05.023","volume":"175","author":"E Angel","year":"2014","unstructured":"Angel, E., Bampis, E., & Chau, V. (2014). Low complexity scheduling algorithms minimizing the energy for tasks with agreeable deadlines. Discrete Applied Mathematics, 175, 1\u201310.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"691_CR4","first-page":"87","volume":"26","author":"V Auletta","year":"1998","unstructured":"Auletta, V., Parente, D., & Persiano, G. (1998). Placing resources on a growing line. Journal of Algorithms, 26(1), 87\u2013100.","journal-title":"Journal of Algorithms"},{"key":"691_CR5","doi-asserted-by":"crossref","unstructured":"Bampis, E. (2016). Algorithmic issues in energy-efficient computation. In Discrete optimization and operations research (pp. 3\u201314). Springer International Publishing.","DOI":"10.1007\/978-3-319-44914-2_1"},{"key":"691_CR6","doi-asserted-by":"crossref","unstructured":"Baptiste, P. (2006). Scheduling unit tasks to minimize the number of idle periods: A polynomial time algorithm for offline dynamic power management. In Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms (SODA\u201906) (pp. 364\u2013367).","DOI":"10.1145\/1109557.1109598"},{"key":"691_CR7","doi-asserted-by":"crossref","unstructured":"Baptiste, P., Chrobak, M., & D\u00fcrr, C. (2007). Polynomial time algorithms for minimum energy scheduling. In Proceedings of the 15th annual European symposium on algorithms (ESA\u201907) (pp. 136\u2013150).","DOI":"10.1007\/978-3-540-75520-3_14"},{"key":"691_CR8","doi-asserted-by":"crossref","unstructured":"Baptiste, P., Chrobak, M., & D\u00fcrr, C. (2012). Polynomial-time algorithms for minimum energy scheduling. ACM Transactions on Algorithms 8(3), 26:1\u201326:29","DOI":"10.1145\/2229163.2229170"},{"key":"691_CR9","doi-asserted-by":"crossref","unstructured":"Bein, W. W., Golin, M. J., Larmore, L. L., & Zhang, Y. (2009). The Knuth\u2013Yao quadrangle-inequality speedup is a consequence of total monotonicity. ACM Transactions on Algorithms, 6(1), 17:1\u201317:22.","DOI":"10.1145\/1644015.1644032"},{"issue":"2","key":"691_CR10","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"RE Burkard","year":"1996","unstructured":"Burkard, R. E., Klinz, B., & Rudolf, R. (1996). Perspectives of Monge properties in optimization. Discrete Applied Mathematics, 70(2), 95\u2013161.","journal-title":"Discrete Applied Mathematics"},{"key":"691_CR11","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.tcs.2015.05.028","volume":"592","author":"DZ Chen","year":"2015","unstructured":"Chen, D. Z., Li, J., & Wang, H. (2015). Efficient algorithms for the one-dimensional k-center problem. Theoretical Computer Science, 592, 135\u2013142.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"691_CR12","first-page":"241","volume":"1","author":"M Chrobak","year":"2011","unstructured":"Chrobak, M., D\u00fcrr, C., Hurand, M., & Robert, J. (2011). Algorithms for temperature-aware task scheduling in microprocessor systems. SUSCOM, 1(3), 241\u2013247.","journal-title":"SUSCOM"},{"key":"691_CR13","unstructured":"Chrobak, M., Eppstein, D., Italiano, G. F., & Yung, M. (1991). Efficient sequential and parallel algorithms for computing recovery points in trees and paths. In 2nd annual ACM-SIAM symposium on discrete algorithms (SODA\u201991) (pp. 158\u2013167)."},{"issue":"3","key":"691_CR14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10951-016-0492-y","volume":"20","author":"M Chrobak","year":"2017","unstructured":"Chrobak, M., Feige, U., Hajiaghayi, M. T., Khanna, S., Li, F., & Naor, S. (2017). A greedy approximation algorithm for minimum-gap scheduling. Journal of Scheduling, 20(3), 279\u2013292.","journal-title":"Journal of Scheduling"},{"key":"691_CR15","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Feige, U., Taghi\u00a0Hajiaghayi, M., Khanna, S., Li, F., & Naor, S. (2013). A greedy approximation algorithm for minimum-gap scheduling. In: Proceedings of 8th international conference on algorithms and complexity (CIAC\u201913) (pp. 97\u2013109).","DOI":"10.1007\/978-3-642-38233-8_9"},{"key":"691_CR16","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Larmore, L. L., & Rytter, W. (2001). The k-median problem for directed trees. In Mathematical foundations of Computer Science 2001, 26th international symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27\u201331, 2001, Proceedings (pp. 260\u2013271).","DOI":"10.1007\/3-540-44683-4_23"},{"key":"691_CR17","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.ipl.2016.11.001","volume":"118","author":"P Damaschke","year":"2017","unstructured":"Damaschke, P. (2017). Refined algorithms for hitting many intervals. Information Processing Letters, 118, 117\u2013122.","journal-title":"Information Processing Letters"},{"key":"691_CR18","doi-asserted-by":"crossref","unstructured":"Demaine, E. D., Ghodsi, M., Hajiaghayi, M. T., Sayedi-Roshkhar, A. S., & Zadimoghaddam, M. (2007). Scheduling to minimize gaps and power consumption. In Proceedings of the ACM symposium on parallelism in algorithms and architectures (SPAA\u201907) (pp. 46\u201354).","DOI":"10.1145\/1248377.1248385"},{"key":"691_CR19","unstructured":"Frederickson, G. N. (1991a). Optimal algorithms for tree partitioning. In 2nd annual ACM\/SIGACT-SIAM symposium on discrete algorithms (SODA\u201991) (pp. 168\u2013177)."},{"key":"691_CR20","doi-asserted-by":"crossref","unstructured":"Frederickson, G. N. (1991b). Parametric search and locating supply centers in trees. In Workshop on algorithms and data structures (WADS\u201991) (pp. 299\u2013319).","DOI":"10.1007\/BFb0028271"},{"issue":"2","key":"691_CR21","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"GN Frederickson","year":"1982","unstructured":"Frederickson, G. N., & Johnson, D. B. (1982). The complexity of selection and ranking in X+Y and matrices with sorted columns. Journal of Computer and System Sciences, 24(2), 197\u2013208.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"691_CR22","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1137\/0213002","volume":"13","author":"GN Frederickson","year":"1984","unstructured":"Frederickson, G. N., & Johnson, D. B. (1984). Generalized selection and ranking: Sorted matrices. SIAM Journal on Computing, 13(1), 14\u201330.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"691_CR23","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1137\/0219013","volume":"19","author":"GN Frederickson","year":"1990","unstructured":"Frederickson, G. N., & Johnson, D. B. (1990). Erratum: Generalized selection and ranking: Sorted matrices. SIAM Journal on Computing, 19(1), 205\u2013206.","journal-title":"SIAM Journal on Computing"},{"key":"691_CR24","unstructured":"Frederickson, G. N., & Zhou, S. (2017). Optimal parametric search for path and tree partitioning. CoRR. arXiv:abs\/1711.00599."},{"issue":"8","key":"691_CR25","doi-asserted-by":"publisher","first-page":"3918","DOI":"10.1109\/TIT.2010.2050947","volume":"56","author":"M Golin","year":"2010","unstructured":"Golin, M., & Zhang, Y. (2010). A dynamic programming approach to length-limited Huffman coding: Space reduction with the Monge property. IEEE Transactions on Information Theory, 56(8), 3918\u20133929.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"7","key":"691_CR26","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0167-6377(91)90041-M","volume":"10","author":"R Hassin","year":"1991","unstructured":"Hassin, R., & Tamir, A. (1991). Improved complexity bounds for location problems on the real line. Operations Research Letters, 10(7), 395\u2013402.","journal-title":"Operations Research Letters"},{"issue":"2","key":"691_CR27","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/1067309.1067324","volume":"36","author":"S Irani","year":"2005","unstructured":"Irani, S., & Pruhs, K. R. (2005). Algorithmic problems in power management. SIGACT News, 36(2), 63\u201376.","journal-title":"SIGACT News"},{"key":"691_CR28","first-page":"45","volume":"31","author":"K Jansen","year":"1997","unstructured":"Jansen, K., Scheffler, P., & Woeginger, G. (1997). The disjoint cliques problem. RAIRO Recherche Op\u00e9rationnelle, 31, 45\u201366.","journal-title":"RAIRO Recherche Op\u00e9rationnelle"},{"key":"691_CR29","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1137\/0212051","volume":"12","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N., & Tamir, A. (1983). New results on the complexity of p-center problems. SIAM Journal on Computing, 12, 751\u2013758.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"691_CR30","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0020-0190(85)90123-1","volume":"20","author":"A Mirzaian","year":"1985","unstructured":"Mirzaian, A., & Arjomandi, E. (1985). Selection in X+Y and matrices with sorted rows and columns. Information Processing Letters, 20(1), 13\u201317.","journal-title":"Information Processing Letters"},{"key":"691_CR31","unstructured":"Wikipedia: Point coordination function. http:\/\/en.wikipedia.org\/wiki\/Point_coordination_function"},{"issue":"3","key":"691_CR32","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0167-6377(00)00041-9","volume":"27","author":"GJ Woeginger","year":"2000","unstructured":"Woeginger, G. J. (2000). Monge strikes again: Optimal placement of web proxies in the Internet. Operations Research Letters, 27(3), 93\u201396.","journal-title":"Operations Research Letters"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00691-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-021-00691-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00691-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,24]],"date-time":"2021-08-24T06:41:05Z","timestamp":1629787265000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-021-00691-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["691"],"URL":"https:\/\/doi.org\/10.1007\/s10951-021-00691-w","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"10 June 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}