An Optimal Fleet Assignment and Flight Scheduling Problem for an Airline Company

Abstract

An original problem statement and solution algorithms are presented for an applied problem in the scheduling theory. The idea of the optimal fleet assignment and Flight Scheduling problem considered in this paper is to find a scheduling control method that minimizes the losses of the airline company from aircraft schedule disruptions. The problem is NP-complete and cannot be solved accurately for any real-life number of dimensions. An efficient parametric algorithm is proposed for finding an approximate solution of the problem. The proposed algorithm is an extension of the schedule optimization algorithm for a system of unrelated parallel machines with job release dates, which is based on the makespan criterion (Cmax). A substantial example is presented of applying the algorithm, as well as statistics of testing it on the data of a generating problem by the Cmax criterion.

Keywords

• Optimal scheduling
• Airline fleet assignment
• Makespan criterion
• Efficient parametric algorithm

Introduction

One of the areas where optimization methods are traditionally applied in practice is the planning of airline operations. In this case, planning involves several stages, the most important being aircraft scheduling, fleet assignment, routing, and crew planning. A detailed review on this topic was published, e.g., by Grönkvist (2005) [1]; the formal problem statements and approaches to solving the basic problems were discussed by Sherali, Bish, and Zhu (2006) [2] and in the numerous publications following individual lines of applied research from among those listed above [3–22].

For instance, the problems and algorithms of airline fleet assignment modeling (FAM) are examined in [3–7]. The main focus in [8–16] is on the aircraft routing problem (ARP). Simultaneous solving of both problems (FAM and ARP) is considered, e.g., in [17–19]. Finally, the studies closest to the subject of the present paper [1, 5, 20–22] consider the optimal scheduling problem, including route changes and fleet assignment.

Copyright © by the paper’s authors. Copying permitted for private and academic purposes.

In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org Obviously, the above listed problems are closely related. All their relevant formal representations belong to the class of intractable problems of mixed programming. The approaches that are used to find their approximate solutions build on classical schemes such as the Lagrangian relaxation methods, column generation, and Benders decomposition and apply the well-known computational tools of combinatorial optimization, methods of cuts, and programming in constraints [1, 2].

The core of this work is an original problem statement in the form of an optimal scheduling problem for a system of unrelated parallel machines (aircraft) with job release dates (flight delays), which is adapted to the airline flight scheduling problem proposed by the authors in [23, 24], together with a special efficient parametric algorithm for its approximate solution [24]. 1

Conceptual and Formal Statement for the Optimal Fleet

Assignment and Flight Scheduling Problem

The input data are airline flight schedules, standard flight times for of all types of aircraft, and standard times for ground handling and flight preparations for all types of aircraft.

The real-time information is flight delays at any given time at all airports.

Then, conceptually, the scheduling problem consists in finding, for the flights in the planning period, such an airline fleet assignment that will minimize the maximum total deviation from the initial schedule for the entire fleet while satisfying all the constraints of the initial schedule in terms of the passenger flow, number of flights, and flight standards.

We use the following notation: l is the airport number, l  L ; i is the flight number, i  Il ,  Il  I , Il  Il'  , l, l' L ;

lL s is the type of aircraft, s  S ; j is the tail number, j  J s ,  J s  J , J s  J s'  , s, s' S ;

sS  i0 is the actual delay of flight i at the time of scheduling,  i0  0 , i  Il , l  L , 0   i0 . Hereinafter,  denotes a vector, matrix, or tensor corresponding to the context of dimension; ti0 is the scheduled departure time of flight i , i  Il , l  L , T 0  ti0 ; ti0  i0 is the possible actual departure time of flight i at the initial time of scheduling;

ti, j is the time of ground handling, preparation, and air travel of flight i of aircraft j , T  ti, j , i  Il , l  L , j  J s , s  S .

We need to find xi, j under the constraints:

1, if aircraft j is assigned to flight i, xi, j   0 otherwise,

i  Il , l  L , j  J s , s  S  xi, j  1 , i  Il l  L , jJ (constraint ( 2 ) means that only one aircraft is assigned to flight i); b j   xi, j  b j , l  L , j  J s s  S ,

iIl (constraint ( 3 ) means that aircraft with tail number j can be assigned to no less than b j and no more than b j flights);

 i, j is a possible delay in the departure of aircraft j on flight i , i  Il , l  L , j  J s , s  S ( i, j can be negative, which is taken into account in constraints ( 5 ) and ( 6 ))  i, j  ti0  i0   ( k, j  tk, j )xk, j , i  I k , j  J s , s  S ,

kIk (constraint ( 4 ) means that the delay of aircraft j at the current step (on flight i ) is a recursive function of the delays accumulated in the previous flights of this aircraft); ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) (7’)   i, j  i, j  yi, j  0 , i  Il , l  L , j  J s , s  S ; yi, j  0 , i  Il , l  L , j  J s , s  S .

  min   i, j xi, j   iIl Constraints ( 5 ) and ( 6 ) neutralize negative delays through the compensating varia bles yi, j  0 ; then,  i, j  0 is the dependent variable, having the meaning of adjusted delay between the arrival of the aircraft j and its flight i , taking into account the required service time on the ground, and

  i, j xi, j   ti, j xi, j   , l  L , j  J s , s  S , iIl iIl

Relations ( 7 ) and ( 8 ) represent the minimax makespan criterion. The use of this criterion helps achieve a uniform distribution of load on the fleet by minimizing the maximum total downtime for any aircraft from the whole set of aircraft of the airline.

Another variant of constraint ( 7 ) is ( 9 )

Instead of, or together with ( 7 ), one can apply an additive criterion of minimization of the total delays

   i, j xi, j  min jJiI Relations ( 4 ), which mediate constraints ( 5 ) and ( 7 ), contain recursions because  any subsequent (in time) values of  i, j and  i, j depend on the previous ones.

Calculating the delays  i, j in all the i previous steps is associated with considerable difficulties because, first, due to the multiplicity of the variants of their formation with the subsequent choice of the best, and, second, the expansion of recursions and reduction of the statement ( 1 ) - ( 8 ) to the one-stage mixed programming problem leads to an increase in the number of Boolean variables and constraints in the problem by a factor of I 2 , where I  sup I [23]. The structural complexity of ( 1 )–( 8 ) is thereby reduced to the computational complexity of the resulting problem statement, which remains intractable given that the initial dimension increases by a large factor.

For more detail on the expansion of recursions for a statement identical to ( 1 )–( 8 ) with the formation of a one-step problem (which we call, for brevity, a direct reduction) and the subsequent formation of a simplified (relaxed) problem with two criteria (called a bicriteria relaxation), which allows one to find close-to-optimal schedules in terms of makespan, see [23, 24]. These works also provide experimental proof of inefficiency of using the direct reduction. Thus, e.g., finding even an approximate solution with no more than a six-percent deviation from the optimum for a problem instance with 20 flights and 5 aircraft took more than 16 hours of computing time using a 6-core processor and the latest version of the IBM ILOG CPLEX optimization studio. In [24], one can also find the results of applying the bicriteria relaxation using CPLEX. Below we compare the accuracy and computing time in the approach developed in our publication with the results achieved through the application of the bicriteria relaxation (Table 9). 2

Parametric Algorithm for Finding Suboptimal Solutions

Since the problem contains recursions, DP is, most likely, the only computational method directly applicable to solving problem ( 1 )–( 8 ). However, the direct application of DP is inefficient, partly because the problem in question is NP-complete. In attempts at finding an accurate solution of ( 1 )–( 8 ), DP leads to an exhaustive search through all possible options. It is easy to calculate the number N of these options. For example, if k is the step number and we assume in ( 2 ) that b j  0 and b j  sup I , I  sup I , J  sup J , then, as shown below, considering that the number of options grows in a geometric progression with DP steps, we have  I 1  N   J  J  2 .. Therefore, the DP method in ( 1 )–( 8 ) has a complexity greater   than the exponential one and is not applicable in its pure form to problems with an actual number of dimensions.

To construct an efficient approximate algorithm, we use a general DP scheme with the sifting of locally worst options at certain DP steps. We tested this approach previously in solving optimal scheduling problems for unrelated parallel machines with job start delays [24]; the tests showed good results in terms of accuracy and speed.

We assume that all flights i  Il , l  L , are arranged in the order of the initial delays (the initial schedule  i0 ), considering the aircraft locations at the time of scheduling. Then, based on the DP procedure, we determine the step number   1, I . We denote the time when aircraft j completes flight  at step  as  f , j ( , j , t , j , x , j ) , j  J s , s  S , and the conditional minimum time of completion  of all flights at steps from 1 to  as  ( , j , ti, j , xi, j ) i  1, I , j  1,   f , j ( , j , t , j , x , j )  max0,[ , j x , j  1, j ( 1, j , ti, j , xi, j )] t , j x , j , j  1, J , i  1, 1 .

2 N  J  J  ...  J k  ...  J

I

 I 1   J 

  J  2 

We can sift out intermediate schedules in DP in different ways. If we discard all intermediate schedules at step k except the locally best one, we have a greedy algorithm. If we keep all the intermediate schedules, we have an exhaustive search through all the options. In the latter case, we have J intermediate schedule options at 2 k step 1, J options at step 2, and J options at step k . If we look for a compromise between accuracy and speed, then, considering that we seek to construct an efficient algorithm, the number of intermediate schedules should be polynomially dependent on the number of Boolean variables in ( 1 )–( 8 ).

The recurrent Bellman relation for this problem is

    , j ( 1, j , ti, j , xi, j )  f , j ( , j , t , j , x , j )  1, j ( 1, j , ti, j , xi, j ), i  1, 1 , ( 11 ) ( 10 ) ( 12 ) ( 13 )  ( , j ,ti, j , xi, j )  max  , j ( 1, j ,ti, j , xi, j ), j  J s , s  S , i  1, .

j

To achieve the minimum makespan in ( 7 )–( 8 ), we should select in the last step the minimum value of  I ( I , j , ti, j , xi, j ) , i.e., find.   min  I ( I , j ,ti, j , xi, j ) j  J s , s  S ,   i  Il , l  L . The total number of scheduling options that we need to find to ensure the best schedule is obtain J options at step 1, J

Let us now consider one such compromise. First, we determine the maximum number K of the options retained at stage k for further analysis. For convenience of description, we assume that K is a constant. For example, we assume that K  1024 and determine the maximum number K '  J k  K . Since the number of possible intermediate schedules increases by a factor of J at each step, we suggest sifting out 11/ J of the locally worst options at each step starting from k 1 .

 ln K   ln J   , where  is the integer part of the number.

Obviously, k : k   If we calculate the total number of schedule options generated in the algorithm, we k k

options at steps from options at step k , and also J k 1 k 1 to I . This scheme is implemented by sifting out J intermediate schedule options at all the steps from k  1 to I . Then, the number of options that remains for further consideration at each step beginning from k 1 is exactly J , and the total number of intermediate schedules N' is

N ' J  J 2  ...  J k 1  J k  ...  J k   J k 1  J  2  I  k  1 J k   ( 14 )

Since k is a constant, relation ( 14 ) represents a polynomial dependence of the complexity of the parametric DP algorithm with option-sifting on the dimension of problem ( 1 )–( 8 ). In this case, k is the degree of this polynomial. For clarity, we compare N with N' , assuming k  3 , I  1000 , and J  100 .

N  1001001 100 2 ,

Then, N '  1002 100 2  100  21003  98009900 . These circumstances underlie the ordinary complexity of the parametric algorithm (its complexity is defined by the parameter k ) and the virtually infinite complexity of the DP method.

Based on ( 14 ), we can estimate the total complexity of the parametric algorithm. To this end, it is sufficient to determine the complexity of the step beginning from k , which directly depends on the number of combinations of the variables xi, j at step k . If we denote this value as Pk , then, obviously, Pk  J k . In fact, this means that at each step beginning from k , the algorithm requires calculating Pk variants of constrains ( 7 ) for all the possible values of xk, j . In total, we have at all steps: P1  J , P2  J 2 , Pl  J k , l  k, I . In the above example, Pk  1003 , and, considering ( 14 ), we obtain a high complexity for a problem with an actual number of dimensions. We can overcome this difficulty either by reducing k or by decomposition.

Below we describe the parametric DP algorithm with the sifting of the locally worst intermediate options. Algorithm

AP 1. Enter the input data ( i0,ti, j ) , j  J s , s  S , i  Il , l  L , and the parameters k and N' . Assuming that 0, j ( 00,ti, j , xi, j )  0 , determine the initial step number  : 0 .

2.  :  1 .

  , j ( , j ,ti, j , xi, j ) .

3. Check the step number. If   I , proceed to point 7; otherwise, proceed to the next point.

4. At step  , determine the sequence of the subsequent steps (rearrange the flight  list), calculate the delays  , j , generate from ( 10 )–( 12 ) all the feasible fleet assign ment options, and calculate f , j ( , j , t , j , x , j ) and the schedule lengths 5. Check N , i.e., the number of options of  , j ( , j ,ti, j , xi, j ) at step  . If   k 6. Sift out J

 lengths  , j ( , j ,ti, j , xi, j ) . Return to point 2. , i.e., N  N ' , then proceed to point 2; otherwise, proceed to the next point. k 1

of all the options generated at point 4 with the largest schedule 7. Choose schedule options with the minimum length. Construct the final schedules using the inverse DP procedure.  A note on the AP algorithm regarding estimates for the delays  i, j :  At each step of the algorithm, one needs to estimate the delays  i, j for aircraft that  have not yet arrived at the airport of departure. The estimates for  i, j are found by solving the subproblems of finding all the shortest paths in a graph composed of the possible connections between the airports. In general, one should find these estimates at each step because the delays can vary from step to step, depending on the previous local fleet assignments. 3

Illustrative Example

Below is an illustrative fragment demonstrating the application of the proposed algorithm for constructing a close-to-initial flight schedule and fleet assignment for three aircraft (designated by their tail numbers 1, 2, and 3) of two different types.

The input data on the flights and time costs are given in Table 1.

In Table 1, the Time column contains ti, j ; the Location column shows the presence or absence of aircraft at the airport of departure at each step of scheduling; and the initial schedule corresponds to  i0 . The Tail Number column shows the numbers j . The data in Table 1 are sorted by  i0 , taking into account the aircraft location. The flights are numbered in the same order.

The algorithm parameters are k  1 , ( N '  3 ), J  3 , and I  11 .

Since k  1 , we can reduce the number of dimensions (the eliminated options are highlighted by filling). 

After the third step, both the aircraft locations and the current delays  i, j change, necessitating a new tail assignment sequence, i.e., a change in the sequence of the algorithm steps (see point 4 in AP ). 1, j  f1, j ,1  majx 1, j  1  max{6;0;0}=6 1  max0, 1,2,0 1,2 , 1  max0,0,    The change in the tail assignment is given in Table 4, whose rows are arranged in  the order of increasing  i, j , considering the current aircraft locations.

Destination airport 2 3 1 1 3 2 2 3 1 1 3   11 x8,1 x8,2 x11,1 x11,2 Flights: 1,2,3,6, 7,10,11, 5,8,4,9 1 1 1 0 0 0

This example clearly demonstrates the universal applicability of the AP algorithm. It is also suitable for solving both the FAM problem and the mixed FAM + ARP problem. The same feature allows finding for the target optimal scheduling problem a k -best solution that minimizes the airline company losses from disruptions in the initial aircraft flight schedules.

The solution obtained by the parametric AP algorithm can be improved using a procedure based on an exchange of flights between aircraft. Below we describe this algorithm.

At the first step, we select an aircraft with the maximum total flight time and try reassigning one of its flights to another aircraft. If the exchange reduces the value of the objective function, we repeat the process; otherwise, we move to the next flight.

At the second step, we select an aircraft with the maximum total flight time and consistently review the flights assigned to this aircraft. In each case, we search for flights that this aircraft makes in less time yet assigned to another aircraft. Then, the flights are exchanged between the aircraft. If the exchange reduces the value of the objective function, we repeat the second step; otherwise, we cancel the exchange and search for another flight suitable for reassignment. We denote the general exchangebased algorithm, as well as the one implemented at step two, as AС . The application of the AС algorithm at step two can be detailed as follows:

Algorithm AС 1. Select aircraft m with the maximum total flight time m   . 2. Assume i : 1 . 3. If i : m , then go to point 14. 4. Assume l : 1 . 5. If xm,l  0 , then go to point 12. 6. Assume j : 1 . 7. If j  l or xi, j  0 or tm, j  tm,l or ti,l  ti, j  m  i , go to point 10. 8. Assume xi, j  0 , xm, j  1 , xi,l  1 , xm,l  0 . 9. Calculate the value of the objective function. If it has decreased, go to point 1; otherwise, assume xi, j  1 , xm, j  0 , xi,l  0 , xm,l  1 .

10. Assume j : j  1 . 11. If j  J , go to point 7. 12. Assume l : l 1. 13. If l  J , go to point 5. 14. Assume i : i 1. 15. If i  I , go to point 3; otherwise, stop the algorithm.

Let us estimate the complexity of the AС algorithm, which searches for flight exchange options between aircraft for any finite schedule obtained by the AP algorithm. Since the former conducts an exhaustive search among all aircraft and all flights and calculates the value of the objective function for every exchange option, 2  the complexity of the exchange-based algorithm for one schedule is O I  J  . But   since the AP algorithm generates J schedules at the final step, the total upper-bound A software implementation of the parametric AP and exchange-based AС algorithms allowed us to investigate their properties for instances with a close-to-actual number of dimensions. The algorithms were tested on the data of the optimal scheduling problem for a system of unrelated parallel machine with job start delays [23]. Table 9 contains the results of testing the instances of problem ( 1 )–( 8 ) with the use of the above-mentioned means of solving the bicriteria relaxation of problem ( 1 )–( 8 ) [23] and the AP and AС algorithms. All the tests have the same number of dimensions. The number of flights is I  100 , and the number of aircraft is J  5 . The algorithms AP and AС were applied with two values of the parameter: k  4 and k  5 .

In Table 9, tda and da are, respectively, the solution time (hh:mm:ss) and the value of the efficiency criterion, which were obtained by applying the basic algorithm based on bicriteria relaxation and IBM ILOG CPLEX [24].The values tdp , dp , pdp , and dp are, respectively, the solution time (in seconds); the value of the criterion; and the relative and absolute worsening (improvement at a negative value) of the criterion achieved by the AP algorithm, compared with the basic algorithm. The corresponding cdp , pdcp , and cdp values were obtained by the AС algorithm.

In general, there is an evident absolute gain in speed due to the efficiency of the AP algorithm and its combination with AС . Moreover, the solutions obtained show almost complete superiority over the basic algorithm in terms of closeness to the optimal solutions. note the following points. There are no a priori accuracy estimates for AP and for the combination AP + AС , but there are a posteriori ones at small dimensions, which are as follows [24]: in approximately 82% of cases, an accurate solution was obtained in the generated tests. In the other cases, the deviation from the optimum was no more than 6%. This conclusion was derived from a comparison of the AP + AС testing results with the solutions of the same tests in CPLEX by the expansion of recursions and the direct reduction of problem ( 1 )–( 8 ) in milp.

The dimensions of the tests (100 flights and 30 aircraft) and the solution time offer hope that the designed toolkit would be efficient in solving real-life problems of airline planning.

Conclusions

The results obtained demonstrate the efficiency of the proposed approaches in solving real-life problems of air transportation planning, including aircraft fleet assignment, routing, and, if necessary, flight scheduling. Thus, our approach would make a promising a contribution to the planning practice of an airline company of any size. A posteriori estimates for the accuracy and speed of the algorithms lead us to conclude that the developed toolkit has evident advantages over its analogs.

The testing confirms experimentally, in terms of computing time, the efficiency of the AP + AС pair. Noteworthy is the insignificant contribution of the AС algorithm to the total complexity. The use of this algorithm adds no more than a second to the total computing time tdp for the tests in Tables 9–11.

References

1. Grönkvist , M.: The Tail Assignment Problem . PhD thesis , Chalmers University of Technology and Göteborg University, Göteborg, Sweden ( 2005 )

2. Sherali , H.D. , Bish , E.K. , Zhu , X. : Airline fleet assignment concepts, models, and algorithms . European Journal of Operational Research 172 , 1 - 30 ( 2006 )

3. Hane , C. A. , Barnhart , C. , Johnson , E. L. , Marsten , R. E. , Nemhauser , G. L. , Sigismondi , G. : The fleet assignment problem: solving a large-scale integer program . Mathematical Programming 70 , 211 - 232 ( 1995 )

4. Gu , Z. , Johnson , E. L. , Nemhauser , G. L. , Wang , Y. : Some Properties of the Fleet Assignment Problem . Technical report , School of Industrial & Systems Engineering , Georgia Institute of Technology, Atlanta, GA , USA ( 1993 )

5. Subramanian , R. , Scheff , Jr. R. P. , Quillinan , J. D. , Wiper , D. S. , Marsten , R. E. Coldstart : Fleet Assignment at Delta Air Lines . Interfaces 24 ( 1 ), 104 - 120 ( 1994 )

6. Ozdemir , Y. , Basligil , H. , Nalbant , K.G. : Optimization of fleet assignment: a case study in Turkey . An International Journal of Optimization and Control: Theories & Applications 2 ( 1 ), 59 - 71 ( 2012 )

7. Blegur , F.M.A. , Bakhtiar , T. , Aman , A. : Scenarios for fleet assignment: a case study at Lion Air . IOSR Journal of Mathematics 10 ( 5 ) Ver . I, 64 - 68 ( 2014 )

8. Kabbani , N. M. , Patty , B. W. : Aircraft routing at American Airlines . In: Proceedings of the Thirty-Second Annual Symposium of AGIFORS ( 1992 )

9. Clarke , L. W. , Johnson , E. L. , Nemhauser , G. L. , Zhu , Z. : The aircraft rotation problem . Annals of Operations Research 69 , 33 - 46 ( 1997 )

10. Cordeau , J. F. , Stojkovi´c, G., Soumis , F. , Desrosiers , J.: Benders decomposition for simultaneous aircraft routing and crew scheduling . Transportation Science 35 ( 4 ), 55 - 76 ( 2001 )

11. Barnhart , C. , Boland , N.L. , Clarke , L.W. , Johnson , E.L. , Nemhauser , G.L. , Shenoi , R.G. Flight string models for aircraft fleeting and routing . Transportation Science 32 ( 3 ), 208 - 220 ( 1998 )

12. Elf , M. , J ¨unger, M. , Kaibel , V. : Rotation planning for the continental service of a European Airline . In: W. Jager and H.-J. Krebs, editors, Mathematics - Key Technologies for the Future. Joint Projects between Universities and Industry . pp. 675 - 689 , Springer ( 2003 )

13. Sarac , A. , Batta , R. , Rump , C. M.: A Branch-and-Price Approach for Operational Aircraft Maintenance Routing . Working Paper, Department of Industrial Engineering, University of Buffalo, Buffalo, NY , USA, ( 2003 )

14. Gopalan , R. , Talluri , K. T.: The aircraft maintenance routing problem . Operations Research , 46 ( 2 ), 260 - 271 ( 1998 )

15. Ahuja , R. K. , Goodstein , J. , Mukherjee , A. , Orlin , J. B. , Sharma , D. : A Very Large-Scale Neighborhood Search Algorithm for the Combined Through and Fleet Assignment Model . Working Paper 4388-01 , MIT Sloan School of Management, Cambridge, USA ( 2001 )

16. Birbil , S.I. , Frenk , J.B.G. , Gromicho , J.A.S. , Zhang, S.: A Network Airline Revenue Management Framework Based on Decomposition by Origins and Destinations . Submitted manuscript ( 2015 )

17. Yan , S. , Tseng , C.H.: A passenger demand model for airline flight scheduling and fleet routing . Computers & Operations Research 29 , 1559 - 1581 ( 2002 )

18. Barnhart , C. , Boland , N.L. , Clarke , L.W. , Johnson , E.L. , Nemhauser , G.L. , Shenoi , R.G.: Flight string models for aircraft fleeting and routing . Transportation Science 32 ( 3 ), 208 - 220 ( 1998 )

19. Sandhu , R. , Klabjan , D. : Integrated Airline Planning . Working paper, submitted for publication, Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Campaign, Urbana, IL, USA ( 2004 )

20. Lettovsky , L. : Airline Operations Recovery: An Optimization Approach . PhD thesis , School of Industrial & Systems Engineering , Georgia Institute of Technology, Atlanta, GA , USA ( 1997 )

21. Kohl , N. , Larsen , A. , Larsen , J. , Ross , A. , Tiourine , S.: Airline Disruption Management - Perspectives , Experiences and Outlook. Research and Technology Report CRTR-0407 , Carmen Systems AB , Gothenburg, Sweden ( 2004 )

22. Rosenberger , J. M.: Topics in Airline Operations . PhD thesis , School of Industrial & Systems Engineering , Georgia Institute of Technology, Atlanta, GA , USA ( 2002 )

23. Avdeenko , T. V. , Mesentsev , Y. A. : Efficient approaches to scheduling for unrelated parallel machines with release dates . IFAC-Papers Online (IFAC Proceedings Volumes) . 49 ( 12 ), 1743 - 1748 ( 2016 )

24. Avdeenko , T. V. , Mezentsev , Y. A. , Estraikh , I.V. : Heuristic approach to unrelated parallel machines scheduling under availability and resource constraints . IFAC-PapersOnline , 50 ( 1 ), 13096 - 13101 ( 2017 )

25. Mezentsev , Y. A. : Binary cut-and-branch method for solving linear programming problems with boolean variables . In: Proc. DOOR 2016 , Vladivostok, Russia, September 19 - 23, CEUR-WS 1623. Pp. 72 - 85 ( 2016 )