INTRODUCTION
Nowadays, Airport capacity is a bottleneck in the air traffic system.
Many airports operate at their maximum capacity (for some hours of the
day). Runways are critical resource of an airport. Airport runway capacity
is subject to large changes, mainly because of weather and visibility
conditions. Therefore, large arrival and departure delays occur frequently.
Capacity should be used in an efficient way. This can be done by creating
efficient landing and departure sequences and allocating an optimum assignment
to runway system.
It should be noted that airport capacity is mostly expressed as sum of
landing and take off operations (Jason et al., 2007). Current and
predicted levels of air traffic demand raise the need for airport capacity
enhancements, as well as reduction of the environmental impact (engine
emissions) and the costs incurred by operational inefficiencies (fuel
burn). In an effort to satisfy such a need, the presence of an automated
decision support system, which includes planning and control algorithms,
has a significant contribution (Anagnostakis et al., 2000).
One of the ways of runway capacity enhancement is increasing the number
of runways. Because of heavy costs and requires occupying urban lands,
construction of new runways often is not possible. Moreover, increasing
the number of runways without optimum operations planning and assignments
will not be undertaken completely. Using which runway, for which operation,
in which time plays an important part in the runways system capacity.
For example, in an airport with the single runway, the following parameters
have their own influential rules in determining operations planning: configuration
of runways, arrival and departure volumes, volume and place of fixes in
a time, place and number of apron gates, place and number of taxiways
and exit rapid taxiways, mix of aircrafts, etc. An increase of the number,
geometric complexity, runway`s orientation and location, runway crossing
points and final approach of runways, workloads of the controllers is
so important that without optimum operations planning and assignments,
most of the capacity of the runways and ultimately the airside capacity,
will not be used. In addition, strong delays, wasting of economic resources
and dissatisfaction of the airport users, among the passengers and airlines,
are of the other consequences.
This research, for the first time presents the scheduling method for
considering runway assignment and operations planning together which is
similar to the real world condition. The airport runway is a scarce resource
that must be shared by different runway operations (arrivals, departures
and runway crossings). The runway system, as a resource shared by all
aircraft, is a significant flow bottleneck due to many causes that either
limit the effective capacity of the airport or increase the demand for
runway service. A new generic method to represent the structure of the
Air Traffic Management (ATM) system is introduced in the following sections.
In some researches, a new structure for ATM has been proposed which is
the base of this research. Such a structure can be useful in any effort
to design and build decisionaiding systems for air traffic controllers,
because it describes the links and dependencies between the three main
traffic elements of ATM arrivals, departures and ground traffic. Runway
Operations Planning (ROP) belongs to Runway Operations Management (ROM),
which in turn is a part of the overall ATM System and is affected by decisions
made in other parts of ROM. The main tasks of ROM are:
• 
Runway configuration management 
• 
Runway assignment management, which determines the runway to be
used by each aircraft 
• 
Runway operations planning, i.e., the tactical planning of runway
usage by different arriving and departing flights 
Although some researchers have explained these three tasks hierarchically,
but in this study, Runway Assignment Management and Runway Operations
Planning have been considered together (Anagnostakis et al., 2001).
Planning the allocation of runway time to the various types of runway
operations can be a challenging task, in any busy airport. Planning and
control function are the two main tactical tasks that must be conceptually
distinguished from each other, without overlooking the interrelations
and links between the corresponding tasks.
These links are usually neither obvious nor easily observable because,
in many cases, one controller mentally performs both planning and control
tasks at the same time. In an airport, both planning and control are performed
in a distributed fashion. Consequently, a successful design of an automated
ROP system that will be under airportwide use must provide the necessary
integration between the different objectives, constraints, controls and
inputs from all parties involved in airport ground operations. Then the
Runway Operations Planning problem is an optimization problem that is
affected by the operational and financial interests of several involved
parties, such as the airport users (airlines, passengers) and the ATM
service providers (airport authority, air traffic controllers) (Anagnostakis
et al., 2001). Generally in literature, regarding objectives and
constraints, operations planning is modeled and solved just for arrivals
or departures.
Assignment of aircrafts (arrivals and departures) to the runways is one
of the main concerns of the controllers; because sometimes in high demands
they should make immediate and optimal decisions which sometimes don`t
lead to overall use of available runways capacity. Most of the assignments
are done for the arrivals. Runway assignment of arrival aircraft is a
tactical decision made by controllers. Strategic reassignments, or allocations,
assist in balancing controller workload and reducing delay, but are difficult
for controllers because of the high workload already associated with the
traffic load. As terminal area controllers become consumed with the task
of separation, strategic runway allocation becomes neglected. During high
workload periods, controllers simply assign runways to fill available
landing slots when aircraft are well within TRACON airspace. This process
of tactical adjustments to the arrival schedule requires coordination
between controllers and ultimately leads to higher workload and increased
delay. For runway assignment, knowledge based runway allocation flowchart
and decision Tree are used. There is a similar process for the departures.
However arrival and departure assignments are done independently.
REQUIREMENT OF INTEGRATION OF ROP AND RAM
Runway assignment is not a problem in single runway airports and just
operations planning for arrival and departure are important. With greater
demands for capacity enhancement, number of runways would be increased,
but an increase in the number of runways calls for their tactical planning;
otherwise it is not possible to use the enhanced capacity in a suitable
manner, comparing to the increase in the number of the added runways.
Compared with increase in the number of runways, operations planning would
be even more complicated because of increase in demand for terminal airspace.
This complexity often brings about high workloads for the air traffic
controllers which leads to selecting simple methods for runway assignments
(for example in parallel runway systems, one runway is assigned for arrivals
and one for departures). This decision is not necessarily an optimal planning
and may not lead to the optimal runway usage. Runway assignment is not
an independent task, because in this case arrivals and departures are
assigned regarding to closeness gate and fix locations of the runways.
Some of the undertaken researches are devoted just to the arrival operations
planning, considering airlines costs. Because of the dependencies between
arriving and departing fights, it is expected that additional cost savings
can be accomplished if arrivals and departures are considered simultaneously.
Therefore, considering arrival and departure operations planning with
runway assignments to increase airport throughput is a must.
SCHEDULING APPROACH FOR PROBLEM ANALYSIS
Scheduling is the allocation of resources over time to perform an allocation
of tasks. The process of scheduling in general requires both sequencing
and resource allocation decisions (Baker, 1974). In order to the objective
function be satisfied, not only the sequencing of the arrival and departure
operations in each runway but also in runways generally should be distribute
optimally. Objective function can include following performance measures:
minimizing average runway occupancy time, minimizing maximum runway occupancy
time, minimizing average aircraft tardiness from time table, minimizing
maximum aircraft tardiness from time table, minimizing number of tardy
aircrafts and so on.
Model formulation: In modeling of this problem, the Hybrid Flow
Shop is used. One of the major advantages of this model to the previously
presented models is that the previous model has been considered as a Real
World Problem model. In this model the separation time of aircrafts and
also the ready time of arrival or (departure) to (or from) the fixed points
have been considered. One of the major objectives of airport officials
is minimizing delays; therefore selected target function is formulated
for 2 Stage Flow Shop with Ready Time as follows that minimizing the delays
is usually the goal of the airport authorities; then:
Subject to:
In which:
j,l 
: 
Aircraft subscript (Job) 
I 
: 
Runway subscript (Machine) 
k 
: 
Approach or departure procedure index 
n 
: 
No. of Aircrafts 
m 
: 
No. of Runways 
z 
: 
No. of approach or departure procedure 
P_{ij} 
: 
The processing time of aircraft j on runway I (form
fix to exit of runway or inversely) 
P`_{kj} 
: 
The processing time of aircraft j on Approach or departure
procedure k (form fix to exit of runway or inversely) 
w_{j} 
: 
Weight factor of aircrafts 
r_{j} 
: 
Ready time of jth aircraft (in fix) 
d_{j} 
: 
Due date of the aircraft j 
C_{j1} 
: 
The completion time of aircraft j in 1st stage 
C_{j2} 
: 
The completion time of aircraft j in 2nd stage 
M 
: 
Large number 
X_{ij} 
: 
A Binary variable: 1 if flight j assigned to runway
i and 0 otherwise 
X`_{kj} 
: 
A Binary variable: 1 if flight j assigned to procedure
k and 0 otherwise 
Y_{kj} 
: 
A Binary variable: 1 if flight l lands earlier than
flight j (in the 2nd stage) and 0 otherwise 
Y`_{lj} 
: 
A Binary variable: 1 if flight l lands earlier than
flight j (in the 1st stage) and 0 otherwise 
S_{i} 
: 
Runway i approach procedures set 
T_{j} 
: 
Tardiness of aircraft j 
Regarding Hybrid 2 stage based on separation time Model, the model is
formulated as follows:
It is assume objective function and constraints till constraint is same
as 1 to 5.
In which is separation time between aircraft l and j, assuming
that aircraft l is serviced earlier than aircraft j.
Constraint description
(2) 
: 
Every aircraft assign to a procedure. 
(3) 
: 
Every aircraft assign to a runway. 
(4) 
: 
Completion time of aircraft j in procedure k is greater or equal
than ready time plus process time of aircraft j in the procedure stage. 
(5) 
: 
Completion time of aircraft j in runway i is greater or equal than
completion time of aircraft j in procedure stage plus process time
of aircraft j in the runway stage. 
(12, 13) 
: 
Start time between two subsequent aircrafts in procedure stage is
greater or equal than Separation time. 
(14, 15) 
: 
Completion time between two subsequent aircrafts in procedure stage
is greater or equal than Separation time. 
(16, 17) 
: 
Completion time of leading aircraft, between two subsequent aircrafts
in procedure stage is greater or equal than completion time of trailing
aircraft plus process time of leading aircraft. 
(18, 19) 
: 
Start time between two subsequent aircrafts in runway stage is greater
or equal than Separation time. 
(20, 21) 
: 
Completion time between two subsequent aircrafts in runway stage
is greater or equal than Separation time. 
(22, 23) 
: 
Completion time of leading aircraft, between two subsequent aircrafts
in runway stage is greater or equal than completion time of trailing
aircraft plus process time of leading aircraft. 
(24) 
: 
Priority constraint in procedure stage for aircrafts j,l. 
(25) 
: 
Priority constraint in runway stage for aircrafts j,l. 
(26) 
: 
Tardiness constraint: Tardiness of aircraft j is greater or equal
than due date of aircraft j subtract of completion time of same aircraft. 
ANALYSIS OF THE SOLUTION
Because all of the above issues are generalization of
model, all issues are NPhard. Therefore, to solve them, it is unavoidable
to use heuristic techniques (Lawler, 1977; Lenstra, 1977).
For solving this problem, two type methods are used: heuristic method
that is the method of adjacent pair wise interchange and metaheuristic
method that is the SA (Simulated Annealing) method.
Due to extensive aspects of the problem and elongation of solving time with
exact methods such as LINGO, metaheuristic method is used to solve the problem
instead of exact methods. It is important to mention that it is very important
to make quick decisions for optimum use of runways. Sometimes this is not possible
with exact methods and this is one of the reasons of using SA solution. This
algorithm is mainly based on Pair Wise Interchange and includes the following
stages.
Neighborhood search method: Unlike constructive algorithms, improvement
heuristics start with an already built schedule and try to improve it
by some given procedures. Their use is necessary since the constructive
algorithms (especially some algorithms that are adapted from pure makespan
heuristics and some dispatching rules such as the SPT and LPT rules) do
not consider due dates (and therefore, they do not consider the minimization
of the number of tardy jobs). In this research, some fast improvement
heuristics will be investigated to improve the overall function value
by dealing mainly with the due date criterion. The iterative algorithms
described in the following and in section 5 are based on the pairwise
interchange (PI) neighborhoods.
The PI neighborhood exchanges a pair of arbitrary jobs π_{r}
and π_{i}, where 1≤i, r≤n and i≠r. Such an operation
swaps the jobs at positions r and i, which yields π = [π_{1}
. . .π_{r1} π_{i} π_{r+1}...π_{i1}
π_{r} π_{it1}. . .π_{n}]. For
example, assume that the current solution is [4 9 8 7 3 1 6 2 5] and then
randomly the couple of job positions to be exchanged is selected, e.g.,
positions 1 and 3. Thus, the new solution will be [8 9 4 7 3 1 6 2 5].
In the PI neighborhood, the current solution has nx(n1)/2 neighbors (Jungwattanakit
et al., 2007).
Step 1 
: 
Take all aircrafts at stage 1 (procedure stage) in one sequence 
Step 2 
: 
Select two arbitrary aircrafts and exchange their positions 
Step 3 
: 
Divide this sequence aircrafts to K sections 
Step 4 
: 
Assign section 1 to procedure 1, section 2 to procedure 2, ... and
section K to procedure K 
Step 5 
: 
Take all aircrafts at stage 2 (runway stage) in one sequence 
Step 6 
: 
Select two arbitrary aircrafts and exchange their positions 
Step 7 
: 
Divide this sequence aircrafts to
section 
Step 8 
: 
Assign section 1 to runway 1, section 2 to runway 2, … and
section to runway 
Determination of an initial solution algorithm: Since the flexible
flow shop scheduling problem is NPhard (this is already true for two
stages, with at least one stage with multiple machines (Gupta, 1988)),
algorithms for finding an optimal solution in polynomial time are unlikely
to exist. Thus, heuristic methods are studied to find approximate solutions.
Most researchers develop existing heuristics for the classical flexible
flow shop problem with identical machines by using a particular sequencing
rule for the first stage. They follow the same scheme (Santos et al.,
1996).
According to Graham notation F2L_{max} problem is the reduced
form of this research problem which is known as a NPhard problem which
results that problem also is a NPhard (Garey and Johnson, 1978).
Therefore, it is not possible to solve the problem using exact methods
in logical time. Instead of exact methods, an innovative method is used
to initial solution of this problem. Because the stage related to the
runways is the main stage, aircraft is allocated to the runways and based
on that, allocation of aircraft to procedures will be specified more.
Major algorithm: In order to allocate the aircraft to runways,
the major problems become a virtual one in which it is assumed that there
is only one stage and for each aircraft a virtual processing time is calculated.
This process is as follows:
Step 1 
: 
Virtual processing time ofaircraft on aircraft is calculated from
the following relationship: 
Step 2 
: 
Prioritize the aircraft based on WEDD algorithm and allocate them
to runways according to virtual processing times (in this step, assume
that procedure stage does not exist). 
Step 3 
: 
After allocation of aircraft to runways, do the time schedule in
the major problem in backward form so as to obtain the time of starting
landing operations of each aircraft on the relevant runway. (The manner
of backward time schedule operations will be explained hereunder).

Step 4 
: 
These times of landing start will be due date for procedures stage.
Now based on these due dates for step 1, obtain allocation of aircraft
to different procedures and operations finish time through WEDD algorithm.

Step 5 
: 
Based on the obtained allocations in step 2 for runways stage and
completion of operations related to procedure step, determine final
time schedule of aircrafts according to the real processing time in
the runways stage. 
Step 6 
: 
Finish the algorithm. 
Backward scheduling algorithm: Do the following operations for
each runway.
Step 1 
: 
Call the number of allocated tasks to the runway, q. 
Step 2 
: 
Time of aircraft q so as to make the time of finishing landing operations
equal to its delivery time (d_{(q)}). In this case call St_{q}
the time of starting landing. Also put u = q. 
Step 3 
: 
Put u = u1. 
Step 4 
: 
If d_{(u)} is the time of delivery of u aircraft, time the
u aircraft in such a way that the time of finishing landing operations
becomes exactly as follows: 
In this case name the time of starting landing St_{(u)}.
Step 5 
: 
If u = 1, finish the algorithm. Otherwise proceed to 
WEDD algorithm: The maximum job lateness and the maximum job tardiness
are minimized by WEDD sequencing can be constructed as follows:
Step 1 
: 
Prioritize the aircraft based on the following sequence: 
Which d_{(j)} and W_{(j)} are respectively the time of
delivery and weight of aircraft with j priority. Also put u = 0.
Step 2 
: 
Put u = u1. 
Step 3 
: 
Allocated the aircraft with u priority to the runway and that can
finish landing operations earlier than other runways. (Regarding the
time of freeing of runways and aircraft ready time). 
Step 4 
: 
if u = n, then finish the algorithm, otherwise proceed to step 2. 
IMPROVEMENT OF SIMULATED ANNEALING METHOD
There are two ways in which SA may be combined with an alternative method;
either using the alternative method to provide a good initial solution
which SA attempts to improve, or by using SA to provide a good initial
solution as a starting point for the alternative method. Johnson et
al. (1987) provide some experimental results for the graph partitioning
problem. They show that both quality of solution and running time may
be improved by the use of a good starting solution. When a good initial
solution is used, the initial temperature in the cooling schedule is reduced;
otherwise the benefits of the good initial solution will be lost. They
also show that starting solutions which take advantage of the special
structure of the problem instance being considered seem preferable to
those obtained by general heuristics.
The second approach is exemplified by using SA as a way of obtaining
a good initial solution for a branch and bound algorithm for integer programming
algorithm.
Iterative simulated annealing algorithm: An SA algorithm is an
iterative search method, in which an initial solution is repeatedly improved
by making small local alterations until no such alteration yields a better
solution. It was developed by Kirkpatrick et al. (1983). An SA
algorithm simulates ideas and mechanisms found in the physical annealing
of a solid. The concept comes from the field of material science in which
a solid is first melted after heated in a high temperature and then it
is slowly cooled so that it reaches a thermodynamic equilibrium.
In general, an SA algorithm is a stochastic optimization method for minimizing
a function f over a discrete domain S. Starting from an initial solution
sεS, an SA algorithm generates a new solution
in the neighborhood of the initial solution s by using a suitable operator.
Concerning the neighborhood, in this research, a PI neighborhood (i.e.,
two arbitrary jobs are selected and interchanged) was considered. The
objective function value of the new solution is then compared to the objective
function value f(ś) of the initial solution (remember that the objective
function value of the full schedule generated from the job sequence for
the first stage is taken). The change in the objective function value,
δ = f (ś)f (s), is calculated. If the objective function value
decreases (δ<0), the new solution is automatically accepted and
it becomes the point from which the search will continue. If the objective
function value increases (δ≥0), then a solution with a larger
objective function value may also be accepted with a probability, usually
determined by a function, exp (δ/T ), where TεR is a control
parameter of the SA algorithm, called the temperature. The role of the
temperature T is significant in the operation of an SA algorithm.
Table 1: 
Time assignment of the example in two stages for test
problems 

AN = Aircraft No., RT = Ready Time, CL = Class, WT =
Weight, DD = Due Date, RWY = Runway and PCR = Procedure 
Table 2: 
Results of test problems for LINGO and SA methods 

MO: Mean of Objective, STD = Standard Deviation, DT
= Duration Time 
This
temperature, which is simply a positive number, is periodically reduced
every NT iterations, where NT denotes the epoch length, so that it moves
gradually from a relatively high value to near zero as the algorithm progresses
according to a function referred to as the cooling schedule (Jungwattanakit et al., 2007).
Validity of SA method: Here for proving the validation of SA,
several small test problems (10 aircraft, 3 procedures and 3 runways)
according to Table 1 designs and then solve with both
LINGO and SA method (Table 2).
It is noted that an optimal solution can be obtained by running commercial
mathematical programming software, LINGO 8.0, with an Intel Pentium 4,
3.4 GHz, Core 2 Duo CPU with 2.00 GB of RAM.
Computational results: Solving the integrated model in macrodimensional
problems (increasing number of aircraft, procedure and runway), SA method
is good; because, with increasing the problem dimension, duration time
of LINGO increase and it is not applicable for air traffic controllers.
Here three problem according Table 3 were considered.
Numerical results and Gantt chart values for these 3 problems, is showed
in Table 49.
Throughout running the problems, it was found in coefficient 0.95, the
duration time of results becomes too long.
It should be noted that in order to be used executively in practice,
this is a decision aiding model not a decision making model.
Table 3: 
Time assignment of three problems 

Table 4: 
Problem 1(15 aircraft, 3 procedure and 3 runways) 

MO = Mean of Objective, STD = Standard Deviation, DT
= Duration Time 
Table 5: 
Gantt table of problem 1 

AN = Aircraft No, PCR No. = Procedure No., RWY No. =
Runway No.
Objective function = 90.8 
At the final
stage, air traffic controllers are responsible for control and direction
of aircraft. The aircraft are classified based on the necessary separation
among aircrafts. Time scheduling is entered to the program as delivery
due times.
According to the Table 49, as one of the very remarkable
advantages of this system we can refer to 3 and 10 runway case of the
above aircraft. Because the aircraft 7 is the 3rd aircraft that enters
the system, according to operating rule, the priority should be given
to the 3rd aircraft on the order of entry (FirstComeFirstServe) and
according to wise logic of air traffic controllers; but as it is observed
by solving this problem and implementing the program, this aircraft is
served on the 15th min and by applying a little delay for it, in order
to make the optimal use of runways system; because total delay of using
the runways is minimized. This is the case that is known as Inserted Idleness
in sequential references of operations and timing. Therefore, by considering
them together and presenting an integrated model of management of allocation
and operational programming of runways, appropriate measures with a more
extended view to make the optimal and maximum use of capacity of airport
air section are taken.
It should be noted that based on the results of this research, the SA
method is known as the best solving method which provide the most optimal
and quickest solution. Attention also should be paid, to the degree of
relaxation and speed of the solving other models too.
Suggestion for temperature reduction coefficient and initial temperature:
One of the other results of this research is determine the temperature
reduction coefficient and initial temperature for SA method, according
to Table 1012.
Table 6: 
Problem 2 (20 aircraft, 3 procedure and 3 runways) 

MO = Mean of Objective, STD = Standard Deviation, DT
= Duration Time 
Table 7: 
Gantt table of problem 2 

AN = Aircraft No, PCR No. = Procedure No. and RWY No.
= Runway No. Objective function = 200.6 
Table 8: 
Problem 3 (20 aircraft, 6 procedure and 4 runways) 

MO = Mean of Objective, STD = Standard Deviation, DT
= Duration Time 
Table 9: 
Gantt table of problem 3 

AN = Aircraft No. PCR No. = Procedure No., RWY No. =
Runway No. objective function = 125.7 
Table 10: 
Problem 1(15 aircraft, 3 procedure and 3 runways) 

TI = Initial Temperature, CO = Reduction Temperature
Coefficient, MEO = Mean Objective, MIO = Min. Objective, MIS = Selected
Min Objective, RC = Reliability Coefficient, RAN = RC Ranking 
Table 11: 
Problem 2 (20 aircraft, 3 procedure and 3 runways) 

TI = Initial Temperature, CO = Reduction Temperature
Coefficient, MEO = Mean Objective, MIO = Min. Objective, MIS = Selected
Min Objective, RC = Reliability Coefficient, RAN = RC Ranking 
Table 12: 
Problem 3 (20 aircraft, 6 procedure and 4 runways) 

TI = Initial Temperature, CO = Reduction Temperature
Coefficient, MEO = Mean Objective, MIO = Min. Objective, MIS = Selected
Min Objective, RC = Reliability Coefficient, RAN = RC Ranking 
According to Table 1012, minimum objective and good
reliability coefficient is shown with underlined numbers. As they show,
best coefficient and initial temperature take place in 0.9 and 1.0, respectively.
CONCLUSION
In this research, for the first time, the process of evolution of scheduling
method which encompasses Integrated Model of Runway Assignment and Operations
Planning for Airside Capacity Enhancement (ACE) is presented. In this
model, 2 stages Flexible Flow Shop method was used.
Regarding the fact that air traffic controllers need decision making
tools for assigning aircraft to runways and vice versa, certainly these
expert and skilled persons have a limited time to select the best option
for the manner of using the runway which may not always lead to the most
optimal option according to the aircraft control work load. This decision
making process gets much more sophisticated so that an assistant decision
maker appears to be unavoidable.
In this research, two solving method for integration of runway assignment
and operations planning model were used. To solve these models, the exact
methods were found suitable when the number of aircraft is small. However,
for large airports with heavy traffic, the SA method can solve the problem
in less time period. Throughout the research, it was found by increasing
coefficient till 0.9, the accuracy of results becomes better. To overcome
the complexity problem, the auxiliary virtual algorithm was used.
Advantages of SA method are acceptable accuracy in the short time that
air traffic controllers can use this model as a decisionaiding and some
cases as decision making tools.