ПДС-алгоритми для двоетапної задачі календарного планування в детермінованій постановці та в умовах невизначеності

dc.contributor.authorПавлов, О.
dc.contributor.authorХалус, О.
dc.contributor.authorМісюра, О.
dc.contributor.authorМельников, О.
dc.contributor.authorМедведєв, М.
dc.date.accessioned2023-05-22T05:55:05Z
dc.date.available2023-05-22T05:55:05Z
dc.date.issued2023
dc.description.abstractРозглядається двоетапна задача календарного планування, в якій на першому етапі розв’язується задача сумарного запізнення моментів завершення роботи ідентичних незалежних пристроїв відносно спільного директивного строку. Цей оптимальний розв’язок водночас повинен задовольняти наступній умові: різниця між найпізнішим та найбільш раннім строками завершення роботи пристроїв є мінімальною в порівнянні з іншими оптимальними розв’язками. На другому етапі кожен пристрій в момент звільнення починає виконувати послідовно незалежно від інших пристроїв нову множину завдань, кожне з яких має свій директивний строк, за критерієм мінімізації сумарного зваженого запізнення виконання кожного завдання відносно його директивного строку. В даній постановці оптимальним розв’язком сформульованої задачі є той, у якого є оптимальний розв’язок першого етапу, а розв’язок другого етапу є умовно оптимальним (оптимальним відносно отриманих моментів звільнення пристроїв після виконання завдань першого етапу). На розв’язок першого етапу може бути накладена додаткова умова: моменти запуску пристроїв на другому етапі повинні задовольняти наперед заданому лексикографічному порядку. Зрозуміло, що в наведеній постановці кожен пристрій є багатофункціональним. Сформульована вище задача в умовах невизначеності означає, що вектори вагових коефіцієнтів критеріїв для кожного пристрою на другому етапі задані неоднозначно. Неоднозначність може бути пов’язана з тим, що вагові коефіцієнти задаються не одним, а декількома експертами, чи в силу того, що другий етап може бути реалізований в майбутньому, і тому вектор вагових коефіцієнтів вважається випадковим дискретним із заданим розподілом, чи його неоднозначність задається відповідною функцією належності. Автори запропонували ПДС-алгоритми розв’язання цієї задачі в детермінованій постановці та в умовах невизначеності. Тобто, кожен алгоритм містить наближений поліноміальний підалгоритм побудови оптимального розкладу, для якого сформульовані достатні ознаки його оптимальності.uk
dc.format.pagerangePp. 184-196uk
dc.identifier.citationПДС-алгоритми для двоетапної задачі календарного планування в детермінованій постановці та в умовах невизначеності / О. Павлов, О. Халус, О. Місюра, О. Мельников, М. Медведєв // Адаптивні системи автоматичного управління : міжвідомчий науково-технічний збірник. – 2023. – № 1 (42). – С. 184-196. – Бібліогр.: 9 назв.uk
dc.identifier.doihttps://doi.org/10.20535/1560-8956.42.2023.279170
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/55894
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.relation.ispartofАдаптивні системи автоматичного управління : міжвідомчий науково-технічний збірник, 2023, № 1 (42)uk
dc.subjectдвоетапна задача календарного плануванняuk
dc.subjectПДС-алгоритмuk
dc.subjectNP-складні нові задачіuk
dc.subjectемпірична матриця парних порівняньuk
dc.subjectневизначеністьuk
dc.subject.udc519.854.2uk
dc.titleПДС-алгоритми для двоетапної задачі календарного планування в детермінованій постановці та в умовах невизначеностіuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Вантажиться...
Ескіз
Назва:
279170-643481-1-10-20230514.pdf
Розмір:
653.42 KB
Формат:
Adobe Portable Document Format
Опис:
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.1 KB
Формат:
Item-specific license agreed upon to submission
Опис: