Tabu Search and genetic algorithm for production process scheduling problem

• Autorzy: Burduk Anna , Musiał Kamil , Kochańska Joanna , Górnicka Dagmara , Stetsenko Anastasia

Identyfikatory

DOI

10.17270/J.LOG.2019.315

Warianty tytułu

PL

Tabu Search i algorytmy genetyczne w harmonogramowaniu procesów produkcyjnych

• Języki publikacji: EN

Abstrakty

EN

Background: The paper deals with production process scheduling problem. In large companies, the decision-making process about operators' work, machines availability and production flow is a very difficult task, which is often being done by employees. Thus, not always the decision made is optimal in terms of cost, production time, etc. Methods: As a solution, two intelligent methods: Tabu Search and the genetic algorithm have been analyzed in field of production scheduling. The aim of this work was to examine the possibility of improving presented decision-making process that is being performed when scheduling, using Tabu Search and genetic algorithms. As a result of experimental research, it has been confirmed that the use of appropriately selected and parameterized intelligent methods allows for the optimization of the analyzed production process due to its duration. The research was case of study performed in cooperation with company that produces components for automotive industry. Results: Basing on collected and analyzed data, considered methods can be more or less successfully used in production process scheduling. Comparing both used algorithms, Tabu Search twice proposed worse solutions, the average operational time was 1.63% shorter than the actual one. In this case, better results were reached by using genetic algorithm - potential operational time was always shorter than the actual one, and it was reduced by 6.3% in total on average. Conclusion: Using algorithms allowed to achieve lower workload of employees and to reduce of operational time, which were the evaluation criteria in performed research. Managers of the analyzed company were pleased with the proposed solution and declared interest in developing these methods for future. This shows that intelligent methods can find, in relatively short time, the solution that is close to the optimal and acceptable from the problem point of view.

PL

Wstęp: Artykuł opisuje problem harmonogramowania procesów produkcyjnych. W dużych przedsiębiorstwach proces podejmowania decyzji dotyczących pracy operatorów, maszyn, dostępności zasobów i przepływu produkcji jest bardzo złożonym zadaniem, często wykonywanym przez pracowników. W związku z tym podjęte decyzje nie zawsze są optymalne w kontekście kosztów, czasu produkcji itp. Metody: Jako rozwiązanie, przeanalizowane zostało użycie, w obszarze harmonogramowania produkcji, dwóch metod inteligentnych: Tabu Search i algorytmów genetycznych. Celem pracy było zbadanie możliwości doskonalenia procesu podejmowania decyzji, który jest wykonywany przy harmonogramowaniu produkcji, przy pomocy Tabu Search i algorytmów genetycznych. Jako wynik eksperymentu przeprowadzonego podczas badań, potwierdzono, że użycie odpowiednio wybranych oraz sparametryzowanych metod inteligentnych pozwala na optymalizację analizowanego procesu produkcji. Badania zostały wykonane we współpracy z przedsiębiorstwem zajmującym się produkcją komponentów dla branży motoryzacyjnej, jako studium przypadku. Wyniki: Zgodnie z zebranymi i przeanalizowanymi danymi, wybrane metody mogą być z mniejszym bądź większym powodzeniem stosowane w procesie harmonogramowania produkcji. Porównując zastosowane algorytmy, Tabu Search dwukrotnie zaproponował rozwiązanie gorsze od aktualnego podejścia przedsiębiorstwa, jednak czas produkcji został skrócony średnio o 1.63%. W tym przypadku, lepsze wyniki pozwoliło osiągnąć zastosowanie algorytmu genetycznego - potencjalny czas produkcji był zawsze krótszy od aktualnie stosowanego rozwiązania, a średni czas produkcji został zredukowany o 6.3%. Wnioski: Zastosowanie algorytmów pozwoliło na osiągnięcie niższego obciążenia pracą operatorów oraz zredukowanie czasu operacyjnego, co stanowiło kryteria oceny w przeprowadzonych badaniach. Kierownictwo analizowanego przedsiębiorstwa było zadowolone z zaproponowanych rozwiązań. Zdecydowali się na stosowanie omawianych metod w codziennym harmonogramowaniu produkcji oraz zadeklarowali zainteresowanie rozwojem stosowania metod w przyszłości. Metody inteligentne pozwalają znaleźć, w relatywnie krótkim czasie, rozwiązanie bliskie optymalnemu i akceptowalne z punktu widzenia analizowanego problemu.

Słowa kluczowe

EN

production process scheduling; Tabu Search; genetic algorithm; heuristic methods; intelligent methods; manufacturing

PL

harmonogramowanie procesów produkcyjnych; Tabu Search; algorytm genetyczny; metody heurystyczne; metody inteligentne; wytwarzanie

• Wydawca: Wyższa Szkoła Logistyki
• Czasopismo: LogForum
• Rocznik: 2019
• Tom: Vol. 15, no. 2
• Strony: 181--189
• Opis fizyczny: Bibliogr. 25 poz., rys., wykr.

Twórcy

autor

Burduk Anna

• Wroclaw University of Science and Technology, Faculty of Mechanical Engineering, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Musiał Kamil

• Wroclaw University of Science and Technology, Faculty of Mechanical Engineering, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Kochańska Joanna

• Wroclaw University of Science and Technology, Faculty of Mechanical Engineering, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Górnicka Dagmara

• Wroclaw University of Science and Technology, Faculty of Mechanical Engineering, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Stetsenko Anastasia

• The National University of Water and Environmental Engineering, Institute of Automation, Cybernetics and Computer Engineering, 11 Soborna St., 33028, Rivne city, Ukraine

Bibliografia

• 1. Ahmad R., Tichadou S., Hascoet J.Y., 2017. A knowledge-based intelligent decision system for production planning, The International Journal of Advanced Manufacturing Technology, 89 (5-8), 1717-172, http://doi.org/10.1007/s00170-016-9214-z.
• 2. Antosz, K., Stadnicka, D., 2014. The results of the study concerning the identification ofthe activities realized in the management of the technical infrastructure in large enterprises, Eksploatacja i. Niezawodność - Maintenance and Reliability, 16 (1), 112-119.
• 3. Bentley P.J., Wakefield J.P., 1998. Finding acceptable solutions in the Pareto-Optimal Range using multiobjective genetic algorithms, in Chawdhry P.K., Roy R., Pant R.K. (Ed.), Soft Computing in Engineering Design and Manufacturing, Springer, London, 231-240. http://doi.org/10.1007/978-1-4471-0427-8_25.
• 4. Bożejko W., Grymin R., Pempera J., 2017. Scheduling and Routing Algorithms for Rail Freight Transportation, Procedia Engineering, 178, 206-212, http://doi.org/10.1016/j.proeng.2017.01.098
• 5. Bożejko W., Pempera J., Smutnicki A., 2008. Parallel Single-Thread Strategies in Schedu-ling, in Rutkowski L., Tadeusiewicz R., Zadeh L.A., Zurada J.M. (Ed.), Artificial Intelligence and Soft Computing, ICAISC 2008, Lecture Notes in Computer Science, 5097, Springer, Berlin, Heidelberg, 995-1006, http://doi.org/10.1007/978-3-540-69731-2_94.
• 6. Bożejko, W., Uchroński, M., Wodecki, M., 2016. Parallel tabu search algorithm with uncertain data for the flexible job shop problem, in Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, Lotfi A., Zurada, Jacek M. (Ed.), ICAISC 2016, LNCS, 9693, Springer, Cham, 419-428, http://doi.org/10.1007/978-3-319-39384-1_36.
• 7. Burduk A., Musiał K., 2016. Optimization of chosen transport task by using genetic algorithms, in Saeed K., Homenda W. (Ed.), CISIM 2016, LNCS, 9842, Springer, Cham, 197-205 http://doi.org/10.1007/978-3-319-45378-1_18.
• 8. Burgy R., Bulbul K., 2018. The job shop scheduling problem with convex costs, European Journal of Operational Research, 268 (1), 82-100, http://doi.org/10.1016/j.ejor.2018.01.027.
• 9. Chen L., Jansen K., Zhang G., 2018. On the optimality of exact and approximation algorithms for scheduling problems, Journal of Computer and System Sciences, 96, 1-32 http://doi.org/10.1016/j.jcss.2018.03.005.
• 10. Dorigo, M., 1992, Optimization, learning and natural algorithms, Ph.D. thesis, Politecnico di Milano, Italy.
• 11. Gdowska K., Książek R., 2017. A random search algorithm for cyclic delivery synchronization problem, Logforum, 13 (3), 263-272, http://doi.org/10.17270/J.LOG.2017.3.2.
• 12. Gola A., Kłosowski G., 2018. Application of fuzzy logic and genetic algorithms in automated works transport organization, in Omatu S., Rodríguez S., Villarrubia G., Faria P., Sitek P., Prieto J. (Ed.), DCAI 2017, AISC, 620, Springer, Cham, 29-36, http://doi.org/10.1007/978-3-319-62410-5_4.
• 13. Górnicka D., Markowski M., Burduk A., 2018. Optimization of production organization in a packaging company by ant colony algorithm, in Burduk A., Mazurkiewicz D. (Ed.), ISPEM 2017, AISC, 637, Springer, Cham, 336-346, http://doi.org/10.1007/978-3-319-64465-3_33.
• 14. Grajek M., Zmuda-Trzebiatowski P., 2014. A heuristic approach to the daily delivery scheduling problem. Case study: alcohol products delivery scheduling within intracommunity trade legislation, Logforum, 10 (2), 163-173.
• 15. Ho W., Xu X., Dey P.K., 2010. Multi-criteria decision making approaches for supplier evaluation and selection: A literaturę review, European Journal of Operational Research, 202 (1), 16-24, http://doi.org/10.1016/j.ejor.2009.05.009.
• 16. Kalinowski K., Skołud B., 2017. The Concept of Ant Colony Algorithm for Scheduling of Flexible Manufacturing Systems, in Graña M., López-Guede J., Etxaniz O., Herrero Á., Quintián H., Corchado E. (Ed.), ICEUTE/SOCO/CISIS 2016. AISC, 527, Springer, Cham, 408-415, http://doi.org/10.1007/978-3-319-47364-2_39.
• 17. Kazemi A., Fazel Zarandi M.H., Moattar Husseini S.M., 2009. A multi-agent system to solve the production-distribution planning problem for a supply chain: a genetic algorithm approach, The International Journal of Advanced Manufacturing Technology, 44 (1-2), 180-193, http://doi.org/10.1007/s00170-008-1826-5.
• 18. Kotowska J., Markowski M., Burduk A., 2018. Optimization of the Supply of Components for Mass Production with the Use of the Ant Colony Algorithm, in Burduk A., Mazurkiewicz D. (Ed.), ISPEM 2017, AISC, 637, Springer, Cham, 347-357, http://doi.org/10.1007/978-3-319-64465-3_34.
• 19. Krenczyk, D., Skołud, B., 2014. Transient states of cyclic production planning and control, Appl. Mech. Mater., 657, 961-965, http://doi.org/10.4028/www.scientific.net/A MM.657.961.
• 20. Kumanan S., Jegan Jose, G., Raja, K., 2006. Multi-project scheduling using an heuristic and a genetic algorithm, 31 (3-4), 360-366, http://doi.org/10.1007/s00170-005-0199-2.
• 21. Musiał K., Kotowska J., Górnicka D., Burduk A., 2017. Tabu Search and Greedy Algorithm Adaptation to Logistic Task, in Saeed K., Homenda W., Chaki R. (Ed.), CISIM 2017, LNCS, 10244, Springer, Cham, 39-49, http://doi.org/10.1007/978-3-319-59105-6_4.
• 22. Paprocka I., Gwiazda A., Baczkowicz M., 2017. Scheduling of an assembly process of a chosen technical mean using the critical chain approach, MATEC Web of Conferences, 94, http://doi.org/10.1051/matecconf/20179406015
• 23. Shishido H.Y., Estrella J.C., Toledo C.F.M., Arantes M.S., 2018. Genetic-based algorithms applied to a workflow scheduling algorithm with security and deadline constraints in clouds, Computers & Electrical Engineering, 69, 378-394, http://doi.org/10.1016/j.compeleceng.2017.12.004.
• 24. Tuncer A., Yildirim M., 2012. Dynamic path planning of mobile robots with improved genetic algorithm, Computers & Electrical Engineering, 38 (6), 1564-1572, http://doi.org/10.1016/j.compeleceng.2012.06.016.
• 25. Zwolińska B., Grzybowska K., Kubica L., 2017. Shaping Production Change Variability In Relation To The Utilized Technology, Proceedings - 24th International Conference On Production Research (ICPR 2017) 51-56, http://doi.org/10.12783/dtetr/icpr2017/17582.

Uwagi

PL

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