Scheduling of Time-Shared Jet Aircraft

Pinar Keskinocak and Sridhar Tayur
Additional contact information
Pinar Keskinocak: Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA 15213
Sridhar Tayur: Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA 15213

Transportation Science, 1998, vol. 32, issue 3, 277-294

Abstract: Motivated by a real application, we consider the following aircraft scheduling problem. At any time, the aircraft are at different locations or are serving a customer and new customer requests arrive, each consisting of a departure location, departure time, and destination. Our objective is to satify these requests (by subcontracting extra aircraft if necessary) at minimum cost under additional constraints of maintenance requirements and previously scheduled trips. We show that the jet aircraft scheduling problem is NP complete and discuss three special cases. We show that the second and third special cases are also NP complete. We provide a polynomial time network flow based algorithm for the first special case and a pseudo-polynomial time dynamic programming algorithm for the second special case. We formulate the problem as a 0–1 integer program and observe that most small and medium size problems can be solved by Cplex. For larger and difficult instances, we provide a fast heuristic with good performance.

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.32.3.277 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:32:y:1998:i:3:p:277-294

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().