Car Resequencing Problem Optimization Under Unexpected Supply Disturbance Condition Considering Remaining in Painted Body Storage as a New Objective

Document Type : Research Paper

Authors

1 Shahrood University of Technology

2 university of tehran

3 Professor Department of Industrial Engineering, Faculty of Engineering, Alzahra University, Tehran, Iran

4 Payam-e-Noor University

10.22070/jqepo.2020.4631.1113

Abstract

One of the most critical problems in managing the car manufacturing factories' final assembly line is Car Sequencing Problem (CSP). The optimal permutation of car models is determined in a mixed model assembly line by solving this problem. In real-world cases, the unforeseen occurrence of disturbances like shortage or delay in feeding required parts to the assembly line cause to stir up an initially planned sequence. In this situation, the car resequencing problem is another challenge that should be solved. This study treats the car resequencing problem with an intermediate buffer before the final assembly line to rearrange the given initial sequence. Two objective functions are considered: (1) minimizing the ratio constraint violations (definitive objective of the car sequencing problem), and (2) minimizing work in process that remained in painted body storage (PBS) buffer. For this problem, a mathematical model as MIP is developed. Since this problem is discussed as intensely NP-hard, a new hybrid algorithm is proposed based on NSGAII and VNS to solve the medium and large scales. The numerical experiments are used according to sample problems in CSP Lib. to run the mathematical model and evaluate the developed approach's performance. The computational results show that the proposed method has a good effect on minimizing two objective functions in solving the medium and large-sized problems.

Keywords


Alszer, S., Krystek, J.,(2017) The algorithms of buffers handling in car sequencing problem presented on an actual production line, 24th International Conference on Production Research ,ISBN: 978-1-60595-507-0.
Asefi, H., Jolai, F., and Rabiee, M., Tayebi Araghi, M. (2014). A hybrid NSGA-II and VNS for solving a bi-objective no-wait flexible flowshop scheduling problem, The International Journal of Advanced Manufacturing Technology. 75: 1017-1033.
Boysen, N., A. Scholl, and Wopperer, N. (2012). Resequencing of Mixed-model Assembly Lines: Survey and Research Agenda. European Journal of Operational Research, 216:594–604.
Boysen, N., and Zenker, M. (2013). A Decomposition Approach for the Car Resequencing Problem with Selectivity Banks. Computers & Operations Research, 40:98–108.
Boysen, N., Golle, U., and Rothlauf, F. (2011). The Car Resequencing Problem with Pull-off Tables. BuR – Business Research, 4:276–292.
Christian Franz, Eric Caap Hällgren & Achim Koberstein (2014): Resequencing orders on mixed-model assembly lines: Heuristic approaches to minimise the number of overload situations, International Journal of Production Research, DOI: 10.1080/00207543.2014.918293.
Chutima, P., and Kirdphoksap, T. (2019).  Solving Many-Objective Car Sequencing Problems on Two-Sided Assembly Lines Using an Adaptive Differential Evolutionary Algorithm, ENGINEERING JOURNAL Volume 23 Issue 4,  DOI:10.4186/ej.2019.23.4.121
Chutima, P., and Olarnviwatchai, S. (2016). A multi-objective car sequencing problem on two-sided assembly lines, Journal of Intelligent Manufacturing, 1:1-20.
Coello, C.A., Lamont, G.B., and Veldhuizen, D.A.V. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems, Second edition, Springer.
Cordeau, J., Laporte, G., and Pasin, F. (2008). Iterated tabu search for the car sequencing problem, European Journal of Operational Research. 191: 945-956.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multi-objective genetic algorithm: NSGA-II. Evol Comput IEEE Trans. 6: 182–197.
Drexl, A., and Kimms, A. (2001). Sequencing JIT mixed-model assembly lines under station-load and part-usage constraints, Management Science, 47: 480-491.
Estellon, B., Gardi, F., and Nouioua, K. (2008). Two local search approaches for solving real-life car sequencing problems, European Journal of Operational Research. 191:928-944.
Fliedner, M., and Boysen, N. (2008).Solving the car sequencing problem via Branch & Bound, European Journal of Operational Research. 191:1023-1042.
Fournier, X., Agard, B. (2007). Improvement of earliness and lateness by postponement on an automotive production line. Flexible Services and Manufacturing Journal, 19, 107–121.
Franz, C., Hällgren, E. and Koberstein, A. (2014). Resequencing orders on mixed-model assembly lines: Heuristic approaches to minimise the number of overload situations, International Journal of Production Research. 52:5823-5840.
Franza, C., Kobersteinb, A., and Suhlc, L. (2015). Dynamic resequencing at mixed-model assembly lines, International Journal of Production Research. 53: 3433–3447.
Gagne, C., Gravel, M., and Price, W.L. (2006). Solving real sequencing problems with ant colony optimization, European Journal of Operational Research. 174: 1427-1448.
Gavranovic, H. (2008). Local search and suffix tree for car sequencing problem with colors, European Journal of Operational Research. 191: 972-980.
Gujjula, R., and Günther, H.O. (2009). Rescheduling Blocked Work pieces at Mixed-model Assembly Lines with Just-in-sequence Supply. In: Proceedings of Asia Pacific Industrial Engineering and Management Systems Conference (APIEMS 2009), Kitakyushu, 2758–2763.
Gujjula, R., and Günther, H.O. (2009). Resequencing Mixed-model Assembly Lines under Just-in-sequence Constraints. In: International Conference on Computers and Industrial Engineering (CIE 2009), Troyes, 668–673.
Gunay E.E., and Kula, U. (2016). A stochastic programming model for resequencing buffer content optimisation in mixed-model assembly lines, International Journal of Production Research, 55: 2897-2912.
Hansen, P., and Mladenović, N. (2001). Variable neighbourhood search: principles and applications. European Journal of Operational Research. 130: 449–467.
Inman, R. R. & Schmeling, D. M. (2003).  Algorithm for agile assembling to-order in the automotive industry, International Journal of Production Research, 41:16, 3831-3848.
Inman, R. R. (2003). ASRS sizing for recreating automotive assembly sequences, International Journal of Production Research, 41:5, 847-863.
Jahren, E., Achá, R.A.,(2018). A column generation approach and new bounds for the car sequencing problem. Annual Operation Research 264, 193–211, doi:10.1007/s10479-017-2663-4
Joly, A., and Frein, Y. (2008). Heuristic for an industrial car sequencing problem considering paint and assembly shop objectives, Computers & Industrial Engineering. 55:295-310.
Kis,T. (2004). On the complexity of the car sequencing problem, Operations Research Letters, 32: 331-335.
Lim, A., Xu, Z. (2009). Searching optimal resequencing and feature assignment on an automated assembly line. Journal of the Operational Research Society, 60, 361–371.
Lutfe Elahi, M., Rajpurohit, K., Rosenberger, J., Zaruba, G., Priest, J. (2015). Optimizing real-time vehicle sequencing of a paint shop conveyor system, Omega 55, 61–72.
Moon, D., Kim, H., Song, C. (2005). A simulation study for implementing color rescheduling storage in an automotive factory. Simulation. 81 (9), 625–635.
Parello, B.D., Kabat, W.C., and Wos, L. (1986).  Job-shop scheduling using automated reasoning: a case study of the car sequencing problem, Journal of Automatic Reason, 2: 1-42.
Prandtstetter, M. and Raidl, G. (2008). An integer linear programming approach and a hybrid variable neighbourhood search for the car sequencing problem. European Journal of Operational Research. 191:1004–1022.
Rahimi-Vahed, A.R., Mirghorbani, S.M., and Rabbani, M. (2007). A Hybrid Multi-Objective Particle Swarm Algorithm for a Mixed-Model Assembly Line Sequencing Problem. Engineering Optimization. 39: 877–898.
Riberio, C., Aloise, D., Noronha, T., and Rocha, C. (2008a). A hybrid heuristic for a multi-objective real-life car sequencing problem with painting and assembly line constraints, European Journal of Operational Research, 191:981-992.
Riberio, C., Aloise, D., Noronha, T., Rocha, C., and Urrutia, S. (2008b). An efficient implementation of a VNS/ILS heuristic for a real-life car sequencing problem, European Journal of Operational Research, 191: 596-611.
Ricardo José de Oliveira dos Reis. (2007). Solving the Car Sequencing Problem from a Multi-objective Perspective. Thesis.
Solnon, C. (2008). Combining two pheromone structures for solving the car sequencing problem with Ant Colony Optimization, European Journal of Operational Research, 191:1043-1055.
Spieckermann, S., Gutenschwager, K., VO, S. (2004). A sequential ordering problem in automotive paint shops. International Journal of Production Research, 42 (9), 1865–1878.
Sun, H., Fan, S., Shao, X. & Zhou,J. (2015). A color-batching problem using selectivity banks in automobile paint shops, International Journal of Production Research, 53:4, 1124-1142.
Thiruvady, D., Morgan, K., Amir, A., & Ernst, A., (2019) Large neighborhood search based on mixed integer programming and ant colony optimization for car sequencing, International Journal of Production Research, DOI: 10.1080/00207543.2019.1630765
Vieira, G. E., Herrmann, J.W., and Lin, E. (2003). Rescheduling Manufacturing Systems: A Framework of Strategies, Policies, and Methods. Journal of Scheduling. 6:39–62.
Zhang Xiang-yang, GAO Liang, WEN Long, Huang Zhao-dong., (2018) A hybrid algorithm based on tabu search and large neighbourhood search for car sequencing problem. Journal of Central South University, 25(2): 315–330. DOI: https://doi.org/10.1007/s11771-018-3739-2.
Zhipeng, T., Xinyu,S., Haiping,Z., Hui,Y., Fei,H. (2015). Small-World Optimization Algorithm and Its Application in a Sequencing Problem of Painted Body Storage in a Car Company, Mathematical Problems in Engineering, Article ID 932502.