ПДС-алгоритми для двоетапної задачі календарного планування в детермінованій постановці та в умовах невизначеності
Вантажиться...
Дата
2023
Автори
Павлов, О.
Халус, О.
Місюра, О.
Мельников, О.
Медведєв, М.
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Розглядається двоетапна задача календарного планування, в якій на першому етапі розв’язується задача сумарного запізнення моментів завершення роботи ідентичних незалежних пристроїв відносно спільного директивного строку. Цей оптимальний розв’язок водночас повинен задовольняти наступній умові: різниця між найпізнішим та найбільш раннім строками завершення роботи пристроїв є мінімальною в порівнянні з іншими оптимальними розв’язками. На другому етапі кожен пристрій в момент звільнення починає виконувати послідовно незалежно від інших пристроїв нову множину завдань, кожне з яких має свій директивний строк, за критерієм мінімізації сумарного зваженого запізнення виконання кожного завдання відносно його директивного строку. В даній постановці оптимальним розв’язком сформульованої задачі є той, у якого є оптимальний розв’язок першого етапу, а розв’язок другого етапу є умовно оптимальним (оптимальним відносно отриманих моментів звільнення пристроїв після виконання завдань першого етапу). На розв’язок першого етапу може бути накладена додаткова умова: моменти запуску пристроїв на другому етапі повинні задовольняти наперед заданому лексикографічному порядку. Зрозуміло, що в наведеній постановці кожен пристрій є багатофункціональним. Сформульована вище задача в умовах невизначеності означає, що вектори вагових коефіцієнтів критеріїв для кожного пристрою на другому етапі задані неоднозначно. Неоднозначність може бути пов’язана з тим, що вагові коефіцієнти задаються не одним, а декількома експертами, чи в силу того, що другий етап може бути реалізований в майбутньому, і тому вектор вагових коефіцієнтів вважається випадковим дискретним із заданим розподілом, чи його неоднозначність задається відповідною функцією належності. Автори запропонували ПДС-алгоритми розв’язання цієї задачі в детермінованій постановці та в умовах невизначеності. Тобто, кожен алгоритм містить наближений поліноміальний підалгоритм побудови оптимального розкладу, для якого сформульовані достатні ознаки його оптимальності.
Опис
Ключові слова
двоетапна задача календарного планування, ПДС-алгоритм, NP-складні нові задачі, емпірична матриця парних порівнянь, невизначеність
Бібліографічний опис
ПДС-алгоритми для двоетапної задачі календарного планування в детермінованій постановці та в умовах невизначеності / О. Павлов, О. Халус, О. Місюра, О. Мельников, М. Медведєв // Адаптивні системи автоматичного управління : міжвідомчий науково-технічний збірник. – 2023. – № 1 (42). – С. 184-196. – Бібліогр.: 9 назв.