{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T04:16:25Z","timestamp":1752984985314},"reference-count":21,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2023,4,28]],"date-time":"2023-04-28T00:00:00Z","timestamp":1682640000000},"content-version":"vor","delay-in-days":58,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,1,10]]},"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:p>This paper studies the bicriteria problem of scheduling <jats:italic>n<\/jats:italic> jobs on a parallel-batching machine to minimize maximum cost and makespan simultaneously. A parallel-batching machine is a machine that can handle up to <jats:italic>b<\/jats:italic> jobs in a batch. The jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the largest processing time of jobs in the batch. We consider the unbounded case. For the above bicriteria scheduling problem, we present an <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>)-time algorithm, which improved the best known <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>4<\/jats:sup>)-time algorithm, and the time complexity is the same as the special case in which maximum cost is maximum lateness. Meanwhile, our algorithm can also solve the single-criterion unbounded parallel-batching scheduling problem to minimize maximum cost in <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>) time, which improved the best known <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>4<\/jats:sup>)-time algorithm.<\/jats:p>","DOI":"10.1051\/ro\/2023003","type":"journal-article","created":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T09:06:16Z","timestamp":1673600776000},"page":"731-741","source":"Crossref","is-referenced-by-count":2,"title":["An improved algorithm on unbounded parallel-batching scheduling to minimize maximum cost and makespan"],"prefix":"10.1051","volume":"57","author":[{"given":"Cheng","family":"He","sequence":"first","affiliation":[]},{"given":"Jing","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Jinglei","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Junling","family":"Wang","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2023,4,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1287\/opre.1030.0092","volume":"52","author":"Agnetis","year":"2004","journal-title":"Oper. Res."},{"key":"R2","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1022231419049","volume":"6","author":"Baker","year":"2003","journal-title":"J. Sched."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Brucker P., Scheduling Algorithms. 3rd edition, Springer, Berlin (2001).","DOI":"10.1007\/978-3-662-04550-3"},{"key":"R4","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R","volume":"1","author":"Brucker","year":"1998","journal-title":"J. Sched."},{"key":"R5","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s40305-019-00258-9","volume":"8","author":"Feng","year":"2020","journal-title":"J. Oper. Res. Soc. China"},{"key":"R6","doi-asserted-by":"crossref","first-page":"7071","DOI":"10.1016\/j.apm.2013.03.013","volume":"37","author":"Feng","year":"2013","journal-title":"Appl. Math. Model."},{"key":"R7","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1016\/j.ipl.2015.07.002","volume":"115","author":"Geng","year":"2015","journal-title":"Inf. Process. Lett."},{"key":"R8","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Discrete Math."},{"key":"R9","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1051\/ro\/2017089","volume":"52","author":"He","year":"2018","journal-title":"RAIRO: OR"},{"key":"R10","doi-asserted-by":"crossref","first-page":"3701","DOI":"10.1051\/ro\/2021175","volume":"55","author":"He","year":"2021","journal-title":"RAIRO: OR"},{"key":"R11","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1051\/ro\/2020144","volume":"55","author":"He","year":"2021","journal-title":"RAIRO: OR"},{"key":"R12","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.tcs.2007.04.034","volume":"381","author":"He","year":"2007","journal-title":"Theor. Comput. Sci."},{"key":"R13","first-page":"369","volume":"33","author":"He","year":"2008","journal-title":"Found. Comput. Decis. Sci."},{"key":"R14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0217595914500250","volume":"31","author":"He","year":"2014","journal-title":"Asia-Pac. J. Oper. Res."},{"key":"R15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ro\/2012023","volume":"47","author":"He","year":"2013","journal-title":"RAIRO: OR"},{"key":"R16","doi-asserted-by":"crossref","first-page":"100698","DOI":"10.1016\/j.disopt.2022.100698","volume":"45","author":"He","year":"2022","journal-title":"Discrete Optim."},{"key":"R17","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1006\/jagm.1996.0051","volume":"21","author":"Hoogeveen","year":"1996","journal-title":"J. Algorithms"},{"key":"R18","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1016\/j.ejor.2004.07.011","volume":"167","author":"Hoogeveen","year":"2005","journal-title":"Eur. J. Oper. Res."},{"key":"R19","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0167-6377(95)00023-D","volume":"17","author":"Hoogeveen","year":"1995","journal-title":"Oper. Res. Lett."},{"key":"R20","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s11590-016-1003-y","volume":"11","author":"Lazarev","year":"2017","journal-title":"Optim. Lett."},{"key":"R21","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1051\/ro:2001109","volume":"35","author":"T\u2019kindt","year":"2001","journal-title":"RAIRO: OR"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023003\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,28]],"date-time":"2023-04-28T08:16:16Z","timestamp":1682669776000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3]]},"references-count":21,"journal-issue":{"issue":"2"},"alternative-id":["ro220386"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023003","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3]]}}}