{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:16Z","timestamp":1740122416995,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T00:00:00Z","timestamp":1708560000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T00:00:00Z","timestamp":1708560000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1467\/22"],"award-info":[{"award-number":["1467\/22"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006260","name":"Technion - Israel Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006260","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the non-preemptive scheduling problem on identical machines where there is a parameter <jats:italic>B<\/jats:italic> and each machine in every unit length time interval can process up to <jats:italic>B<\/jats:italic> different jobs. The goal function we consider is the makespan minimization and we develop an EPTAS for this problem. Prior to our work a PTAS was known only for the case of one machine and constant values of <jats:italic>B<\/jats:italic>, and even the case of non-constant values of <jats:italic>B<\/jats:italic> on one machine was not known to admit a PTAS.<\/jats:p>","DOI":"10.1007\/s10878-024-01108-y","type":"journal-article","created":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T15:02:58Z","timestamp":1708614178000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["EPTAS for parallel identical machine scheduling with time restrictions"],"prefix":"10.1007","volume":"47","author":[{"given":"G.","family":"Jaykrishnan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7935-6218","authenticated-orcid":false,"given":"Asaf","family":"Levin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,22]]},"reference":[{"issue":"1","key":"1108_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon N, Azar Y, Woeginger GJ, Yadid T (1998) Approximation schemes for scheduling on parallel machines. J Sched 1(1):55\u201366","journal-title":"J Sched"},{"key":"1108_CR2","doi-asserted-by":"crossref","unstructured":"Benmansour R, Braun O, Artiba A (2014) On the single-processor scheduling problem with time restrictions. In: International conference on control, decision and information technologies, CoDIT 2014, pp 242\u2013245","DOI":"10.1109\/CoDIT.2014.6996900"},{"issue":"4","key":"1108_CR3","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s10951-018-0579-8","volume":"22","author":"R Benmansour","year":"2019","unstructured":"Benmansour R, Braun O, Hanafi S (2019) The single-processor scheduling problem with time restrictions: complexity and related problems. J Sched 22(4):465\u2013471","journal-title":"J Sched"},{"issue":"4","key":"1108_CR4","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s10951-013-0342-0","volume":"17","author":"O Braun","year":"2014","unstructured":"Braun O, Chung F, Graham R (2014) Single-processor scheduling with time restrictions. J Sched 17(4):399\u2013403","journal-title":"J Sched"},{"issue":"2","key":"1108_CR5","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s00291-016-0431-5","volume":"38","author":"O Braun","year":"2016","unstructured":"Braun O, Chung F, Graham R (2016) Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions. OR Spectrum 38(2):531\u2013540","journal-title":"OR Spectrum"},{"issue":"4","key":"1108_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M Cesati","year":"1997","unstructured":"Cesati M, Trevisan L (1997) On the efficiency of polynomial time approximation schemes. Inf Process Lett 64(4):165\u2013171","journal-title":"Inf Process Lett"},{"key":"1108_CR7","doi-asserted-by":"crossref","unstructured":"Chen L, Jansen K, Luo W, Zhang G (2016) An efficient PTAS for parallel machine scheduling with capacity constraints. In: International conference on combinatorial optimization and applications (COCOA), pp 608\u2013623","DOI":"10.1007\/978-3-319-48749-6_44"},{"issue":"3","key":"1108_CR8","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1016\/j.ejor.2004.09.002","volume":"171","author":"M Dell\u2019Amico","year":"2006","unstructured":"Dell\u2019Amico M, Iori M, Martello S, Monaci M (2006) Lower bounds and heuristic algorithms for the $$k_i$$-partitioning problem. Eur J Oper Res 171(3):725\u2013742","journal-title":"Eur J Oper Res"},{"issue":"3","key":"1108_CR9","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1002\/jos.68","volume":"4","author":"M Dell\u2019Amico","year":"2001","unstructured":"Dell\u2019Amico M, Martello S (2001) Bounds for the cardinality constrained $$P||C_{max}$$ problem. J Sched 4(3):123\u2013138","journal-title":"J Sched"},{"key":"1108_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R Downey","year":"1999","unstructured":"Downey R, Fellows M (1999) Parameterized complexity. Springer, New York, NY"},{"issue":"1\u20132","key":"1108_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-013-0706-4","volume":"147","author":"L Epstein","year":"2014","unstructured":"Epstein L, Levin A (2014) An efficient polynomial time approximation scheme for load balancing on uniformly related machines. Math Program 147(1\u20132):1\u201323","journal-title":"Math Program"},{"key":"1108_CR12","unstructured":"Epstein L, Levin A (2014) Minimum total weighted completion time: Faster approximation schemes. arXiv:1404.1059"},{"key":"1108_CR13","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum J, Grohe M (2006) Parameterized complexity theory. Springer-Verlag, Berlin Heidelberg"},{"issue":"10\u201311","key":"1108_CR14","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1016\/S0898-1221(03)90201-X","volume":"46","author":"Y He","year":"2003","unstructured":"He Y, Tan Z, Zhu J, Yao E (2003) $$k$$-partitioning problems for maximizing the minimum load. Comput. Math. Appl. 46(10\u201311):1671\u20131681","journal-title":"Comput. Math. Appl."},{"volume-title":"Approximation algorithms for NP-hard problems","year":"1997","key":"1108_CR15","unstructured":"Hochbaum DS (ed) (1997) Approximation algorithms for NP-hard problems. PWS Pub. Co, Boston"},{"issue":"1","key":"1108_CR16","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum DS, Shmoys DB (1987) Using dual approximation algorithms for scheduling problems theoretical and practical results. J ACM 34(1):144\u2013162","journal-title":"J ACM"},{"issue":"3","key":"1108_CR17","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"DS Hochbaum","year":"1988","unstructured":"Hochbaum DS, Shmoys DB (1988) A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J Comput 17(3):539\u2013551","journal-title":"SIAM J Comput"},{"issue":"2","key":"1108_CR18","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/090749451","volume":"24","author":"K Jansen","year":"2010","unstructured":"Jansen K (2010) An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. SIAM J Discrete Math 24(2):457\u2013485","journal-title":"SIAM J Discrete Math"},{"key":"1108_CR19","unstructured":"Jansen K, Klein K, Maack M, Rau M (2019) Empowering the configuration-IP\u2014new PTAS results for scheduling with setups times. In: 10th conference on Innovations in Theoretical Computer Science (ITCS), pp 44:1\u201344:19"},{"issue":"4","key":"1108_CR20","doi-asserted-by":"publisher","first-page":"1371","DOI":"10.1287\/moor.2019.1036","volume":"45","author":"K Jansen","year":"2020","unstructured":"Jansen K, Klein K-M, Verschae J (2020) Closing the gap for makespan scheduling via sparsification techniques. Math Oper Res 45(4):1371\u20131392","journal-title":"Math Oper Res"},{"issue":"10","key":"1108_CR21","doi-asserted-by":"publisher","first-page":"4134","DOI":"10.1007\/s00453-019-00581-w","volume":"81","author":"K Jansen","year":"2019","unstructured":"Jansen K, Maack M (2019) An EPTAS for scheduling on unrelated machines of few different types. Algorithmica 81(10):4134\u20134164","journal-title":"Algorithmica"},{"key":"1108_CR22","doi-asserted-by":"crossref","unstructured":"Kannan R (1983) Improved algorithms for integer programming and related lattice problems. In: 15th Annual ACM symposium on Theory of computing (STOC), pp 193\u2013206","DOI":"10.1145\/800061.808749"},{"issue":"6","key":"1108_CR23","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1007\/s00453-021-00797-9","volume":"83","author":"Y Kawase","year":"2021","unstructured":"Kawase Y, Kimura K, Makino K, Sumita H (2021) Optimal matroid partitioning problems. Algorithmica 83(6):1653\u20131676","journal-title":"Algorithmica"},{"issue":"5","key":"1108_CR24","first-page":"359","volume":"39","author":"H Kellerer","year":"2011","unstructured":"Kellerer H, Kotov V (2011) A 3\/2-approximation algorithm for $$k_i$$-partitioning. Oper Res Lett 39(5):359\u2013362","journal-title":"Oper Res Lett"},{"issue":"7","key":"1108_CR25","doi-asserted-by":"publisher","first-page":"3025","DOI":"10.1007\/s00453-019-00566-9","volume":"81","author":"I Kones","year":"2019","unstructured":"Kones I, Levin A (2019) A unified framework for designing EPTAS for load balancing on parallel machines. Algorithmica 81(7):3025\u20133046","journal-title":"Algorithmica"},{"issue":"4","key":"1108_CR26","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra HW Jr (1983) Integer programming with a fixed number of variables. Math Oper Res 8(4):538\u2013548","journal-title":"Math Oper Res"},{"key":"1108_CR27","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.disopt.2017.12.001","volume":"28","author":"A Zhang","year":"2018","unstructured":"Zhang A, Chen Y, Chen L, Chen G (2018) On the NP-hardness of scheduling with time restrictions. Discrete Optim 28:54\u201362","journal-title":"Discrete Optim"},{"issue":"4","key":"1108_CR28","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/s11590-016-1038-0","volume":"11","author":"A Zhang","year":"2017","unstructured":"Zhang A, Ye F, Chen Y, Chen G (2017) Better permutations for the single-processor scheduling with time restrictions. Optim Lett 11(4):715\u2013724","journal-title":"Optim Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01108-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01108-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01108-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T23:13:43Z","timestamp":1710285223000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01108-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,22]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["1108"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01108-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,2,22]]},"assertion":[{"value":"17 January 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"10"}}