Optimal Scheduling of Jobs on a Transmission Network

A number of jobs have to be carried out on a gas transmission network every year, which restrict the transmission capacity of the network while they are in progress. There are certain pairs of jobs which must not be in progress at the same time. The network must meet a convex annual demand pattern. The problem of scheduling the jobs over the summer construction period to meet these conditions is formulated as a mixed-integer linear programming problem which is solved by a branch-and-bound algorithm. Results and benefits to the operators of the network are described.