If you were using a Java-enabled browser, you would see an animated display that looks like this:

The Four Node Scheduling problem Java Demo

Clicking on one of the rectangles forming the schedule will toggle that part of the schedule (i.e. swap weather the schedule says to maintain the line in that week or not). Planned maintenance is shown as green.

Histograms show the electricity flow in the adjacent line in each week of the nine week plan. Should this exceed the lines capacity the plot is shown in red.

The costs for each week of the plan are given in black and the combined cost is shown in white. The best known schedule has a cost of 1255.

The Auto schedule button runs the minimium increased cost greedy scheduler.

Briefly the four node problem was devised by The National Grid Company plc as test problem for scheduling the maintenance of electrical transmission lines.

The problem is how to schedule the maintenance of eight electrical power transmission lines arranged in pairs which connect four nodes (or substations) so as to disrupt the supply of electricity the least. Each line takes one week to maintain, all eight have to be maintained within a nine week plan.

Back ground

W.B.Langdon 22 January 1999 (last update 23 April 2011