Buffer management in solving a real sequencing problem in the automotive industry – Paint Shop 4.0 concept

• Autorzy: Bysko Sara , Krystek Jolanta , Bysko Szymon , Lenort Radim

Identyfikatory

DOI

10.24425/acs.2019.130203

• Języki publikacji: EN

Abstrakty

EN

The paper presents a Car Sequencing Problem, widely considered in the literature. The issue considered by the researchers is only a reduced problem in comparison with the problem in real automotive production. Consequently, a new concept, called Paint Shop 4.0., is considered from the viewpoint of a sequencing problem. The paper is a part of the previously conducted research, identified as Car Sequencing Problem with Buffers (CSPwB), which extended the original problem to a problem in a production line equipped with buffers. The new innovative approach is based on the ideas of Industry 4.0 and the buffer management system. In the paper, sequencing algorithms that have been developed so far are discussed. The original Follow-up Sequencing Algorithm is presented, which is still developed by the authors. The main goal of the research is to find the most effective algorithm in terms of minimization of painting gun changeovers and synchronization necessary color changes with periodic gun cleanings. Carried out research shows that the most advanced algorithm proposed by the authors outperforms other tested methods, so it is promising to be used in the automotive industry.

Słowa kluczowe

EN

sequencing; car production; paint shop; buffer management; changeovers

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2019
• Tom: Vol. 29, No. 3
• Strony: 507--527
• Opis fizyczny: Bibliogr. 51 poz., rys., wzory

Twórcy

autor

Bysko Sara

• The Faculty of Automatic Control, Electronics and Computer Science, Silesian University of Technology, Gliwice, Poland

autor

Krystek Jolanta

• The Faculty of Automatic Control, Electronics and Computer Science, Silesian University of Technology, Gliwice, Poland

autor

Bysko Szymon

• ProPoint Sp. z o. o. Sp. k., Gliwice, Poland

autor

Lenort Radim

• SKODA AUTO University, Czech Republic

Bibliografia

• [1] S. Alszer, J. Krystek, and S. Bysko: Simulation and virtual commissioning for intelligent buffer control system – case study. Proceedings of 2nd International Conference on Robotics and Automation Engineering (ICRAE 2017), Shanghai, China (2017), 207–211. doi: 10.1109/ICRAE.2017.8291381.
• [2] S. Alszer, J. Krystek, and S. Bysko: Complex Approach to the Control of Car Body Buffering in the Paint Shop. Automation 2018. Advances in Automation, Robotics and Measurement Techniques (2018), 152–161. doi: 10.1007/978-3-319-77179-3_14.
• [3] S. Alszer and J. Krystek: Car Sequencing Problem – confrontation with real automotive industry. CLC 2017 – Carpathian Logistics Congress – Congress Proceedings, Liptovsky Jan, Slovakia (2017), 240–245.
• [4] J. Bautista, J. Pereira, and B. Adenso-Diaz: A Beam Search approach for the optimization version of the Car Sequencing Problem. Annals of Operations Research, 159(1), (2008), 233–244. doi: 10.1007/s10479-007-0278-x.
• [5] J. Bautista, J. Pereira, and B. Adenso-Diaz: A GRASP approach for the extended car sequencing problem. Journal of Scheduling, 11(1), (2008), 3–16. doi: 10.1007/s10951-007-0046-4.
• [6] M. E. Bergen, P. Van Beek, and T. Carchrae: Constraint-based vehicle assembly line sequencing. Proceedings of the 14th Canadian Conference on Artificial Intelligence (2011), 88–99. doi: 10.1007/3-540-45153-6_9.
• [7] V. Chankong and Y. Y Haimes: Multiobjective Decision Making: Theory and Methodology. System Science and Engineering, North-Holland, Amsterdam, 1983.
• [8] J. Cheng, Y. Lu, G. Puskorius, S. Bergeon, and J. Xiao: Vehicle sequencing based on evolutionary computation. Evolutionary Computation (CEC 99), 2 (1999), 1207–1214. doi: 10.1109/CEC.1999.782573.
• [9] T. L. Chew, J. M. David, A. Nguyen and Y. Tourbier: Solving constraint satisfaction problems with simulated annealing: The car sequencing problem revisited. Proceedings of the International Workshop on Expert System & Their Applications, Avigon, France (1992), 405–416.
• [10] Ph. Codognet and D. Diaz: Compiling constraints in clp(FD). Journal of Logic Programming, 27(3), (1996), 185–226. doi: 10.1016/0743-1066(95)00121-2.
• [11] F. Cordeau, G. Laporte, and F. Pasin: Iterated tabu search for the car sequencing problem. European Journal of Operational Research, 191(3), (2008), 945–965. doi: 10.1016/j.ejor.2007.04.048.
• [12] A. J. Davenport, E. P. K. Tsang, C. Wang, and K. Zhu: Genet: a connectionist architecture for solving constraint satisfaction problems by iterative improvement. Proceedings of AAAI’94, Seattle, Washington (1994), 325–330.
• [13] A. J. Davenport and E. P. K. Tsang: Solving constraint satisfaction sequencing problems by iterative repair. Proceedings of The First International Conference on The Practical Application of Constraint Technologies and Logic Programming (PACLP), Blackpool, England, (1999), 345–357.
• [14] M. Dincbas, H. Simonis, and P. Van Hentenryck: Solving the car-sequencing problem in constraint logic programming. Proceedings of ECAI-88, Munich, Germany, (1988), 290–295.
• [15] A. Drexl and A. Kimms: Sequencing jit mixed-model assembly lines under station load and part-usage constraints. Management Science, 47(3), (2001), 480–491. doi: 10.1287/mnsc.47.3.480.9777.
• [16] A. Drexl, A. Kimms, and L. Matthiessen: Algorithms for the car sequencing and the level scheduling problem. Journal of Scheduling, 9(2), (2006), 153–176. doi: 10.1007/s10951-006-7186-9.
• [17] M. Fertsch and P. Pawlewski: Changes simulation in the organization of production – case study. Proceedings of the 2009 Winter Simulation Conference, Austin, Texas (2009), 2225–2230.
• [18] M. Fliedner and N. Boysen: Solving the car sequencing problem via Branch & Bound. European Journal of Operational Research, 191(3), 2008, 1023–1042. doi: 10.1016/j.ejor.2007.04.045.
• [19] I. P. Gent: Two results on car–sequencing problems. Technical Report APES-02-1998, University of St. Andrews, 1998.
• [20] P. Golińska, M. Fertsch, and P. Pawlewski: Production flow control in automotive industry – quick scan approach. International Journal of Production Research, (2011), 1–25. doi: 10.1080/00207543.2010.536180.
• [21] U. Golle, F. Rothlauf, and N. Boysen: Iterative Beam Search for Car Sequencing. Working Papers in Information Systems and Business Administration, Paper Working Paper 02/2011. Johannes Gutenberg-University, Mainz, 2011.
• [22] J. Gottlieb, M. Puchta, and C. Solnon: A study of greedy, local search and ant colony optimization approaches for car sequencing problems. Proceedings of Evo Workshops (2003), 246–257. doi: 10.1007/3-540-36605-9_23.
• [23] M. Gravel, C. Gagne, and W. L. Price: Review and comparison of three methods for the solution of the car-sequencing problem. Journal of the Operational Research Society, 56(11), (2005), 1287–1295. doi: 10.1057/palgrave.jors.2601955.
• [24] Ł. Hadas, P. S. Cyplik, and M. Fertsch: Method Of Buffering Critical Resources in Make-to-Order Shop Floor Control in Manufacturing Complex Products. International Journal of Production Research, 47(8), (2009), 2125–2139.
• [25] P. van Hentenryck, H. Simonis, and M. Dincbas: Constraint satisfaction using constraint logic programming. Artificial Intelligence, 58(1-3), (1992), 113–159. doi: 10.1016/0004-3702(92)90006-J.
• [26] K. S. Hindi and M. G. Ploszajski: Formulation and solution of a selection and sequencing problem in car manufacture. Computers and Industrial Engineering, 26(1), (1994), 203–211. doi: 10.1016/0360-8352(94)90038-8.
• [27] W. J. Van Hoeve, G. Pesant, L. M. Rousseau, and A. Sabharwal: Revisiting the sequence constraint. 12th International Conference on Principles and Practice of Constraint Programmaing (CP’2006), (2006), 620–634.
• [28] A. Jaszkiewicz, P. Kominek and M. Kubiak: Adaptation of the Genetic Local Search Algorithm to a Car Sequencing Problem. Proceedings of the 7th National Conference on Evolutionary Algorithms and Global Optimization, Kazimierz Dolny, Poland (2004), 67–74.
• [29] T. Kis: On the complexity of the car sequencing problem. Operations Research Letters, 32(4), (2004), 331–335. doi: 10.1016/j.orl.2003.09.003.
• [30] L. S. C. Koh and S. M. Saad: How Uncertainty Disturbs SME Manufacturers. Proceedings of 17th ICPR (2003), Virginia, Blacksburg.
• [31] J. Krystek and S. Alszer: Contemporary aspects of car sequencing problem in a paint shop. Mechanik, 7, (2017), 527–529. doi: 10.17814/mechanik.2017.7.67
• [32] J. Krystek and S. Alszer: The role of buffer warehouses in selected production systems. In ICIL 2016 Conference Proceedings, Zakopane, Poland, (2016), 119–127.
• [33] J. H. M. Lee, H. F. Leung and H. W. Won: Performance of a comprehensive and efficient constraint library based on local search. Proceedings of 11th Australian JCAI, (1998), 191–202. doi: 10.1007/BFb0095052.
• [34] L. Michel and P. Van Hentenryck: A constraint-based architecture for local search. OOPSLA ’02: Proceedings of the 17th ACM SIGPLAN Conference on Object oriented programming, systems, languages, and applications, Seattle, Washington, (2002), 83–100. New. doi: 10.1145/582419.582430.
• [35] E. Michlowicz: Improving the efficiency and reliability of material flow in buffered systems. Scientific Journals of the Maritime University of Szczecin, 42(114), (2015), 26–32.
• [36] S. Minton, M.D. Johnston, A.B. Philips and P. Laird: Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 58, (1992), 161–205. doi: 10.1016/0004-3702(92)90007-K.
• [37] B. Neveu, G. Trombettoni and F. Glover: Id walk: A candidate list strategy with a simple diversification device. Proceedings of International Conference on Principles and Practice of Constraint Programming CP’2004, (2004), 423–437. doi: 10.1007/978-3-540-30201-8_32.
• [38] B. D. Parello, W. C. Kabat and L. J. Wos: Job-shop scheduling using automated reasoning: a case study of the car sequencing problem. Journal of Automated Reasoning, 2(1), (1986), 1–42. doi: 10.1007/BF00246021.
• [39] L. Perron and P. Shaw: Combining forces to solve the car sequencing problem. Proceedings of CP-AI-OR’2004, (2004), 225–239. doi: 10.1007/978-3-540-24664-0_16.
• [40] M. Puchta and J. Gottlieb: Solving car sequencing problems by local optimization. Proceedings of EvoWorkshops, (2002), 132–142. doi: 10.1007/3-540-46004-7_14.
• [41] J. C. Regin and J. F. Puget: A filtering algorithm for global sequencing constraints. In Proceedings of International Conference on Principles and Practice of Constraint Programming CP’1997, (1997), 32–46. doi: 10.1007/BFb0017428.
• [42] R. J. O. dos Reis: Solving the Car Sequencing Problem from a Multiobjective Perspective. PhD thesis, Universidade Tecnica de Lisboa, Lisbonne, 2007.
• [43] M. Risler, M. Chiarandini, L. Paquete, T. Schiavinotto, and T. Stutzle: An algorithm for the car sequencing problem of the ROADEF 2005 challenge. Technical Report AIDA–04–06, (2004). Germany: FG Intellektik, TU Darmstadt, Darmstadt, 2004.
• [44] S. Solnon: Solving permutation constraint satisfaction problems with artificial ants. textit Proceedings of ECAI’2000, (2000), 118–122.
• [45] C. Solnon, V. D. Cung, A. Nguyen, and C. Artigues: 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), (2008), 912–927. doi: 10.1016/j.ejor.2007.04.033.
• [46] S. Spieckermann, K. Gutenschwanger, and S. Voss: A sequential ordering problem in automotive paint shops. International Journal of Production Research, 42(9), (2004), 1865–1878.
• [47] T. Stutzle and H. H. Hoos: MAX-MIN Ant System. Journal of Future Generation Computer Systems, 16, (2000), 889–914. doi: 10.1016/S0167-739X(00)00043-1.
• [48] D. Thiruvady, B. Meyer, and A. T. Ernst: Car Sequencing with Constraint-Based ACO. Proceedings of 2011 Genetic and Evolutionary Computation Conference (GECCO’2011), (2011), 163–170. doi: 10.1145/2001576.2001599.
• [49] J. B. Valdondo and J. P. Gude: Sequencing JIT Mixed Model Assembly Lines Under Station-Load and Part-Usage Constraints using Lagrangean Relaxations. Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2007), (2007), 550–552. doi: 10.13140/RG.2.2.29497.77920.
• [50] T. Warwick and E. Tsang: Tackling car sequencing problems using a genetic algorithm. Journal of Evolutionary Computation – MIT Press, 3(3), (1995), 267–298. doi: 10.1162/evco.1995.3.3.267.
• [51] N. Zufferey, M. Studer, and E. A. Silver: Tabu search for a car sequencing problem. Proceedings of the 19th International Florida Artificial Intelligence Research Society Conference (FLAIRS 2006), (2006), 457–462. doi: 10.1007/978-3-319-23350-5_8.

Uwagi

EN

1. This is an open-access article distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives License (CC BY-NC-ND 3.0 https://creativecommons.org/licenses/by-nc-nd/3.0/), which permits use, distribution, and reproduction in any medium, provided that the article is properly cited, the use is non-commercial, and no modifications or adaptations are made

PL

2. Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).