ЗАДАЧА СКЛАДАННЯ ПЛАНУ РЕМОНТУ ОБ’ЄКТІВ ЕЛЕКТРИЧНОЇ МЕРЕЖІ
Ключові слова
Анотація
Розглянуто задачу двокритеріального планування робіт з відновлення електропостачання після аварійного відключення в умовах обмежених ресурсів — ремонтних бригад, які працюють паралельно. Така ситуація є типовою для міських інфраструктурних систем у критичних умовах, коли необхідно швидко ухвалювати рішення з урахуванням кількох суперечливих цілей. Математична постановка задачі враховує два критерії: мінімізацію середнього зваженого часу перебування громадян без електропостачання та мінімізацію загального часу роботи ремонтних бригад (makespan). Запропонована модель належить до класу задач складання розкладу на паралельних машинах з роботами, що мають ваги, які відображають соціальну значущість кожної роботи. Для розв’язання цієї задачі розроблено три алгоритми: евристичний, алгоритм локального пошуку з переміщенням робіт (АЛП1) та алгоритм локального пошуку з обміном робіт (АЛП2). Евристичний алгоритм поєднує підходи до оптимального складання розкладу на одній машині (за критерієм середнього зваженого часу) та ідеї балансування навантаження на кількох машинах (LPT-алгоритм). АЛП1 базується на поступовому поліпшенні початкового розкладу шляхом переміщення робіт між бригадами з оцінкою компромісу між двома критеріями. АЛП2 реалізує випадкові обміни парами робіт між машинами з відбором поліпшень за принципом справедливого компромісу, що забезпечує нижчу обчислювальну складність зі збереженням високої якості розв’язків. Проведено обчислювальні експерименти, які підтвердили ефективність розроблених алгоритмів. Встановлено, що АЛП1 та АЛП2 забезпечують поліпшення результатів, отриманих евристичним алгоритмом, у середньому на 3,5…5 %. Експерименти з різними параметрами задачі продемонстрували закономірне зростання часу роботи алгоритмів з розмірністю задачі, а також перевагу АЛП2 у швидкодії порівняно з АЛП1 завдяки обмеженню кількості локальних змін. Запропонований підхід дозволяє ефективно розв’язувати задачі планування відновлення електропостачання, поєднуючи класичні методи теорії розкладів з урахуванням соціально важливих аспектів.
