Створення математичних моделей та методів ієрархічного планування та прийняття рішень в виробничих системах з обмеженими ресурсами

1. Номер державної реєстрації теми – 0108U001346.
2. Науковий керівник – д.т.н., проф. Павлов О.А.
3. Суть розробки, основні результати.

Загальна фундаментальна проблема, на вирішення якої спрямовано проект – розробка математичних моделей та методів ієрархічного планування та прийняття рішень в складних організаційно-виробничих системах з мережним представленням технологічних процесів та обмеженими ресурсами.

Створена методологія побудови ієрархічних моделей планування та прийняття рішень в складних організаційно-виробничих системах. На її основі розроблена ієрархічна модель планування, якій відповідає принципово новий рівень математичного забезпечення та в якій загальна математична модель задачі календарного планування замінена послідовністю дискретних математичних моделей, сумісних з ієрархією рішень, що повинні бути прийняті на кожному рівні управління. Розроблена система взаємозв’язаних моделей та методів їх розв’язання дозволяє враховувати велику кількість різноманітних виробничих зв’язків, наявних ресурсів, складність продукції, велику кількість стадій виробництва, неодночасність надходження завдань на виконання. На відміну від існуючих методів планування, кращі з яких містять лінійну чи випадкову комбінацію різних правил переваги, що не гарантує якості отриманих розв’язків, в процесі розв’язання задачі планування визначається стратегія пошуку глобального оптимуму, що дозволяє отримати розв’язки, близькі до оптимальних.

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

На основі нового авторського підходу до розв’язання задачі багатокритеріального вибору створено конструктивні математичні моделі оптимізації лінійного та випуклого квадратичного програмування в методі аналізу ієрархії Сааті для знаходження ваг за добре чи погано погодженими неоднорідними матрицями парних порівнянь, за матрицями парних порівнянь, що не містять цифрової інформації та за матрицями парних порівнянь з однобічними обмеженнями. Нові моделі оптимізації вирішують проблему знаходження ваг за погано погодженою неоднорідною матрицею та обґрунтування ефективності отриманого розв’язку, що суттєво розширює можливості їх практичного використання.

Створено інформаційну технологію та інтегрований пакет програм, що реалізує розв’язання задач планування в складних організаційно-виробничих системах за різними критеріями оптимальності та задачі багатокритеріального вибору на основі нових моделей оптимізації за неоднорідними матрицями парних порівнянь для знаходження ваг в методі аналізу ієрархії Сааті. Таким чином, вперше в комплексі розв’язано проблему як побудови календарних планів за різними критеріями оптимальності, так і вибору найкращого з них.