Mathematical Model and Algorithm for sequencing operations in the machine building industry

Document Type : research paper


Department of Industrial Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran


In this paper, the problem of sequencing machines in the final assembly line with regard to the supply of parts has been investigated. For this reason, a basic integer linear programming model has been developed and based on this, the problem-solving algorithm is developed in accordance with the reaction-based approach based on the renewal of the sequence of operations. Also, due to the Np-hardness of the problem, a meta-innovative method based on the variable-neighborhood search algorithm is presented. To evaluate the proposed solution method, a sample of library issues was used and to simulate the disruption event, test questions were designed in large, medium and small dimensions. The results show that, in three categories of problems, the proposed meta-innovation method is approaching it in a very appropriate way compared to the best available method. In addition, due to the solving time, it is much more efficient than the optimal solution method and is responsive. The immediate needs are to update the sequence of operations in the face of disturbances created in the car production line.


Article Title [فارسی]

ارایه مدل ریاضی و الگوریتم فراابتکاری جهت تعیین توالی عملیات در صنعت ماشین سازی

Authors [فارسی]

  • محمد فلاح
  • ندا گورانی
گروه مهندسی صنایع، واحد تهران مرکزی، دانشگاه آزاد اسلامی، تهران، ایران
Abstract [فارسی]

میزان در اﯾﻦ ﻣﻘﺎﻟﻪ ﻣﺴﺌﻠﻪ ﺗﻌﯿﯿﻦ ﺗﻮاﻟﯽ ماشین‌ها در ﺧﻂ ﻣﻮﻧﺘﺎژ ﻧﻬﺎﯾﯽ ﺑﺎ در ﻧﻈﺮ ﮔﺮﻓﺘﻦ ﺗﺎﻣﯿﻦ ﻗﻄﻌﺎت ﺑﺮرﺳﯽ ﺷﺪه اﺳﺖ. ﺑﺪﯾﻦ ﺟﻬﺖ ﯾﮏ ﻣﺪل ﭘﺎﯾﻪ ای ﺑﺮﻧﺎﻣﻪ رﯾﺰی ﺧﻄﯽ ﻋﺪد ﺻﺤﯿﺢ ﺗﻮﺳﻌﻪ ﯾﺎﻓﺘﻪ و ﺑﺮ ﻣﺒﻨﺎی آن، اﻟﮕﻮرﯾﺘﻢ ﺣﻞ ﻣﺴﺌﻠﻪ ﻣﻄﺎﺑﻖ ﺑﺎ روﯾﮑﺮد واﮐﻨﺸﯽ و ﻣﺒﺘﻨﯽ ﺑﺮ ﺗﺠﺪﯾﺪ ﺗﻮاﻟﯽ ﻋﻤﻠﯿﺎت، ﺗﻮﺳﻌﻪ ﯾﺎﻓﺘﻪ اﺳﺖ. ﻫﻤﭽﻨﯿﻦ ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ Np-hard ﺑﻮدن ﻣﺴﺌﻠﻪ، ﯾﮏ روش ﻓﺮا اﺑﺘﮑﺎری ﻣﺒﺘﻨﯽ ﺑﺮ اﻟﮕﻮرﯾﺘﻢ ﺟﺴﺘﺠﻮی ﻫﻤﺴﺎﯾﮕﯽ ﻣﺘﻐﯿﺮ ارائه گردیده است. ﺟﻬﺖ ارزﯾﺎﺑﯽ روش ﺣﻞ ﭘﯿﺸﻨﻬﺎدی، از ﻧﻤﻮﻧﻪ ﻣﺴﺎﺋﻞ ﮐﺘﺎﺑﺨﺎﻧﻪ ای بهره گرفته و ﺟﻬﺖ ﺷﺒﯿﻪ ﺳﺎزی رﺧﺪاد اﺧﺘﻼل، ﻣﺴﺎﺋﻞ آزﻣﻮن در اﺑﻌﺎد ﺑﺰرگ، ﻣﺘﻮﺳﻂ و ﮐﻮﭼﮏ ﻃﺮاﺣﯽ ﺷﺪه اﻧﺪ. ﻧﺘﺎﯾﺞ ﺑﺪﺳﺖ آﻣﺪه ﺑﯿﺎﻧﮕﺮ آن اﺳﺖ ﮐﻪ در ﺳﻪ دﺳﺘﻪ ﻣﺴﺎﺋﻞ، روش ﻓﺮا اﺑﺘﮑﺎری ﭘﯿﺸﻨﻬﺎدی در ﻣﻘﺎﯾﺴﻪ ﺑﺎ ﺑﻬﺘﺮﯾﻦ روش ﻣﻮﺟﻮد، ﺗﺎ ﺣﺪ ﺑﺴﯿﺎر ﻣﻨﺎﺳﺒﯽ ﺑﻪ آن ﻧﺰدﯾﮏ ﺷﺪه و ﻋﻼوه ﺑﺮ اﯾﻦ، از ﺟﻬﺖ زﻣﺎن ﺣﻞ ﻧﯿﺰ ﺑﺴﯿﺎر ﮐﺎراﺗﺮ از روش ﺣﻞ ﺑﻬﯿﻨﻪ ﺑﻮده و ﭘﺎﺳﺨﮕﻮی ﻧﯿﺎزﻫﺎی آﻧﯽ ﺑﻪ روزآوری ﺗﻮاﻟﯽ ﻋﻤﻠﯿﺎت در ﻣﻮاﺟﻬﻪ ﺑﺎ اﺧﺘﻼﻻت اﯾﺠﺎد ﺷﺪه در ﺧﻂ ﺗﻮﻟﯿﺪ ﺧﻮدرو ﻣﯽﺑﺎشد

Keywords [فارسی]

  • ﺗﻌﯿﯿﻦ ﺗﻮاﻟﯽ ﻋﻤﻠﯿﺎت ماشین سازی
  • اﺧﺘﻼل ﺗﺎﻣﯿﻦ
  • ﺛﺒﺎت
  • روﯾﮑﺮد واﮐﻨﺸﯽ
1-      Boysen N., Fliedner M. and Scholl A., (2009), “Sequencing mixed-model assembly lines: Survey, classification and model critique”, European Journal of Operational Research 192, 2, 349–373.
2-      Boysen, N., Golle, U. and Rothlauf, F. (2011), “The Car Resequencing Problem with Pull-Off Tables”, German Academic Association for Business Research (VHB), Volume 4, Issue 2, 276-292.
3-      Boysen N., Kiel M. and Scholl A., (2011), “Sequencing mixed-model assembly lines to minimize the number of work overload situations”, International Journal of Production Research, 49, 16, 4735-4760.
4-      Boysen N, Scholl A. and Wopperer N. (2012), “Resequencing of mixed-model assembly lines: survey and research agenda”, European Journal of Operational Research, 216(3), 594–604.
5-      Ding F. Y. and He J., (2008), “A heuristic procedure for the automobile assembly-line sequencing problem considering multiple product options”, International Journal of Production Research, 46, 20, 5827–5847.
6-      Ding, F.-Y. and 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, 1525–1543.
7-       Estellon B. and Gardi F., (2013), ”Car sequencing is NP-hard: a short proof”, Journal of the Operational Research Society, 64, 1503–1504.
8-      Fliedner, M. and Boysen, N., (2008),
“Solving the car sequencing problem via branch & bound”, European Journal of Operational Research, 191, 3, 1023– 1042.
9-      Franz C., Hällgren E. C. and Koberstein A., (2014), “Resequencing orders on mixed-model assembly lines: Heuristic approaches to minimize the number of overload situations”, International Journal of Production Research, DOI: 10.1080/00207543. 2014. 918293.
10-  GentI. P. and Walsh T., (1999), “CSPLIB: A benchmark library for constraints”, Technical Report, APES-09-1999, Department of Computer Science, University of Strathclyde, UK.
11-  Gagne C., Gravel M. and Price W. L., (2006), “Solving real car sequencing problems with ant colony optimization”, European Journal of Operational Research, 174, 3, 1427–1448.
12-  Gavranovic H., (2008), “Local search and suffix tree for car sequencing problem with colors”, European Journal of Operational Research, 191, 3, 972-980.
13-  Gottlieb J., Puchta M. and Solnon C., (2003), “A study of greedy, local search and ant colony optimization approaches for car sequencing problems, in: Applications of Evolutionary ComputingLNCS”, 2611, Springer, 246–257.
14-  Grave, M., Gagne, C., and Price, W. L., (2006), “Review and comparison of three methods for the solution of the car equencing problem”, Journal of the Operational Research Society, 56, 11, 1287–1295.
15-  Joly A. and Frein Y., (2008), “Heuristics for an industrial car sequencing problem considering paint and assembly shop objectives”, Computers & Industrial Engineering, 55, 295–310.
16-  Kis, T, (2014), “On the complexity of the car sequencing problem”, Operations Research Letters, 32, 4, 331–335.
17-  Meissner S., (2010),“Controlling just-in-sequence flow-production”, Logistic. Res., 2, 45–53.
18-  Prandtstetter, M. and 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.
19-  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.
20-  Sialaetal M., (2015), “A study of constraint programming heuristics for the car-sequencing problem”, Engineering Applications of Artificial Intelligence, 38, 34–44.
21-  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, 3, 912–927.
22-  Wu, T., Blackhurts, J. and Grady, P.O, (2007), “Methodology for supply chain disruption analysis”, International Journal of Production Research, 45, 1665-1682.
23-  Yavuz M., (2013), “Iterated beam search for the combined car sequencing and level scheduling problem”, International Journal of Production Research, 51, 12, 3698-3718.
24-  Yong-yi Wu and Hai-ping zhu, (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.