{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:10:54Z","timestamp":1740103854440,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,10,22]],"date-time":"2024-10-22T00:00:00Z","timestamp":1729555200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,22]],"date-time":"2024-10-22T00:00:00Z","timestamp":1729555200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["MN 59\/4-1","MN 59\/4-1"],"award-info":[{"award-number":["MN 59\/4-1","MN 59\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2024,12]]},"abstract":"Abstract<\/jats:title>\n The \n \n $$1\\vert \\text {s-batch}(\\infty ),r_j\\vert \\sum w_jU_j$$<\/jats:tex-math>\n \n \n \n 1<\/mml:mn>\n |<\/mml:mo>\n s-batch<\/mml:mtext>\n \n (<\/mml:mo>\n \u221e<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n <\/mml:mrow>\n \n r<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n |<\/mml:mo>\n \u2211<\/mml:mo>\n <\/mml:mrow>\n \n w<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n U<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> scheduling problem takes as input a batch setup time \n \n $$\\Delta $$<\/jats:tex-math>\n \n \u0394<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and a set of n<\/jats:italic> jobs, each having a processing time, a release date, a weight, and a due date; the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy (Oper Res Lett 16(2):79\u201386, 1994); as a wide generalization of Knapsack<\/jats:sc>, it is \n \n $$\\textsf{NP}$$<\/jats:tex-math>\n \n NP<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-hard. In this work, we provide a multivariate complexity analysis of the \n \n $$1\\vert \\text {s-batch}(\\infty ), r_j\\vert \\sum w_jU_j$$<\/jats:tex-math>\n \n \n \n 1<\/mml:mn>\n |<\/mml:mo>\n s-batch<\/mml:mtext>\n \n (<\/mml:mo>\n \u221e<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n <\/mml:mrow>\n \n r<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n |<\/mml:mo>\n \u2211<\/mml:mo>\n <\/mml:mrow>\n \n w<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n U<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> problem with respect to several natural parameters. That is, we establish a classification into fixed-parameter tractable and \n \n $$\\textsf{W}[1]$$<\/jats:tex-math>\n \n \n W<\/mml:mi>\n [<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-hard problems, for parameter combinations of (i) \n \n $$\\#p$$<\/jats:tex-math>\n \n \n #<\/mml:mo>\n p<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> = number of distinct processing times, (ii) \n \n $$\\#w$$<\/jats:tex-math>\n \n \n #<\/mml:mo>\n w<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> = number of distinct weights, (iii) \n \n $$\\#d$$<\/jats:tex-math>\n \n \n #<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> = number of distinct due dates, (iv) \n \n $$\\#r$$<\/jats:tex-math>\n \n \n #<\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> = number of distinct release dates. Thereby, we significantly extend the work of Hermelin et al. (Ann Oper Res 298:271\u2013287, 2018) who analyzed the parameterized complexity of the non-batch variant of this problem without release dates. As one of our key results, we prove that \n \n $$1\\vert \\text {s-batch}(\\infty ), r_j\\vert \\sum w_jU_j$$<\/jats:tex-math>\n \n \n \n 1<\/mml:mn>\n |<\/mml:mo>\n s-batch<\/mml:mtext>\n \n (<\/mml:mo>\n \u221e<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n <\/mml:mrow>\n \n r<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n |<\/mml:mo>\n \u2211<\/mml:mo>\n <\/mml:mrow>\n \n w<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n U<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is \n \n $$\\textsf{W}[1]$$<\/jats:tex-math>\n \n \n W<\/mml:mi>\n [<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-hard parameterized by the number of distinct processing times and distinct due dates. To the best of our knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that \n \n $$1\\vert \\text {s-batch}(\\infty ), r_j\\vert \\sum w_jU_j$$<\/jats:tex-math>\n \n \n \n 1<\/mml:mn>\n |<\/mml:mo>\n s-batch<\/mml:mtext>\n \n (<\/mml:mo>\n \u221e<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n <\/mml:mrow>\n \n r<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n |<\/mml:mo>\n \u2211<\/mml:mo>\n <\/mml:mrow>\n \n w<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n U<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is fixed-parameter tractable parameterized by \n \n $$\\#d + \\#p + \\#r$$<\/jats:tex-math>\n \n \n #<\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n #<\/mml:mo>\n p<\/mml:mi>\n +<\/mml:mo>\n #<\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, and parameterized by \n \n $$\\#d + \\#w$$<\/jats:tex-math>\n \n \n #<\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n #<\/mml:mo>\n w<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s10951-024-00818-9","type":"journal-article","created":{"date-parts":[[2024,10,22]],"date-time":"2024-10-22T22:02:06Z","timestamp":1729634526000},"page":"545-556","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Serial batching to minimize the weighted number of tardy jobs"],"prefix":"10.1007","volume":"27","author":[{"given":"Danny","family":"Hermelin","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4721-5354","authenticated-orcid":false,"given":"Matthias","family":"Mnich","sequence":"additional","affiliation":[]},{"given":"Simon","family":"Omlor","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,22]]},"reference":[{"key":"818_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Lewi, K., & Williams, R. (2014). Losing weight by gaining edges. In Proceedings of the ESA 2014. Lecture Notes Computer Science (Vol. 8737, pp. 1\u201312).","DOI":"10.1007\/978-3-662-44777-2_1"},{"issue":"3","key":"818_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. Mathematical Methods of Operational Research, 52(3), 355\u2013367.","journal-title":"Mathematical Methods of Operational Research"},{"key":"818_CR3","volume-title":"Scheduling","author":"P Brucker","year":"2007","unstructured":"Brucker, P. (2007). Scheduling (5th ed.). Berlin: Springer Berlin Heidelberg.","edition":"5"},{"issue":"1","key":"818_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01303431","volume":"43","author":"P Brucker","year":"1996","unstructured":"Brucker, P., & Kovalyov, M. Y. (1996). Single machine batch scheduling to minimize the weighted number of late jobs. Mathematical Methods of Operational Research, 43(1), 1\u20138.","journal-title":"Mathematical Methods of Operational Research"},{"issue":"5","key":"818_CR5","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1080\/07408170108936839","volume":"33","author":"TCE Cheng","year":"2001","unstructured":"Cheng, T. C. E., & Kovalyov, M. Y. (2001). Single machine batch scheduling with sequential job processing. IIE Transactions, 33(5), 413\u2013420.","journal-title":"IIE Transactions"},{"key":"818_CR6","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F. V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized algorithms. Cham: Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"818_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2016.06.004","volume":"84","author":"M Etscheid","year":"2017","unstructured":"Etscheid, M., Kratsch, S., Mnich, M., & R\u00f6glin, H. (2017). Polynomial kernels for weighted problems. Journal of Computer and System Sciences, 84, 1\u201310.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"818_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2021.06.012","volume":"298","author":"JW Fowler","year":"2022","unstructured":"Fowler, J. W., & M\u00f6nch, L. (2022). A survey of scheduling with parallel batch (p-batch) processing. European Journal of Operational Research, 298(1), 1\u201324.","journal-title":"European Journal of Operational Research"},{"issue":"6","key":"818_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3421750","volume":"67","author":"MX Goemans","year":"2020","unstructured":"Goemans, M. X., & Rothvoss, T. (2020). Polynomiality for bin packing with a constant number of item types. Journal of the ACM, 67(6), 1\u201321.","journal-title":"Journal of the ACM"},{"key":"818_CR10","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"3","author":"RL Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnoy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 3, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"key":"818_CR11","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10479-018-2852-9","volume":"298","author":"D Hermelin","year":"2018","unstructured":"Hermelin, D., Karhi, S., Pinedo, M., & Shabtay, D. (2018). New algorithms for minimizing the weighted number of tardy jobs on a single machine. Annals of Operations Research, 298, 271\u2013287.","journal-title":"Annals of Operations Research"},{"issue":"1","key":"818_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.ejor.2018.07.038","volume":"273","author":"D Hermelin","year":"2019","unstructured":"Hermelin, D., Pinedo, M., Shabtay, D., & Talmon, N. (2019). On the parameterized tractability of single machine scheduling with rejection. European Journal of Operational Research, 273(1), 67\u201373.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"818_CR13","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0167-6377(94)90063-9","volume":"16","author":"DS Hochbaum","year":"1994","unstructured":"Hochbaum, D. S., & Landy, D. (1994). Scheduling with batching: minimizing the weighted number of tardy jobs. Operations Research Letters, 16(2), 79\u201386.","journal-title":"Operations Research Letters"},{"key":"818_CR14","first-page":"85","volume-title":"Reducibility among combinatorial problems","author":"RM Karp","year":"1972","unstructured":"Karp, R. M. (1972). Reducibility among combinatorial problems (pp. 85\u2013103). Springer."},{"issue":"5","key":"818_CR15","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10951-017-0550-0","volume":"21","author":"D Knop","year":"2018","unstructured":"Knop, D., & Kouteck\u00fd, M. (2018). Scheduling meets n-fold integer programming. Journal of Scheduling, 21(5), 493\u2013503.","journal-title":"Journal of Scheduling"},{"issue":"1\u20132","key":"818_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-019-01402-2","volume":"184","author":"D Knop","year":"2020","unstructured":"Knop, D., Kouteck\u00fd, M., & Mnich, M. (2020). Combinatorial n-fold integer programming and applications. Mathematical Programming, 184(1\u20132), 1\u201334.","journal-title":"Mathematical Programming"},{"issue":"1","key":"818_CR17","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1287\/mnsc.16.1.77","volume":"16","author":"EL Lawler","year":"1969","unstructured":"Lawler, E. L., & Moore, J. M. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16(1), 77\u201384.","journal-title":"Management Science"},{"key":"818_CR18","doi-asserted-by":"crossref","unstructured":"Lenstra, H. W. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research 8(4), 538\u2013548.","DOI":"10.1287\/moor.8.4.538"},{"key":"818_CR19","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.cor.2018.07.020","volume":"100","author":"M Mnich","year":"2018","unstructured":"Mnich, M., & van Bevern, R. (2018). Parameterized complexity of machine scheduling: 15 open problems. Computers & Operations Research, 100, 254\u2013261.","journal-title":"Computers & Operations Research"},{"issue":"1","key":"818_CR20","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-014-0830-9","volume":"154","author":"M Mnich","year":"2015","unstructured":"Mnich, M., & Wiese, A. (2015). Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1), 533\u2013562.","journal-title":"Mathematical Programming"},{"issue":"1","key":"818_CR21","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"JM Moore","year":"1968","unstructured":"Moore, J. M. (1968). An $$n$$ job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15(1), 102\u2013109.","journal-title":"Management Science"},{"key":"818_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3","volume-title":"Scheduling: Theory, algorithms, and systems","author":"M Pinedo","year":"2016","unstructured":"Pinedo, M. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.","edition":"5"},{"issue":"2","key":"818_CR23","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/S0377-2217(99)00153-8","volume":"120","author":"CN Potts","year":"2000","unstructured":"Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: A review. European Journal of Operational Research, 120(2), 228\u2013249.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"818_CR24","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"SK Sahni","year":"1976","unstructured":"Sahni, S. K. (1976). Algorithms for scheduling independent tasks. Journal of the ACM, 23(1), 116\u2013127.","journal-title":"Journal of the ACM"},{"key":"818_CR25","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Bredereck, R., Bulteau, L., Komusiewicz, C., Talmon, N., & Woeginger, G. J. (2016). Precedence-constrained scheduling problems parameterized by partial order width. In Proceedings of the DOOR 2016. Lecture Notes Computer Science (Vol. 9869, pp. 105\u2013120).","DOI":"10.1007\/978-3-319-44914-2_9"},{"issue":"5","key":"818_CR26","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s10951-014-0398-5","volume":"18","author":"R van Bevern","year":"2015","unstructured":"van Bevern, R., Mnich, M., Niedermeier, R., & Weller, M. (2015). Interval scheduling and colorful independent sets. Journal of Scheduling, 18(5), 449\u2013469.","journal-title":"Journal of Scheduling"},{"issue":"3","key":"818_CR27","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s10951-016-0478-9","volume":"20","author":"R van Bevern","year":"2017","unstructured":"van Bevern, R., Niedermeier, R., & Such\u00fd, O. (2017). A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: Few machines, small looseness, and small slack. Journal of Scheduling, 20(3), 255\u2013265.","journal-title":"Journal of Scheduling"},{"issue":"4","key":"818_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. R. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43(4), 692\u2013703.","journal-title":"Operations Research"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00818-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-024-00818-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00818-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T18:33:39Z","timestamp":1738694019000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-024-00818-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,22]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["818"],"URL":"https:\/\/doi.org\/10.1007\/s10951-024-00818-9","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2024,10,22]]},"assertion":[{"value":"25 July 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}