隨著航空交通量逐年增加，天空變的更加擁擠，使得機場容量不足，加上流量管制，會造成繁忙機場在尖峰時刻班機的延遲，使成本增加。目前航管人員所使用的方法是先到先服務(First-Come-First-Served)，此方法無法改變飛機的進場順序，可能會造成降落的飛機等待時間過長而產生時間和成本的浪費。此研究在探討以最佳拆解法來加快排程演算法的求解速度，此演算法會將飛機的進場排序來做拆解，透過將進場順序拆解成較小的子集來重新排序進場的飛機，並有兩個主要的目標，第一個目標是要減少演算法的計算時間，透過拆解原始的最佳化問題來減少計算時間，讓我們可以在計算更大的飛機序列時也可以在短時間內完成。第二個目標是希望排序完成的飛機序列可以跟原來的作法一樣是最佳序列。最後會將此演算法與二次規劃算法來做比較，證明其方法的效率以及可行性。

Our sky has become overcrowded due to an increase in yearly air transports, which in turn has caused a shortage in airport capacity. Aircraft flow constraints result in delays in busy airports during peak times and will in turn increase the costs for airline companies. The current method used by air traffic controllers (ATCs) is First-Come-First-Served (FCFS). However, this method is insufficient to solve the sequence issues faced by aircraft. In this research, an optimal partition method is proposed to decrease the scheduling algorithm calculation time. In the algorithm, the sequence is broken down into several smaller subsequences and rescheduled to the aforementioned sequences with two main targets. The first target is to try to reduce the total computation time, which enables the computation of a longer sequence than was possible in the past. The second target would be to alter the previous sequence into a new and more efficient way for aircraft to land. Aircraft are overlapped between subsequences to ensure this method doesn’t happen while scheduling the sequence without overlapping, both separated subsequences have their optimal sequence. Once the separated sequences are combined, however, the complete sequence may not have the most optimal sequencing. The new approach sequence allows aircraft to land faster and in a more orderly fashion than the original sequence, thus reducing the makespan period. Finally, several simulation results are used to demonstrate the effectiveness of the proposed approach phase.

[1] OAG, "On-time performance for airlines and airports and TOP 20 busiest routes" 2018.
[2] ACI, "Annual World Airport Traffic Forecasts 2017–2040", 2017.
[3] Schulz, E., "Global Networks, Global Citizens Global Market Forecast 2018 - 2037", 2018.
[4] Capri, S., and Ignaccolo, M.,"Genetic algorithms for solving the aircraft sequencing problem: the introduction of departures into the dynamic model," Journal of Air Transport Management, vol. 10, no. 5, pp. 345-351, 2004.
[5] ICAO, "CNS/ATM," 1998.
[6] Abela, J., Abramson, D., Krishnamoorthy, M., Silva, A. De, and Mills, M., "Computing Optimal Schedules for Landing Aircraft," The 12th National Conference of the Australian Society for Operations Research, pp. 71-90, 1993.
[7] Beasley, J. E., Krishnamoorthy, M., Sharaiha Y. M., and Abramson D., "Scheduling aircraft landings -the static case", Transportation Science, vol. 34, No. 2, pp. 180-197, 2000.
[8] Bennell, J. A., Potts, C. N., and Mesgarpour, M., "A Review of Airport Runway Optimization", University of Southampton, 2009.
[9] Wen, M., "Algorithms of Scheduling Aircraft Landing Problem,"Department of Informatics and Mathematical Modelling Technical University of Denmark, 2005.
[10] Dear, R. G., "The Dynamic Scheduling of Aircraft in The Near Terminal Area," Flight Transportation Laboratory Massachusetts Institute of Technology Cambridge, 1976.
[11] Dear, R. G., and Sherif, Y. S.,"The Dynamic Scheduling of Aircraft in High Density Terminal Areas," Microelectronics. Reliability, vol. 29, No. 5, pp. 743-749, 1989.
[12] Lieder, A., Briskorn, D., and Stolletz, R., "A Dynamic Programming Approach for The Aircraft Landing Problem with Aircraft Classes," European Journal of Operational Research, vol. 243, no. 1, pp. 61-69, 2015.
[13] Wang, T. C., and Li, Y. J., "Optimal Scheduling and Speed Adjustment in En Route Sector for Arriving Airplanes," Journal of Aircraft, vol. 48, no. 2, pp. 673-682, 2011.
[14] Wang, T. C., and Chen, T. C., "Arrival and Departure Aircraft Scheduling with Turbulence Interaction Concept," Journal of Aircraft, vol. 53, No. 5 , 2016.
[15] Wang, T. C., and Tsao, C. H., "Time-Based Separation for aircraft Landing Using Danger Value Distribution Flow Model ," Mathematical Problems in Engineering, vol. 2012, pp. 16, 2012.
[16] FAA, "Air traffic control," 2018.
[17] FAA, "Instrument Flying Handbook, "2001.
[18] CAA, "Air Traffic Management Procedures,"2017.
[19] ICAO, "Air Traffic Management Procedures For Air Navigation Services Doc 4444,"2016.
[20] Nicolaon, J. P., Freville, E., Vidal, A., Crick, P., "Potential Benefits of a Time-based Separation Procedure to maintain the Arrival Capacity of an Airport in strong head-wind conditions," no. Fifth USA/Europe Air Traffic Management Research and Development Seminar ,2003.
[21] Balakrishnan, H., and Chandran, B., "Scheduling Aircraft Landings under Constrained Position Shifting ,"AIAA Guidance, Navigation, and Control Conference, Colorado, 2006.
[22] Briskorn, D. and Stolletz, R., "Aircraft landing problems with aircraft classes," Journal of Scheduling, vol. 17, pp. 31-45, 2014.
[23] Goldberg, D. E., and Holland, J. H., " Genetic Algorithms And Machine Learning," Machine Learning, vol. 3, pp. 95-99, 1988.
[24] Shanno, D. F., and Weil, R. L., " Linear Programming with Absolute Value Functionals," Operations Research, pp.120-124, 1971.