Важкорозв’язувані задачі комбінаторної оптимізації та теорія ПДС-алгоритмів
| dc.contributor.advisor | Павлов, О. А. | |
| dc.contributor.advisor | Pavlov, Alexander A. | |
| dc.date.accessioned | 2024-03-18T17:05:02Z | |
| dc.date.available | 2024-03-18T17:05:02Z | |
| dc.date.issued | 2019 | |
| dc.description.abstract | Робота є продовженням циклу робіт з розвитку теорії ПДС-алгоритмів і створення на її основі моделей і методів календарного та оперативного планування та прийняття рішень в складних соціально-економічних системах з мережевим представленням технологічних процесів та обмеженими ресурсами. Мета роботи – розвиток авторської теорії та методології побудови ПДС-алгоритмів для важкорозв’язуваних задач комбінаторної оптимізації (ВЗКО – задачі, для яких не існує поліноміальних алгоритмів розв’язання) та створення на їх основі високоефективних методів розв’язання досліджуваних задач календарного та оперативного планування. ПДС-алгоритми включають поліноміальну складову, яка строго реалізує оптимальний розв’язок, і точний експоненціальний підалгоритм або поліноміальну апроксимацію точного алгоритму (наближений або евристичний алгоритм). Перевагою ПДС-алгоритмів перед існуючими методами є те, що на їх основі можна побудувати для задач великої розмірності як точні, так і наближені алгоритми з оцінками якості отриманих розв’язків або евристичні алгоритми. На основі теорії ПДС-алгоритмів у роботі створено нові методи та ефективні ПДСалгоритми для п’яти ВЗКО, зокрема, для двох з шості найбільш складних та відомих в світі класичних ВЗКО – NP-трудних в сильному розумінні задач мінімізації сумарного зваженого моменту закінчення завдань на одному приладі з відношенням передування та мінімізації сумарного зваженого запізнення завдань на одному приладі. Також досліджено ефективність чотирьох інших ПДС-алгоритмів. Створені ПДС-алгоритми включено до математичного та програмного забезпечення розробленої у попередніх роботах чотирьохрівневої моделі календарного та оперативного планування в системах з мережним представленням технологічних процесів та обмеженими ресурсами. У результаті створено інформаційну технологію та новий інтегрований пакет програм календарного та оперативного планування в соціально-економічних системах у різних прикладних областях. | |
| dc.description.abstractother | The work continues a series of works devoted to the development of the theory of PSCalgorithms and to the creation on its basis of models and methods of scheduling, operational planning, and decision-making in complex socio-economic systems with a network representation of technological processes and limited resources. The purpose of the work is to develop the authors’ theory and methodology for PSC-algorithms constructing for intractable problems of combinatorial optimization (IPCO – problems for which there are no polynomial time solving algorithms) and to create on their basis highly efficient methods to solve the studied scheduling and operational planning problems. PSC-algorithms include the polynomial component that builds a strictly optimal solution and the exact exponential subalgorithm or the polynomial approximation of the exact algorithm (approximation or heuristic algorithm). The advantage of PSC-algorithms over existing methods is that they can be used to construct, for large-scale problems, both exact and approximation algorithms with estimates of the deviation of obtained solutions from the optimum, or heuristic algorithms. In this work, based on the theory of PSC-algorithms, we have created new methods and efficient PSC-algorithms for five IPCO, in particular, for two of the six most complex and worldwide-known classical IPCO: NP-hard in the strong sense problems of the total weighted completion time of jobs minimization on one machine with a precedence relations and the total weighted tardiness of jobs minimization on one machine. We also investigated the efficiency of four other PSC-algorithms. Then we included the created PSC-algorithms into the mathematics and software of the four-level model of scheduling and operational planning in systems with network representation of technological processes and limited resources which we developed in the previous works. As a result, we have created an information technology and a new integrated software package for scheduling and operational planning in socio-economic systems in various fields of application. | |
| dc.format.extent | 6 с. | |
| dc.identifier.govdoc | 0117U000460 | |
| dc.identifier.other | 2034 | |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/65603 | |
| dc.language.iso | uk | |
| dc.publisher | КПІ ім. Ігоря Сікорського | |
| dc.publisher.place | Київ | |
| dc.title | Важкорозв’язувані задачі комбінаторної оптимізації та теорія ПДС-алгоритмів | |
| dc.title.alternative | Intractable problems of combinatorial optimization and the theory of PSC-algorithms | |
| dc.type | Technical Report |
Файли
Контейнер файлів
1 - 1 з 1
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 8.98 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: