Using Evolutionary Algorithms for the Scheduling of Aircrew on Airborne Early Warning and Control System
Abstract
Equipped with an advanced radar and other electronic systems mounted on its body, Airborne Early Warning and Control System (AWACS) enables the airspace to be monitored from medium to long distances and facilitates effective control of friendly aircraft. To operate the complex equipment and fulfill its critical functions, AWACS has a specialised flight and mission crew, all of whom are extensively trained in their respective roles. For mission accomplishment and effective use of resources, tasks should be scheduled, and individuals should be assigned to missions appropriately. In this paper, we implemented evolutionary algorithms for scheduling aircrew on AWACS and propose a novel approach using Genetic Algorithms (GA) with a special encoding strategy and modified genetic operations tailored to the problem. The objective is to assign aircrew to various AWACS tasks such as flights, simulator sessions, ground training classes and other squadron duties while aiming to maximise combat readiness and minimise operational costs. The presented approach is applied to several test instances consisting notional weekly schedules of Turkish Boeing 737 AEW&C Peace Eagle AWACS Base, generated similar to real-world examples. To test the algorithm and evaluate solution performance, experiments have been conducted on a novel scheduling software called AWACS Crew Scheduling (ACS), developed as a test bed. Computational results reveal that presented GA approach proves to be quite successful in solving the AWACS Crew Scheduling Problem and exhibits superior performance when compared to manual methods.
References
Mevlutoglu, A. Commentary on assessing the Turkish Defense Industry: Structural issues and major challenges. Defence Studies, 2017. 17(3), 282-294. https://doi.org/10.1080/14702436.2017.1349534
Milligan, M.K. Implementing COTS open systems technology on AWACS. Crosstalk: J. Def. Software Eng., 2000.
Chen, E. The future of AWACS: Technological Advancement or Technological Relic. 2017, Air Command and Staff College, Air University Maxwell AFB United States.
Delaney, W.P. Air Defense of the United States: Strategic Missions and Modern Technology. International Security, 1990, 15(1), 181-211. https://doi.org/10.2307/2538986
Christopher, S. Active electronically-steered array surveillance radar: Indian value addition. Def. Sci. J., 2010, 60(2), 184-188. https://doi.org/10.14429/dsj.60.338
Van Deventer, R. Airborne warning and control system (AWACS) and space: A framework to help understand the issues. Air Univ Maxwell AFB School of Advanced Airpower Studies, 2000.
Elliott, L.R.; Cardenas, R. & Schiflett, S.G. Measurement of AWACS Team Performance in Distributed Mission Scenarios. Air Force Research Lab Brooks AFB TX, 1999. https://doi.org/10.1037/e438122006-001
Colegrove, C.M. & Bennett Jr, W. Competency-based training: Adapting to warfighter needs. Air Combat Command Langley AFB VA Flight Operations Division, 2006. https://doi.org/10.21236/ada469472
Evans, S.E. Improving the cost efficiency and readiness of MC-130 aircrew training. The Pardee RAND Graduate School: Santa Monica, 2015, pp. 146.
Kawakami, T. An aid for flight squadron scheduling. Naval Postgraduate School (NPS), Monterey, California. (MSc. Thesis), 1990.
Gokcen, O.B. Robust aircraft squadron scheduling in the face of absenteeism. Air Force Institute of Technology (AFIT) School of Engineering and Management: Wright Patterson AirForce Base, Ohio. 2008. (MSc. Thesis)
Durkan, M. Multi-objective decision analysis for assignment problems. Air Force Institute of Technology (AFIT) School of Engineering and Management: Wright Patterson Air Force Base, Ohio. (MSc. Thesis), 2011.
Van Brabant, J.D. A monthly squadron sortie scheduling model for improved combat readiness. Naval Postgraduate School (NPS), Monterey, California. 1993. (MSc Thesis)
Nguyen, C.T. An interactive decision support system for scheduling fighter pilot training. Air Force Institute of Technology (AFIT) School of Engineering and Management: Wright Patterson AFB, Ohio. 2002. (MSc Thesis)
Newlon, T.M. Mathematical programming model for fighter training squadron pilot scheduling. Air Force Institute of Technology (AFIT) School of Engineering and Management: Wright Patterson AFB, Ohio. 2007. (MSc Thesis)
Brown, R.P. Optimizing readiness and equity in marine corps aviation training schedules. Naval Postgraduate School: Monterey, California. 1995. (MSc. Thesis)
Yavuz, M. Optimizing an F-16 squadron weekly pilot schedule for the Turkish Air Force. Air Force Institute of Technology (AFIT) School of Engineering and Management: Wright Patterson AFB, Ohio. 2010. (MSc. Thesis)
Boyd, Jay A.H.; Case, A. Cunningham; Darren, P. Gray; & John, L. Parker. Network flow model for optimizing fighter squadron scheduling. Dayton: Graduate Research Project, Air Force Institute of Technology, 2006.
Vestli, M.; Lundsbakken, L.; Fagerholt, K. & Hvattum, L.M. Scheduling fighter squadron training missions using column generation. Optimization Letters, 2015, 9(8), 1659-1674. https://doi.org/10.1007/s11590-014-0794-y
Sevimli, A. Sortie generation simulation of a fighter squadron. 2016, Air Force Institute of Technology (AFIT) School of Engineering and Management: Wright Patterson AFB, Ohio. (MSc. Thesis)
Aslan, D., A decision support system for effective scheduling in an F-16 Pilot Training Squadron. Air Force Institute of Technology (AFIT) School of Engineering and Management: Wright Patterson Air Force Base, Ohio. (MSc. Thesis), 2003.
Dyer, D.E. A visual programming methodology for tactical aircrew scheduling and other applications. Defense Technical Information Center, 1991. https://doi.org/10.21236/ada244635
Erdemir, U. Optimizing flight schedules by an automated decision support system. Air Force Institute of Technology (AFIT) School of Engineering and Management: Wright Patterson AFB, Ohio. 2014. (MSc Thesis)
Shirley Jr, M.D. An Improved Heuristic for Intercontinental Ballistic Missile Crew Scheduling. Air Force Institute of Technology (AFIT) School of Engineering and Management: Wright Patterson AFB, Ohio. 1994. (MSc Thesis)
Boke, C. Combining and Analyzing the Tanker and Aircrew Scheduling Heuristics. Air Force Institute of Technology (AFIT) School of Engineering and Management: Wright Patterson AFB, Ohio. 2003. (MSc Thesis)
Mitchell, M. An introduction to genetic algorithms. MIT Press, 1998, pp. 221. https://doi.org/10.1002/cplx.6130010108
Holland, J. Adaptation in artificial and natural systems. Ann Arbor: The University of Michigan Press, 1975, pp. 232. https://doi.org/10.7551/mitpress/1090.001.0001
Angeline, P.J. Evolution revolution: An introduction to the special track on genetic and evolutionary programming. IEEE Expert: Intelligent Syst. Applications, 1995, 10(3), 6-10. https://doi.org/10.1109/MIS.1995.10027
Davis, L. Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991, pp. 385. https://doi.org/10.1016/s0004-3702(98)00016-2
Belew, R. Evolving networks: Using the genetic algorithm with connectionist learning. In Proceedings of the Second Artificial Life Conference, Addison-Wesley, 1991, pp. 511-547.
Goldberg, D.E. & Holland, J.H. Genetic algorithms and machine learning. Machine Learning, 1988, 3(2), 95-99. https://doi.org/10.1023/a:1022602019183
Kearney, William T., Using genetic algorithms to evolve artificial neural networks. Honors Theses, 2016, Paper 818.
Michalewicz, Z., Evolution strategies and other methods. In Genetic Algorithms+Data Structures=Evolution Programs. Springer, 1996, pp. 159-177. https://doi.org/ 0.1007/978-3-662-02830-8_9
Montana, D.J. & Davis, L. Training feedforward neural networks using genetic algorithms. In International Joint Conference on Artificial Intelligence, 1989.
Schaffer, J.D.; Whitley, D. & Eshelman, L.J. Combinations of genetic algorithms and neural networks: A survey of the state of the art. In IEEE International Workshop on Combinations of Genetic Algorithms and Neural Networks, 1992, pp. 1-37. https://doi.org/10.1109/cogann.1992.273950
Sexton, R.S. & Sikander, N.A. Data mining using a genetic algorithm- trained neural network. Intelligent Syst. Accounting, Finance Management, 2001, 10(4), 201-210. https://doi.org/10.1002/isaf.205
Goldberg, D.E. & Deb, K. A comparative analysis of selection schemes used in genetic algorithms. Foundations Genetic Algorithms, 1991, 1, 69-93. https://doi.org/10.1016/b978-0-08-050684-5.50008-2
Kitano, H. Empirical studies on the speed of convergence of neural network training using genetic algorithms. In AAAI, 1990.
Miller, G.F.; Todd, P.M. & Hegde, S.U. Designing neural networks using genetic algorithms. In International Conference on Genetic Algortihms, 1989.
Holland, J.H. Genetic algorithms and classifier systems: Foundations and future directions. Michigan Univ., Ann Arbor (USA), 1987. https://doi.org/10.1016/0004-3702(89)90050-7
Vidulich, M.A.; Nelson, W. Todd; Robert, S. Bolia; Nicole, M. Guilliams & Annie, B. McLaughlin. An Evaluation of speech controls for AWACS Weapons Directors. 2004, Sytronics Inc Dayton Oh. https://doi.org/10.21236/ada423447
Rao, P. Computers in air defence. Def. Sci. J., 1987, 37(4), 507-513. https://doi.org/10.14429/dsj.37.5950
Where otherwise noted, the Articles on this site are licensed under Creative Commons License: CC Attribution-Noncommercial-No Derivative Works 2.5 India