Scheduling of time-shared jet aircraft

Scheduling of time-shared jet aircraft

0.00 Avg rating0 Votes
Article ID: iaor2001825
Country: United States
Volume: 32
Issue: 3
Start Page Number: 277
End Page Number: 294
Publication Date: Aug 1998
Journal: Transportation Science
Authors: ,
Keywords: networks, programming: dynamic, programming: integer
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 satisfy 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.

Reviews

Required fields are marked *. Your email address will not be published.