Задача складання плану ремонту об’єктів електричної мережі

Abstract

This paper addresses a bi-criteria scheduling problem for restoring power supply after an emergency outage under limited resources — specifically, repair crews operating in parallel. Such situations are typical for urban infrastructure systems under critical conditions, where rapid decision-making is required while simultaneously considering multiple conflicting objectives. The mathematical formulation of the problem involves two objectives: minimizing the average weighted blackout time for citizens and minimizing the total working time of the repair crews (makespan). The proposed model belongs to the class of parallel machine scheduling problems with weighted jobs, where weights reflect the social importance of each task (district). To solve this problem, three algorithms have been developed: a heuristic algorithm, a local search algorithm with job relocation (LS1), and a local search algorithm with job exchange (LS2). The heuristic algorithm combines strategies for optimal single-machine scheduling (based on average weighted completion time) with load-balancing techniques for parallel machines (LPT algorithm). LS1 is based on the step-by-step improvement of the initial schedule by relocating jobs between crews while evaluating trade-offs between the two objectives. LS2 performs randomized exchanges of job pairs between machines and retains improvements based on the principle of fair compromise, which ensures lower computational complexity while maintaining high solution quality. Computational experiments confirm the effectiveness of the developed algorithms. It was found that LS1 and LS2 improve upon the heuristic solution by an average of 3.5…5 %. Experiments with different problem sizes showed consistent increases in execution time as task complexity grows, with LS2 outperforming LS1 in runtime due to its limited number of local modifications. The proposed approach enables efficient power restoration planning by integrating classical scheduling techniques with socially meaningful decision criteria.

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