{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T03:01:42Z","timestamp":1781665302959,"version":"3.54.5"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T00:00:00Z","timestamp":1705017600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T00:00:00Z","timestamp":1705017600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we consider an application of lot-streaming for processing a lot of multiple items in a hybrid flow shop (HFS) for the objective of minimizing makespan. The HFS that we consider consists of two stages with a single machine available for processing in Stage 1 and <jats:italic>m<\/jats:italic> identical parallel machines in Stage 2. We call this problem a 1\u2009+\u2009<jats:italic>m<\/jats:italic> TSHFS-LSP (two-stage hybrid flow shop, lot streaming problem), and show it to be NP-hard in general, except for the case when the sublot sizes are treated to be continuous. The novelty of our work is in obtaining closed-form expressions for optimal continuous sublot sizes that can be solved in polynomial time, for a given number of sublots. A fast linear search algorithm is also developed for determining the optimal number of sublots for the case of continuous sublot sizes. For the case when the sublot sizes are discrete, we propose a branch-and-bound-based heuristic to determine both the number of sublots and sublot sizes and demonstrate its efficacy by comparing its performance against that of a direct solution of a mixed-integer formulation of the problem by CPLEX<jats:sup>\u00ae<\/jats:sup>.<\/jats:p>","DOI":"10.1007\/s10898-023-01354-0","type":"journal-article","created":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T12:02:53Z","timestamp":1705060973000},"page":"435-455","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Single-lot, lot-streaming problem for a 1\u2009+\u2009m hybrid flow shop"],"prefix":"10.1007","volume":"89","author":[{"given":"Sanchit","family":"Singh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1744-2281","authenticated-orcid":false,"given":"Subhash C.","family":"Sarin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,1,12]]},"reference":[{"issue":"3","key":"1354_CR1","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1016\/j.cor.2011.05.020","volume":"39","author":"S Carpov","year":"2012","unstructured":"Carpov, S., Carlier, J., Nace, D., Sirdey, R.: Two-stage hybrid flow shop with precedence constraints and parallel machines at second stage. Comput. Oper. Res. 39(3), 736\u2013745 (2012)","journal-title":"Comput. Oper. Res."},{"key":"1354_CR2","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10898-015-0298-z","volume":"66","author":"M Cheng","year":"2016","unstructured":"Cheng, M., Sarin, S.C., Singh, S.: Two-stage, single-lot, lot streaming problem for a 1+2 hybrid flow shop. J. Global Optim. 66, 263\u2013290 (2016)","journal-title":"J. Global Optim."},{"issue":"3","key":"1354_CR3","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"issue":"10","key":"1354_CR4","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1080\/07408179708966404","volume":"29","author":"R Devor","year":"1997","unstructured":"Devor, R., Graves, R., Mills, J.J.: Agile manufacturing research: accomplishments and opportunities. IIE Trans. 29(10), 813\u2013823 (1997)","journal-title":"IIE Trans."},{"issue":"1\u20132","key":"1354_CR5","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s00170-008-1577-3","volume":"42","author":"M Gholami","year":"2009","unstructured":"Gholami, M., Zandieh, M., Alem-Tabriz, A.: Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. Int. J. Adv. Manuf. Technol. 42(1\u20132), 189\u2013201 (2009)","journal-title":"Int. J. Adv. Manuf. Technol."},{"issue":"4","key":"1354_CR6","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1057\/jors.1988.63","volume":"39","author":"JN Gupta","year":"1988","unstructured":"Gupta, J.N.: Two-stage, hybrid flowshop scheduling problem. J. Oper. Res. Soc. 39(4), 359\u2013364 (1988)","journal-title":"J. Oper. Res. Soc."},{"issue":"7","key":"1354_CR7","doi-asserted-by":"publisher","first-page":"1489","DOI":"10.1080\/00207549108948025","volume":"29","author":"JN Gupta","year":"1991","unstructured":"Gupta, J.N., Tunc, E.A.: Schedules for a two-stage hybrid flowshop with parallel machines at the second stage. Int. J. Prod. Res. 29(7), 1489\u20131502 (1991)","journal-title":"Int. J. Prod. Res."},{"issue":"3","key":"1354_CR8","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/0377-2217(94)90407-3","volume":"77","author":"JN Gupta","year":"1994","unstructured":"Gupta, J.N., Tunc, E.A.: Scheduling a two-stage hybrid flowshop with separable setup and removal times. Eur. J. Oper. Res. 77(3), 415\u2013428 (1994)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"1354_CR9","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/S0377-2217(96)90070-3","volume":"89","author":"J Hoogeveen","year":"1996","unstructured":"Hoogeveen, J., Lenstra, J.K., Veltman, B.: Preemptive scheduling in a two-stage multiprocessor flow shop is np-hard. Eur. J. Oper. Res. 89(1), 172\u2013175 (1996)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"1354_CR10","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1111\/j.1937-5956.2002.tb00492.x","volume":"11","author":"Z Jin","year":"2002","unstructured":"Jin, Z., Ohno, K., Ito, T., Elmaghraby, S.E.: Scheduling hybrid flow shops in printed circuit board assembly lines. Prod. Oper. Manag. 11(2), 216\u2013230 (2002)","journal-title":"Prod. Oper. Manag."},{"issue":"3\u20134","key":"1354_CR11","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/s00170-007-0977-0","volume":"37","author":"J Jungwattanakit","year":"2008","unstructured":"Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., Werner, F.: Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Int. J. Adv. Manuf. Technol. 37(3\u20134), 354\u2013370 (2008)","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"1354_CR12","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0925-5273(99)00115-2","volume":"66","author":"AA Kalir","year":"2000","unstructured":"Kalir, A.A., Sarin, S.C.: Evaluation of the potential benefits of lot streaming in flow shop systems. Int. J. Prod. Econ. 66, 131\u2013142 (2000)","journal-title":"Int. J. Prod. Econ."},{"issue":"4","key":"1354_CR13","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1109\/70.88060","volume":"5","author":"A Kusiak","year":"1989","unstructured":"Kusiak, A.: Aggregate scheduling of a flexible machining and assembly system. IEEE Trans. Robot. Autom. 5(4), 451\u2013459 (1989)","journal-title":"IEEE Trans. Robot. Autom."},{"issue":"1","key":"1354_CR14","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/S0377-2217(96)00213-5","volume":"102","author":"S Li","year":"1997","unstructured":"Li, S.: A hybrid two-stage flow shop with part family, batch production, major and minor set-ups. Eur. J. Oper. Res. 102(1), 142\u2013156 (1997)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1354_CR15","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1016\/j.ejor.2006.06.066","volume":"187","author":"J Liu","year":"2008","unstructured":"Liu, J.: Single-job lot streaming in m- 1 two-stage hybrid flow shops. Eur. J. Oper. Res. 187(3), 1171\u20131183 (2008)","journal-title":"Eur. J. Oper. Res."},{"issue":"8","key":"1354_CR16","doi-asserted-by":"publisher","first-page":"1439","DOI":"10.1016\/j.cor.2009.11.001","volume":"37","author":"I Ribas","year":"2010","unstructured":"Ribas, I., Leisten, R., Frami\u00f1an, J.M.: Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Comput. Oper. Res. 37(8), 1439\u20131454 (2010)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"1354_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2009.09.024","volume":"205","author":"R Ruiz","year":"2010","unstructured":"Ruiz, R., V\u00e1zquez-Rodr\u00edguez, J.A.: The hybrid flow shop scheduling problem. Eur. J. Oper. Res. 205(1), 1\u201318 (2010)","journal-title":"Eur. J. Oper. Res."},{"key":"1354_CR18","volume-title":"Algorithms (Deluxe): Book and 24-Part Lecture Series","author":"R Sedgewick","year":"2015","unstructured":"Sedgewick, R., Wayne, K.: Algorithms (Deluxe): Book and 24-Part Lecture Series. Addison-Wesley Professional (2015)"},{"key":"1354_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2022.119151","volume":"214","author":"W Shao","year":"2023","unstructured":"Shao, W., Shao, Q., Pi, D.: Modeling and optimization of distributed heterogeneous hybrid flow shop lot streaming scheduling problem. Expert Syst. Appl. 214, 119151 (2023)","journal-title":"Expert Syst. Appl."},{"issue":"2","key":"1354_CR20","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0377-2217(89)90208-7","volume":"43","author":"C Sriskandarajah","year":"1989","unstructured":"Sriskandarajah, C., Sethi, S.P.: Scheduling algorithms for flexible flow shops: worst and average case performance. Eur. J. Oper. Res. 43(2), 143\u2013160 (1989)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1354_CR21","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/s10845-005-7029-0","volume":"16","author":"L Tang","year":"2005","unstructured":"Tang, L., Liu, W., Liu, J.: A neural network model and algorithm for the hybrid flow shop scheduling problem in a dynamic environment. J. Intell. Manuf. 16(3), 361\u2013370 (2005)","journal-title":"J. Intell. Manuf."},{"issue":"11","key":"1354_CR22","doi-asserted-by":"publisher","first-page":"3037","DOI":"10.1080\/00207549608905076","volume":"34","author":"H Tsubone","year":"1996","unstructured":"Tsubone, H., Ohba, M., Uetake, T.: The impact of lot sizing and sequencing on manufacturing performance in a two-stage hybrid flow shop. Int. J. Prod. Res. 34(11), 3037\u20133053 (1996)","journal-title":"Int. J. Prod. Res."},{"issue":"3","key":"1354_CR23","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1016\/0377-2217(93)E0366-6","volume":"85","author":"R Vickson","year":"1995","unstructured":"Vickson, R.: Optimal lot streaming for multiple products in a two-machine flow shop. Eur. J. Oper. Res. 85(3), 556\u2013575 (1995)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1354_CR24","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1287\/opre.36.3.445","volume":"36","author":"RJ Wittrock","year":"1988","unstructured":"Wittrock, R.J.: An adaptable scheduling algorithm for flexible flow lines. Oper. Res. 36(3), 445\u2013453 (1988)","journal-title":"Oper. Res."},{"issue":"5","key":"1354_CR25","doi-asserted-by":"publisher","first-page":"68","DOI":"10.3390\/a11050068","volume":"11","author":"V Yaurima-Basaldua","year":"2018","unstructured":"Yaurima-Basaldua, V., Tchernykh, A., Villalobos-Rodr\u00b4\u0131guez, F., Salomon-Torres, R.: Hybrid flow shop with unrelated machines, setup time, and work in progress buffers for bi-objective optimization of tortilla manufacturing. Algorithms 11(5), 68 (2018)","journal-title":"Algorithms"},{"key":"1354_CR26","doi-asserted-by":"publisher","first-page":"107305","DOI":"10.1016\/j.asoc.2021.107305","volume":"106","author":"B Zhang","year":"2021","unstructured":"Zhang, B., Pan, Q., Meng, L.L., Zhang, X.L., Ren, Y.P., Li, J.Q., Jiang, S.C.: A collaborative variable neighborhood descent algorithm for the hybrid flow shop scheduling problem with consistent sublots. Appl. Soft Comput. 106, 107305 (2021)","journal-title":"Appl. Soft Comput."},{"issue":"1","key":"1354_CR27","first-page":"49","volume":"9","author":"W Zhang","year":"2003","unstructured":"Zhang, W., Liu, J., Linn, R.J.: Model and heuristics for lot streaming of one job in m+1 hybrid flow shop. Int. J. Oper. Quant. Manag. 9(1), 49\u201364 (2003)","journal-title":"Int. J. Oper. Quant. Manag."},{"issue":"2","key":"1354_CR28","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.ijpe.2004.04.005","volume":"96","author":"W Zhang","year":"2005","unstructured":"Zhang, W., Yin, C., Liu, J., Linn, R.J.: Multi-job lot streaming to minimize the mean completion time in m+1 hybrid flow shop. Int. J. Prod. Econ. 96(2), 189\u2013200 (2005)","journal-title":"Int. J. Prod. Econ."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-023-01354-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-023-01354-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-023-01354-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T07:12:46Z","timestamp":1715584366000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-023-01354-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,12]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["1354"],"URL":"https:\/\/doi.org\/10.1007\/s10898-023-01354-0","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,12]]},"assertion":[{"value":"8 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}