OPTIMAL SCHEDULING WITH MAXIMUM POSITION SHIFT (MPS) CONSTRAINTS - A RUNWAY SCHEDULING APPLICATION

This paper presents results from a doctoral dissertation (reference 12 ), on the problem of scheduling with Maximum Position Shift (MPS) cons traints. The problem typically arises in a queueing system, when the s ervice rate depends on the sequence in which customers are handled by the server. Such a queueing system is the airport runway system, where it has been shown (references 3, ro, 12) that rearranging the sequenc e of landings and takeoffs affects the runway capacity - that is, the rate of runway operations. An optimal Dynamic Programming (DP) schedul ing algorithm is developed that takes as input the set of currently kn own flights, their desired time of operation, basis of the First Come First Served (FCFS) sequence, and a matrix of Air Traffic Control (ATC ) minimum time separations, in order to produce an optimal schedule de fined as runway and threshold time assignments maximizing runway capac ity.