Runway Scheduling Using Generalized Dynamic Programming

Abstract

y, the runway scheduling problem (RSP) can be thought of as a job shop scheduling problem [11] withprecedence and release time constraints, where the objective is to sequence a set of jobs (aircraft) in a particularordertobeprocessedbyaprocessor(runway)sothatsomecostfunctionisminimized. Fortherunwayschedulingproblem, one wants to find an efficient schedule for aircraft to use the runway. The output, then, to the runwayscheduling problem is a time for each aircraft to begin using the runway, which will be referred to as a runwayschedule.Therunwayschedulingproblemisformallydescribedasfollows: Givenanorderedsetofdepartureaircraft Q d foreachdeparturequeue d ,asetofdepartureaircraft G g foreachgate g ofcardinality1,anorderedsetofaircraft C c foreachrunwaycrossingqueue c ,asetofaircraft P i thatmustnotusetherunwaybeforeaircraft i ,anearliesttime α ( i )foraircraft i toreachtherunway,andvarioustimingconstraints(describedbelow),findthesetof non-dominating a runwayschedule(s)withrespecttobothdelayandthroughput.A diagram of a typical problem is shown below in Figure 1. This diagram shows an example airport with onedeparture runway, a ramp area, and a network of taxiways. Each aircraft on the airport surface waits to use therunwayinchainlikestructurescalledqueues. Forthisdiagram,departureaircraftlocatedwithintherampareaareattheirgatesorgatequeues,anddepartureaircraftnearthetopleftentranceofthedeparturerunwayarewaitingindeparturequeues. Finally,thereisonetaxiwaythatcrossestherunwaywithachainoftwoaircraftwaitingcross.Theseaircraftwaitingtocrosstherunwayaresaidtobewaitingintheircrossingqueue.Tobeexact,anaircraf

Original document

The different versions of the original document can be found in:

• http://www.aviationsystemsdivision.arc.nasa.gov/publications/2011/AIAA-2011-6380.pdf

• http://arc.aiaa.org/doi/pdf/10.2514/6.2011-6380,

http://dx.doi.org/10.2514/6.2011-6380

• https://www.aviationsystemsdivision.arc.nasa.gov/publications/2011/AIAA-2011-6380.pdf,

https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20140013217.pdf,

https://www.aviationsystems.arc.nasa.gov/publications/2011/AIAA-2011-6380.pdf,

https://ntrs.nasa.gov/search.jsp?R=20140013217,

https://repository.exst.jaxa.jp/dspace/handle/a-is/62500,

http://www.aviationsystems.arc.nasa.gov/publications/2011/AIAA-2011-6380.pdf,

https://core.ac.uk/display/103715779,

https://academic.microsoft.com/#/detail/2034589963