An airline would like to cover k flight legs using minimum number of planes. These legs should be combined into consecutive flights to be performed by each aircraft, and their start and end times should be scheduled. The start time for flight i is si and the end time is ei. If flight leg j is to be performed after i, the plane requires rij hours in order to get from the destination of flight i to the origin of flight j,Start and end times of each flight leg are given and will not be changed. a) Formulate the problem of finding a schedule as minimum cost flow problem in a network with lower and upper bounds on the arcs. You should clearly state how to construct the network from the given data, and justify that your formulation correctly models the problem. b) How would the formulation change if a plane is restricted to fly at most D hours? Can the problem still be formulated as a minimum cost flow problem? |