Inicio  /  Algorithms  /  Vol: 16 Par: 1 (2023)  /  Artículo
ARTÍCULO
TITULO

Improvement of Ant Colony Algorithm Performance for the Job-Shop Scheduling Problem Using Evolutionary Adaptation and Software Realization Heuristics

Pavel V. Matrenin    

Resumen

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?s 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.

 Artículos similares

       
 
Gabriel García-Gutiérrez, Diego Arcos-Aviles, Enrique V. Carrera, Francesc Guinjoan, Emilia Motoasca, Paúl Ayala and Alexander Ibarra    
The main benefits of fuzzy logic control (FLC) allow a qualitative knowledge of the desired system?s behavior to be included as IF-THEN linguistic rules for the control of dynamical systems where either an analytic model is not available or is too comple... ver más
Revista: Applied Sciences