{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T01:03:23Z","timestamp":1776128603314,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T00:00:00Z","timestamp":1740009600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T00:00:00Z","timestamp":1740009600000},"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":["12271491"],"award-info":[{"award-number":["12271491"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071442"],"award-info":[{"award-number":["12071442"]}],"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":[[2025,3]]},"DOI":"10.1007\/s10878-025-01267-6","type":"journal-article","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T19:17:46Z","timestamp":1740079066000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Multiple identical serial-batch machines scheduling with release dates and submodular rejection penalties"],"prefix":"10.1007","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1443-9554","authenticated-orcid":false,"given":"Zhichao","family":"Geng","sequence":"first","affiliation":[]},{"given":"Lingfa","family":"Lu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,20]]},"reference":[{"key":"1267_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01607-w","author":"A Atamt\u00fcrk","year":"2021","unstructured":"Atamt\u00fcrk A, Narayanan V (2021) Submodular function minimization and polarity. Math Program. https:\/\/doi.org\/10.1007\/s10107-020-01607-w","journal-title":"Math Program"},{"key":"1267_CR2","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s001860000088","volume":"52","author":"P Baptiste","year":"2000","unstructured":"Baptiste P (2000) Batching identical jobs. Math Method Oper Res 52:355\u2013367","journal-title":"Math Method Oper Res"},{"key":"1267_CR3","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1137\/S0895480196300522","volume":"13","author":"Y Bartal","year":"2000","unstructured":"Bartal Y, Leonardi S, Spaccamela A, Sgall J, Stougie L (2000) Multi-processor scheduling with rejection. SIAM J Discret Math 13:64\u201378","journal-title":"SIAM J Discret Math"},{"key":"1267_CR4","doi-asserted-by":"publisher","first-page":"1044","DOI":"10.1007\/s10878-020-00649-2","volume":"40","author":"R Chen","year":"2020","unstructured":"Chen R, Li S (2020) Minimizing maximum delivery completion time for order scheduling with rejection. J Comb Optim 40:1044\u20131064","journal-title":"J Comb Optim"},{"key":"1267_CR5","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF02248589","volume":"26","author":"E Coffman","year":"1990","unstructured":"Coffman E, Yannakakis J, Magazine M, Santos C (1990) Batching sizing and job sequencing on a single machine. Ann Oper Res 26:135\u2013147","journal-title":"Ann Oper Res"},{"key":"1267_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-021-00719-z","author":"M Cui","year":"2021","unstructured":"Cui M, Xu D, Guo L, Wu D (2021) Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint. J Comb Optim. https:\/\/doi.org\/10.1007\/s10878-021-00719-z","journal-title":"J Comb Optim"},{"key":"1267_CR7","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0166-218X(02)00458-4","volume":"131","author":"L Fleicher","year":"2003","unstructured":"Fleicher L, Iwata S (2003) A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Appl Math 131:311\u2013322","journal-title":"Discrete Appl Math"},{"key":"1267_CR8","volume-title":"Submodular functions and optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige S (2005) Submodular functions and optimization, 2nd edn. Elsevier, Amsterdam","edition":"2"},{"key":"1267_CR9","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"3","author":"M Garey","year":"1978","unstructured":"Garey M, Johnson D (1978) Strong NP-completeness results: motivation, examples, and implications. J Assoc Comput Mach 3:499\u2013508","journal-title":"J Assoc Comput Mach"},{"key":"1267_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cam.2017.10.002","volume":"332","author":"Z Geng","year":"2018","unstructured":"Geng Z, Yuan JJ, Yuan JL (2018) Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost. Appl Math Comput 332:1\u201318","journal-title":"Appl Math Comput"},{"key":"1267_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Springer, Berlin"},{"key":"1267_CR12","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.cie.2011.08.014","volume":"62","author":"A Hamidinia","year":"2012","unstructured":"Hamidinia A, Khakabimamaghani S, Mazdeh M, Jafari M (2012) A genetic algorithm for minimizing total tardiness\/earliness of weighted jobs in a batched delivery system. Comput Ind Eng 62:29\u201338","journal-title":"Comput Ind Eng"},{"key":"1267_CR13","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.disopt.2015.02.001","volume":"16","author":"C He","year":"2015","unstructured":"He C, Lin H, Lin Y (2015) Bounded serial-batching scheduling for minimizing maximum lateness and makespan. Discrete Optim 16:70\u201375","journal-title":"Discrete Optim"},{"key":"1267_CR14","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/s10951-020-00656-5","volume":"23","author":"C He","year":"2020","unstructured":"He C, Xu C, Lin H (2020) Serial-batching scheduling with two agents to minimize makespan and maximum cost. J Sched 23:609\u2013617","journal-title":"J Sched"},{"key":"1267_CR15","doi-asserted-by":"crossref","unstructured":"Lee Y, Sidford A, Wong S (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp 1049\u20131065","DOI":"10.1109\/FOCS.2015.68"},{"key":"1267_CR16","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1016\/j.ipl.2014.06.009","volume":"114","author":"S Li","year":"2014","unstructured":"Li S, Zhang Y (2014) Serial batch scheduling on uniform parallel machines to minimize total completion time. Inform Process Lett 114:692\u2013695","journal-title":"Inform Process Lett"},{"key":"1267_CR17","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/s10878-020-00642-9","volume":"40","author":"P Liu","year":"2020","unstructured":"Liu P, Lu X (2020) New approximation algorithms for machine scheduling with rejection on single and parallel machine. J Comb Optim 40:929\u2013952","journal-title":"J Comb Optim"},{"key":"1267_CR18","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical programming the state of the art","author":"L Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz L (1983) Submodular functions and convexity. In: Bachm A, Grtschel M, Korte B (eds) Mathematical programming the state of the art. Springer, Berlin, pp 235\u2013237"},{"key":"1267_CR19","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:653\u2013661","journal-title":"Eur J Oper Res"},{"key":"1267_CR20","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 C (2016) Faster algorithms for single machine scheduling with release dates and rejection. Inform Process Lett 116:503\u2013507","journal-title":"Inform Process Lett"},{"key":"1267_CR21","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105514","volume":"137","author":"O Ozturk","year":"2022","unstructured":"Ozturk O (2022) When serial batch scheduling involves parallel batching decisions: a branch and price scheme. Comput Oper Res 137:105514","journal-title":"Comput Oper Res"},{"key":"1267_CR22","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.omega.2017.12.003","volume":"82","author":"J Pei","year":"2019","unstructured":"Pei J, Liu X, Fan W, Pardalos P, Lu S (2019) A hybrid ba-vns algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers. Omega 82:55\u201369","journal-title":"Omega"},{"key":"1267_CR23","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J Combin Theory B 80:346\u2013355","journal-title":"J Combin Theory B"},{"key":"1267_CR24","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.ejor.2013.08.013","volume":"233","author":"D Shabtay","year":"2014","unstructured":"Shabtay D (2014) The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost. Eur J Oper Res 233:64\u201374","journal-title":"Eur J Oper Res"},{"key":"1267_CR25","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 off-line scheduling with rejection. J Sched 16:3\u201328","journal-title":"J Sched"},{"key":"1267_CR26","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.ijpe.2017.10.015","volume":"195","author":"O Shahvari","year":"2018","unstructured":"Shahvari O, Logendran R (2018) A comparison of two stage-based hybrid algorithms for a batch scheduling problem in hybrid flow shop with learning effect. Int J Prod Econ 195:227\u2013248","journal-title":"Int J Prod Econ"},{"key":"1267_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-021-00753-x","author":"J Sun","year":"2021","unstructured":"Sun J, Sheng H, Sun Y, Du D, Zhang X (2021) Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty. J Comb Optim. https:\/\/doi.org\/10.1007\/s10878-021-00753-x","journal-title":"J Comb Optim"},{"key":"1267_CR28","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1287\/opre.43.4.692","volume":"43","author":"S Webster","year":"1995","unstructured":"Webster S, Baker K (1995) Scheduling groups of jobs on a single machine. Oper Res 43:692\u2013703","journal-title":"Oper Res"},{"key":"1267_CR29","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2016.04.005","volume":"630","author":"D Xu","year":"2016","unstructured":"Xu D, Wang F, Du D, Wu C (2016) Approximation algorithms for submodular vertex cover problems with linear\/submodular penalties using primal-dual technique. Theor Comput Sci 630:117\u2013125","journal-title":"Theor Comput Sci"},{"key":"1267_CR30","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s10288-016-0304-4","volume":"14","author":"L Zhang","year":"2016","unstructured":"Zhang L, Lu L (2016) Parallel-machine scheduling with release dates and rejection. 4OR Q J Oper Res 14:165\u2013172","journal-title":"4OR Q J Oper Res"},{"key":"1267_CR31","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:975\u2013978","journal-title":"Eur J Oper Res"},{"key":"1267_CR32","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":"1267_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-021-00842-x","author":"H Zheng","year":"2022","unstructured":"Zheng H, Gao S, Liu W, Wu W, Du D, Hou B (2022) Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties. J Comb Optim. https:\/\/doi.org\/10.1007\/s10878-021-00842-x","journal-title":"J Comb Optim"},{"key":"1267_CR34","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 Q J Oper Res 15:387\u2013406","journal-title":"4OR Q J Oper Res"},{"key":"1267_CR35","first-page":"211","volume":"16","author":"J Zou","year":"2015","unstructured":"Zou J, Miao C (2015) The single machine serial batch scheduling problems with rejection. Oper Res-Ger 16:211\u2013221","journal-title":"Oper Res-Ger"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01267-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01267-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01267-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T21:07:04Z","timestamp":1741900024000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01267-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,20]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["1267"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01267-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,20]]},"assertion":[{"value":"3 February 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2025","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 relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"32"}}