Constraint-Based Maintenance Scheduling On An Electric Power-Distribution Network
Constraint-Based Maintenance Scheduling On An Electric Power-Distribution Network
Constraint-Based Maintenance Scheduling On An Electric Power-Distribution Network
Tom Creemers1, Llus Ros Giralt1, Jordi Riera1, Carles Ferrarons2, Josep Roca2, Xavier Corbella2
1
Institut de Ciberntica (UPC / CSIC) Diagonal, 647, 2a planta 08028 Barcelona, Spain Telephone: + 34 3 401 66 53 Fax: +34 3 401 66 05 email: creemers,ros,riera@ic.upc.es ENHER, S.A. Passeig de Grcia, 132 08008 Barcelona, Spain Telephone: + 34 3 415 50 00 Fax: + 34 3 415 75 72
2
Abstract: The exploitation of a power-distribution network involves the scheduling of multiple maintenance and unforeseen repair tasks. The main resource is a network subject to topological, economical and electric constraints. A line section being maintained needs to be isolated from the rest of the network by opening all surrounding switches. This, in turn, would leave other areas of the network de-energized, which is unacceptable in most cases. Hence, these areas have to get their supply via some alternative way, i.e., service needs being restored closing switches connecting to an energized part of the network, taking into account overloading of branches, energy losses, and the cost of the necessary switching operations. In case tasks are carried out in the same area, switching operations might be shared among them. In some cases a valid network reconguration might not even exist. Finally, typical scheduling constraints have to be met: resources of limited availability (manpower, vehicles, etc.), due dates, priority relations, etc. We present PLANETS, a prototype scheduler based on CHIP, generating nearoptimal schedules for the tasks to be carried out in one week making sure that, at any moment in time, the network is appropriately recongured to guarantee power supply to all consumers. The minimization criterion involves lateness, priority and total cost of the necessary switching operations. Keywords: scheduling, combinatorial optimization, resources, constraints, power-distribution network reconguration, service restoration.
1. Introduction
1.1 Problem statement
Imagine the following scene at the dispatching center of an electric company. The planning engineer has just ordered the send-off of a vehicle to close switch number 6576 of the distribution network. The purpose: to keep on supplying electricity to some consumers affected by maintenance of an upstream line section. However, the planning engineer soon realizes that, two days before, switch number 6576 had already been closed for some time, and that by properly advancing the repair tasks in the schedule, the extra displacement of the vehicle to the switch could have been saved. At the dispatching center, these and other similar situations arise frequently in the daily exploitation of the network. The planning engineer, who, among other assignments, has to lead and coordinate all maintenance tasks on the distribution network, is at the same time responsible for nding those solutions that cost least to the company. Every week, he has to design the maintenance schedule for the following one, optimally distributing in time all foreseen maintenance tasks. Moreover, he has to gure out how to recongure the distribution network to be able to carry out this schedule. The preparation of such schedule is not trivial. Certainly, the engineer is facing a complex decision problem since he needs to consider lots of constraints and assign values to many variables. Indeed: In order to carry out every foreseen maintenance task, it is rst of all necessary to isolate the affected line section by opening all nearest surrounding switches. Next, the engineer has to decide through which of the many possible alternative paths of the network, he will keep on energizing all consumers affected by a maintenance task. He has to recongure the network while keeping it radial, i.e., there may not exist any closed loops, and ensuring that current limits of all lines are not exceeded. The number of disconnected consumers has to be minimized. The disconnection of a customer is only justied in certain cases where there does not exist any reconguration of the network that can maintain power supply. The amount of unconsumed energy translates directly into prot loss for the company. He has to achieve optimal usage of the companys limited resources involved in maintenance activities. These are basically: equipment, mobile technical staff, transportable generators, distribution operators, and the distribution network itself. By properly constructing the schedule this is possible. He has to consider the dynamic behaviour of the energy demand along the week. Thus, for example, a maintenance task involving the disconnection of a main line carrying high current values, cannot be performed at peak hours. The overload produced in neighbouring lines as a consequence of the reconguration could cause signicant damage. Additionally, he has to meet temporal constraints such as priorities, due dates and, for some
tasks, a priori xed dates. Finally, if we bear in mind the huge size of the electric networks dealt with (they can easily contain 2000 nodes and 800 switches), we understand the combinatorial complexity of the problem the planning engineer is periodically faced with.
It is also clear from past experiences that any scheduling problem is a possible candidate for a constraint-based approach. We show that the electric and topological constraints which delimit the possible states of the network, cut additionally the search space of all possible schedules. In other words, the states of certain switches at a particular moment in time, constrain the execution of maintenance jobs in certain parts of the network at that same time. Conversely, a (partial) solution for the scheduling problem cuts the space of possible network congurations. Indeed, inserting a job in some part of the network constrains the possible states of certain switches during job execution. Hence, solving the scheduling problem and the reconguration problem at the same time by creating a highly interconnected network of constraints in temporal, topological (switch states) and electric (currents) dimensions, aids nding a solution to both problems.
3. PLANETS
In this section we present the prototype system PLANETS (PLanning Activities on NETworkS), which will assist the planning engineer at the dispatching service of the Spanish electricity utility ENHER in scheduling the foreseen maintenance activities to be performed in an upcoming week on the power-distribution network, as well re-scheduling them together with unforeseen and urgent repair tasks. The output is a schedule in the form of a Gantt chart completed with a list of switching operations to be able to perform the necessary recongurations of the network.
CLIC
C language Interface
3.3 Constraints
Following, we describe the different kinds of constraints used in PLANETS:
Isolation Constraints: During job execution, the area surrounding the maintained branch must be in outage state. This is achieved by opening all surrounding switches. The constraint was implemented by means of an extension to the built-in element/3 constraint, forcing a number of elements in a list of currents (of the maintained branch) or switch states (of the surrounding switches) to be 0, starting at a position indicated by a temporal domain variable (the start time of the job). Resource Constraints: The available amount of resources must be respected at all times. Possible resources required by a maintenance job are vehicles, manpower, etc. The constraint is enforced by a straightforward use of the built-in cumulative/8. Precedence Constraints: Jobs on ancestor branches must be carried out before jobs on their descendant branches. The constraint translates in a number of inequality relations between temporal domain variables. Apart from these precedences, every job has additionally an absolute priority number. However, these priorities are not considered as hard constraints. They merely act as preferences. Violations represent an additional cost per time slot that can be minimized. Consumer Constraints: At all times there must ow a minimal non-zero current to all consumers. These constraint will propagate changes to the domains of many other current variables and, doing so, will force the network to recongure itself in case of an outage. In case such a reconguration would be impossible, we allow exceptionally the isolation of some consumers during a period of at most the duration of the particular job. This exception was necessary to avoid failure of the scheduler and getting a no answer. It is implemented by the built-in atmost/3 constraint: the list of currents supplying any of these consumers can have at most d zeros, where d is the duration of the particular job. For all other consumers, the constraint is enforced simply by setting the initial domain of their respective lists of current variables. Continuity Constraints: On all nodes, except the root and consumer nodes, the continuity law of Kirchoff must hold at all times. This constraint says that the sum of all incoming currents in a node must equal the sum of all outgoing currents. It forms the basis for the propagation of current domains through the network. These constraints are linear equations between domain variables. Switch-behaviour Constraints: An open switch cannot carry current. This constraint forms the basis for the topological reconguration of the network in all 15 time slots. It is implemented by means of the conditional-propagation construct in CHIP. For all 15 elements of the lists of currents and the lists of switch states, we have: (if S #= 0 then I #= 0), (if I #\= 0 then S #= 1), Radiality Constraints: At all times the network must be radial, i.e., not contain any closed cycles. This is enforced by searching all possible cycles and stating that, at any
time, at least one of the switches in any cycle must be open, using the atmost/3 built-in. Overload Constraints: In every branch, current must be below its allowable maximum. This constraint translates into simple inequalities on the current domain variables. Energy-demand Constraints: In every consumer branch the domain of the current variable is restricted to a pre-dened prole of energy demands. Due-date Constraints: Any job must be nished before its due date. In the normal case, this is a hard constraint. However, the user can indicate that it should be treated as a soft one, minimizing violations. Violations again represent a cost per time slot. The interactions between the above types of constraints and the domain variables on which they act are graphically represented in gure 2.
Precedence Constraints
Switch States
Continuity Constraints
Switch-behavior Constraints
Currents
Overload & Energy-demand Constraints Figure 2. A high-level representation of the constraint network.
associated costs: a cost for changing its state (from 0 to 1 or from 1 to 0), and a cost for staying in a non-nominal state during one time slot. These cost terms are added up for all switches and over all 15 time slots, yielding the global cost which is minimized. most_constrained switches are labeled rst, trying rst their nominal state.
6. Acknowledgements
This project was nanced by ENHER, S.A. (Empresa Nacional Hidroelctrica del Ribagorzana). We would like to express our gratitude to Manel Batlle of ORIGIN, S.A. for his valuable help in the development of the interface with the DISPOT load-ow library.
7. Bibliography
[Aggoun 92] Aggoun, A., Beldiceanu, N., Extending CHIP in Order to Solve Complex Scheduling and Placement Problems. Actes des premires journes francophones sur la programmation en logique, Lille, France, 1992. [Aoki 88] K. Aoki, H. Kuwabara, T. Satoh, M. Kanezashi. An Efcient Algorithm for Load Balancing of Transformers and Feeders by Switch Operation in Large Scale Distribution Systems. IEEE Trans. on Power Delivery. Vol. 3, No. 4, pp. 18651872, October 1988. [Filkorn 91] Filkorn, T., Schmid, R., Tidn, E., Warkentin, P., Experiences from a Large Industrial Circuit Design Application, in Proc. International Logic Programming Symposium, 581-595, 1991. [Heintze 91] Heintze, N., Michaylov, S., Stuckey, P., CLP( ) and Some Electrical Engineering Problems, in Journal of Automated Reasoning, 9, pp 231-260, 1992. [Jung 93] K. h. Jung, H. Kim, Y. Ko. Articial Neural-Network Based Feeder Reconguration for Loss Reduction in Distribution Systems. IEEE Trans. on Power Delivery, Vol. 8, No. 3, pp. 1356-1366, July 1993. [Le Pape 94] Le Pape, C., Constraint-Based Programming for Scheduling: An Historical Perspective, Working Paper, Operations Research Society Seminar on Constraint Handling Techniques, London, United Kingdom, 1994. [Liu 88] C. C. Liu, S. J. Lee, S. S. Venkata. An Expert System Operational Aid for Restoration and Loss Reduction of Distribution Systems. IEEE Trans. on Power Systems, Vol. 3, No. 2, May 1988. [Nara 92] K. Nara, A. Shiose, M. Kitigawa, T. Ishihara. Implementation of Genetic Algorithm for Distribution Systems Loss Minimum Reconguration. IEEE Trans. on Power Systems. Vol. 7, No. 3, pp. 1044-1049, August 1992. [Nerode 93] Nerode, A., Kohn, W., Hybrid Systems and Constraint Logic Programming, Proc. 10th International Conference on Logic Programming, pp 18-24, 1993. [Puget 94] Puget, J.-F., A C++ Implementation of CLP, Technical Report, ILOG, S.A., 1994. [Shirmohammadi 92] Shirmohammadi, D., Service Restoration in Distribution Networks via Network Reconguration, in IEEE Trans. on Power Delivery, Vol.7, No.2, pp. 952-958, April 1992. [Simonis 87] Simonis, H., Dincbas, M., Using Logic Programming for Fault Diagnosis in Digital Circuits, German Workshop on Articial Intelligence (GWAI-87), Geseke, Germany, pp 139-148, September 1987. [Simonis 88] Simonis, H., Nguyen, H.N., Dincbas, M., Verication of digital circuits using CHIP, Proceedings of the IFIP WG10.2 International Working Conference on the Fusion of Hardware Design and Verication, Glasgow, Scotland, July 1988. [Simonis 89] Simonis, H., Test Generation using the Constraint Logic Programming language CHIP, in Proceedings of the 6th International Conference on Logic Programming, 1989. [Simonis 90] Simonis, H., Graf, T., Technology Mapping in CHIP, Technical Report TR-LP-44, ECRC, Munich, Germany, 1990. [Tsai 93] M. S. Tsai, C.C. Liu, V. N. Mesa, R. Hartwell. IOPADS (Intelligent Operation Planning Aid for Distribution Systems). IEEE Trans. on Power Delivery. Vol. 8, No. 3, pp. 1562-1569, July 1993. [Van Hentenryck 89] Van Hentenryck, P., Constraint Satisfaction in Logic Programming, MIT Press, 1989. [Wong 87] Wong, K. P., Cheung, H. N, Articial Intelligence Approach to Load Allocation in Distribution Substations. IEE Proceedings, Vol. 134, Part C, No. 5, September 1987, pp. 357-365.