Genetic Algorithms for Schedule Optimisation

W.Langdon@cs.ucl.ac.uk 22 January 1999

The National Grid Company plc. are interested in the problem of planning maintenance of the electricity transmission network so as to minimise costs throughout the entire network, throughout each year. There are considerable cost savings to be made by improved planning. W. B. Langdon was awarded a CASE studentship by the National Grid Company plc. in order to investigate a solution to this problem using genetic algorithms.

Initially we started with a small demonstration network but have now applied the lessons learnt to the South Wales region of the whole network (see next figure).

The fitness of each trial schedule is based upon two parts; a benefit for performing maintenance and penalties for maintenance activity which could cause line power flows to exceed their capacity or isolate sections of the network, either directly or as a result of faults. In practice more expensive generators must be run to ensure against this, the alternative generators are the principle cost of maintenance.

Given forecast electricity demand for the next year and the price of each electricity generator the cheapest generation can be forecast. Using this, the location of demand for electricity and a maintenance schedule, the electrical power flows for the entire network can be calculated. It is from this the fitness of the schedule is calculated, which is then used to guide the genetic search for still better schedules.

We have obtained good results for the South Wales region using a "greedy" scheduling heuristic and are now investigating solutions using genetic programming and considering possible network fault conditions.

South Wales Region of the Supergrid

Reports on earlier work on the four node problem and a genetic programming approach to the South Wales regional problems are available.

A different GA approach was tried by T. G. W. Gordon for his MSc Thesis.


Last updated 23 April 2011