1. ПДС-алгоритми для двоетапної задачі календарного планування в детермінованій постановці та в умовах невизначеності
- Author
-
A. Pavlov, E. Khalus, E. Misura, O. Melnikov, and M. Medvediev
- Subjects
двоетапна задача календарного планування ,пдс-алгоритм ,np- складні нові задачі ,емпірична матриця парних порівнянь ,невизначеність ,Automation ,T59.5 - Abstract
Розглядається двоетапна задача календарного планування, в якій на першому етапі розв’язується задача сумарного запізнення моментів завершення роботи ідентичних незалежних пристроїв відносно спільного директивного строку. Цей оптимальний розв’язок водночас повинен задовольняти наступній умові: різниця між найпізнішим та найбільш раннім строками завершення роботи пристроїв є мінімальною в порівнянні з іншими оптимальними розв’язками. На другому етапі кожен пристрій в момент звільнення починає виконувати послідовно незалежно від інших пристроїв нову множину завдань, кожне з яких має свій директивний строк, за критерієм мінімізації сумарного зваженого запізнення виконання кожного завдання відносно його директивного строку. В даній постановці оптимальним розв’язком сформульованої задачі є той, у якого є оптимальний розв’язок першого етапу, а розв’язок другого етапу є умовно оптимальним (оптимальним відносно отриманих моментів звільнення пристроїв після виконання завдань першого етапу). На розв’язок першого етапу може бути накладена додаткова умова: моменти запуску пристроїв на другому етапі повинні задовольняти наперед заданому лексикографічному порядку. Зрозуміло, що в наведеній постановці кожен пристрій є багатофункціональним. Сформульована вище задача в умовах невизначеності означає, що вектори вагових коефіцієнтів критеріїв для кожного пристрою на другому етапі задані неоднозначно. Неоднозначність може бути пов’язана з тим, що вагові коефіцієнти задаються не одним, а декількома експертами, чи в силу того, що другий етап може бути реалізований в майбутньому, і тому вектор вагових коефіцієнтів вважається випадковим дискретним із заданим розподілом, чи його неоднозначність задається відповідною функцією належності. Автори запропонували ПДС-алгоритми розв’язання цієї задачі в детермінованій постановці та в умовах невизначеності. Тобто, кожен алгоритм містить наближений поліноміальний підалгоритм побудови оптимального розкладу, для якого сформульовані достатні ознаки його оптимальності. Бібл. 9
- Published
- 2023
- Full Text
- View/download PDF