Scheduling with lot streaming in a two-machine re-entrant flow shop
DOI:
https://doi.org/10.31181/oresta111221142cKeywords:
scheduling, lot streaming, re-entrant flow shop, makespanAbstract
Lot streaming is splitting a job-lot of identical items into several sublots (portions of a lot) that can be moved to the next machines upon completion so that operations on successive machines can be overlapped; hence, the overall performance of a multi-stage manufacturing environment can be improved. In this study, we consider a scheduling problem with lot streaming in a two-machine re-entrant flow shop in which each job-lot is processed first on Machine 1, then goes to Machine 2 for its second operation before it returns to the primary machine (either Machine 1 or Machine 2) for the third operation. For the two cases of the primary machine, both single-job and multi-job cases are studied independently. Optimal and near-optimal solution procedures are developed. Our objective is to minimize the makespan, which is the maximum completion time of the sublots and job lots in the single-job and multi-job cases, respectively. We prove that the single-job problem is optimally solved in polynomial-time regardless of whether the third operation is performed on Machine 1 or Machine 2. The multi-job problem is also optimally solvable in polynomial time when the third operation is performed on Machine 2. However, we prove that the multi-job problem is NP-hard when the third operation is performed on Machine 1. A global lower bound on the makespan and a simple heuristic algorithm are developed. Our computational experiment results reveal that our proposed heuristic algorithm provides optimal or near-optimal solutions in a very short time.
Downloads
References
Alfieri, A., Glass, C. A., & van de Velde, S. L. (2012). Lot streaming in a two-machine flow shop with attached setup times. IIE Transactions, 44(8), 695–710. https://doi.org/10.1080/0740817X.2011.649384
Alfieri, A., Zhou, S., Scatamacchia, R., & van de Velde, S. L. (2021). Dynamic programming algorithms and Lagrangian lower bounds for a discrete lot streaming problem in a two-machine flow shop. 4OR, 19(2), 265–288. https://doi.org/10.1007/s10288-020-00449-8
Baker, K. R. (1988). Lot streaming to reduce cycle time in a flow shop, Working Paper, The Amos Tuck School of Business Administration, Dartmouth College, Hanover, NH, USA.
Baker, K. R. (1995). Lot streaming in the two-stage flow shop with setup times. Annals of Operations Research, 57(1), 1–11. https://doi.org/10.1007/BF02099687
Buscher, U. & Shen, L. (2009). An integrated tabu search algorithm for the lot streaming problem in job shops. European Journal of Operational Research, 199(2), 385–399. https://doi.org/10.1016/j.ejor.2008.11.046
Çetinkaya, F. C. (1994). Lot streaming in a two-stage flow shop with set-up, processing and removal times separated. Journal of Operational Research Society, 45(12), 1445–1455. https://doi.org/10.1057/jors.1994.221
Çetinkaya, F. C. (2005). Unit sized transfer batch scheduling in an automated two-machine flow-line cell with one transport agent. International Journal of Advanced Manufacturing Technology, 29(1–2), 178–183. https://doi.org/10.1007/s00170-004-2493-9
Çetinkaya, F. C., & Kayalıgil, M. S. (1992). Unit sized transfer batch scheduling with setup times. Computers & Industrial Engineering, 22(2), 177–183. https://doi.org/10.1016/0360-8352(92)90045-L
Çetinkaya, F. C., & Duman, M. (2010). Lot streaming in a two-machine mixed shop. International Journal of Advanced Manufacturing Technology, 49(9–12), 1161–1173. https://doi.org/10.1007/s00170-009-2473-1
Chang, J. H., & Chiu, H. N. (2005). A comprehensive review of lot streaming. International Journal of Production Research, 43(8), 1515–1536. https://doi.org/10.1080/00207540412331325396
Chen, J., & Steiner, G. (1997). Lot streaming with detached setups in three-machine flow shops. European Journal of Operational Research, 96(3), 591–611. https://doi.org/10.1016/S0377-2217(96)00091-4
Chen, J., & Steiner, G. (1998). Lot streaming with attached setups in three-machine flow shops. IIE Transactions, 30(11), 1075–1084. https://doi.org/10.1023/A:1007563814941
Cheng, M., Mukherjee, N. J., & Sarin, S. C. (2013). A review of lot streaming. International Journal of Production Research, 51(23–24), 7023–7046. https://doi.org/10.1080/00207543.2013.774506
Cheng, M., & Sarin, S. C. (2020). Lot streaming in a two-stage assembly system. Annual Reviews in Control, 50(23–24), 303–316. https://doi.org/10.1016/j.arcontrol.2020.08.004
Cheng, M., Sarin, S.C., & Singh, S. (2016). Two-stage, single-lot, lot streaming problem for a 1+2 hybrid flow shop. Journal of Global Optimization, 66(2), 263–290. https://doi.org/10.1007/s10898-015-0298-z
Davendra, D., Senkerik, R., Zelinka, I., Pluhacek, M., & Bialic-Davendra, M. (2014). Utilising the chaos-induced discrete self organising migrating algorithm to solve the lot-streaming flowshop scheduling problem with setup time. Soft Computing, 18(4), 669–681. https://doi.org/10.1007/s00500-014-1219-7
Defersha, F. M., & Chen, M. (2010). A hybrid genetic algorithm for flowshop lot streaming with setups and variable sublots. International Journal of Production Research, 48(6), 1705–1726. https://doi.org/10.1080/00207543.2011.574952
Defersha, F. M. (2011). A comprehensive mathematical model for hybrid flexible flowshop lot streaming problem. International Journal of Industrial Engineering Computations, 2(2), 283–294. https://doi.org/ 10.5267/j.ijiec.2010.07.006
Defersha, F. M., & Chen, M. (2012a). Mathematical model and parallel genetic algorithm for hybrid flexible flowshop lot streaming problem. The International Journal of Advanced Manufacturing Technology, 62(1–4), 249–265. https://doi.org/10.1007/s00170-011-3798-0
Defersha, F. M., & Chen, M. (2012b). Jobshop lot streaming with routing flexibility, sequence-dependent setups, machine release dates and lag time. International Journal of Production Research, 50(2), 2331–2352. https://doi.org/10.1080/00207543.2011.574952
Feldmann, M., & Biskup, D. (2008). Lot streaming in a multiple product permutation flow shop with intermingling. International Journal of Production Research, 46(1), 197–216. https://doi.org/10.1080/00207540600930065
Glass, C. A., Possani, E. (2011). Lot streaming multiple jobs in a flow shop. International Journal of Production Research, 49(9), 2669–2681. https://doi.org/10.1080/00207543.2010.532935
Gomez-Gasquet, P., Segura-Andres, R., & Andres-Romano, C. (2013). A review of lot streaming in a flow shop environment with makespan criteria. Journal of Industrial Engineering and Management, 6(3), 761–770. http://dx.doi.org/10.3926/jiem.553
Johnson, S. M. (1954). Optimal two and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61–68. https://doi.org/10.1002/nav.3800010110
Kim, J. S., Kang, S. H., & Lee, S. M. (1997). Transfer batch scheduling for a two-stage flowshop with identical parallel machines at each stage. Omega-International Journal of Management Science, 25(5), 547–555. https://doi.org/10.1016/S0305-0483(97)00015-7
Lev, V., & Adiri, I. (1984). V-shop scheduling. European Journal of Operational Research, 18(1), 51–56. https://doi.org/10.1016/0377-2217(84)90260-1
Li, J. Q., Tao, X. R., Jia, B. X., Han, Y. Y., Liu, C., Duan, P. Zheng, Z. X., & Sanga, H. Y. (2020). Efficient multi-objective algorithm for the lot-streaming hybrid flowshop with variable sub-lots. Swarm and Evolutionary Computation, 5, Article 100600. https://doi.org/10.1016/j.swevo.2019.100600
Liu, J. (2008). Single-job lot streaming in m-1 two-stage hybrid flowshops. European Journal of Operational Research, 187(3), 1171–1183. https://doi.org/10.1016/j.ejor.2006.06.066
Marimuthu, S., Ponnambalam, S. G., Jawahar, N. (2008). Evolutionary algorithms for scheduling m-machine flow shop with lot streaming. Robotics and Computer-Integrated Manufacturing, 24(1), 125–139. https://doi.org/10.1016/j.rcim.2006.06.007
Marimuthu, S., Ponnambalam, S. G., Jawahar, N. (2009). Threshold accepting and Ant-colony optimization algorithms for scheduling m-machine flow shops with lot streaming. Journal of Materials Processing Technology, 209(2), 1026–1041. https://doi.org/10.1016/j.jmatprotec.2008.03.013
Martin, C. H. (2009). A hybrid genetic algorithm/mathematical programming approach to the multi-family flowshop scheduling problem with lot streaming. Omega, 37(1), 126–137. https://doi.org/10.1016/j.omega.2006.11.002
Meng, T., Pan, Q. K., Li, J. Q., & Sang, H. Y. (2018). An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem. Swarm and Evolutionary Computation, 38, 64–78. https://doi.org/10.1016/j.swevo.2017.06.003
Naderi, B, & Yazdani, M. (2015). Modelling and Scheduling Lot Streaming Flexible Flow Lines. Journal of Optimization in Industrial Engineering, 8(18), 61–69. http://www.qjie.ir/article_221.html
Nejati, M., Mahdavi, I., Hassanzadeh, R., & Mahdavi-Amiri, N. (2016). Lot streaming in a two-stage assembly hybrid flow shop scheduling problem with a work shift constraint. Journal of Industrial and Production Engineering, 33(7), 459–471. https://doi.org/10.1080/21681015.2015.1126653
Pan, Q. K., Tasgetiren, M. F., Suganthan, P. N., & Chua, T. J. (2011). A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Information sciences, 181(12), 2455–2468. https://doi.org/10.1016/j.ins.2009.12.025
Potts, C. N., & Baker, K. R. (1989). Flow shop scheduling with lot streaming. Operations Research Letters, 8(6), 297–303. https://doi.org/10.1016/0167-6377(89)90013-8
Pranzo, M. (2004). Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times. European Journal of Operational Research, 153(3), 581–592. https://doi.org/10.1016/S0377-2217(03)00264-9
Reither, S. (1966). A system for managing job shop production. Journal of Business, 39(3), 371–393.
Rossit, D., Tohmé, F., Frutos, M., Bard, J & Broz, D. (2016). A non-permutation flowshop scheduling problem with lot streaming: A Mathematical model. International Journal of Industrial Engineering Computations, 7(3), 507–516. https://doi.org/ 10.5267/j.ijiec.2015.11.004
Salazar-Moya, A., & Garcia, M. V. (2021). Lot Streaming in Different Types of Production Processes: A PRISMA Systematic Review. Designs, 5(4), 67. https://doi.org/10.3390/designs5040067
Sarin, S. C., & Jaiprakash, P. (2007). Flow shop lot streaming. Springer. http://dx.doi.org/10.1007/978-0-387-47688-9
Sarin, S. C., Yao, L., & Trietsch, D. (2011). Single-batch lot streaming in a two-stage assembly system. International Journal of Planning and Scheduling, 1(1–2), 90–108. https://doi.org/10.1504/IJPS.2011.044604
Sriskandarajah, C., & Wagneur, E. (1999). Lot streaming and scheduling multiple products in two-machine no-wait flow shops. IIE Transactions, 31(8), 695–707. https://doi.org/10.1023/A:1007643210135
Şen, A., & Benli, Ö. S. (1999). Lot streaming in open shops. Operations Research Letters, 23(3–5), 135–142. https://doi.org/10.1016/S0167-6377(98)00026-1
Trietsch, D. (1989). Polynomial transfer lot sizing techniques for batch processing on consecutive machines. Working Paper, Naval Postgraduate School, Monterey, California, USA. https://core.ac.uk/download/pdf/36722285.pdf
Trietsch, D., & Baker, K. R. (1993). Basic techniques for lot streaming. Operations Research, 41(6), 1065–1076. https://doi.org/10.1287/opre.41.6.1065
Tseng, C. T., & Liao, C. J. (2008). A discrete particle swarm optimization for lot-streaming flowshop scheduling problem. European Journal of Operational Research, 191(2), 360–373. https://doi.org/10.1016/j.ejor.2007.08.030
Vickson, R. G. (1995). Optimal lot streaming for multiple products in a two-machine flow shop. European Journal of Operational Research, 85(3), 556–575. https://doi.org/10.1016/0377-2217(93)E0366-6
Vickson, R. G., & Alfredson, B. E. (1992). Two-and three-machine flow shop scheduling problems with equal sized transfer batches. International Journal of Production Research, 30(7), 1551–1574. https://doi.org/10.1080/00207549208948107
Wang, M., Sethi. S. P., & Van De Velde, S. L. (1997). Minimizing makespan in a class of re-entrant shops. Operations Research, 45(5), 702–712. https://doi.org/10.1287/opre.45.5.702
Wang, S., (1997). Minimizing makespan in a class of re-entrant shops. Operations Research, 45(5), 702–712. https://doi.org/10.1287/opre.45.5.702
Wang, S., Kurz, M., Mason, S. J., & Rashidi, E. (2019). Two-stage hybrid flow shop batching and lot streaming with variable sublots and sequence-dependent setups. International Journal of Production Research, 57(22), 6893–6907. https://doi.org/10.1080/00207543.2019.1571251
Yang, D. L., & Chern, M. S. (2000). Two-machine flowshop group scheduling problem. Computers & Operations Research, 27(10), 975–985.
https://doi.org/10.1016/S0305-0548(99)00070-2
Yao, L., & Sarin, S. C. (2014). Multiple-lot, lot streaming in a two-stage assembly system. Essays in production, project planning and scheduling (pp. 357–388). Springer. https://doi.org/10.1007/978-1-4614-9056-2_15
Yoon, S. H., & Ventura, J. A. (2002). An application of genetic algorithms to lot-streaming flow shop scheduling. IIE Transactions, 34(9), 779–787. https://doi.org/10.1080/07408170208928911
Zhang, B., Pan, Q. K., Gao, L., Zhang, X. L., Sang, H. Y., & Li, J. Q. (2017). An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming. Applied Soft Computing, 52, 14–27. https://doi.org/10.1016/j.asoc.2016.12.021
Zhang, W., Liu, J., & Linn, R. J. (2003). Model and heuristics for lot streaming of one job in m-1 hybrid flowshops. International Journal of Operations and Quantitative Management, 9(1), 49–64. http://www.ijoqm.org/v9no1.asp
Zhang, W., Yin, C., Liu, J., & Linn, R. J. (2005). Multi-job lot streaming to minimize the mean completion time in m–1 hybrid flowhops. International Journal of Production Economics, 96(2), 189–200. https://doi.org/10.1016/j.ijpe.2004.04.005
