{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T13:18:07Z","timestamp":1780060687494,"version":"3.54.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T00:00:00Z","timestamp":1728604800000},"content-version":"vor","delay-in-days":10,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009057","name":"University of Graz","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009057","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,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study scheduling problems with release times and rejection costs with the objective function of minimizing the maximum lateness. Our main result is a PTAS for the single machine problem with an upper bound on the rejection costs. This result is extended to parallel, identical machines. The corresponding problem of minimizing the rejection costs with an upper bound on the lateness is also examined. We show how to compute a PTAS for determining an approximation of the Pareto frontier on both objective functions on parallel, identical machines. Moreover, we present an FPTAS with strongly polynomial time for the maximum lateness problem without release times on identical machines when the number of machines is constant. Finally, we extend this FPTAS to the case of unrelated machines.<\/jats:p>","DOI":"10.1007\/s10878-024-01205-y","type":"journal-article","created":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T18:01:26Z","timestamp":1728669686000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Minimizing the maximum lateness for scheduling with release times and job rejection"],"prefix":"10.1007","volume":"48","author":[{"given":"Imed","family":"Kacem","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7618-3956","authenticated-orcid":false,"given":"Hans","family":"Kellerer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,10,11]]},"reference":[{"key":"1205_CR1","first-page":"15","volume":"10","author":"J Csirik","year":"1991","unstructured":"Csirik J, Frenk JBG, Labbe M, Zhang S (1991) Heuristics for the 0\u20131 min-knapsack problem. Acta Cybernet 10:15\u201320","journal-title":"Acta Cybernet"},{"key":"1205_CR2","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0166-218X(81)90008-1","volume":"3","author":"GV Gens","year":"1981","unstructured":"Gens GV, Levner EV (1981) Fast approximation algorithms for job sequencing with deadlines. Discrete Appl Math 3:313\u2013318","journal-title":"Discrete Appl Math"},{"key":"1205_CR3","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/moor.17.1.22","volume":"17","author":"LA Hall","year":"1992","unstructured":"Hall LA, Shmoys DB (1992) Jackson\u2019s rule for single machine scheduling: making a good heuristic better. Math Oper Res 17:22\u201335","journal-title":"Math Oper Res"},{"key":"1205_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s10288-016-0303-5","volume":"14","author":"C He","year":"2016","unstructured":"He C, Leung J, Lee K, Pinedo M (2016) Improved algorithms for single machine scheduling with release dates and rejections. 4OR 14:41\u201355","journal-title":"4OR"},{"key":"1205_CR5","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.ejor.2018.07.038","volume":"273","author":"D Hermelin","year":"2019","unstructured":"Hermelin D, Pinedo M, Shabtay D, Talmon N (2019) On the parameterized tractability of single machine scheduling with rejection. Eur J Oper Res 273:67\u201373","journal-title":"Eur J Oper Res"},{"key":"1205_CR6","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O Ibarra","year":"1975","unstructured":"Ibarra O, Kim CE (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J ACM 22:463\u2013468","journal-title":"J ACM"},{"key":"1205_CR7","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.tcs.2015.12.020","volume":"616","author":"D Jiang","year":"2016","unstructured":"Jiang D, Tan J (2016) Scheduling with job rejection and nonsimultaneous machine available time on unrelated parallel machines. Theoret Comput Sci 616:94\u201399","journal-title":"Theoret Comput Sci"},{"issue":"3","key":"1205_CR8","doi-asserted-by":"publisher","first-page":"970","DOI":"10.1007\/s10878-015-9924-4","volume":"32","author":"I Kacem","year":"2016","unstructured":"Kacem I, Kellerer H, Seifaddini M (2016) Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval. J Comb Optim 32(3):970\u2013981","journal-title":"J Comb Optim"},{"issue":"12","key":"1205_CR9","doi-asserted-by":"publisher","first-page":"3825","DOI":"10.1007\/s00453-018-0417-6","volume":"80","author":"I Kacem","year":"2018","unstructured":"Kacem I, Kellerer H (2018) Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints. Algorithmica 80(12):3825\u20133843","journal-title":"Algorithmica"},{"issue":"3","key":"1205_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s10951-009-0146-4","volume":"14","author":"I Kacem","year":"2011","unstructured":"Kacem I, Kellerer H (2011) Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates. J Sched 14(3):257\u2013265","journal-title":"J Sched"},{"key":"1205_CR11","first-page":"185","volume-title":"Handbook of scheduling: algorithms, models, and performance analysis","author":"H Kellerer","year":"2004","unstructured":"Kellerer H (2004) Minimizing the maximum lateness. In: Leung JY-T (ed) Handbook of scheduling: algorithms, models, and performance analysis, vol 10. Chapman and Hall\/CRC, pp 185\u2013196"},{"key":"1205_CR12","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/j.tcs.2006.08.030","volume":"369","author":"H Kellerer","year":"2006","unstructured":"Kellerer H, Strusevich VA (2006) A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date. Theoret Comput Sci 369:230\u2013238","journal-title":"Theoret Comput Sci"},{"key":"1205_CR13","first-page":"205","volume":"22","author":"H Kise","year":"1979","unstructured":"Kise H, Ibaraki T, Mine H (1979) Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times. J Oper Res Soc Jpn 22:205\u2013224","journal-title":"J Oper Res Soc Jpn"},{"key":"1205_CR14","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/0377-2217(77)90070-4","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra JK, Rinnooy Kan AHJ, Brucker P (1977) Complexity of machine scheduling problems. Ann Oper Res 1:342\u2013362","journal-title":"Ann Oper Res"},{"key":"1205_CR15","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.tcs.2015.10.007","volume":"607","author":"W Li","year":"2015","unstructured":"Li W, Li J, Zhang X, Chen Z (2015) Penalty cost constrained identical parallel machine scheduling problem. Theoret Comput Sci 607:181\u2013192","journal-title":"Theoret Comput Sci"},{"key":"1205_CR16","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1023\/A:1026272526225","volume":"6","author":"M Mastrolilli","year":"2003","unstructured":"Mastrolilli M (2003) Efficient approximation schemes for scheduling problems with release dates and delivery times. J Sched 6:521\u2013531","journal-title":"J Sched"},{"key":"1205_CR17","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-014-0830-9","volume":"154","author":"M Mnich","year":"2015","unstructured":"Mnich M, Wiese A (2015) Scheduling and fixed-parameter tractability. Math Program B 154:533\u2013562","journal-title":"Math Program B"},{"key":"1205_CR18","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0166-218X(92)00110-8","volume":"48","author":"E Nowicki","year":"1994","unstructured":"Nowicki E, Smutnicki C (1994) An approximation algorithm for single-machine scheduling with release times and delivery times. Discret Appl Math 48:69\u201379","journal-title":"Discret Appl Math"},{"key":"1205_CR19","unstructured":"Papadimitriou CH, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. In: Proceedings of the 41st annual symposium on foundations of computer science (FOCS\u201900), pp 86\u201392"},{"key":"1205_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-05921-6","volume-title":"Scheduling","author":"M Pinedo","year":"2022","unstructured":"Pinedo M (2022) Scheduling, 6th edn. Springer, New York","edition":"6"},{"key":"1205_CR21","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1287\/opre.28.6.1436","volume":"28","author":"CN Potts","year":"1980","unstructured":"Potts CN (1980) Analysis of a heuristic for one machine sequencing with release dates and delivery times. Oper Res 28:1436\u20131441","journal-title":"Oper Res"},{"key":"1205_CR22","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.tcs.2007.03.006","volume":"282","author":"K Pruhs","year":"2007","unstructured":"Pruhs K, Woeginger G (2007) Approximation schemes for a class of subset selection problems. Theoret Comput Sci 282:151\u2013156","journal-title":"Theoret Comput Sci"},{"key":"1205_CR23","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10951-012-0303-z","volume":"16","author":"D Shabtay","year":"2013","unstructured":"Shabtay D, Gaspar N, Kaspi M (2013) A survey on offline scheduling with rejection. J Sched 16:3\u201328","journal-title":"J Sched"},{"key":"1205_CR24","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0166-218X(98)00059-6","volume":"87","author":"A Tamir","year":"1998","unstructured":"Tamir A (1998) Fully polynomial approximation schemes for locating a tree-shaped facility: a generalization of the knapsack problem. Discret Appl Math 87:229\u2013243","journal-title":"Discret Appl Math"},{"key":"1205_CR25","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1016\/j.ejor.2008.10.006","volume":"198","author":"LQ Zhang","year":"2009","unstructured":"Zhang LQ, Lu LF, Yuan JJ (2009) Single machine scheduling with release dates and rejection. Eur J Oper Res 198:975\u2013978","journal-title":"Eur J Oper Res"},{"key":"1205_CR26","doi-asserted-by":"publisher","first-page":"1877","DOI":"10.1016\/j.tcs.2010.02.006","volume":"411","author":"LQ Zhang","year":"2010","unstructured":"Zhang LQ, Lu LF, Yuan JJ (2010) Single-machine scheduling under the job rejection constraint. Theoret Comput Sci 411:1877\u20131882","journal-title":"Theoret Comput Sci"},{"key":"1205_CR27","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10288-016-0339-6","volume":"15","author":"X Zhong","year":"2017","unstructured":"Zhong X, Ou J (2017) Improved approximation algorithms for parallel machine scheduling with release dates and job rejection. 4OR 15:387\u2013406","journal-title":"4OR"},{"key":"1205_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.05.033","volume":"690","author":"X Zhong","year":"2017","unstructured":"Zhong X, Ou J (2017) Parallel machine scheduling with restricted job rejection. Theoret Comput Sci 690:1\u201311","journal-title":"Theoret Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01205-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01205-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-01205-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T19:10:46Z","timestamp":1729192246000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01205-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1205"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01205-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"1 August 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 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 declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"23"}}