GENETIC ALGORITHMS FOR THE RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM IN AIRCRAFT HEAVY MAINTENANCE

Kusol  Pimapunsri; Darawan  Weeranant; Andreas  Riel

Authors

Kusol Pimapunsri Department of Industrial Engineering, Faculty of Engineering, King Mongkut’s University of Technology North Bangkok, Bangkok, Thailand.
Darawan Weeranant Department of Industrial Engineering, Faculty of Engineering, Rajamangala University of Technology Phra Nakhon, Bangkok, Thailand.
Andreas Riel G-SCOP Laboratory, Grenoble Institute of Technology, Grenoble, France.

Keywords:

Genetic algorithm, RCPSP, aircraft maintenance

Abstract

Due to complex sets of interrelated activities in aircraft heavy maintenance (AHM), many airlines have to deal with substantial aircraft maintenance downtime. The scheduling problem in AHM is regarded as an NP-hard problem. Using exact algorithms can be time-consuming or even infeasible. This article proposes genetic algorithms for solving the resource-constrained project scheduling problem (RCPSP) in AHM. The objective of the study was to minimise the makespan of the maintenance plan. The proposed algorithms applied five heuristic dispatching rules to generate an initial population based on activity list formation. Resource allocation methods for RCPSP – earliest start time (EST) and workgroup and earliest start time (WEST) – were used to evaluate the fitness value. The elitist and roulette wheel methods were applied in the selection process. The sequences of the activity lists were then iteratively improved by crossover and mutation operations. The results show that the proposed algorithms perform efficiently compared to the existing solutions in terms of computational time and resource allocation.

References

Chen, C.-F., Wu, M.-C., and Lin, K.-H. (2013). Effect of solution representations on Tabu search in scheduling applications. Comput. Oper. Res., 40(12):2,817-2,825.

Eppinger, S.D. and Browning, T.R. (2012). Design Structure Matrix Methods and Applications. MIT Press, MA, 334p.

Franco, E.G., Zurita, F.T., and Delgadillo, G.M. (2007). A genetic algorithm for the resource constrained project scheduling problem (RSPSP). Bolivia Res. Develop., 1(7):41-52.

Friend, C.H. (1992). Aircraft Maintenance Management. Longman, Essex, England, 192p.

Gokdag, H. and Yildiz, A.R. (2012). Structural damage detection using modal parameters and particle swarm optimization. Mater. Test., 54(6):416-420.

Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA, 372p.

Goncalves, J.F., de Magalhaes Mendes, J.J., and Resende, M.G. (2005). A hybrid genetic algorithm for the job shop scheduling problem. Eur. J. Oper. Res., 167(1):77-95.

Goncalves, J.F., de Magalhaes Mendes, J.J., and Resende, M.G. (2008). A genetic algorithm for the resource constrained multi-project scheduling problem. Eur. J. Oper. Res., 189(3):1,171-1,190.

Habibi, F., Barzinpour, F., and Sadjadi, S. (2018). Resource-constrained project scheduling problem: review of past and recent developments. J. Proj. Manag., 3(2):55-88.

Hartmann, S. and Drexl, A. (1998). Project scheduling with multiple modes: A comparison of exact algorithms. Networks, 32(4):283-297.

Holland, J.H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Cambridge, MA, 211p.

Kadam, S.U. and Kadam, N.S. (2014). Solving resource-constrained project scheduling problem by genetic algorithm. In: 2014 2nd International Conference on Business and Information Management (ICBIM); January 9-11, 2014; Durgapur, India, p. 159-164.

Kiani, M. and Yildiz, A.R. (2016). A comparative study of non-traditional methods for vehicle crashworthiness and NVH optimization. Arch. Comput. Methods. Eng., 23(4):723-734.

Kolisch, R. and Hartmann, S. (2017). Heuristic algorithms for solving the resource-constrained project scheduling problem: Classification and computational analysis. In: Project Scheduling-Recent Models, Algorithms and Application. Weglarz, J. (ed.). Kluwer Academic, Boston, USA, p. 147-178.

Michalewicz, Z. (1994). Genetic Algorithms + Data Structures = Evolution Programs, 2nd ed. Springer-Verlag, Berlin, p. 1,030.

Pasala, S., Kumar, B.N., and Satapathy, S.C. (2013). A study of roulette wheel and elite selection on GA to solve job shop scheduling. Proceedings of the International Conference on Frontiers of Intelligent Computing: Theory and Applications; November 14-16, 2013; Bhubaneswar, Odisa, India, p. 477-485.

Pimapunsri, K. and Weeranant, D. (2018). Solving complexity and resource-constrained project scheduling problem in aircraft heavy maintenance. Int. J. Appl. Eng. Res., 13(11):8,998-9,004.

Qin, Y., Wang, Z.X., Chan, F.T., Chung, S.H., and Qu, T. (2019). A mathematical model and algorithms for the aircraft hangar maintenance scheduling problem. Appl. Math. Model., 67:491–509.

Rosales, L.J.S. (2015). Analysing uncertainty and delays in aircraft heavy maintenance, [Ph.D. thesis]. Alliance Manchester Business School, University of Manchester, Great Britain, p. 326.

Schmidt, M. (2017). A review of aircraft turnaround operations and simulations. Prog. Aerosp. Sci., 92:25-38.

Sriram, C. and Haghani, A. (2003). An optimization model for aircraft maintenance scheduling and re-assignment. Transport Res. A-Pol., 37(1):29-48.

Sukkerd, W. and Wuttipornpun, T. (2016). Hybrid genetic algorithm and tabu search for finite capacity material requirement planning system in flexible flow shop with assembly operations. Comput. Ind. Eng., 97:157-169.

Syswerda, G. (1991). Schedule optimization using genetic algorithms. In: Handbook of Genetic Algorithms. Davis, L. (ed.). Van Nostrand Reinhold, New York, p. 332–349.

Ting, C.K., Su, C.H., and Lee, C.N. (2010). Multi-parent extension of partially mapped crossover for combinatorial optimization problems. Expert Syst. Appl., 37(3):1,879-1,886.

Tormos, P., and Lova, A. (2001). A competitive heuristic solution technique for resource-constrained project scheduling. Ann. Oper. Res., 102:65-81.

UK Department for Business, Innovation and Skills. (2016). UK aerospace maintenance, repair, overhaul and logistics industry analysis – BIS research paper No. 275. Available from: Government Digital Service, UK.

Wall, M.B. (1996). A genetic algorithm for resource-constrained scheduling, [Ph.D. thesis]. Department of Mechanical Engineering, Massachusetts Institute of Technology. Cambridge, MA, p. 62.

Wang, J. (2016). Optimization and simulation of resource constrained scheduling problem using genetic algorithm. Sci. J. Bus. Manag., 4(6):229–237.

Weeranant, D., and Pimapunsri, K. (2017). Application of DSM and simulation technique to improve aircraft maintenance master plan. Proceedings of the 13th International Conference on Engineering, Science and Technology; June 6-8, 2017; Chonburi, Thailand, p. 29-33.

Yassine, A. (2004). An introduction to modeling and analyzing complex product development processes using the design structure matrix (DSM) method. Compu. Sci., 51(9):1-17.

Yassine, A. and Braha, D. (2003). Complex concurrent engineering and the design structure matrix method. Concurr. Eng., 11(3):165-176.