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

Інформація × Реєстраційний номер 0201U008143, 0100U000390 , Науково-дослідна робота Назва роботи Розвиток та алгоритмічна реалізація математичного апарату конструктивної теорії розв'язання важкорозв'язуваних задач комбінаторної оптимізації Назва етапу роботи Керівник роботи Павлов О.А., Дата реєстрації 19-12-2001 Організація виконавець Науково-дослідний інститут інформаційних процесів Національного Технічного Університету України "КПІ" Опис етапу Об'єкт дослідження - планування функціонування складних систем. Мета роботи - розробка теоретичних основ, методів та ефективних точних ПДС-алгоритмів (алгоритмів з поліноміальною та декомпозиційною складовими) розв'язання NP-склад-них задач комбінаторної оптимізації. Досліджені важкорозв'язувані задачі комбінаторної оптимізації "Мінімізація сумарного зваженого моменту виконання завдань при відношенні порядку, заданому орієнтованим ациклічним графом" (МЗМ) та "Мінімізація сумарного штрафу при виконанні незалежних завдань з директивними строками" (МСШ), що входять до складу системи планування та управління функціонуванням дрібносерійного виробництва в ринкових умовах (СПУДВ). Для задачі МЗМ отримано точний ефективний ПДС-алгоритм її розв'язання і визначені нові поліноміально розв'язувані її підкласи. На основі проведених досліджень властивостей задачі МСШ виведено нові властивості оптимальних розв'язків цієї задачі. Розроблено новий точний та новий наближений алгоритми розв'язання задачі МСШ; для наближ еного алгоритму одержано оцінку відхилення розв'язків від оптимальних. Розроблено ефективні швидкодіючі алгоритми внутрішньо-коміркового планування в системі СПУДВ за критеріями мінімізації штрафу підприємства за невиконання вчасно виробів, для яких задані директивні строки, а також за умов існування виробів, директивні строки яких в процесі виконання не можуть бути порушені та мінімальної тривалості переналагодження комірки для випадку, коли комірка складається з одного робочого місця. Дослідження показують, що отримані алгоритми є ефективними та можуть бути використані для розв'язання деяких класів NP-складних задач за поліноміальний час. Опис продукції Автори роботи Додано в НРАТ 2020-04-02 Закрити