Solving the Car Sequencing Problem with Considering Unexpected Supply Disturbances

Document Type : Original Article


1 Ph.D Student, Payame Noor University.

2 Professor, Tehran University.

3 Assistant Professor, Payame Noor University.

4 Associat Professor, Alzahra University.


This paper treats the car sequencing problem in final assembly line considering the unexpected occurrence of parts supply disturbance. In this regard, a basic integer linear programming model is developed using GAMS software and based on that, problem solving algorithm according to a reactive approach with considering supply disturbance occurrence is presented. Considering NP-hardness of the problem, a metaheuristic approach based on variable neighborhood search algorithm has been presented. For evaluating the proposed method, sample problems in CSPLib have been used and for simulating the supply disturbance occurrence, test problems in 3 sizes of small, medium and large have been designed. The obtained results show the high performance of proposed algorithm with respect to the best existing solution in all three categories of the problem.


1. Alem Tabriz, A., & Bagherzadeh Azar, M. (2012). Formulating Manufacturing Strategies – Case study in Automotive Industry. Journal of Indusrial Management Perspective, 5, 131-153.
2. Alinezhad, A., Sabet, S., & Ekhtiari, M. (2014). Solving Fuzzy Multiple Objective Dynamic Cellular Manufacturing System Problem using a Hybrid Algorithm of NSGA-II and Progressive Simulated Annealing. Journal of Indusrial Management Perspective, 15, 131-156.
3. Bard, J.F., Dar-El, E., Shtub, A., (1992). An analytic framework for sequencing mixed model assembly lines. International Journal of Production Research, 30, 35–48.
4. Bolat, A., (1997). Stochastic procedures for scheduling minimum job sets on mixed model assembly lines. Journal of Operational Research Society, 48, 490-501.
5. Boysen, N., et al. (2009). Sequencing mixed-model assembly lines: Survey, classification and model critique. European Journal of Operational Research, 192, 349–373.
6. Boysen, N., et al. (2011). Sequencing mixed-model assembly lines to minimize the number of work overload situations. International Journal of Production Research, 49(16), 4735-4760.
7. Boysen, N., Golle, U., Rothlauf, F. (2011). The Car Resequencing Problem with Pull-Off Tables. German Academic Association for Business Research (VHB), 4(2), 276-292.
8. Boysen, N., Scholl, A., Wopperer, N. (2012). Resequencing of mixed-model assembly lines: survey and research agend. 9. Celano, G., Costa, A., Fichera, S., Perrone, G., (2004). Human factor policy testing in sequencing of manual mixed model assembly lines. Computers &Operations Research 31, 39–59.
10. Davenport, A.J., & Tsang, E. )1999(. Solving constraint satisfaction sequencing problems by iterative repair. In: Proceedings of the First International Conference on the Practical Applications of Constraint Technologies and Logic Programming (PACLP), 345–357.
11. Ding, F.-Y., Sun, H. (2004). Sequence alteration and restoration related to sequenced parts delivery on an automobile mixed-model assembly line with multiple departments. International Journal of Production Research, 42(8), 525–1543.
12. Franz, C., Hällgren, E., Koberstein, A. (2014). Resequencing orders on mixed-model assembly lines: Heuristic approaches to minimize the number of overload situations, International Journal of Production Research.
13. Hansen, P. & Mladenovic, N. (1997).Variable neighborhood search. Computers and Operations Research, 24(11), 1097-1100.
14. Gan, H.-S. & Wirth, A., (2005). Comparing deterministic, robust and online scheduling using entropy. International Journal of Production Research, 43, 2113–2134.
15. Gent, I.P., Walsh, T. (1999). CSPLIB: A benchmark library for constraints, Technical Report, APES-09-1999, Department of Computer Science, University of Strathclyde, UK.
16. Gravel, M., Gagne, C., and Price, W. L. (2006). Review and comparison of three methods for the solution of the car sequencing problem. Journal of the Operational Research Society, 56(11), 1287–1295.
17. Joly, A., & Frein, Y. (2008). Heuristics for an industrial car sequencing problem considering paint and assembly shop objectives. Computers & Industrial Engineering, 55, 295–310.
18. Kis, T. (2004). On the complexity of the car sequencing problem. Operations Research Letters, 32(4), 331–335.
19. Kubiak, W. (2003). Cyclic just-in-time sequences are optimal. Journal of Global Optimization 27, 333–347.
20. Meissner, S. (2010). Controlling just-in-sequence flow-production, Logistic. Res., 2, 45–53.
21. Miltenburg, J. (2001). One-piece flow manufacturing on U-shaped production lines: A tutorial. IIE Transactions, 33, 303–321.
22. Monden, Y., (1998). Toyota Production System: An integrated approach to just-in-time, third ed. Norcross.
23. Moreno, N., Corominas, A. (2006). Solving the minmax product rate variation problem (PRVP) as a bottleneck assignment problem. Computers &Operations Research, 33, 928–939.
24. Parello, B., Kabat, W., & Wos, L. (1986). Job-shop scheduling using automated reasoning: a case study of the car sequencing problem. Journal of Automatic Reason, 2, 1–42.
25. Prandtstetter, M. & Raidl, G. (2008). An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem. European Journal of Operational Research, 191(3), 1004–1022.
26. Rabieh, M., Azar, A., Modarres, M., & Fetanat, M., (2011). Mathematical Modeling for Multi Objective Robust Sourcing Problem: An Approach in Reduction of Supply Chain Risk (Case study: IKCO Supply Chain). Journal of Indusrial Management Perspective, 1, 57-77.
27. Rahmani, D. (2013). Proactive-reactive approach to reduce the effect of unexpected disruptions in dynamic scheduling problems, Phd Thesis, Iran University of Science and Technology.
28. Sarker, B.R., & Pan, H., (1998). Designing a mixed-model assembly line to minimize the costs of idle and utility times. Computers & Industrial Engineering, 34, 609–628.
29. Sialaetal, M. (2015). A study of constraint programming heuristics for the car-sequencing problem, Engineering Applications of Artificial Intelligence, 38, 34–44.
30. Solnon, C. (2008). The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF’2005 challenge problem. European Journal of Operational Research, 191, 912–927.
31. Solnon, C., )2000(. Solving permutation constraint satisfaction problems with artificial ants. In: 14th European Conference on Artificial Intelligence, Amsterdam, pp.118–122.
32. Sumichrast, R.T., Oxenrider, K.A., & Clayton, E.R. (2000). An evolutionary algorithm for sequencing production on a paced assembly line. Decision Science,31, 149–172.
33. Wu, T., Blackhurts, J. & Grady, P.O. (2007). Methodology for supply chain disruption analysis. International Journal of Production Research, 45, 1665-1682.
34. Yavuz, M. (2013). Iterated beam search for the combined car sequencing and level scheduling problem. International Journal of Production Research, 51(12), 3698-3718.
35. Yong-yi et al. (2013). A Hybrid Heuristic for Multi-shop Car Sequencing Problem with a Buffer, International Asia Conference, on Industrial Engineering and Management Innovation (IEMI2013), Springer-Verlag Berlin Heidelberg.
36. Zegordi S.H. Davarzani (2012).  Disruption & Sanction in Supply Chain: Analysis & Solution, Tehran, Indusrial Management Publication.
37. 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 Volume, Article ID 932502, 10 pages.