{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T18:14:59Z","timestamp":1757614499915,"version":"3.44.0"},"reference-count":28,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T00:00:00Z","timestamp":1757030400000},"content-version":"vor","delay-in-days":66,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2020MA030"],"award-info":[{"award-number":["ZR2020MA030"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2025,7,2]]},"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>This paper addresses a single-machine parallel batch scheduling problem involving <jats:italic>n<\/jats:italic> jobs managed by two agents. The goal is to achieve simultaneous minimization of the makespan for agent <jats:italic>A<\/jats:italic> and the maximum cost for agent <jats:italic>B<\/jats:italic>. Both agents operate independently, with agents <jats:italic>A<\/jats:italic> and <jats:italic>B<\/jats:italic> handling <jats:italic>n<jats:sub>A<\/jats:sub><\/jats:italic> and <jats:italic>n<jats:sub>B<\/jats:sub><\/jats:italic> jobs respectively. The parallel batch machine has the capability to concurrently handle a maximum of <jats:italic>b<\/jats:italic> jobs grouped together as a batch. The processing time for the entire batch is determined by the longest processing time among the individual jobs assigned to that particular batch. For the unbounded version (<jats:italic>b<\/jats:italic> \u2265 <jats:italic>n<\/jats:italic>) with either incompatible or compatible job groups, an <jats:italic>O<\/jats:italic>(<jats:italic>n<jats:sub>A<\/jats:sub><\/jats:italic> + <jats:italic>n<jats:sub>B<\/jats:sub><\/jats:italic><jats:sup>4<\/jats:sup>)-time algorithm is presented. For the bounded version (<jats:italic>b &lt; n<\/jats:italic>) with incompatible job groups, when all jobs of agent <jats:italic>B<\/jats:italic> share identical processing times, an <jats:italic>O<\/jats:italic>(<jats:italic>n<jats:sub>A<\/jats:sub><\/jats:italic> log <jats:italic>n<jats:sub>A<\/jats:sub><\/jats:italic> + <jats:italic>n<jats:sub>B<\/jats:sub><\/jats:italic><jats:sup>2<\/jats:sup>)-time algorithm is presented. For the bounded version with compatible job groups, when all jobs of agent <jats:italic>B<\/jats:italic> share identical processing times, an <jats:italic>O<\/jats:italic>(<jats:italic>n<jats:sub>A<\/jats:sub><\/jats:italic> log <jats:italic>n<jats:sub>A<\/jats:sub><\/jats:italic> + <jats:italic>n<jats:sub>A<\/jats:sub>n<jats:sub>B<\/jats:sub><\/jats:italic> + <jats:italic>n<jats:sub>B<\/jats:sub><\/jats:italic><jats:sup>3<\/jats:sup>)-time algorithm is presented. The algorithms for the unbounded version with incompatible job groups and the bounded version with compatible job groups generalize or improve the previously known algorithms, while the algorithms for the unbounded version with compatible job groups and the bounded version with incompatible job groups are the first polynomial time algorithms for them.<\/jats:p>","DOI":"10.1051\/ro\/2025092","type":"journal-article","created":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T14:45:37Z","timestamp":1751553937000},"page":"2219-2240","source":"Crossref","is-referenced-by-count":0,"title":["Optimizing two-agent single-machine parallel batch scheduling: achieving pareto efficiency in makespan and maximum cost objectives"],"prefix":"10.1051","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9017-7827","authenticated-orcid":false,"given":"Shuguang","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-9324-8923","authenticated-orcid":false,"given":"Jing","family":"Wei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-6431-2330","authenticated-orcid":false,"given":"Yong","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0618-8326","authenticated-orcid":false,"given":"Armand Jean","family":"Noel Irangabiye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2025,9,5]]},"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","unstructured":"Agnetis A., Billaut J.-C., Gawiejnowicz S., Pacciarelli D. and Soukhal A., Multiagent Scheduling: Models and Algorithms. Springer, Berlin Heidelberg (2014).","DOI":"10.1007\/978-3-642-41880-8"},{"key":"R3","unstructured":"Aho A.V. and Hopcroft J.E., The Design and Analysis of Computer Algorithms. Pearson Education, India (1974)."},{"key":"R4","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1022231419049","volume":"6","author":"Baker","year":"2003","journal-title":"J. Sched."},{"key":"R5","unstructured":"Brucker P., Scheduling Algorithms, 5th edition. Springer, Berlin Heidelberg (2007)."},{"key":"R6","unstructured":"Brucker P. and Knust S., Complexity Results for Scheduling Problems (2009)."},{"key":"R7","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":"R8","doi-asserted-by":"crossref","first-page":"6072","DOI":"10.1080\/00207543.2021.1979680","volume":"60","author":"Dusadeerungsikul","year":"2022","journal-title":"Int. J. Prod. Res."},{"key":"R9","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":"R10","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":"R11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2021.06.012","volume":"298","author":"Fowler","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"R12","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.ejor.2018.07.040","volume":"273","author":"Gao","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Graham R.L., Lawler E.L., Lenstra J.K. and Rinnooy Kan A.H.G.. Optimization and approximation in deterministic sequencing and scheduling: a survey, in Annals of Discrete Mathematics. Vol. 5. Elsevier, B.C. Canada (1979) 287\u2013326.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"R14","first-page":"109","volume":"22","author":"He","year":"2018","journal-title":"Oper. Res. Trans. China"},{"key":"R15","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":"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":"688","DOI":"10.1016\/j.ejor.2022.01.018","volume":"302","author":"He","year":"2022","journal-title":"Eur. J. Oper. Res."},{"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":"694","DOI":"10.1007\/s11750-020-00588-5","volume":"29","author":"Kacem","year":"2021","journal-title":"Top"},{"key":"R20","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1287\/mnsc.19.5.544","volume":"19","author":"Lawler","year":"1973","journal-title":"Manag. Sci."},{"key":"R21","doi-asserted-by":"crossref","first-page":"764","DOI":"10.1287\/opre.40.4.764","volume":"40","author":"Lee","year":"1992","journal-title":"Oper. Res."},{"key":"R22","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1007\/s10951-011-0253-x","volume":"15","author":"Li","year":"2012","journal-title":"J. Sched."},{"key":"R23","doi-asserted-by":"crossref","first-page":"106343","DOI":"10.1016\/j.ipl.2022.106343","volume":"180","author":"Li","year":"2023","journal-title":"Inf. Process. Lett."},{"key":"R24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2013.09.017","volume":"235","author":"Perez-Gonzalez","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"R25","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1016\/j.apm.2009.04.007","volume":"34","author":"Sabouni","year":"2010","journal-title":"Appl. Math. Model."},{"key":"R26","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1080\/00207543.2019.1699671","volume":"59","author":"Shi","year":"2021","journal-title":"Int. J. Prod. Res."},{"key":"R27","unstructured":"T\u2019kindt V. and Billaut J.-C., Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Berlin Heidelberg (2006)."},{"key":"R28","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/j.jmsy.2022.08.004","volume":"65","author":"Wang","year":"2022","journal-title":"J. Manuf. Syst."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2025092\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T07:57:34Z","timestamp":1757059054000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2025092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":28,"journal-issue":{"issue":"4"},"alternative-id":["ro240054"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2025092","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2025,7]]}}}