{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T22:44:40Z","timestamp":1777502680949,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,4,30]],"date-time":"2023-04-30T00:00:00Z","timestamp":1682812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,30]],"date-time":"2023-04-30T00:00:00Z","timestamp":1682812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071417"],"award-info":[{"award-number":["12071417"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2023,5]]},"DOI":"10.1007\/s10878-023-01032-7","type":"journal-article","created":{"date-parts":[[2023,4,30]],"date-time":"2023-04-30T12:01:16Z","timestamp":1682856076000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Algorithms for single machine scheduling problem with release dates and submodular penalties"],"prefix":"10.1007","volume":"45","author":[{"given":"Xiaofei","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Man","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaoyu","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6024-3854","authenticated-orcid":false,"given":"Lei","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,30]]},"reference":[{"issue":"2","key":"1032_CR1","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1137\/S0097539797324874","volume":"29","author":"S Albers","year":"1999","unstructured":"Albers S (1999) Better bounds for online scheduling. SIAM J Comput 29(2):459\u2013473","journal-title":"SIAM J Comput"},{"issue":"1","key":"1032_CR2","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1137\/S0895480196300522","volume":"13","author":"Y Bartal","year":"2000","unstructured":"Bartal Y, Leonardi S, Marchetti-Spaccamela A, Sgall J, Stougie L (2000) Multiprocessor scheduling with rejection. SIAM J Discret Math 13(1):64\u201378","journal-title":"SIAM J Discret Math"},{"issue":"6","key":"1032_CR3","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2","volume":"3","author":"R Fleischer","year":"2000","unstructured":"Fleischer R, Wahl M (2000) Online scheduling revisited. J Sched 3(6):343\u2013353","journal-title":"J Sched"},{"key":"1032_CR4","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R Graham","year":"1966","unstructured":"Graham R (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45:1563\u20131581","journal-title":"Bell Syst Tech J"},{"key":"1032_CR5","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R Graham","year":"1969","unstructured":"Graham R (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17:416\u2013429","journal-title":"SIAM J Appl Math"},{"key":"1032_CR6","doi-asserted-by":"crossref","unstructured":"He C, Leung JYT, Lee K, Pinedo ML (2016) Improved algorithms for single machine scheduling with release dates and rejections. OR 14: 41\u201355","DOI":"10.1007\/s10288-016-0303-5"},{"key":"1032_CR7","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D Hochbaum","year":"1987","unstructured":"Hochbaum D, Shmoys D (1987) Using dual approximation algorithms for scheduling problems: theoretical and practical results. J ACM 34:144\u2013162","journal-title":"J ACM"},{"key":"1032_CR8","first-page":"1230","volume-title":"the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA 2009","author":"S Iwata","year":"2009","unstructured":"Iwata S, Orlin JB (2009) A simple combinatorial algorithm for submodular function minimization. In: Mathieu C (ed) the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA 2009. SIAM, USA, pp 1230\u20131237"},{"issue":"2","key":"1032_CR9","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1287\/moor.26.2.324.10559","volume":"26","author":"K Jansen","year":"2001","unstructured":"Jansen K, Porkolab L (2001) Improved approximation schemes for scheduling unrelated parallel machines. Math Oper Res 26(2):324\u2013338","journal-title":"Math Oper Res"},{"issue":"4","key":"1032_CR10","doi-asserted-by":"publisher","first-page":"1371","DOI":"10.1287\/moor.2019.1036","volume":"45","author":"K Jansen","year":"2020","unstructured":"Jansen K, Klein KM, Verschae J (2020) Closing the gap for makespan scheduling via sparsification techniques. Math Oper Res 45(4):1371\u20131392","journal-title":"Math Oper Res"},{"key":"1032_CR11","doi-asserted-by":"crossref","unstructured":"Lawler EL (1973) Optimal sequencing a single machine subject to precedence constraints. Manage Sci","DOI":"10.1287\/mnsc.19.5.544"},{"issue":"05","key":"1032_CR12","doi-asserted-by":"publisher","first-page":"1250029","DOI":"10.1142\/S0217595912500297","volume":"29","author":"W Li","year":"2012","unstructured":"Li W, Li J, Zhang T (2012) Two approximation schemes for scheduling on parallel machines under a grade of service provision. Asia-Pacific J Oper Res 29(05):1250029","journal-title":"Asia-Pacific J Oper Res"},{"key":"1032_CR13","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"},{"issue":"1","key":"1032_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.3390\/math8010133","volume":"8","author":"X Liu","year":"2020","unstructured":"Liu X, Li W (2020) Approximation algorithm for the single machine scheduling problem with release dates and submodular rejection penalty. Mathematics 8(1):133","journal-title":"Mathematics"},{"key":"1032_CR15","doi-asserted-by":"publisher","first-page":"2165","DOI":"10.1007\/s11590-021-01724-1","volume":"15","author":"X Liu","year":"2021","unstructured":"Liu X, Li W (2021) Approximation algorithms for the multiprocessor scheduling with submodular penalties. Optim Lett 15:2165\u20132180","journal-title":"Optim Lett"},{"issue":"2","key":"1032_CR16","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.ijpe.2010.12.003","volume":"130","author":"L Lu","year":"2011","unstructured":"Lu L, Ng C, Zhang L (2011) Optimal algorithms for single-machine scheduling with rejection to minimize the makespan. Int J Prod Econ 130(2):153\u2013158","journal-title":"Int J Prod Econ"},{"issue":"3","key":"1032_CR17","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1016\/j.ejor.2014.09.028","volume":"241","author":"J Ou","year":"2015","unstructured":"Ou J, Zhong X, Wang G (2015) An improved heuristic for parallel machine scheduling with rejection. Eur J Oper Res 241(3):653\u2013661","journal-title":"Eur J Oper Res"},{"key":"1032_CR18","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/j.ipl.2016.02.008","volume":"116","author":"J Ou","year":"2016","unstructured":"Ou J, Zhong X, Li CL (2016) Faster algorithms for single machine scheduling with release dates and rejection. Inf Process Lett 116:503\u2013507","journal-title":"Inf Process Lett"},{"key":"1032_CR19","unstructured":"Rudin JF (2001) Improved bounds for the on-line scheduling problem. PhD thesis, The University of Texas at Dallas"},{"key":"1032_CR20","doi-asserted-by":"publisher","first-page":"61","DOI":"10.3390\/math10010061","volume":"10","author":"W Wang","year":"2022","unstructured":"Wang W, Liu X (2022) A Combinatorial 2-approximation algorithm for the parallel-machine scheduling with release times and submodular penalties. Mathematics 10:61","journal-title":"Mathematics"},{"issue":"3","key":"1032_CR21","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1016\/j.ejor.2008.10.006","volume":"198","author":"L Zhang","year":"2009","unstructured":"Zhang L, Lu L, Yuan J (2009) Single machine scheduling with release dates and rejection. Eur J Oper Res 198(3):975\u2013978","journal-title":"Eur J Oper Res"},{"key":"1032_CR22","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/s10878-016-0044-6","volume":"35","author":"X Zhang","year":"2018","unstructured":"Zhang X, Xu D, Du D, Wu C (2018) Approximation algorithms for precedence-constrained identical machine scheduling with rejection. J Comb Optim 35:318\u2013330","journal-title":"J Comb Optim"},{"key":"1032_CR23","doi-asserted-by":"crossref","unstructured":"Zhang L, Lu L (2016) Parallel-machine scheduling with release dates and rejection. 4OR 14, 165\u2013172","DOI":"10.1007\/s10288-016-0304-4"},{"key":"1032_CR24","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s10878-021-00842-x","volume":"44","author":"H Zheng","year":"2022","unstructured":"Zheng H, Gao S, Liu W, Wu W, Du D (2022) Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties. J Comb Optim 44:343\u2013353","journal-title":"J Comb Optim"},{"key":"1032_CR25","doi-asserted-by":"publisher","first-page":"934","DOI":"10.1007\/s10878-016-0016-x","volume":"33","author":"X Zhong","year":"2017","unstructured":"Zhong X, Pan Z, Jiang D (2017) Scheduling with release times and rejection on two parallel machines. J Comb Optim 33:934\u2013944","journal-title":"J Comb Optim"},{"key":"1032_CR26","doi-asserted-by":"crossref","unstructured":"Zhong X, Ou J (2017) Improved approximation algorithms for parallel machine scheduling with release dates and job rejection. 4OR 15, 387\u2013406","DOI":"10.1007\/s10288-016-0339-6"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01032-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-023-01032-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01032-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,27]],"date-time":"2023-05-27T03:41:55Z","timestamp":1685158915000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-023-01032-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,30]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1032"],"URL":"https:\/\/doi.org\/10.1007\/s10878-023-01032-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,30]]},"assertion":[{"value":"4 April 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2023","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 known competing financial interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interest"}}],"article-number":"105"}}