{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:10:46Z","timestamp":1740103846062,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T00:00:00Z","timestamp":1649635200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T00:00:00Z","timestamp":1649635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Fraunhofer-Institut f\u00fcr Techno- und Wirtschaftsmathematik ITWM"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper is the first to consider online algorithms to schedule a proportionate flexible flow shop of batching machines (PFFB). The scheduling model is motivated by manufacturing processes of individualized medicaments, which are used in modern medicine to treat some serious illnesses. We provide two different online algorithms, proving also lower bounds for the offline problem to compute their competitive ratios. The first algorithm is an easy-to-implement, general local scheduling heuristic. It is 2-competitive for PFFBs with an arbitrary number of stages and for several natural scheduling objectives. We also show that for total\/average flow time, no deterministic algorithm with better competitive ratio exists. For the special case with two stages and the makespan or total completion time objective, we describe an improved algorithm that achieves the best possible competitive ratio <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varphi =\\frac{1+\\sqrt{5}}{2}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c6<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mfrac>\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:msqrt>\n                          <mml:mn>5<\/mml:mn>\n                        <\/mml:msqrt>\n                      <\/mml:mrow>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:mfrac>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the golden ratio. All our results also hold for proportionate (non-flexible) flow shops of batching machines (PFB) for which this is also the first paper to study online algorithms.<\/jats:p>","DOI":"10.1007\/s10951-022-00732-y","type":"journal-article","created":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T22:02:41Z","timestamp":1649714561000},"page":"643-657","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online algorithms to schedule a proportionate flexible flow shop of batching machines"],"prefix":"10.1007","volume":"25","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7724-2644","authenticated-orcid":false,"given":"Sandy","family":"Heydrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8726-9963","authenticated-orcid":false,"given":"Sven O.","family":"Krumke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,11]]},"reference":[{"key":"732_CR1","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/978-3-030-48439-2_72","volume":"2019","author":"H Ackermann","year":"2020","unstructured":"Ackermann, H., Heydrich, S., & Wei\u00df, C. (2020). Analyzing and optimizing the throughput of a pharmaceutical production process. Operations Research Proceedings, 2019, 591\u2013597.","journal-title":"Operations Research Proceedings"},{"issue":"4","key":"732_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":"1","key":"732_CR3","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.ijpe.2008.10.009","volume":"117","author":"MR Amin-Naseri","year":"2009","unstructured":"Amin-Naseri, M. R., & Beheshti-Nia, M. A. (2009). Hybrid flow shop scheduling with parallel batching. International Journal of Production Economics, 117(1), 185\u2013196.","journal-title":"International Journal of Production Economics"},{"key":"732_CR4","unstructured":"Brucker, P. (2007). Scheduling Algorithms (5th ed.). Springer."},{"issue":"1","key":"732_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1080\/00207720903428906","volume":"42","author":"J Cao","year":"2011","unstructured":"Cao, J., Yuan, J., Li, W., & Bu, H. (2011). Online scheduling on batching machines to minimise the total weighted completion time of jobs with precedence constraints and identical processing times. International Journal of Systems Science, 42(1), 51\u201355.","journal-title":"International Journal of Systems Science"},{"key":"732_CR6","doi-asserted-by":"crossref","unstructured":"Chai, X., Li, W., Zhu, Y. (2019). Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine. Annals of Operations Research.","DOI":"10.1007\/s10479-019-03352-6"},{"issue":"1","key":"732_CR7","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1023\/B:JOCO.0000021939.01674.1f","volume":"8","author":"B Chen","year":"2004","unstructured":"Chen, B., Deng, X., & Zang, W. (2004). On-line scheduling a batch processing system to minimize total weighted job completion time. Journal of Combinatorial Optimization, 8(1), 85\u201395.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"3","key":"732_CR8","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1023\/A:1027316504440","volume":"7","author":"X Deng","year":"2003","unstructured":"Deng, X., Poon, C. K., & Zhang, Y. (2003). Approximation algorithms in batch processing. Journal of Combinatorial Optimization, 7(3), 247\u2013257.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"4","key":"732_CR9","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s10878-010-9298-6","volume":"22","author":"Y Fang","year":"2011","unstructured":"Fang, Y., Liu, P., & Lu, X. (2011). Optimal on-line algorithms for one batch machine with grouped processing times. Journal of Combinatorial Optimization, 22(4), 509\u2013516.","journal-title":"Journal of Combinatorial Optimization"},{"key":"732_CR10","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). Elsevier.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"732_CR11","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":"5","key":"732_CR12","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s10951-020-00667-2","volume":"23","author":"C Hertrich","year":"2020","unstructured":"Hertrich, C., Wei\u00df, C., Ackermann, H., Heydrich, S., & Krumke, S. O. (2020). Scheduling a proportionate flow shop of batching machines. Journal of Scheduling, 23(5), 575\u2013593.","journal-title":"Journal of Scheduling"},{"issue":"04","key":"732_CR13","doi-asserted-by":"publisher","first-page":"1450030","DOI":"10.1142\/S0217595914500304","volume":"31","author":"C Jiao","year":"2014","unstructured":"Jiao, C., Li, W., & Yuan, J. (2014). A best possible online algorithm for scheduling to minimize maximum flow-time on bounded batch machines. Asia-Pacific Journal of Operational Research, 31(04), 1450030.","journal-title":"Asia-Pacific Journal of Operational Research"},{"issue":"5","key":"732_CR14","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"},{"issue":"18","key":"732_CR15","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1016\/j.ipl.2011.06.008","volume":"111","author":"W Li","year":"2011","unstructured":"Li, W., & Yuan, J. (2011). Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time. Information Processing Letters, 111(18), 907\u2013911.","journal-title":"Information Processing Letters"},{"issue":"3","key":"732_CR16","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s40305-017-0179-x","volume":"6","author":"WH Li","year":"2018","unstructured":"Li, W. H., & Chai, X. (2018). Online scheduling on bounded batch machines to minimize the maximum weighted completion time. Journal of the Operations Research Society of China, 6(3), 455\u2013465.","journal-title":"Journal of the Operations Research Society of China"},{"key":"732_CR17","doi-asserted-by":"crossref","unstructured":"Lin, R., Li, W., Chai, X. (2019). On-line scheduling with equal-length jobs on parallel-batch machines to minimise maximum flow-time with delivery times. Journal of the Operational Research Society.","DOI":"10.1080\/01605682.2019.1578626"},{"issue":"6","key":"732_CR18","doi-asserted-by":"publisher","first-page":"1575","DOI":"10.1080\/00207541003610262","volume":"49","author":"H Luo","year":"2011","unstructured":"Luo, H., Huang, G. Q., Zhang, Y. F., & Dai, Q. Y. (2011). Hybrid flowshop scheduling with batch-discrete processors and machine maintenance in time windows. International Journal of Production Research, 49(6), 1575\u20131603.","journal-title":"International Journal of Production Research"},{"key":"732_CR19","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.ijpe.2014.05.012","volume":"156","author":"R Ma","year":"2014","unstructured":"Ma, R., Wan, L., Wei, L., & Yuan, J. (2014). Online bounded-batch scheduling to minimize total weighted completion time on parallel machines. International Journal of Production Economics, 156, 31\u201338.","journal-title":"International Journal of Production Economics"},{"issue":"1","key":"732_CR20","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)"},{"key":"732_CR21","doi-asserted-by":"crossref","unstructured":"Pinedo, M. (2012). Scheduling (5th ed.). Springer.","DOI":"10.1007\/978-1-4614-2361-4"},{"issue":"3","key":"732_CR22","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":"732_CR23","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":"732_CR24","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"},{"issue":"4","key":"732_CR25","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s40305-014-0060-0","volume":"2","author":"J Tian","year":"2014","unstructured":"Tian, J., Fu, R., & Yuan, J. (2014). Online over time scheduling on parallel-batch machines: A survey. Journal of the Operations Research Society of China, 2(4), 445\u2013454.","journal-title":"Journal of the Operations Research Society of China"},{"issue":"3","key":"732_CR26","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1002\/nav.5","volume":"48","author":"G Zhang","year":"2001","unstructured":"Zhang, G., Cai, X., & Wong, C. K. (2001). On-line algorithms for minimizing makespan on batch processing machines. Naval Research Logistics, 48(3), 241\u2013258.","journal-title":"Naval Research Logistics"},{"issue":"2","key":"732_CR27","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1080\/07408170304378","volume":"35","author":"G Zhang","year":"2003","unstructured":"Zhang, G., Cai, X., & Wong, C. (2003). Optimal on-line algorithms for scheduling on parallel batch processing machines. IIE Transactions, 35(2), 175\u2013181.","journal-title":"IIE Transactions"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00732-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-022-00732-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00732-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T18:30:12Z","timestamp":1667241012000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-022-00732-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,11]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["732"],"URL":"https:\/\/doi.org\/10.1007\/s10951-022-00732-y","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2022,4,11]]},"assertion":[{"value":"25 February 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}