Реєстраційний номер
0220U100685,
0117U000460
, Науково-дослідна робота
Назва роботи
Важкорозв'язувані задачі комбінаторної оптимізації та теорія ПДС-алгоритмів
Назва етапу роботи
Керівник роботи
Павлов Олександр Анатолійович, Доктор технічних наук
Дата реєстрації
23-01-2020
Організація виконавець
Національний технічний університет України "Київський політехнічний інститут імені Ігоря Сікорського"
Опис етапу
Робота є продовженням циклу робіт з розвитку авторської теорії та методології побудови ПДС-алгоритмів для важкорозв’язуваних задач комбінаторної оптимізації (ВЗКО – задачі, для яких не існує поліноміальних алгоритмів розв’язання) і створення на її основі моделей і методів календарного та оперативного планування та прийняття рішень в складних соціально-економічних системах з мережевим представленням технологічних процесів та обмеженими ресурсами. ПДС-алгоритми включають поліноміальну складову, яка строго реалізує оптимальний розв’язок, і точний експоненціальний підалгоритм або поліноміальну апроксимацію точного алгоритму (наближений або евристичний алгоритм). Перевагою ПДС-алгоритмів перед існуючими методами є те, що на їх основі можна побудувати для задач великої розмірності як точні, так і наближені алгоритми з оцінками якості отриманих розв’язків або евристичні алгоритми. На основі теорії ПДС-алгоритмів у роботі створено нові методи та ефективні ПДС-алгоритми для п’яти ВЗКО, зокрема, для двох з шості найбільш складних та відомих в світі класичних ВЗКО – NP-трудних в сильному розумінні задач мінімізації сумарного зваженого моменту закінчення завдань на одному приладі з відношенням передування та мінімізації сумарного зваженого запізнення завдань на одному приладі. Також досліджено ефективність чотирьох інших ПДС-алгоритмів. Створені ПДС-алгоритми включено до математичного та програмного забезпечення розробленої у попередніх роботах чотирьохрівневої моделі календарного та оперативного планування в системах з мережним представленням технологічних процесів та обмеженими ресурсами. У результаті створено інформаційну технологію та новий інтегрований пакет програм календарного та оперативного планування в соціально-економічних системах у різних прикладних областях.
Опис продукції
Нові ефективні ПДС-алгоритми та результати статистичних досліджень їх ефективності для наступних ВЗКО:
– Мінімізація сумарного зваженого запізнення завдань відносно директивних строків на одному приладі;
– Мінімізація сумарного зваженого запізнення завдань з узгоджуваними вагами відносно спільного директивного строку на ідентичних паралельних приладах;
– Мінімізація сумарного випередження завдань для одного приладу з різними директивними строками;
– Мінімізація максимального випередження / запізнення моментів закінчення роботи паралельних приладів зі спільним директивним строком;
– Мінімізація сумарного зваженого моменту закінчення завдань на одному приладі при відношеннях передування, заданих орієнтованим ациклічним графом загального вигляду..
Результати статистичних досліджень ефективності раніше створених ПДС-алгоритмів для наступних ВЗКО:
– виконання незалежних завдань паралельними приладами рівної та різної продуктивності за критеріями максимізації мінімального моменту початку виконання завдань у допустимому розкладі, складеному лексикографічному критерію оптимальності;
– мінімізація сумарного випередження моментів закінчення роботи паралельних приладів зі спільним директивним строком;
– мінімізація сумарного випередження/запізнення на одному приладі з довільними директивними строками;
– мінімізація сумарного запізнення при виконанні завдань паралельними приладами рівної продуктивності зі спільним директивним строком при умові, що моменти запуску приладів фіксовані;
Модифікована чотирьохрівнева модель КОП в мережевих системах з обмеженими ресурсами. Інформаційна технологія багаторівневого КОП у вигляді універсальної ієрархічної системи КОП. Результати, які отримані, є новими і перевищують світовий науковий рівень.
Автори роботи
Жданова Олена Григорівна
Ковалюк Тетяна Володимирівна
Лисецький Тарас Миколайович
Місюра Олена Борисівна
Мельников Олег Валентинович
Павлов Олександр Анатолійович
Сперкач Майя Олегівна
Халус Олена Андріївна
Додано/оновлено в НРАТ
2020-04-02
