IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v34y2000i2p180-197.html
   My bibliography  Save this article

Scheduling Aircraft Landings—The Static Case

Author

Listed:
  • J. E. Beasley

    (The Management School, Imperial College, London SW7 2AZ, England)

  • M. Krishnamoorthy

    (CSIRO Mathematical and Information Sciences, Private Bag No. 10, Clayton South MDC, VIC 3169, Australia)

  • Y. M. Sharaiha

    (The Management School, Imperial College, London SW7 2AZ, England)

  • D. Abramson

    (Department of Digital Systems, Monash University, Clayton, VIC 3169, Australia)

Abstract

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.

Suggested Citation

  • J. E. Beasley & M. Krishnamoorthy & Y. M. Sharaiha & D. Abramson, 2000. "Scheduling Aircraft Landings—The Static Case," Transportation Science, INFORMS, vol. 34(2), pages 180-197, May.
    • Handle: RePEc:inm:ortrsc:v:34:y:2000:i:2:p:180-197
    DOI: 10.1287/trsc.34.2.180.12302
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.34.2.180.12302
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.34.2.180.12302?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Carsten Jordan & Andreas Drexl, 1995. "A Comparison of Constraint and Mixed-Integer Programming Solvers for Batch Sequencing with Sequence-Dependent Setups," INFORMS Journal on Computing, INFORMS, vol. 7(2), pages 160-165, May.
    2. Andreussi, Alberto & Bianco, Lucio & Ricciardelli, Salvatore, 1981. "A simulation model for aircraft sequencing in the near terminal area," European Journal of Operational Research, Elsevier, vol. 8(4), pages 345-354, December.
    3. L. Bianco & P. Dell'Olmo & S. Giordani, 1999. "Minimizing total completion time subject to release dates and sequence‐dependentprocessing times," Annals of Operations Research, Springer, vol. 86(0), pages 393-415, January.
    4. Lucio Bianco & Salvatore Ricciardelli & Giovanni Rinaldi & Antonio Sassano, 1988. "Scheduling tasks with sequence‐dependent processing times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(2), pages 177-184, April.
    5. Harilaos N. Psaraftis, 1980. "A Dynamic Programming Approach for Sequencing Groups of Identical Jobs," Operations Research, INFORMS, vol. 28(6), pages 1347-1359, December.
    6. Tan, K. C. & Narasimhan, R., 1997. "Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach," Omega, Elsevier, vol. 25(6), pages 619-634, December.
    7. Kut C. So, 1990. "Some Heuristics for Scheduling Jobs on Parallel Machines with Setups," Management Science, INFORMS, vol. 36(4), pages 467-475, April.
    8. C. S. Venkatakrishnan & Arnold Barnett & Amedeo R. Odoni, 1993. "Landings at Logan Airport: Describing and Increasing Airport Capacity," Transportation Science, INFORMS, vol. 27(3), pages 211-227, August.
    9. Lee, Young Hoon & Pinedo, Michael, 1997. "Scheduling jobs on parallel machines with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 100(3), pages 464-474, August.
    10. Matteo Fischetti & Gilbert Laporte & Silvano Martello, 1993. "The Delivery Man Problem and Cumulative Matroids," Operations Research, INFORMS, vol. 41(6), pages 1055-1064, December.
    11. Jean-Claude Picard & Maurice Queyranne, 1978. "The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling," Operations Research, INFORMS, vol. 26(1), pages 86-110, February.
    12. Alfred Blumstein, 1959. "The Landing Capacity of a Runway," Operations Research, INFORMS, vol. 7(6), pages 752-763, December.
    13. Franca, Paulo M. & Gendreau, Michel & Laporte, Gilbert & Muller, Felipe M., 1996. "A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times," International Journal of Production Economics, Elsevier, vol. 43(2-3), pages 79-89, June.
    14. Liao, C. J. & Yu, W. C., 1996. "Sequencing heuristics for dependent setups in a continuous process industry," Omega, Elsevier, vol. 24(6), pages 649-659, December.
    15. A. G. Lockett & A. P. Muhlemann, 1972. "Technical Note—A Scheduling Problem Involving Sequence Dependent Changeover Times," Operations Research, INFORMS, vol. 20(4), pages 895-902, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Allahverdi, Ali & Gupta, Jatinder N. D. & Aldowaisan, Tariq, 1999. "A review of scheduling research involving setup considerations," Omega, Elsevier, vol. 27(2), pages 219-239, April.
    2. Ahmed Ghoniem & Hanif D. Sherali & Hojong Baik, 2014. "Enhanced Models for a Mixed Arrival-Departure Aircraft Sequencing Problem," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 514-530, August.
    3. Hanen Akrout & Bassem Jarboui & Patrick Siarry & Abdelwaheb Rebaï, 2012. "A GRASP based on DE to solve single machine scheduling problem with SDST," Computational Optimization and Applications, Springer, vol. 51(1), pages 411-435, January.
    4. A R Brentnall & R C H Cheng, 2009. "Some effects of aircraft arrival sequence algorithms," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(7), pages 962-972, July.
    5. J E Beasley & M Krishnamoorthy & Y M Sharaiha & D Abramson, 2004. "Displacement problem and dynamically scheduling aircraft landings," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(1), pages 54-64, January.
    6. Mujawar, Sachin & Huang, Simin & Nagi, Rakesh, 2012. "Scheduling to minimize stringer utilization for continuous annealing operations," Omega, Elsevier, vol. 40(4), pages 437-444.
    7. Pohl, Maximilian & Kolisch, Rainer & Schiffer, Maximilian, 2021. "Runway scheduling during winter operations," Omega, Elsevier, vol. 102(C).
    8. Julia Bennell & Mohammad Mesgarpour & Chris Potts, 2013. "Airport runway scheduling," Annals of Operations Research, Springer, vol. 204(1), pages 249-270, April.
    9. Rakesh Prakash & Jitamitra Desai & Rajesh Piplani, 2022. "An optimal data-splitting algorithm for aircraft sequencing on a single runway," Annals of Operations Research, Springer, vol. 309(2), pages 587-610, February.
    10. Raf Jans, 2009. "Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 123-136, February.
    11. Kinable, Joris & Cire, Andre A. & van Hoeve, Willem-Jan, 2017. "Hybrid optimization methods for time-dependent sequencing problems," European Journal of Operational Research, Elsevier, vol. 259(3), pages 887-897.
    12. Sepehr Nemati & Oleg V. Shylo & Oleg A. Prokopyev & Andrew J. Schaefer, 2016. "The Surgical Patient Routing Problem: A Central Planner Approach," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 657-673, November.
    13. Drexl, Andreas & Jordan, Carsten & Kimms, Alf, 1997. "Gruppierungs- und Reihenfolgeprobleme in der Fertigung," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 447, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    14. Silva, Marcos Melo & Subramanian, Anand & Vidal, Thibaut & Ochi, Luiz Satoru, 2012. "A simple and effective metaheuristic for the Minimum Latency Problem," European Journal of Operational Research, Elsevier, vol. 221(3), pages 513-520.
    15. Russ J. Vander Wiel & Nikolaos V. Sahinidis, 1996. "An exact solution approach for the time‐dependent traveling‐salesman problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(6), pages 797-820, September.
    16. Jason A. D. Atkin & Geert De Maere & Edmund K. Burke & John S. Greenwood, 2013. "Addressing the Pushback Time Allocation Problem at Heathrow Airport," Transportation Science, INFORMS, vol. 47(4), pages 584-602, November.
    17. Akbari, Vahid & Shiri, Davood, 2021. "Weighted online minimum latency problem with edge uncertainty," European Journal of Operational Research, Elsevier, vol. 295(1), pages 51-65.
    18. Roberto Roberti & Aristide Mingozzi, 2014. "Dynamic ng-Path Relaxation for the Delivery Man Problem," Transportation Science, INFORMS, vol. 48(3), pages 413-424, August.
    19. Rivera, Juan Carlos & Murat Afsar, H. & Prins, Christian, 2016. "Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 249(1), pages 93-104.
    20. Samà, Marcella & D’Ariano, Andrea & D’Ariano, Paolo & Pacciarelli, Dario, 2017. "Scheduling models for optimal aircraft traffic control at busy airports: Tardiness, priorities, equity and violations considerations," Omega, Elsevier, vol. 67(C), pages 81-98.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:34:y:2000:i:2:p:180-197. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.