{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:59Z","timestamp":1740122459579,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T00:00:00Z","timestamp":1723766400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T00:00:00Z","timestamp":1723766400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Project of Yunnan Province Caiyun Postdoctoral","award":["No. 72"],"award-info":[{"award-number":["No. 72"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,9]]},"DOI":"10.1007\/s10878-024-01203-0","type":"journal-article","created":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T20:21:51Z","timestamp":1723839711000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The prize-collecting single machine scheduling with bounds and penalties"],"prefix":"10.1007","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8267-8848","authenticated-orcid":false,"given":"Guojun","family":"Hu","sequence":"first","affiliation":[]},{"given":"Pengxiang","family":"Pan","sequence":"additional","affiliation":[]},{"given":"Suding","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Ping","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Runtao","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,16]]},"reference":[{"key":"1203_CR1","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/j.cie.2017.06.026","volume":"111","author":"H Abedinnia","year":"2017","unstructured":"Abedinnia H, Clock CH, Grosse EH, Schneider M (2017) Machine scheduling problems in production: a tertiary study. Comput Ind Eng 111:403\u2013416. https:\/\/doi.org\/10.1016\/j.cie.2017.06.026","journal-title":"Comput Ind Eng"},{"issue":"1","key":"1203_CR2","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. https:\/\/doi.org\/10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","journal-title":"J Sched"},{"issue":"1","key":"1203_CR3","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 Discret Math 13(1):64\u201378. https:\/\/doi.org\/10.1137\/S0895480196300522","journal-title":"SIAM Discret Math"},{"key":"1203_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.dam.2022.02.005","volume":"313","author":"M Bold","year":"2022","unstructured":"Bold M, Goerigk M (2022) Investigating the recoverable robust single machine scheduling problem under interval uncertainty. Discret Appl Math 313:99\u2013114. https:\/\/doi.org\/10.1016\/j.dam.2022.02.005","journal-title":"Discret Appl Math"},{"key":"1203_CR5","doi-asserted-by":"publisher","unstructured":"de Weerdt M, Baart R, He L (2021) Single-machine scheduling with release times, deadlines, setup times, and rejection. Eur J Oper Res 291(2):629\u2013639. https:\/\/doi.org\/10.1016\/j.ejor.2020.09.042","DOI":"10.1016\/j.ejor.2020.09.042"},{"key":"1203_CR6","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1016\/j.tcs.2014.10.047","volume":"562","author":"J Fan","year":"2015","unstructured":"Fan J, Lu XW, Liu PH (2015) Integrated scheduling of production and delivery on a single machine with availability constraint. Theoret Comput Sci 562:581\u2013589. https:\/\/doi.org\/10.1016\/j.tcs.2014.10.047","journal-title":"Theoret Comput Sci"},{"key":"1203_CR7","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H Freeman and Company, New York City"},{"issue":"11","key":"1203_CR8","doi-asserted-by":"publisher","first-page":"3164","DOI":"10.1080\/00207543.2016.1266055","volume":"55","author":"E Gerstl","year":"2017","unstructured":"Gerstl E, Mosheiov G (2017) Single machine scheduling problems with generalised due-dates and job-rejection. Int J Prod Res 55(11):3164\u20133172. https:\/\/doi.org\/10.1080\/00207543.2016.1266055","journal-title":"Int J Prod Res"},{"issue":"9","key":"1203_CR9","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45(9):1563\u20131581. https:\/\/doi.org\/10.1002\/j.1538-7305.1966.tb01709.x","journal-title":"Bell Syst Tech J"},{"key":"1203_CR10","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 5:287\u2013326. https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","journal-title":"Ann Discret Math"},{"issue":"1","key":"1203_CR11","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s40305-021-00364-7","volume":"11","author":"JS Guo","year":"2023","unstructured":"Guo JS, Liu W, Hou B (2023) An approximation algorithm for P-prize-collecting set cover problem. J Oper Res Soc China 11(1):207\u2013217. https:\/\/doi.org\/10.1007\/s40305-021-00364-7","journal-title":"J Oper Res Soc China"},{"key":"1203_CR12","doi-asserted-by":"publisher","first-page":"114058","DOI":"10.1016\/j.tcs.2023.114058","volume":"972","author":"SN Guo","year":"2023","unstructured":"Guo SN, Ma R, Sun YF, Zhang XY, Zhang Y (2023) Online scheduling with deterioration and unexpected processor breakdown. Theor Comput Sci 972:114058. https:\/\/doi.org\/10.1016\/j.tcs.2023.114058","journal-title":"Theor Comput Sci"},{"issue":"1","key":"1203_CR13","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 JYT, Lee K, Pinedo ML (2016) Improved algorithms for single machine scheduling with release dates and rejections. 4OR 14(1):41\u201355. https:\/\/doi.org\/10.1007\/s10288-016-0303-5","journal-title":"4OR"},{"issue":"1","key":"1203_CR14","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. https:\/\/doi.org\/10.1145\/7531.7535","journal-title":"J ACM"},{"issue":"3","key":"1203_CR15","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1016\/j.ejor.2004.07.011","volume":"167","author":"H Hoogeveen","year":"2005","unstructured":"Hoogeveen H (2005) Multicriteria scheduling. Eur J Oper Res 167(3):592\u2013623. https:\/\/doi.org\/10.1016\/j.ejor.2004.07.011","journal-title":"Eur J Oper Res"},{"issue":"2","key":"1203_CR16","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 Discret Math 24(2):457\u2013485. https:\/\/doi.org\/10.1137\/090749451","journal-title":"SIAM Discret Math"},{"issue":"4","key":"1203_CR17","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. https:\/\/doi.org\/10.1287\/moor.2019.1036","journal-title":"Math Oper Res"},{"issue":"1","key":"1203_CR18","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.ejor.2012.12.028","volume":"228","author":"H Kellerer","year":"2013","unstructured":"Kellerer H, Strusevich V (2013) Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product. Eur J Oper Res 228(1):24\u201332. https:\/\/doi.org\/10.1016\/j.ejor.2012.12.028","journal-title":"Eur J Oper Res"},{"issue":"7","key":"1203_CR19","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. https:\/\/doi.org\/10.1007\/s00453-019-00566-9","journal-title":"Algorithmica"},{"issue":"4","key":"1203_CR20","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1007\/s11590-019-01389-x","volume":"14","author":"M Kong","year":"2020","unstructured":"Kong M, Liu XB, Pei J, Zhou ZP, Pardalos PM (2020) Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine. Optim Lett 14(4):857\u2013871. https:\/\/doi.org\/10.1007\/s11590-019-01389-x","journal-title":"Optim Lett"},{"issue":"1","key":"1203_CR21","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10288-017-0356-0","volume":"16","author":"WD Li","year":"2018","unstructured":"Li WD, Cui QN (2018) Vector scheduling with rejection on a single machine. 4OR 16(1):95\u2013104. https:\/\/doi.org\/10.1007\/s10288-017-0356-0","journal-title":"4OR"},{"issue":"part 2","key":"1203_CR22","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.tcs.2015.10.007","volume":"607","author":"WD Li","year":"2015","unstructured":"Li WD, Li JP, Zhang XJ, Chen ZB (2015) Penalty cost constrained identical parallel machine scheduling problem. Theor Comput Sci 607(part 2):181\u2013192. https:\/\/doi.org\/10.1016\/j.tcs.2015.10.007","journal-title":"Theor Comput Sci"},{"issue":"4","key":"1203_CR23","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s10878-023-01032-7","volume":"45","author":"XF Liu","year":"2023","unstructured":"Liu XF, Xiao M, Li WD, Zhu YY, Ma L (2023) Algorithms for single machine scheduling problem with release dates and submodular penalties. J Comb Optim 45(4):105. https:\/\/doi.org\/10.1007\/s10878-023-01032-7","journal-title":"J Comb Optim"},{"issue":"2","key":"1203_CR24","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.ijpe.2010.12.003","volume":"130","author":"LF Lu","year":"2011","unstructured":"Lu LF, Ng CT, Zhang LQ (2011) Optimal algorithms for single-machine scheduling with rejection to minimize the makespan. Int J Prod Econ 130(2):153\u2013158. https:\/\/doi.org\/10.1016\/j.ijpe.2010.12.003","journal-title":"Int J Prod Econ"},{"issue":"8","key":"1203_CR25","doi-asserted-by":"publisher","first-page":"1315","DOI":"10.1080\/01605682.2019.1621222","volume":"71","author":"B Mor","year":"2020","unstructured":"Mor B, Shapira D (2020) Scheduling with regular performance measures and optional job rejection on a single machine. J Oper Res Soc 71(8):1315\u20131325. https:\/\/doi.org\/10.1080\/01605682.2019.1621222","journal-title":"J Oper Res Soc"},{"issue":"3","key":"1203_CR26","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1016\/j.ejor.2014.09.028","volume":"241","author":"JW Ou","year":"2015","unstructured":"Ou JW, Zhong XL, Wang GQ (2015) An improved heuristic for parallel machine scheduling with rejection. Eur J Oper Res 241(3):653\u2013661. https:\/\/doi.org\/10.1016\/j.ejor.2014.09.028","journal-title":"Eur J Oper Res"},{"issue":"1","key":"1203_CR27","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(1):3\u201328. https:\/\/doi.org\/10.1007\/s10951-012-0303-z","journal-title":"J Sched"},{"key":"1203_CR28","doi-asserted-by":"publisher","unstructured":"Sun RQ, Deng B (2023) W-prize-collecting scheduling problem on a single machine. In: Proceedings of the 2022 6th international conference on computer science and artificial intelligence (CSAI \u201922). Association for computing machinery, New York, USA, pp 237\u2013242. https:\/\/doi.org\/10.1145\/3577530.3577568","DOI":"10.1145\/3577530.3577568"},{"issue":"3","key":"1203_CR29","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(3):975\u2013978. https:\/\/doi.org\/10.1016\/j.ejor.2008.10.006","journal-title":"Eur J Oper Res"},{"issue":"1","key":"1203_CR30","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s10878-021-00842-x","volume":"44","author":"HY Zheng","year":"2022","unstructured":"Zheng HY, Gao SG, Liu W, Wu WL, Du DZ, Hou B (2022) Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties. J Comb Optim 44(1):343\u2013353. https:\/\/doi.org\/10.1007\/s10878-021-00842-x","journal-title":"J Comb Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01203-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01203-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01203-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T20:52:42Z","timestamp":1727297562000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01203-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,16]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["1203"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01203-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,8,16]]},"assertion":[{"value":"1 August 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 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 known financial interests or personal relationships that might influence the work reported here.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"12"}}