Comparing Genetic Algorithm and Variable Neighborhood Search Method for Solving Job Shop Problem

Jana Vugdelija – University of Belgrade, Faculty of Organisational Sciences, Jove Ilića 154, Belgrade, Serbia

Abstract: Job Shop scheduling problem is one of the most complex and researched problems in the field of production planning. In this paper, two methods for solving Job Shop scheduling problem are presented and com­pared. The genetic algorithm and variable neighborhood search method were chosen and implemented in software for solving Job Shop problem. The paper first briefly presents Job Shop scheduling problem and then ex­plains the development of solving software and implementation of selected solution methods. The results of using implemented genetic algorithm and variable neighborhood search method are presented on test instances with various dimensions. Solutions obtained using these two methods were put in comparison and analyzed, as well as compared with the optimal or best-known solutions in the literature.

6th International Scientific Conference on Recent Advances in Information Technology, Tourism, Economics, Management and Agriculture – ITEMA 2022 – Conference Proceedings, Hybrid (University of Maribor, Slovenia), October 27, 2022

ITEMA Conference Proceedings published by: Association of Economists and Managers of the Balkans – Belgrade, Serbia

ITEMA conference partners: Faculty of Economics and Business, University of Maribor, Slovenia; Faculty of Organization and Informatics, University of Zagreb, Varaždin; Faculty of Geography, University of Belgrade, Serbia; Institute of Marketing, Poznan University of Economics and Business, Poland; Faculty of Agriculture, Banat’s University of Agricultural Sciences and Veterinary Medicine ”King Michael I of Romania”, Romania

ITEMA Conference 2022 Conference Proceedings: ISBN 978-86-80194-63-9, ISSN 2683-5991, DOI: https://doi.org/10.31410/ITEMA.2022

Creative Commons Non Commercial CC BY-NC: This article is distributed under the terms of the Creative Commons Attribution-Non-Commercial 4.0 License (https://creativecommons.org/licenses/by-nc/4.0/) which permits non-commercial use, reproduction and distribution of the work without further permission. 

References 

Brinkkötter, W., & Brucker, P. (1999). Solving open benchmark problems for the job shop problem.

Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and job shops scheduling. Mathematics of Operations Research, 1(2), 117–129.

Hansen, P., Mladenović, N., Todosijević, R., & Hanafi, S. (2017). Variable neighborhood search: basics and variants. EURO Journal on Computational Optimization, 5(3), 423-454.

Holland, J. H. (1992), Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, MIT press

Huang, K. L., & Liao, C. J. (2008). Ant colony optimization combined with taboo search for the job shop scheduling problem. Computers & operations research, 35(4), 1030-1046.

Li, J. Q., Pan, Q. K., & Tasgetiren, M. F. (2014). A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Applied Mathematical Modelling, 38(3), 1111-1132.

Li, X., & Gao, L. (2016). An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 174, 93-110.

Liu, S. Q., Kozan, E., (2009), Scheduling trains as a blocking parallel-machine Job Shop sched­uling problem, Computers & Operations Research, 36(10), 2840-2852

Mattfeld, D. C. (2013). Evolutionary Search and the Job Shop: Investigations on Genetic Algo­rithms for Production Scheduling, Springer Science & Business Media.

Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & operations research, 24(11), 1097-1100.

Nouiri, M., Bekrar, A., Jemai, A., Niar, S., & Ammari, A. C. (2018). An effective and distribut­ed particle swarm optimization algorithm for flexible job-shop scheduling problem. Jour­nal of Intelligent Manufacturing, 29(3), 603-615.

Pinedo, L. (2008). Scheduling – theory, algorithms, and systems, Prentice hall.

Saidi-Mehrabad, M., Dehnavi-Arani, S., Evazabadian, F., & Mahmoodian, V. (2015). An Ant Colony Algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs. Computers & Industrial Engineering, 86, 2-13.

Sevkli, M., & Azdin, M. E. (2006), A Variable Neighbourhood Search Algorithm for Job Shop Scheduling Problems, Lecture Notes in Computer Science book series (LNCS, volume 3906).

Shylo, O. V. (2014). Job shop scheduling at Oleg V. Shylo: Personal webpage http://optimizizer.com/TA.php  

Taillard, E. (1993). Benchmarks for Basic Scheduling Problems, European Journal of Opera­tional Research, Vol. 64, No. 2, pp. 278-285.

Turing, A. M. (1950). Computing Machinery and Intelligence, Mind, Vol. 59, No. 236 pp. 433–460.

Zhang, J., Ding, G., Zou, Y., Qin, S., & Fu, J. (2019). Review of job shop scheduling research and its new perspectives under Industry 4.0. Journal of Intelligent Manufacturing, 30(4), 1809-1830.