Stochastic Runway Scheduling

Runway scheduling deals with the sequencing of arriving and departing aircraft at airports such that a predefined objective is optimized subject to several operational constraints. Different from the existing deterministic approaches in the literature, we consider a new approach to the stochastic version of this problem within the general context of machine scheduling problems. As part of our analysis, we first show that a restricted version of the stochastic runway-scheduling problem is equivalent to a machine-scheduling problem on a single machine with sequence-dependent setup times and stochastic due dates. We then extend this restricted model by considering characteristics specific to the runway-scheduling problem and present two different stochastic integer programming models. We derive some tight valid inequalities for these formulations and propose a solution methodology based on sample average approximation and Lagrangian-based scenario decomposition. Realistic data sets are then used to perform a detailed computational study involving implementations and analyses of several different configurations of the models. The results from the computational tests indicate that truncated versions of the proposed solution algorithm, where the best solution is reported after short run times, almost always produce very high-quality solutions, implying that the proposed stochastic approach to runway scheduling is likely to be practically implementable with potential value over current practice or deterministic models.