Розв'язання багатокритеріальної задачі складання розкладу з використанням генетичного алгоритму
Вантажиться...
Дата
2021
DOI
doi.org/10.20998/2522-9052.2021.1.14
Науковий ступінь
Рівень дисертації
Шифр та назва спеціальності
Рада захисту
Установа захисту
Науковий керівник
Члени комітету
Видавець
Національний технічний університет "Харківський політехнічний інститут"
Анотація
Робота присвячена багатокритеріальній задачі складання розкладу, в якій задана множина робіт повинна бути виконана декількома виконавцями різної продуктивності. За виконання роботи відповідному виконавцю нараховується певна кількість бонусів, яка залежить від часу виконання роботи. Критеріями оцінки розкладу є загальний час виконання усіх робіт та кількість витрачених бонусів. В ході проведених досліджень були
проаналізовані основні підходи до розв’язання задач багатокритеріальної оптимізації, на основі яких обрано підхід Парето. В якості алгоритму було обрано генетичний алгоритм. Метою даної роботи є підвищення ефективності розв’язання задач багатокритеріальної оптимізації шляхом реалізації евристичного алгоритму та підвищення його швидкодії. Завданнями роботи є визначення переваг та недоліків підходів, що використовуються для розв’язання задач багатокритеріальної оптимізації, розробка генетичного алгоритму для розв’язання багатокритеріальної задачі складання розкладу та дослідження його ефективності. Розроблені оператори генетичного алгоритму, які враховують особливості досліджуваної задачі, та дозволяють отримувати в процесі роботи розв’язки Парето. Завдяки впровадженню паралельних обчислень в реалізації генетичного алгоритму вдалося підвищити його швидкодію в порівнянні із звичайною версією. Розроблений алгоритм може бути використано при вирішенні задачі оптимального розподілу ресурсів, що є частиною системи нарахування бонусів співробітникам.
The work is devoted to the multiobjective task of scheduling, in which a given set of works must be performed by several performers of different productivity. A certain number of bonuses is accrued for the work performed by the respective executor, which depends on the time of work performance. The criteria for evaluating the schedule are the total time of all jobs and the amount of bonuses spent. In the research the main approaches to s olving multiobjective optimization problems were analyzed, based on which the Pareto approach was chosen. The genetic algorithm was chosen as the algorithm. The purpose of this work is to increase the efficiency of solving multicriteria optimization problems by implementing a heuristic algorithm and increase its speed. The tasks of the work are to determine the advantages and disadvantages of the approaches used to solve multicriteria optimization problems, to develop a genetic algorithm for solving the multicriteria scheduling problem and to study its efficiency. Operators of the genetic algorithm have been developed, which take into account the peculiarities of the researched problem and allow to obtain Pareto solutions in the process of work. Due to the introduction of parallel calculations in the implementation of the genetic algorithm, it was possible to increase its speed compared to the conventional version. The developed algorithm can be used in solving the problem of optimal allocation of resources, which is part of the system of accrual of bonuses to employees.
The work is devoted to the multiobjective task of scheduling, in which a given set of works must be performed by several performers of different productivity. A certain number of bonuses is accrued for the work performed by the respective executor, which depends on the time of work performance. The criteria for evaluating the schedule are the total time of all jobs and the amount of bonuses spent. In the research the main approaches to s olving multiobjective optimization problems were analyzed, based on which the Pareto approach was chosen. The genetic algorithm was chosen as the algorithm. The purpose of this work is to increase the efficiency of solving multicriteria optimization problems by implementing a heuristic algorithm and increase its speed. The tasks of the work are to determine the advantages and disadvantages of the approaches used to solve multicriteria optimization problems, to develop a genetic algorithm for solving the multicriteria scheduling problem and to study its efficiency. Operators of the genetic algorithm have been developed, which take into account the peculiarities of the researched problem and allow to obtain Pareto solutions in the process of work. Due to the introduction of parallel calculations in the implementation of the genetic algorithm, it was possible to increase its speed compared to the conventional version. The developed algorithm can be used in solving the problem of optimal allocation of resources, which is part of the system of accrual of bonuses to employees.
Опис
Ключові слова
евристика, фронт Парето, heuristics, Pareto front
Бібліографічний опис
Розв'язання багатокритеріальної задачі складання розкладу з використанням генетичного алгоритму / А. В. Казмірчук [та ін.] // Сучасні інформаційні системи = Advanced Information Systems. – 2021. – Т. 5, № 1. – С. 100-107.