Improvement of Ant Colony Algorithm Performance for the Job-Shop Scheduling Problem Using Evolutionary Adaptation and Software Realization Heuristics
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
Improvement of Ant Colony Algorithm Performance for the Job-Shop Scheduling Problem Using Evolutionary Adaptation and Software Realization Heuristics
|
|
| Автор |
Matrenin, P. V.
|
|
| Тематика |
ANT COLONY OPTIMIZATION
GENETIC ALGORITHM JOB-SHOP SCHEDULING PROBLEM MULTIPHASIC SYSTEMS PARALLEL COMPUTING ANT COLONY OPTIMIZATION ARTIFICIAL INTELLIGENCE HEURISTIC METHODS JOB SHOP SCHEDULING ALGORITHM PERFORMANCE ANT COLONIES ALGORITHM ANT COLONY OPTIMIZATION ALGORITHMS EVOLUTIONARY ADAPTATION JOB SHOP SCHEDULING PROBLEMS MULTIPHASIC SYSTEM PARALLEL COM- PUTING PARALLELIZATIONS PLANNING TASKS SCHEDULING PROBLEM GENETIC ALGORITHMS |
|
| Описание |
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. © 2022 by the author.
Ministry of Education and Science of the Russian Federation, Minobrnauka The research funding from the Ministry of Science and Higher Education of the Russian Federation (Ural Federal University Program of Development within the Priority-2030 Program) is gratefully acknowledged. |
|
| Дата |
2024-04-05T16:35:23Z
2024-04-05T16:35:23Z 2023 |
|
| Тип |
Article
Journal article (info:eu-repo/semantics/article) |info:eu-repo/semantics/publishedVersion |
|
| Идентификатор |
Matrenin, PV 2023, 'Improvement of Ant Colony Algorithm Performance for the Job-Shop Scheduling Problem Using Evolutionary Adaptation and Software Realization Heuristics', Algorithms, Том. 16, № 1, 15. https://doi.org/10.3390/a16010015
Matrenin, P. V. (2023). Improvement of Ant Colony Algorithm Performance for the Job-Shop Scheduling Problem Using Evolutionary Adaptation and Software Realization Heuristics. Algorithms, 16(1), [15]. https://doi.org/10.3390/a16010015 1999-4893 Final All Open Access, Gold https://www.scopus.com/inward/record.uri?eid=2-s2.0-85146727253&doi=10.3390%2fa16010015&partnerID=40&md5=c67f1e05696ac80591808164ae744668 https://www.mdpi.com/1999-4893/16/1/15/pdf?version=1672052900 http://elar.urfu.ru/handle/10995/130914 10.3390/a16010015 85146727253 000914298000001 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
cc-by https://creativecommons.org/licenses/by/4.0/ |
|
| Формат |
application/pdf
|
|
| Издатель |
MDPI
|
|
| Источник |
Algorithms
Algorithms |
|