Важкорозв’язувані задачі комбінаторної оптимізації та теорія ПДС-алгоритмів

1. Номер державної реєстрації, номер реєстрації в університеті: 0117U000460,
2. Науковий керівник: д.т.н., проф. Павлов О.А., Павлов А.А., Pavlov Alexander A.

3. Суть розробки, основні результати:
(укр.)
Робота є продовженням циклу робіт з розвитку теорії ПДС-алгоритмів і створення на її основі моделей і методів календарного та оперативного планування та прийняття рішень в складних соціально-економічних системах з мережевим представленням технологічних процесів та обмеженими ресурсами. Мета роботи – розвиток авторської теорії та методології побудови ПДС-алгоритмів для важкорозв’язуваних задач комбінаторної оптимізації (ВЗКО – задачі, для яких не існує поліноміальних алгоритмів розв’язання) та створення на їх основі високоефективних методів розв’язання досліджуваних задач календарного та оперативного планування. ПДС-алгоритми включають поліноміальну складову, яка строго реалізує оптимальний розв’язок, і точний експоненціальний підалгоритм або поліноміальну апроксимацію точного алгоритму (наближений або евристичний алгоритм). Перевагою ПДС-алгоритмів перед існуючими методами є те, що на їх основі можна побудувати для задач великої розмірності як точні, так і наближені алгоритми з оцінками якості отриманих розв’язків або евристичні алгоритми.
На основі теорії ПДС-алгоритмів у роботі створено нові методи та ефективні ПДС-алгоритми для п’яти ВЗКО, зокрема, для двох з шості найбільш складних та відомих в світі класичних ВЗКО – NP-трудних в сильному розумінні задач мінімізації сумарного зваженого моменту закінчення завдань на одному приладі з відношенням передування та мінімізації сумарного зваженого запізнення завдань на одному приладі. Також досліджено ефективність чотирьох інших ПДС-алгоритмів. Створені ПДС-алгоритми включено до математичного та програмного забезпечення розробленої у попередніх роботах чотирьохрівневої моделі календарного та оперативного планування в системах з мережним представленням технологічних процесів та обмеженими ресурсами. У результаті створено інформаційну технологію та новий інтегрований пакет програм календарного та оперативного планування в соціально-економічних системах у різних прикладних областях.