Airport runway scheduling

Airport runway optimization is an ongoing challenge for air traffic controllers. Since demand for air-transportation is predicted to increase, there is a need to realize additional take-off and landing slots through better runway scheduling. In this paper, we review the techniques and tools of operational research and management science that are used for scheduling aircraft landings and take-offs. The main solution techniques include dynamic programming, branch and bound, heuristics and meta-heuristics.     

Scatter Search and Bionomic Algorithms for the aircraft landing problem

The problem of deciding how to land aircraft approaching an airport involves assigning each aircraft to an appropriate runway, computing a landing sequence for each runway and scheduling the landing time for each aircraft. Runway allocation, sequencing and scheduling for each aircraft must ensure the scheduled landing time lies within a predefined time window and meet separation time requirements with other aircraft. The objective is to achieve effective runway use.In this paper, the multiple runway case of the static Aircraft Landing Problem is considered. Two heuristic techniques are presented: Scatter Search and the Bionomic Algorithm, population heuristic approaches that have not been applied to this problem before.Computational results are presented for publicly available test problems involving up to 500 aircraft and five runways showing that feasible solutions of good quality can be produced relatively quickly.     

Scheduling aircraft landings at London Heathrow using a population heuristic

With increasing levels of air traffic, making effective use of limited airport capacity is obviously important. This paper reports on an investigation undertaken by National Air Traffic Services in the UK into improving runway utilisation at London Heathrow. This investigation centred on developing an algorithm for improving the scheduling of aircraft waiting to land. The heuristic algorithm developed (a population heuristic) is discussed and results presented using actual operational data relating to aircraft landings at London Heathrow. This data indicates that our algorithm could have improved on air traffic control decisions in such cases by between 2–5?% in terms of reducing the timespan required to land all of the aircraft considered.     

基于优先级的进离港航班排序优化问题研究

研究机场终端区进离港航班排序优化问题,对于提高跑道利用率以及降低航班延误损失具有重要意义。本文首先考虑航班运行方式(降落和起飞)、飞机类型以及航班的重要程度(航程是否连续)的不同所造成延误损失的不同,设计三维优先级表反映调度优先等级,并将其转化为延误成本系数。其次,为实现调度的公平性和减轻管制人员的工作负荷,设置允许延误的航班架次约束、邻边约束以及最大限制位置约束。再次,以最小化航班总延误成本为目标建立模型,提出相应的改进蚁群算法(GJAC)进行求解。最后通过数值实验验证所提算法在考虑调度优先等级及上述约束条件的同时能有效减少进离港航班队列的总延误成本。     

Optimal fuzzy counterparts of scheduling rules

The optimality of a fuzzy logic alternative to the usual treatment of uncertainties in a scheduling system using probability theory is examined formally. Fuzzy scheduling techniques proposed in the literature either fuzzify directly the existing scheduling rules, or solve mathematical programming problems to determine the optimal schedules. In the former method, the fuzzy optimality for the optimal scheduling rules is usually not justified but still assumed. In this paper, the necessary conditions for fuzzy optimality are defined, and fuzzy counterparts of some of the well-known scheduling rules such as shortest processing time (SPT) and earliest due date (EDD) are developed.     

A Simulation Model for Calculating Annual Congestion Delay Arising from Airport Runway Operations

This paper describes a simulation model of delays to aircraft caused by airport runway congestion. It was developed for the Australian Government as part of the Sydney Airport Project. Subsequently, it was used in a traffic management study of the airport which examined the scope of deferring the need for additional runway capacity by adopting administrative measures affecting runway utilization.     

A genetic algorithm for flow shop scheduling problems

Many scheduling problems are NP-hard problems. For such NP-hard combinatorial optimization problems, heuristics play a major role in searching for near-optimal solutions. In this paper we develop a genetic algorithm-based heuristic for the flow shop scheduling problem with makespan as the criterion. The performance of the algorithm is compared with the established NEH algorithm. Computational experience indicates that genetic algorithms can be good techniques for flowshop scheduling problems.     

Vehicle Scheduling — A Case Study

An application of vehicle scheduling techniques to the planning and operation of medical specimen collection services is described and a decision-making procedure suggested for use in this problem area. Some interesting results concerning the behaviour of vehicle scheduling savings algorithms, obtained during the course of the study, are also presented.     

Scheduling with list processing and problem oriented data structures: An itinerant teacher example

Heuristics are often employed to solve scheduling problems when complicated sets of constraints render standard mathematical approaches intractable. This paper illustrates how list processing and problem oriented data structures were utilized to facilitate development of an effective scheduling heuristic for itinerant teachers. The techniques employed would prove to be extremely useful in solving many other scheduling problems.     

A computational study of constraint satisfaction for multiple capacitated job shop scheduling

We introduce the multiple capacitated job shop scheduling problem as a generalization of the job shop scheduling problem. In this problem machines may process several operations simultaneously. We present an algorithm based on constraint satisfaction techniques to handle the problem effectively. The most important novel feature of our algorithm is the consistency checking. An empirical performance analysis is performed using a well-known set of instances of the job shop scheduling problem and a newly constructed set of instances of the multiple capacitated job shop scheduling problem. We show that our algorithm performs well for both sets of instances.     

Improved local search algorithms for the rectangle packing problem with general spatial costs

The rectangle packing problem with general spatial costs is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. This problem is very general, and various types of packing problems and scheduling problems can be formulated in this form. For this problem, we have previously presented local search algorithms using a pair of permutations of rectangles to represent a solution. In this paper, we propose speed-up techniques to evaluate solutions in various neighborhoods. Computational results for the rectangle packing problem and a real-world scheduling problem exhibit good prospects of the proposed techniques.     

Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems

In this article, we consider three decomposition techniques for permutation scheduling problems. We introduce a general iterative decomposition algorithm for permutation scheduling problems and apply it to the permutation flow shop scheduling problem. We also develop bounds needed for this iterative decomposition approach and compare its computational requirements to that of the traditional branch and bound algorithms. Two heuristic algorithms based on the iterative decomposition approach are also developed. extensive numerical study indicates that the heuristic algorithms are practical alternatives to very costly exact algorithms for large flow shop scheduling problems.     

The Scheduling of Magistrates to Courts

The problem of scheduling Magistrates to Courts may be formulated generally as an integer programming problem. However, when a particular problem is considered it is found that heuristic scheduling techniques will produce an acceptable solution to this particular problem without the need to use complex algorithms. The use of a computer program to implement the heuristic scheduling was found to produce a considerable saving in clerical effort.     

Data and queueing analysis of a Japanese air-traffic flow

Congestion is a major cause of inefficiency in air transportation. A question is whether delays during the arrival phase of a flight can be absorbed more fuel-efficiently in the future. In this context, we analyze Japan’s flow strategy empirically and use queueing techniques in order to gain insight into the generation of the observed delays. Based on this, we derive a rule to balance congestion delays more efficiently between ground and en-route. Whether fuel efficiency can be further improved or not will depend on the willingness to review the concept of runway pressure.     

A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis

In this note we propose an iterative scheduling technique which consists of consecutive forward/backward scheduling passes aimed at reducing the project duration by smoothing out the project's resource profile. The idea of iterative scheduling is initiated by Li and Willis in their related paper. The only common point between their scheduling technique and the one proposed here is the iterative feature. The two techniques differ both in algorithmic aspects and in the way activities are selected for scheduling at a decision point. In the technique proposed here activities are evaluated by well-reputed dispatching rules and a conflict based decision-making process called Local Constraint Based Analysis (LCBA). The results on benchmark problems from the literature demonstrate that LCBA specifically exploits the flexible activity time windows provided by the iterative scheduling technique.     

MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: A benchmark scheduling problem of the pharmaceutical industry

An efficient systematic iterative solution strategy for solving real-world scheduling problems in multiproduct multistage batch plants is presented. Since the proposed method has its core a mathematical model, two alternative MIP scheduling formulations are suggested. The MIP-based solution strategy consists of a constructive step, wherein a feasible and initial solution is rapidly generated by following an iterative insertion procedure, and an improvement step, wherein the initial solution is systematically enhanced by implementing iteratively several rescheduling techniques, based on the mathematical model. A salient feature of our approach is that the scheduler can maintain the number of decisions at a reasonable level thus reducing appropriately the search space. A fact that usually results in manageable model sizes that often guarantees a more stable and predictable optimization model behavior. The proposed strategy performance is tested on several complicated problem instances of a multiproduct multistage pharmaceuticals scheduling problem. On average, high quality solutions are reported with relatively low computational effort. Authors encourage other researchers to adopt the large-scale pharmaceutical scheduling problem to test on it their solution techniques, and use it as a challenging comparison reference.     

On distributed scheduling with heterogeneously delayed network-state information

We study the problem of distributed scheduling in wireless networks, where each node makes individual scheduling decisions based on heterogeneously delayed network state information (NSI). This leads to inconsistency in the views of the network across nodes, which, coupled with interference, makes it challenging to schedule for high throughputs. We characterize the network throughput region for this setup, and develop optimal scheduling policies to achieve the same. Our scheduling policies have a threshold-based structure and, moreover, require the nodes to use only the “smallest critical subset” of the available delayed NSI to make decisions. In addition, using Markov chain mixing techniques, we quantify the impact of delayed NSI on the throughput region. This not only highlights the value of extra NSI for scheduling, but also characterizes the loss in throughput incurred by lower complexity scheduling policies which use homogeneously delayed NSI.     

Some effects of aircraft arrival sequence algorithms

Although various airport landing sequencing algorithms have been considered in the literature, little work has been done in comparing their effects on Air Traffic Control, especially against first-come first-served (FCFS) runway sequences, the method most widely used in practice. This paper compares a number of such algorithms using a discrete-event simulation model of an airport with a single landing runway. Statistical methods are used to test for effects of sequencing algorithm, delay-sharing strategy, arrival rate and wake-vortex mix. Little benefit to delay, or stability of sequencing advice, is found from advanced sequencing when small changes are made to inputs calibrated to a specific airspace. Advanced sequencing improves landing rate, compared with FCFS sequencing, only when aircraft arrival rate is greater than maximum runway landing rate, and wake-vortex mix is sufficiently varied. Constrained position shifting constraints limit these improvements and it is shown that deterministic optimal techniques may actually be sub-optimal in a dynamic environment. Our main conclusion is that FCFS is a robust method under many conditions.     

Multifleet routing and multistop flight scheduling for schedule perturbation

Efficient and effective incidental scheduling techniques for schedule perturbation are essential to an airline carrier's operations. This research aims at developing a framework to assist carriers in fleet routing and flight scheduling for schedule perturbations in the operations of multifleet and multistop flights. The framework is based on a basic multifleet schedule perturbation model constructed as a timespace network from which strategic models are developed to research incidental scheduling. These network models are formulated as multiple commodity network flow problems. Lagrangian relaxation with subgradient methods accompanied by the network simplex method, a Lagrangian heuristic and a modified subgradient method are developed to solve the problems. A case study regarding the international operations of a major Taiwan airline carrier is presented.