{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T13:14:13Z","timestamp":1768569253175,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,9,17]],"date-time":"2020-09-17T00:00:00Z","timestamp":1600300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,17]],"date-time":"2020-09-17T00:00:00Z","timestamp":1600300800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Fraunhofer Institute for Industrial Mathematics (ITWM)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we study a proportionate flow shop of batching machines with release dates and a fixed number <jats:inline-formula><jats:alternatives><jats:tex-math>$$m \\ge 2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of machines. The scheduling problem has so far barely received any attention in the literature, but recently its importance has increased significantly, due to applications in the industrial scaling of modern bio-medicine production processes. We show that for any fixed number of machines, the makespan and the sum of completion times can be minimized in polynomial time. Furthermore, we show that the obtained algorithm can also be used to minimize the weighted total completion time, maximum lateness, total tardiness and (weighted) number of late jobs in polynomial time if all release dates are 0. Previously, polynomial time algorithms have only been known for two machines.<\/jats:p>","DOI":"10.1007\/s10951-020-00667-2","type":"journal-article","created":{"date-parts":[[2020,9,17]],"date-time":"2020-09-17T14:06:27Z","timestamp":1600351587000},"page":"575-593","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Scheduling a proportionate flow shop of batching machines"],"prefix":"10.1007","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5646-8567","authenticated-orcid":false,"given":"Christoph","family":"Hertrich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0577-9933","authenticated-orcid":false,"given":"Christian","family":"Wei\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4091-5558","authenticated-orcid":false,"given":"Heiner","family":"Ackermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sandy","family":"Heydrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven O.","family":"Krumke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,17]]},"reference":[{"key":"667_CR1","doi-asserted-by":"crossref","unstructured":"Ackermann, H., Heydrich, S., & Wei\u00df, C. (2020+). Analyzing and optimizing the throughput of a pharmaceutical production process. In Operations research proceedings 2019, Springer, accepted.","DOI":"10.1007\/978-3-030-48439-2_72"},{"issue":"4","key":"667_CR2","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1287\/opre.40.4.750","volume":"40","author":"JH Ahmadi","year":"1992","unstructured":"Ahmadi, J. H., Ahmadi, R. H., Dasu, S., & Tang, C. S. (1992). Batching and scheduling jobs on batch and discrete processors. Operations Research, 40(4), 750\u2013763.","journal-title":"Operations Research"},{"issue":"3","key":"667_CR3","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 Operations Research, 52(3), 355\u2013367.","journal-title":"Mathematical Methods of Operations Research"},{"key":"667_CR4","volume-title":"Scheduling Algorithms","author":"P Brucker","year":"2007","unstructured":"Brucker, P. (2007). Scheduling Algorithms (5th ed.). Berlin: Springer.","edition":"5"},{"key":"667_CR5","unstructured":"Brucker, P., & Knust, S. (2009). Complexity results for scheduling problems. http:\/\/www.informatik.uni-osnabrueck.de\/knust\/class\/. Accessed on September 11, 2018."},{"issue":"4","key":"667_CR6","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s10951-009-0150-8","volume":"14","author":"P Brucker","year":"2011","unstructured":"Brucker, P., & Shakhlevich, N. V. (2011). A polynomial-time algorithm for a flow-shop batching problem with equal-length operations. Journal of Scheduling, 14(4), 371\u2013389.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"667_CR7","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R","volume":"1","author":"P Brucker","year":"1998","unstructured":"Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., et al. (1998). Scheduling a batching machine. Journal of Scheduling, 1(1), 31\u201354.","journal-title":"Journal of Scheduling"},{"key":"667_CR8","doi-asserted-by":"crossref","unstructured":"Chen, Z., Zheng, X., Zhou, S., Liu, C., & Chen, H. (2019). Quantum-inspired ant colony optimisation algorithm for a two-stage permutation flow shop with batch processing machines. International Journal of Production Research.","DOI":"10.1080\/00207543.2019.1661535"},{"issue":"5","key":"667_CR9","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s10951-010-0176-y","volume":"13","author":"A Condotta","year":"2010","unstructured":"Condotta, A., Knust, S., & Shakhlevich, N. V. (2010). Parallel batch scheduling of equal-length jobs with release and due dates. Journal of Scheduling, 13(5), 463\u2013477.","journal-title":"Journal of Scheduling"},{"issue":"4","key":"667_CR10","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/j.orl.2019.04.004","volume":"47","author":"E Diessel","year":"2019","unstructured":"Diessel, E., & Ackermann, H. (2019). Domino sequencing: Scheduling with state-based sequence-dependent setup times. Operations Research Letters, 47(4), 274\u2013280.","journal-title":"Operations Research Letters"},{"issue":"2","key":"667_CR11","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117\u2013129.","journal-title":"Mathematics of Operations Research"},{"key":"667_CR12","doi-asserted-by":"crossref","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In P. L. Hammer, E. L. Johnson, & B. H. Korte (Eds.), Discrete optimization II, annals of discrete mathematics (Vol. 5, pp. 287\u2013326). Amsterdam: Elsevier.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"667_CR13","unstructured":"Hertrich, C. (2018). Scheduling a proportionate flow shop of batching machines. Master thesis, Technische Universit\u00e4t Kaiserslautern. http:\/\/nbn-resolving.de\/urn:nbn:de:hbz:386-kluedo-54968."},{"issue":"1","key":"667_CR14","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0166-218X(90)90093-R","volume":"28","author":"DS Hochbaum","year":"1990","unstructured":"Hochbaum, D. S., & Shamir, R. (1990). Minimizing the number of tardy job units under release time constraints. Discrete Applied Mathematics, 28(1), 45\u201357.","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"667_CR15","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1287\/opre.39.4.648","volume":"39","author":"DS Hochbaum","year":"1991","unstructured":"Hochbaum, D. S., & Shamir, R. (1991). Strongly polynomial algorithms for the high multiplicity scheduling problem. Operations Research, 39(4), 648\u2013653.","journal-title":"Operations Research"},{"issue":"2","key":"667_CR16","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0167-6377(86)90104-5","volume":"5","author":"Y Ikura","year":"1986","unstructured":"Ikura, Y., & Gimple, M. (1986). Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters, 5(2), 61\u201365.","journal-title":"Operations Research Letters"},{"issue":"1","key":"667_CR17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"SM Johnson","year":"1954","unstructured":"Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61\u201368.","journal-title":"Naval Research Logistics Quarterly"},{"issue":"4","key":"667_CR18","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1287\/opre.40.4.764","volume":"40","author":"CY Lee","year":"1992","unstructured":"Lee, C. Y., Uzsoy, R., & Martin-Vega, L. A. (1992). Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 40(4), 764\u2013775.","journal-title":"Operations Research"},{"issue":"5","key":"667_CR19","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1007\/s10845-014-0874-y","volume":"26","author":"D Li","year":"2015","unstructured":"Li, D., Meng, X., Liang, Q., & Zhao, J. (2015). A heuristic-search genetic algorithm for multi-stage hybrid flow shop scheduling with single processing machines and batch processing machines. Journal of Intelligent Manufacturing, 26(5), 873\u2013890.","journal-title":"Journal of Intelligent Manufacturing"},{"key":"667_CR20","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.cor.2019.04.016","volume":"108","author":"F Li","year":"2019","unstructured":"Li, F., Zhang, Y., Wei, H., & Lai, X. (2019). Integrated problem of soaking pit heating and hot rolling scheduling in steel plants. Computers & Operations Research, 108, 238\u2013246.","journal-title":"Computers & Operations Research"},{"key":"667_CR21","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":"667_CR22","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":"6","key":"667_CR23","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s10951-007-0041-9","volume":"10","author":"CT Ng","year":"2007","unstructured":"Ng, C. T., & Kovalyov, M. Y. (2007). Batching and scheduling in a multi-machine flow shop. Journal of Scheduling, 10(6), 353\u2013364.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"667_CR24","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1002\/nav.21518","volume":"60","author":"SS Panwalkar","year":"2013","unstructured":"Panwalkar, S. S., Smith, M. L., & Koulamas, C. (2013). Review of the ordered and proportionate flow shop scheduling research. Naval Research Logistics (NRL), 60(1), 46\u201355.","journal-title":"Naval Research Logistics (NRL)"},{"issue":"3","key":"667_CR25","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10951-018-0560-6","volume":"22","author":"W Passchyn","year":"2019","unstructured":"Passchyn, W., & Spieksma, F. C. R. (2019). Scheduling parallel batching machines in a sequence. Journal of Scheduling, 22(3), 335\u2013357.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"667_CR26","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1002\/1099-1425(200101\/02)4:1<25::AID-JOS58>3.0.CO;2-7","volume":"4","author":"CN Potts","year":"2001","unstructured":"Potts, C. N., Strusevich, V. A., & Tautenhahn, T. (2001). Scheduling batches with simultaneous job processing for two-machine shop problems. Journal of Scheduling, 4(1), 25\u201351.","journal-title":"Journal of Scheduling"},{"key":"667_CR27","unstructured":"Rachamadugu, R. V., Vepsalainen, A., & Morton, T. E. (1982). Scheduling in proportionate flowshops. Tech. Rep. CMU-RI-TR-83-10, Carnegie Mellon University, Pittsburgh, PA."},{"issue":"3","key":"667_CR28","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1016\/S0377-2217(02)00352-1","volume":"147","author":"CS Sung","year":"2003","unstructured":"Sung, C. S., & Kim, Y. H. (2003). Minimizing due date related performance measures on two batch processing machines. European Journal of Operational Research, 147(3), 644\u2013656.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"667_CR29","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1080\/03052159708941133","volume":"28","author":"CS Sung","year":"1997","unstructured":"Sung, C. S., & Yoon, S. H. (1997). Minimizing maximum completion time in a two-batch-processing-machine flowshop with dynamic arrivals allowed. Engineering Optimization, 28(3), 231\u2013243.","journal-title":"Engineering Optimization"},{"issue":"1","key":"667_CR30","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0377-2217(99)00031-4","volume":"121","author":"CS Sung","year":"2000","unstructured":"Sung, C. S., Kim, Y. H., & Yoon, S. H. (2000). A problem reduction and decomposition approach for scheduling for a flowshop of batch processing machines. European Journal of Operational Research, 121(1), 179\u2013192.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"667_CR31","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10951-017-0530-4","volume":"21","author":"Y Tan","year":"2018","unstructured":"Tan, Y., M\u00f6nch, L., & Fowler, J. W. (2018). A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines. Journal of Scheduling, 21(2), 209\u2013226.","journal-title":"Journal of Scheduling"},{"key":"667_CR32","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.dam.2016.04.019","volume":"211","author":"C Wei\u00df","year":"2016","unstructured":"Wei\u00df, C., Knust, S., Shakhlevich, N., & Waldherr, S. (2016). The assignment problem with nearly monge arrays and incompatible partner indices. Discrete Applied Mathematics, 211, 183\u2013203.","journal-title":"Discrete Applied Mathematics"},{"issue":"16","key":"667_CR33","doi-asserted-by":"publisher","first-page":"4919","DOI":"10.1080\/00207543.2016.1140920","volume":"54","author":"S Zhou","year":"2016","unstructured":"Zhou, S., Li, X., Chen, H., & Guo, C. (2016). Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm. International Journal of Production Research, 54(16), 4919\u20134937.","journal-title":"International Journal of Production Research"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-020-00667-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-020-00667-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-020-00667-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,17]],"date-time":"2021-09-17T01:57:23Z","timestamp":1631843843000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-020-00667-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,17]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["667"],"URL":"https:\/\/doi.org\/10.1007\/s10951-020-00667-2","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,17]]},"assertion":[{"value":"17 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}