Пошук академічних текстів

Інформація × Реєстраційний номер 0203U002689, 0102U000585 , Науково-дослідна робота Назва роботи Розвиток конструктивної теорії побудови ефективних точних алгоритмів для важкорозв'язуваних комбінаторних задач як основи математичних моделей дослідження складних систем Назва етапу роботи Керівник роботи Павлов О.А., Дата реєстрації 26-12-2003 Організація виконавець Науково-дослідний інститут інформаційних процесів Національного Технічного Університету України "КПІ" Опис етапу Розробка призначена для розвитку розробленої авторами нової, що не має аналогів у світі, конструктивної теорії розв'язання важкорозв'язуваних задач комбінаторної оптимізації (ВЗКО), розробці теоретичних основ та методів проектування ефективних точних ПДС-алгоритмів (алгоритмів з поліноміальною та декомпозиційною складовими) їх розв'язання. Розглянуті властивості двох типів ПДС-алгоритмів - з адитивною і неадитивною структурою - на прикладі задач "Максимальна незалежна множина" (МНМ), "Мінімізація сумарного зваженого моменту виконання завдань при відношенні порядку, заданому орієнтованим аціклічним графом" (МЗМ). Досліджено властивості цих задач, розроблено оригінальні точні ПДС-алгоритми їх розв'язання. Визначено поліноміально розв'язувані підкласи даних задач, правила відсікань та розпаралелювання обчислень для підвищення ефективності розв'язання задач. Розроблено два алгоритми зведення задачі "Здійсненність" до задачі МНМ. Розроблено нові оригінальні ефективні алгоритми розв'язання задач "Мінімізаціясумарного зваженого запізнення при виконанні завдань" (МЗЗ), "Мінімізація сумарного запізнення при виконанні завдань" (МСЗ). На основі цих алгоритмів розроблено наближені алгоритми з оцінкою відхилення розв'язків від оптимальних. Для усіх задач виведено умови, при виконанні яких оптимальний розклад досягається за поліноміальний від розмірності час. Алгоритми розв'язання задач МЗМ, МЗЗ та МСЗ та їх програмне забезпечення увійшли до складу алгоритмічного забезпечення розробленої авторами адаптивної автоматизованої системи планування та управління функціонуванням дрібносерійного виробництва (СПУДВ). Маємо технічну та програмну документацію на систему СПУДВ, демонстраційну версію системи. Розробка не має аналогів в Україні. Опис продукції Автори роботи Додано в НРАТ 2020-04-02 Закрити