The problem of sequencing and scheduling airplanes landing and taking off on a runway is under consideration. We propose a new family of valid inequalities which are obtained from the study of the single machine scheduling problem polytope. In this paper we consider the integrated management of departures and arrivals on a single runway, and we will refer to this problem as ADMAN (Arrival and Departure MANagement). In ADMAN, one wants to (jointly) schedule the take-offs and the landings of a set of airplanes F . For each arrival and departure ight i 2 F , an arrival/departure window Ti is given, and the ight must land/takeoff in this time window, however the departure can be canceled (at high cost). Two successive ights i and j on the runway must be separated by a minimum time interval sij which depends on the involved airplanes. The official timetable provides wanted arrival and departure times. However, when one or more airplanes are delayed, a new schedule must be found, so that (some measure of) the deviation from the official timetable is minimized. For details on the different approaches for AMAN and DMAN we refer the reader to a recent survey [1]. The great majority of the approaches presented in the literature are heuristic or meta-heuristic - see again [1], but also the literature discussion in the recent paper by [2]. As for MIP approaches, we observe rst that ADMAN can be interpreted as a classical single machine scheduling problem with sequence dependent setup times and earliness/tardiness objective function (for a recent paper on this problem see [3]). The runway corresponds to the machine, ights correspond to jobs and time separations between ights on the runway to setup times. In this paper the Time Indexed (TI) formulations is considered. In TI formulations, the time horizon is discretized in small ⋆ The research of I. Vasilyev is supported by the Russian Foundation for Basic Research, research project No. 14-07-00382 Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
Introduction and problem statement time periods. The schedule of a given ight (job) is modeled by a set of binary variables, each associated with a feasible departure or arrival time period.
Let L and D be the sets of arriving and departure ights correspondingly, L[D = F . Let us associate a binary variable xit with every i 2 F and every t 2 Ti, which is 1 if and only if ight i arrives/departs at time t. Also, with every departure i 2 D we associate a binary variable yi which is 1 if i is dropped and 0 otherwise. Since every ight is assigned (at most) one arrival/departure time in a feasible schedule, for every i 2 F and every k; l 2 Ti, k ̸= l, we have xik + xil 1.
Consider now two distinct ights i; j 2 F , and assume that the assignment k and l violates the separation requirement between i and j, that is sji < l k < sij . Then, we have either xik = 0 or xjl = 0 in any feasible solution. In turn, this can be expressed by the constraint xik + xjl 1 and we say that the pair (of indices) fik; jlg is an incompatible pair. For an instance of the problem, we let I be the set of all incompatible pairs (of indices).
With an instance of the problem, we associate an undirected graph G(V; E) called con ict graph. The nodes of G are in one-to-one correspondence to the x variables of the formulation and we have an edge between two nodes whenever the associated variables cannot both assume value 1. More formally, we let and
V = fit : i 2 F; t 2 Tig
E = I [ ffik; ilg : ik; il 2 V; k ̸= lg:
From the above discussion, it follows that x represents a feasible schedule, if and only if x satis es: xik + xjl 1
fik; jlg 2 E
A clique of an undirected graph is a subset of the nodes such that every two nodes
in the subset are adjacent. Incidently, observe that any pair of adjacent nodes is also
a clique (of cardinality 2). Let K be a clique of the con ict graph G(V; E), and let x
satisfy (
If K V is a clique and u; v 2 K, then the edge fu; vg is said to be covered by K.
An I-cover is a set of cliques K1; K2; : : : , such that every edge in I is covered by at
least one clique in the set. Let K = fK1; K2; : : : g be a I-cover. It is not difficult to see
that x satis es (
1 (i) ∑ xi;l l2Ti (ii) ∑ xit min ∑ ciyi + ∑
∑ qitxit i2F t2Ti ∑ xit = 1; i 2 L ∑ xit + yi = 1; i 2 D
1; K 2 K it2K xit 2 f0; 1g; i 2 F; t 2 Ti yi 2 f0; 1g; i 2 D where K = fK1; K2; : : : g is a I-cover and the (4:iii) de ne an I-cover system of inequalities.
Constraints (4.i) ensure that every arrival is assigned an arrival time from its time window, whereas constraints (4.ii) ensure that every departure is either dropped or assigned a departure time from its time window. Finally, constraints (4.iii) are the Icover inequalities which ensure that the schedule respects separation constraints. The objective function represents the overall cost of the solution. Observe that constraints (3.i) are implied by (4:i) and (4:ii), whereas 3.ii) are precisely (4.iii). 2
Valid inequalities
Title Suppressed Due to Excessive Length
We are nally able to write a 0,1 linear programming formulation of the problem:
(
One of the original and well studied example of I-cover system of inequalities (see, e.g., [3] and [4]) is given by the family of inequalities: xjt +
∑ k2Ti\[t sij+1;t] xik 1 i; j 2 F; i ̸= j; t 2 Tj
Note that each clique inequality of system (5) can be strengthened by lifting in a trivial fashion, giving the following system: ∑ xjl +
∑ l2Tj\[t sji+1;t] k2Ti\[t sij+1;t] xik 1 i; j 2 F; i < j; t 2 Tj [ Ti
In the sequel, for all Q F , jQj 2, and all i 2 Q, we let si(Q) = minfsij : j 2
Q n ig. A family of clique inequalities valid for (
∑ i2F l2[t si(F )+1;t]\Ti xil 1 t 2 T:
We refer to the formulation (
With the aim of de ning a stronger but also more compact time-indexed formulation, we introduce a new family of clique inequalities - that we call (S; t)-clique inequalities - generalizing (7): Proposition 1. Let t 2 T , S F and, with jSj minfsij : j 2 S n ig. The (S; t)-clique inequality: ∑
∑
i2S l2[t si(S)+1;t]\Ti
xil
is valid for (
Proof. It follows directly from (7) and from the trivial observation that any constraint which is valid for a subset of ights and time periods, is also valid for the larger sets.
Our preliminary computational experiments show, that with careful selection and separation algorithm for (S; t)-clique inequalities (8) along with some special xing and lifting procedures, allow us to develop an efficient branch-and-cut method to solve the real world instances to optimality.