A Multi-stage Stochastic Programming Approach in a Dynamic Cell Formation Problem with Uncertain Demand: a Case Study

Document Type : Research Paper


Department of Industrial Engineering, Yazd University, Yazd, Iran


This paper addresses a dynamic cell formation problem (DCFP) including a multi-period planning horizon in which demands for each product in each period are different and uncertain. Because the demand uncertainty is considered as stochastic data by discrete scenarios on a scenario tree, a multi-stage nonlinear mixed-integer stochastic programming is applied such that the objective function is minimizing of machine purchase costs, the operating costs, both inter and intra-cell material handling costs, and the machine relocation costs over the planning horizon. The main goal of the current study is to determine the optimal cell configuration in each period in order to achieve the minimum total expected costs under the given constraints. The nonlinear model is transformed into a linear form to this reason that GAMS can get to global optimal solutions in linear models. In order to find the optimal solutions, by using the GAMS for small and medium-sized problems, the optimal solutions are obtained. They applied in two bounds namely the Sum of Pairs Expected Values (SPEV) and the Expectation of Pairs Expected Value (EPEV). Also, according to the scenario-based model, the efficiency of two suggested bounds is shown in terms of the computational time. Finally, a practical case study is presented in detail to illustrate the application of the proposed model and it's solving method. The results show the efficiency of using SPEV and EPEV for several random examples as well as the proposed case study.


Main Subjects

Aryanezhad, M. B., Deljoo, V. and Mirzapour Al-e-Hashem. S. M. J. (2009). Dynamic Cell Formation and the Worker Assignment Problem: A New Model. The International Journal of Advanced Manufacturing Technology, Vol.41(3-4), pp. 329–42.
Arzi, Y., Bukchin, J., and Masin, M. (2001). An efficiency frontier approach for the design of cellular manufacturing systems in a lumpy demand environment. European Journal of Operational Research, Vol.134 (2), pp. 346-364.
Askin, R. G., Selim, H. M., and Vakharia, A. J. (1997). A methodology for designing flexible cellular manufacturing systems. IIE transactions, Vol. 29(7), pp. 599-610.
Bagheri, M., and Bashiri, M. (2014). A new mathematical model towards the integration of cell formation with operator assignment and inter-cell layout problems in a dynamic environment. Applied Mathematical Modelling, Vol. 38(4), pp. 1237-1254.
Bajestani, M. A., Rabbani, M., Rahimi-Vahed, A. R., and Khoshkhou, G. B. (2009). A multi-objective scatter search for a dynamic cell formation problem. Computers & operations research, Vol. 36(3), pp. 777-794.
Balakrishnan, J., and Hung Cheng, C. (2005). Dynamic cellular manufacturing under multiperiod planning horizons. Journal of manufacturing technology management, Vol. 16(5), pp. 516-530.
Birge, J R, and F Louveaux. (1997). Introduction to Stochastic Programming. Series in Operations Research and Financial Engineering.
Bulgak, A. A., and Bektas, T. (2009). Integrated cellular manufacturing systems design with production planning and dynamic system reconfiguration. European journal of operational research, Vol. 192(2), pp. 414-428.
Chen, M. (1998). A mathematical programming model for system reconfiguration in a dynamic cellular manufacturing environment. Annals of Operations Research, Vol. 77, pp. 109-128.
Defersha, F. M., and Chen, M. (2006). Machine cell formation using a mathematical model and a genetic-algorithm-based heuristic. International Journal of Production Research, Vol. 44(12), pp. 2421-2444.
Dupańćová, J., Consigli, G., and Wallace, S. W. (2000). Scenarios for multistage stochastic programs. Annals of operations research, Vol. 100(1-4), pp. 25-53.
Farunghi, H., and Mostafayi, S. (2016). Robust Optimization Approach for Design for a Dynamic Cell Formation Considering Labor Utilization: Bi-objective Mathematical Model. International Journal of Supply and Operations Management, Vol. 3(1), pp. 1143-1167.
Ghotboddini, M. M., Rabbani, M., and Rahimian, H. (2011). A comprehensive dynamic cell formation design: Benders’ decomposition approach. Expert Systems with Applications, Vol. 38(3), pp. 2478-2488.
Egilmez, G., Singh, S., and Ozguner, O. (2017). Cell formation in a cellular manufacturing system under uncertain demand and processing times: a stochastic genetic algorithm approach. International Journal of Services and Operations Management, Vol. 26(2), pp. 162-185.
Esmaeilbeigi, R., Naderi, B., Arshadikhamseh, A., and Loni, P. (2017). An Estimated Formulation for the Capacitated Single Allocation p-hub Median Problem with Fixed Costs of Opening Facilities. International Journal of Supply and Operations Management, Vol. 4(1), pp. 63-72.
Javadian, N., Aghajani, A., Rezaeian, J., and Sebdani, M. J. G. (2011). A multi-objective integrated cellular manufacturing systems design with dynamic system reconfiguration. The International Journal of Advanced Manufacturing Technology, Vol. 56(1-4), pp. 307-317.
Kall, PETER, S, and W Wallace. (1994). “Stochastic Programming.” Jonh Wiley & Sons, Chichester.
Kall, P., & Mayer, J. (1976). Stochastic linear programming (Vol. 7). Berlin: Springer-Verlag.  
Kia, R., Khaksar-Haghani, F., Javadian, N., and Tavakkoli-Moghaddam, R. (2014). Solving a multi-floor layout design model of a dynamic cellular manufacturing system by an efficient genetic algorithm. Journal of Manufacturing Systems, Vol. 33(1), pp. 218-232.
Kia, R., Baboli, A., Javadian, N., Tavakkoli-Moghaddam, R., Kazemi, M., and Khorrami, J. (2012). Solving a group layout design model of a dynamic cellular manufacturing system with alternative process routings, lot splitting and flexible reconfiguration by simulated annealing. Computers & operations research, Vol. 39(11), pp. 2642-2658.
Koushki, F. (2018). “Performance Measurement and Productivity Management in Production Units with Network Structure by Identification of the Most Productive Scale Size Pattern.”  International Journal of Supply and Operations Management, Vol. 5(4), pp. 379-395.
Maggioni, Francesca, Elisabetta Allevi, and Marida Bertocchi. (2012). Measures of information in multistage stochastic programming. In STOPROG-2012-Stochastic Programming for Implementation and Advanced Applications (pp. 78-82). The Association of Lithuanian Serials. 
Maggioni, F., Allevi, E., and Bertocchi, M. (2014). Bounds in multistage linear stochastic programming. Journal of Optimization Theory and Applications, Vol. 163(1), pp. 200-229.
Mahdavi, I., Aalaei, A., Paydar, M. M., and Solimanpur, M. (2010). Designing a mathematical model for dynamic cellular manufacturing systems considering production planning and worker assignment. Computers & Mathematics with Applications, Vol. 60(4), pp. 1014-1025.
Mahmoodian, V., Jabbarzadeh, A., Rezazadeh, H., and Barzinpour, F. (2017). A novel intelligent particle swarm optimization algorithm for solving cell formation problem. Neural Computing and Applications, pp. 1-15.
Moslemipour, G. (2018). A hybrid CS-SA intelligent approach to solve uncertain dynamic facility layout problems considering dependency of demands. Journal of Industrial Engineering International, Vol. 14(2), pp. 429-442.
Niakan, F., Baboli, A., Moyaux, T., and Botta-Genoulaz, V. (2016). A bi-objective model in sustainable dynamic cell formation problem with skill-based worker assignment. Journal of Manufacturing Systems, Vol. 38, pp. 46-62.
Rabbani, M., Farrokhi-Asl, H., and Ravanbakhsh, M. (2019). Dynamic cellular manufacturing system considering machine failure and workload balance. Journal of Industrial Engineering International, Vol. 15(1), pp. 25-40.
Rabbani, M., Ravanbakhsh, M., Farrokhi-Asl, H., and Taheri, M. (2017). Using metaheuristic algorithms for solving a hub location problem: application in passive optical network planning.  International Journal of Supply and Operations Management, Vol. 4(1), pp. 15-32.
Rezaie, K., Gereie, A., Ostadi, B., and Shakhseniaee, M. (2009). Safety interval analysis: A risk-based approach to specify low-risk quantities of uncertainties for contractor’s bid proposals. Computers & Industrial Engineering, Vol. 56(1), pp. 152-156.
Rheault, M., Drolet, J. R., and Abdulnour, G. (1996). Dynamic cellular manufacturing system (DCMS). Computers & Industrial Engineering, Vol. 31(1-2), pp. 143-146.
Safaei, N., Saidi-Mehrabad, M., and Jabal-Ameli, M. S. (2008). A hybrid simulated annealing for solving an extended model of dynamic cellular manufacturing system. European Journal of Operational Research, Vol. 185(2), pp. 563-592.
Safaei, N., Saidi-Mehrabad, M., Tavakkoli-Moghaddam, R., and Sassani, F. (2008). A fuzzy programming approach for a cell formation problem with dynamic and uncertain conditions. Fuzzy Sets and Systems, Vol. 159(2), pp. 215-236.
Safaei, N., and Tavakkoli-Moghaddam, R. (2009). Integrated multi-period cell formation and subcontracting production planning in dynamic cellular manufacturing systems. International Journal of Production Economics, Vol. 120(2), pp. 301-314.
Saidi-Mehrabad, M., and Safaei, N. (2007). A new model of dynamic cell formation by a neural approach. The International Journal of Advanced Manufacturing Technology, Vol. 33(9-10), pp. 1001-1009.
Saxena, L. K., and Jain, P. K. (2012). An integrated model of dynamic cellular manufacturing and supply chain system design. The International Journal of Advanced Manufacturing Technology, Vol. 62(1-4), pp. 385-404.
Shakhsi-Niaei, M. , Iranmanesh, S. H., and Torabi, S. A. (2013). A review of mathematical optimization applications in oil-and-gas upstream & midstream management. International Journal of Energy and Statistics, Vol. 1(02), pp. 143-154.
Shishebori, D. (2014). Study of facility location-network design problem in presence of facility disruptions: A case study (research note). International Journal of Engineering-Transactions A: Basics, Vol. 28(1), pp. 97-108.
Shishebori, D., Akhgari, M. J., Noorossana, R., and Khaleghi, G. H. (2015). An efficient integrated approach to reduce scraps of industrial manufacturing processes: a case study from gauge measurement tool production firm. The International Journal of Advanced Manufacturing Technology, Vol. 76(5-8), pp. 831-855.
Shishebori, Davood, and Abdolsalam Ghaderi. (2015). “An integrated approach for reliable facility location/network design problem with link disruption.” International Journal of Supply and Operations Management, Vol. 2(1), pp.  633-640.
Taboun, S. M., Merchawi, N. S., and Ulger, T. (1998). Part family and machine cell formation in multiperiod planning horizons of cellular manufacturing systems. Production Planning & Control, Vol. 9(6), pp. 561-571.
Tavakkoli-Moghaddam, R., Aryanezhad, M. B., Safaei, N., and Azaron, A. (2005). Solving a dynamic cell formation problem using metaheuristics. Applied Mathematics and Computation, Vol. 170(2), pp. 761-780.
Wang, X., Tang, J., and Yung, K. L. (2009). Optimization of the multi-objective dynamic cell formation problem using a scatter search approach. The International Journal of Advanced Manufacturing Technology, Vol. 44(3-4), pp. 318-329.
Wang, Y., and Tang, J. (2018). Cost and Service-Level-Based Model for a Seru Production System Formation Problem with Uncertain Demand. Journal of Systems Science and Systems Engineering, Vol. 27(4), pp. 519-537.
Wemmerlöv, U., and Hyer, N. L. (1987). Research issues in cellular manufacturing. International Journal of Production Research, Vol. 25(3), pp. 413-431.
Zarrinpoor, N. (2018). An Exploration of Evolutionary Algorithms for a Bi-Objective Competitive Facility Location Problem in Congested Systems. International Journal of Supply and Operations Management, Vol. 5(3), pp. 266-282.
Zohrevand, A.M., H. Rafiei, and A. H. Zohrevand. (2016). Multi-Objective Dynamic Cell Formation Problem: A Stochastic Programming Approach. Computers & Industrial Engineering, Vol. 98, pp. 323-332.