{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T14:16:42Z","timestamp":1773238602836,"version":"3.50.1"},"reference-count":56,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T00:00:00Z","timestamp":1672012800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Ministry of Science and Higher Education of the Russian Federation"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Planning tasks are important in construction, manufacturing, logistics, and education. At the same time, scheduling problems belong to the class of NP-hard optimization problems. Ant colony algorithm optimization is one of the most common swarm intelligence algorithms and is a leader in solving complex optimization problems in graphs. This paper discusses the solution to the job-shop scheduling problem using the ant colony optimization algorithm. An original way of representing the scheduling problem in the form of a graph, which increases the flexibility of the approach and allows for taking into account additional restrictions in the scheduling problems, is proposed. A dynamic evolutionary adaptation of the algorithm to the conditions of the problem is proposed based on the genetic algorithm. In addition, some heuristic techniques that make it possible to increase the performance of the software implementation of this evolutionary ant colony algorithm are presented. One of these techniques is parallelization; therefore, a study of the algorithm\u2019s parallelization effectiveness was made. The obtained results are compared with the results of other authors on test problems of scheduling. It is shown that the best heuristics coefficients of the ant colony optimization algorithm differ even for similar job-shop scheduling problems.<\/jats:p>","DOI":"10.3390\/a16010015","type":"journal-article","created":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T02:53:11Z","timestamp":1672109591000},"page":"15","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Improvement of Ant Colony Algorithm Performance for the Job-Shop Scheduling Problem Using Evolutionary Adaptation and Software Realization Heuristics"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5704-0976","authenticated-orcid":false,"given":"Pavel V.","family":"Matrenin","sequence":"first","affiliation":[{"name":"Ural Power Engineering Institute, Ural Federal University named after the first President of Russia B.N. Yeltsin, 620002 Ekaterinburg, Russia"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/nav.3800010110","article-title":"Optimal two- and three-stage production schedules with setup times included","volume":"1","author":"Johnson","year":"1954","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_2","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. (1989). Sequencing and Scheduling: Algorithms and Complexity, Technische Universiteit Eindhoven."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Brucker, P., and Knust, S. (2012). Complex Scheduling, Springer.","DOI":"10.1007\/978-3-642-23929-8"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1049\/iet-cim.2018.0009","article-title":"Review on flexible job shop scheduling","volume":"1","author":"Xie","year":"2019","journal-title":"IET Collab. Intell. Manuf."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Leusin, M.E., Frazzon, E.M., Uriona Maldonado, M., K\u00fcck, M., and Freitag, M. (2018). Solving the Job-Shop Scheduling Problem in the Industry 4.0 Era. Technologies, 6.","DOI":"10.3390\/technologies6040107"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"105731","DOI":"10.1016\/j.cor.2022.105731","article-title":"A survey of job shop scheduling problem: The types and models","volume":"142","author":"Xiong","year":"2022","journal-title":"Comput. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/j.ejor.2004.03.012","article-title":"A hybrid genetic algorithm for the job shop scheduling problem","volume":"167","author":"Resende","year":"2005","journal-title":"Eur. J. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2968","DOI":"10.1016\/j.cor.2012.02.024","article-title":"Exponentially better than brute force: Solving the job-shop scheduling problem optimally by dynamic programming","volume":"39","author":"Gromicho","year":"2012","journal-title":"Comput. Oper. Res. Arch."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"961","DOI":"10.1007\/s10845-013-0837-8","article-title":"A research survey: Review of AI solution strategies of job shop scheduling problem","volume":"26","author":"Bulkan","year":"2015","journal-title":"J. Intell. Manuf."},{"key":"ref_10","unstructured":"Matrenin, P.V., and Manusov, V.Z. (2022, January 19\u201320). The cyclic job-shop scheduling problem: The new subclass of the job-shop problem and applying the simulated annealing to solve it. Proceedings of the IEEE 2nd International Conference on Industrial Engineering, Applications and Manufacturing (ICIEAM), Chelyabinsk, Russia."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0166-218X(94)90204-6","article-title":"A branch and bound algorithm for job shop scheduling problem","volume":"49","author":"Brucker","year":"1994","journal-title":"Discret. Appl. Math."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1016\/j.cor.2006.05.009","article-title":"Lagrangian bounds for just-in-time job shop scheduling","volume":"35","author":"Baptiste","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1023\/B:JIMS.0000034116.50789.df","article-title":"Fuzzy priority rule for job shop scheduling","volume":"15","author":"Canbolat","year":"2004","journal-title":"J. Intell. Manuf."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/S0377-2217(99)00347-1","article-title":"Bidirectional planning: Improving priority rule-based heuristic for scheduling resource-constrained projects","volume":"127","author":"Klein","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Stastny, J., Skorpil, V., Balogh, Z., and Klein, R. (2021). Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm. Appl. Sci., 11.","DOI":"10.3390\/app11041921"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"3527","DOI":"10.1007\/s00500-021-06481-y","article-title":"Flexible job shop scheduling problem considering machine and order acceptance, transportation costs, and setup times","volume":"26","author":"Ziaee","year":"2022","journal-title":"Soft Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/j.cie.2015.04.006","article-title":"A local search genetic algorithm for the job shop scheduling problem with intelligent agents","volume":"85","author":"Asadzadeh","year":"2015","journal-title":"Comput. Ind. Eng."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.cie.2016.03.011","article-title":"Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem","volume":"96","author":"Kulak","year":"2016","journal-title":"Comput. Ind. Eng."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.cie.2007.04.010","article-title":"A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems","volume":"53","author":"Gao","year":"2007","journal-title":"Comput. Ind. Eng."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Matrenin, P.V., and Sekaev, V.G. (2015, January 21\u201323). Particle Swarm optimization with velocity restriction and evolutionary parameters selection for scheduling problem. Proceedings of the IEEE International Siberian Conference on Control and Communications (SIBCON), Omsk, Russia.","DOI":"10.1109\/SIBCON.2015.7147143"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2791","DOI":"10.1016\/j.cor.2006.12.013","article-title":"An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers","volume":"35","author":"Liu","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.engappai.2007.03.008","article-title":"Ant colony intelligence in multi-agent dynamic manufacturing scheduling","volume":"21","author":"Xiang","year":"2008","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_23","first-page":"157","article-title":"Generalized swarm intelligence algorithms with domain-specific heuristics","volume":"10","author":"Matrenin","year":"2021","journal-title":"IAES Int. J. Artif. Intell."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.cor.2006.02.024","article-title":"A very fast TS\/SA algorithm for the job shop scheduling problem","volume":"35","author":"Zhang","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1109\/4235.585893","article-title":"No free lunch theorems for optimization","volume":"1","author":"Wolpert","year":"1997","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/j.tcs.2005.05.020","article-title":"Ant colony optimization theory: A survey","volume":"344","author":"Dorigo","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Dorigo, M., and St\u00fctzle, T. (2019). Ant colony optimization: Overview and recent advances. Handbook of Metaheuristics, Springer.","DOI":"10.1007\/978-3-319-91086-4_10"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Neroni, M. (2021). Ant Colony Optimization with Warm-Up. Algorithms, 14.","DOI":"10.3390\/a14100295"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Xu, Q., Zhang, L., and Yu, W. (2022). A Localization Method of Ant Colony Optimization in Nonuniform Space. Sensors, 22.","DOI":"10.3390\/s22197389"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.neucom.2018.02.104","article-title":"High-order graph matching based on ant colony optimization","volume":"328","author":"Wu","year":"2019","journal-title":"Neurocomputing"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Al-Shourbaji, I., Helian, N., Sun, Y., Alshathri, S., and Abd Elaziz, M. (2022). Boosting Ant Colony Optimization with Reptile Search Algorithm for Churn Prediction. Mathematics, 10.","DOI":"10.3390\/math10071031"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1016\/j.asoc.2014.10.016","article-title":"A fast hybrid primal heuristic for multiband robust capacitated network design with multiple time periods","volume":"26","author":"Krolikowski","year":"2015","journal-title":"Appl. Soft Comput."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Li, S., Wei, Y., Liu, X., Zhu, H., and Yu, Z. (2022). A New Fast Ant Colony Optimization Algorithm: The Saltatory Evolution Ant Colony Optimization Algorithm. Mathematics, 10.","DOI":"10.3390\/math10060925"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Chen, X., and Dai, Y. (2020, January 12\u201314). Research on an Improved Ant Colony Algorithm Fusion with Genetic Algorithm for Route Planning. Proceedings of the 4th IEEE Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), Electr Network, Chongqing, China.","DOI":"10.1109\/ITNEC48623.2020.9084730"},{"key":"ref_35","unstructured":"Bauer, A., Bullnheimer, B., Richard, F.H., and Strauss, C. (1999, January 6\u20139). An Ant Colony Optimization Approach for the Single Machine Total Tardiness Problem. Proceedings of the Congress on Evolutionary Computation-CEC99, Washington, DC, USA."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/s10951-015-0429-x","article-title":"Ant colony systems for the single-machine total weighted earliness tardiness scheduling problem","volume":"19","author":"Alhajraf","year":"2016","journal-title":"J. Sched."},{"key":"ref_37","unstructured":"Purism, A., Bello, R., Trujillo, Y., Nowe, A.Y., and Mart\u00ednez, Y. (2007, January 13\u201316). Two-Stage ACO to Solve the Job Shop Scheduling Problem. Proceedings of the 12th Iberoamericann Congress on Pattern Recognition (CIARP), Valparaiso, Chile."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/j.procs.2017.08.267","article-title":"A Modified Ant Colony Optimization algorithm for the Distributed Job shop Scheduling Problem","volume":"112","author":"Chaouch","year":"2017","journal-title":"Procedia Comput. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1007\/s00170-008-1404-x","article-title":"Hybridizing tabu search with ant colony optimization for solving job shop scheduling problems","volume":"40","author":"Eswaramurthy","year":"2009","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Tran, L.V., Huynh, B.H., and Akhtar, H. (2019). Ant Colony Optimization Algorithm for Maintenance, Repair and Overhaul Scheduling Optimization in the Context of Industrie 4.0. Appl. Sci., 9.","DOI":"10.3390\/app9224815"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Wang, L., Cai, J., Li, M., and Liu, Z. (2017). Flexible Job Shop Scheduling Problem Using an Improved Ant Colony Optimization. Sci. Program., 9016303.","DOI":"10.1155\/2017\/9016303"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1023\/B:JMMA.0000038614.39977.6f","article-title":"An Ant Colony Optimization Algorithm for Shop Scheduling Problems","volume":"3","author":"Blum","year":"2004","journal-title":"J. Math. Model. Algorithms"},{"key":"ref_43","unstructured":"Da Silva, A.R. (2022, November 20). Solving the Job Shop Scheduling Problem with Ant Colony Optimization. Available online: https:\/\/arxiv.org\/abs\/2209.05284."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"100512","DOI":"10.1016\/j.cosrev.2022.100512","article-title":"Hybridizations of evolutionary algorithms with Large Neighborhood Search","volume":"46","author":"Blum","year":"2022","journal-title":"Comput. Sci. Rev."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-540-73297-6_1","article-title":"Hybrid Evolutionary Algorithms: Methodologies, Architectures, and Reviews","volume":"75","author":"Grosan","year":"2007","journal-title":"Stud. Comput. Intell."},{"key":"ref_46","first-page":"341","article-title":"Topology Optimization of the Network with Renewable Energy Sources Generation Based on a Modified Adapted Genetic Algorithm","volume":"65","author":"Bramm","year":"2022","journal-title":"Energ. Proc. CIS High. Educ. Inst. Power Eng. Assoc."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/s13040-018-0164-x","article-title":"Investigating the parameter space of evolutionary algorithms","volume":"11","author":"Sipper","year":"2018","journal-title":"BioData Min."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/mnsc.34.3.391","article-title":"The shifting bottleneck procedure for job shop scheduling","volume":"34","author":"Adams","year":"1991","journal-title":"Manag. Sci."},{"key":"ref_49","unstructured":"Fisher, H., and Thompson, G. (1963). Probabilistic Learning Combination of Local Job-Shop Scheduling Rules in Industrial Scheduling, Prentice-Hall."},{"key":"ref_50","unstructured":"Lawrence, S. (1984). Supplement to Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques, Carnegie Mellon University. Tech. rep., GSIA."},{"key":"ref_51","first-page":"61","article-title":"Using algorithms for combining heuristics in constructing optimal schedules","volume":"10","author":"Sekaev","year":"2009","journal-title":"Inf. Technol."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1057\/jors.1990.166","article-title":"OR-Library: Distributing test problems by electronic mail","volume":"41","author":"Beasley","year":"1990","journal-title":"J. Oper. Res. Soc."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/j.ejor.2021.03.026","article-title":"Four decades of research on the open-shop scheduling problem to minimize the makespan","volume":"295","author":"Ahmadian","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"3020","DOI":"10.1109\/TASE.2021.3104716","article-title":"Real-Time Scheduling for Dynamic Partial-No-Wait Multiobjective Flexible Job Shop by Deep Reinforcement Learning","volume":"19","author":"Luo","year":"2022","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1109\/JSYST.2020.2990921","article-title":"Modular Reconfigurable Robot Distributed Computing System for Tracking Multiple Objects","volume":"15","author":"Romanov","year":"2021","journal-title":"IEEE Syst. J."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"19286","DOI":"10.1109\/ACCESS.2020.2968378","article-title":"Efficiency-Oriented Production Scheduling Scheme: An Ant Colony System Method","volume":"8","author":"Wan","year":"2020","journal-title":"IEEE Access"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/15\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:51:40Z","timestamp":1760147500000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,26]]},"references-count":56,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["a16010015"],"URL":"https:\/\/doi.org\/10.3390\/a16010015","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,26]]}}}