Scheduling of Time-Shared Jet Aircraft

Keskinocak, Pinar; Tayur, Sridhar
August 1998
Transportation Science;Aug98, Vol. 32 Issue 3, p277
Academic Journal
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.


Related Articles

  • Processing time generation schemes for parallel machine scheduling problems with various correlation structures. Lin, Yang; Pfund, Michele; Fowler, John // Journal of Scheduling;Dec2014, Vol. 17 Issue 6, p569 

    This research considers the generation of random processing times for parallel machine scheduling problems. We present several processing time generation schemes that consider different levels and combinations of machine correlation and job correlation. Also, metrics to evaluate the amounts of...

  • ROUTING AND SCHEDULING ON A SHORELINE WITH RELEASE TIMES. Psaraftis, Harilaos N.; Solomon, Marius M.; Magnanti, Thomas L.; Kim, Tai-up // Management Science;Feb1990, Vol. 36 Issue 2, p212 

    In this paper we examine computational complexity issues and develop algorithms for a class of"shoreline" single-vehicle routing and scheduling problems with release time constraints. Problems in this class are interesting for both practical and theoretical reasons. From a practical perspective,...

  • A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering. Bartholdi III, John J. // Operations Research;May/Jun81, Vol. 29 Issue 3, p501 

    The problem of cyclic staff scheduling is solved by a linear programming round-off heuristic for which a bound on the absolute error is established. The quality of the bound is independent of the resource requirements. Moreover, the quality of the bound improves as the matrix of resource...

  • Competitive genetic algorithms for the open-shop scheduling problem. Prins, Christian // Mathematical Methods of Operations Research;2000, Vol. 52 Issue 3, p389 

    Abstract. For more than two machines, and when preemption is forbidden, the computation of minimum makespan schedules for the open-shop problem is NP-hard. Compared to the flow-shop and the job-shop, the open-shop has free job routes which lead to a much larger solution space, to smaller gaps...

  • Solving the Teacher Assignment-Course Scheduling Problem by a Hybrid Algorithm. Gunawan, Aldy; Kien Ming Ng; Kim Leng Poh // International Journal of Computer, Information & Systems Science;2007, Vol. 1 Issue 2, p136 

    This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem...

  • A special purpose multi-criteria heuristic function for a single machine scheduling problem with forward dynamic programming. Ozdagoglu, Guzin; Erdem, Sabri; Salum, Latif // International Journal of Advanced Manufacturing Technology;Sep2013, Vol. 68 Issue 5-8, p1875 

    Sequencing is one of the major research areas in increasing manufacturing productivity. In case of multiple items to be manufactured using multiple processes, complex sequencing may also be considered as a queuing problem where the products are processed with respect to the priorities which can...

  • OPTIMIZING OVER THE EFFICIENT SET USING A TOP-DOWN SEARCH OF FACES. Sayin, Serpil // Operations Research;Jan/Feb2000, Vol. 48 Issue 1, p65 

    The problem of optimizing a linear function over the efficient set of multiple objective linear programming problem is studied. The decomposition of the efficient faces is used as the basis of a search-based algorithm to solve this problem. The faces of the feasible region are characterized by...

  • Earliness-Tardiness Scheduling Around Almost Equal Due Dates. Hoogeveen, J. A.; Van De Velde, S. L. // INFORMS Journal on Computing;Winter97, Vol. 9 Issue 1, p92 

    Discusses the existence of another class of problems that are structurally less complicated than the general earliness-tardiness problem. Details of common due date problems; Logic behind Emmons' matching algorithm; List of earliness-tardiness problems to which the optimality principle of the...

  • Combined column generation and constructive heuristic for a proportionate flexible flow shop scheduling. Huang, Yueh-Min; Shiau, Der-Fang // International Journal of Advanced Manufacturing Technology;Sep2008, Vol. 38 Issue 7/8, p691 

    In a proportionate flow shop problem, jobs have to be processed through a fixed sequence of machines, and processing time for each job is equal on all machines. Such a problem has seldom been tackled. Proportionate flexible flow shop (PFFS) scheduling problems combine the properties of...


Read the Article


Sign out of this library

Other Topics