Scheduling Aircraft Landings--The Static Case

Beasley, J. E.; Krishnamoorthy, M.; Sharaiha, Y. M.; Abramson, D.
May 2000
Transportation Science;May2000, Vol. 34 Issue 2, p180
Academic Journal
In this paper, we consider the problem of scheduling aircraft (plane) landings at an airport. This problem is one of deciding a landing time for each plane such that each plane lands within a predetermined time window and that separation criteria between the landing of a plane and the landing of all successive planes are respected. We present a mixed-integer zero-one formulation of the problem for the single runway case and extend it to the multiple runway case. We strengthen the linear programming relaxations of these formulations by introducing additional constraints. Throughout, we discuss how our formulations can be used to model a number of issues (choice of objective function, precedence restrictions, restricting the number of landings in a given time period, runway workload balancing) commonly encountered in practice. The problem is solved optimally using linear programming-based tree search. We also present an effective heuristic algorithm for the problem. Computational results for both the heuristic and the optimal algorithm are presented for a number of test problems involving up to 50 planes and four runways.


Related Articles

  • The General Flowshop Scheduling Problem: Mathematical Models. Sadjadi, S. J.; Aryanezhad, M. B.; Ziaee, Mohsen // Journal of Applied Sciences;2008, Vol. 8 Issue 17, p3032 

    In this study, consider three general flowshop scheduling problems: (1) with the objective function of the total weighted tardiness and the assumption of having ready times for jobs, (2) with the objective function of the makespan and the constraints of time lags and (3) with the makespan as...

  • SINGLE-MACHINE SCHEDULING OF UNIT-TIME JOBS WITH EARLINESS AND TARDINESS PENALTIES. Verma, Sushil; Dessouky, Maged // Mathematics of Operations Research;Nov98, Vol. 23 Issue 4, p930 

    The problem of determining a schedule of jobs with unit-time lengths on a single machine that minimizes the total weighted earliness and tardiness penalties with respect to arbitrary rational due-dates is formulated as an integer programming problem. We show that if the penalties meet a certain...

  • A GENERALIZED MODEL FOR PRODUCTION SCHEDULING BY TRANSPORTATION METHOD OF LP. Singhal, Kalyanmal // Industrial Management;Sep/Oct77, Vol. 19 Issue 5, p1 

    Proposes a generalized model for production scheduling using the transportation method of linear programming. Possibility of using the model without advanced knowledge in Quantitative Methods; Usability of the model on managers; factors contributing the development of a production scheduling...

  • Minimizing total tardiness on parallel machines with preemptions. Kravchenko, Svetlana; Werner, Frank // Journal of Scheduling;Apr2012, Vol. 15 Issue 2, p193 

    The basic scheduling problem we are dealing with in this paper is the following one. A set of jobs has to be scheduled on a set of parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing at its release date. All jobs have the same...

  • SCHEDULING TO MINIMIZE MAXIMUM WORKLOAD. Lüthi, Hans-Jakob; Polyméris, Andrés // Management Science;Nov85, Vol. 31 Issue 11, p1409 

    We pose the following problem: given m jobs, each of which requires a certain total amount of labour that must be performed within specified time periods, how should one schedule the jobs' execution to obtain a total workload that is as even as possible? A related question is: what is the...

  • Combining Column Generation and Lagrangean Relaxation to Solve Single-Machine Common Due Date Problem. van den Akker, Marjan; Hoogeveen, Han; van den Velde, Steef // INFORMS Journal on Computing; 

    Column generation has proved to be an effective technique for solving the linear programming relaxation ofhuge set covering or set partitioning problems,and column generation approaches have led to state-of-the-art so-called branch-and-price algorithms for various archetypical combinatorial...

  • COMPUTING TETRAETHYL-LEAD REQUIREMENTS IN A LINEAR-PROGRAMMING FORMAT. Kawaratani, T.K.; Ullman, R.J.; Dantzig, George B. // Operations Research;Jan/Feb60, Vol. 8 Issue 1, p24 

    Describes the tetraethyllead requirements in a linear-programming format. Scheduling of refinery operations; Approximation of the general function by a convex linear combination of a mesh of representative points.

  • How to Analyse the Results of Linear Programs-- Part 3: Infeasibility Diagnosis. Greenberg, Harvey J. // Interfaces;Nov/Dec93, Vol. 23 Issue 6, p120 

    One problem in debugging a linear program is finding a way to diagnose an infeasible instance. The sources of error could be structural, such as inadvertent omission of activities, or data related, such as insufficient supply to meet demand. I present techniques that LP experts have used in...

  • A Linear Programming Model for Cargo Movement Evaluation. Gould, F. J. // Transportation Science;Nov71, Vol. 5 Issue 4, p344 

    A linear programming model is presented for minimizing the steady state cost of moving cargo carriers over certain routes subject to numerous constraints on both the cargo and carrier movement. There are several types of cargo and carriers, transshipment is allowed, cargo and carriers are linked...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics