Scheduling of time-shared jet aircraft

DOI10.1287/TRSC.32.3.277MaRDI QIDQ2783817zbMATH OpenOpenAlexWikidataFDO

Authors Pinar Keskinocak, Sridhar R. Tayur

Publication date 1 July 2002

Published in Transportation Science (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/8b2c7b5b8b42bb49f3c7fe749535490b2990d963

zbMATH Keywords

0-1 integer programaircraft scheduling problemNP completepolynomial time network flow based algorithmpseudo-polynomial time dynamic programming algorithm

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90)

Review text

dummary: 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.

Recommendations

• Some properties of the fleet assignment problem
• Heuristics for flight and maintenance planning of mission aircraft
• Network flow-based approaches for integrated aircraft fleeting and routing
• Daily Aircraft Routing and Scheduling
• scientific article; zbMATH DE number 1951555

Cited in

(12)

• License class design: Complexity and algorithms
• An iterative graph expansion approach for the scheduling and routing of airplanes
• Strategic planning in fractional aircraft ownership programs
• Scheduling aircraft landings using airlines' preferences
• Models and solution methods for the generation of flight schedules
• Scheduling charter aircraft
• A decision support model for establishing an air taxi service: a case study
• Effective truckload dispatch decision methods with incomplete advance load information
• Stressing symbolic scheduling techniques within aircraft maintenance optimization
• scientific article; zbMATH DE number 1523212 (Why is no real title available?)
• On the complexity of adjacent resource scheduling
• Aircraft and crew scheduling for fractional ownership programs

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: Scheduling of time-shared jet aircraft

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2783817)