The Problem of Scheduling the Maintenance of Power Grid Facilities

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.