Scheduling Post-disaster Repairs in Electricity Distribution Networks with Uncertain Repair Times

摘要

Natural disasters, such as hurricanes, large wind and ice storms, typically require the repair of a large number of components in electricity distribution networks. Since power cannot be restored before the completion of repairs, optimally scheduling the available crews to minimize the cumulative duration of the customer interruptions reduces the harm done to the affected community. We have previously proposed approximation algorithms to schedule post-disaster repairs in electricity distribution networks with complete damage information [1]. In this paper, we extend our previous work to the case with incomplete damage information. We model this problem as scheduling a set of jobs with stochastic processing times on parallel identical machines in order to minimize the total weighted energization time. A linear programming (LP) based list scheduling policy is proposed and then analyzed in terms of theoretical performance.