A Modified Adaptive Genetic Algorithm for the Flexible Job-Shop Scheduling Problem

Abstract:

Combined with the stage-related characteristics in solving process of the Flexible Job-shop Scheduling Problem (FJSP) and the evolution characteristics of Genetic Algorithm (GA), a modified Adaptive Genetic Algorithm based on iterative generation and analysis of fitness values distribution is presented in this paper, which has both methods advantages. Instance simulation verifies that the FJSPs own characteristics are utilized in its solution by using the modified AGA, which overcomes traditional GAs limitation that initial stage of evolution is early and random search of medium-late stage is slow. Such methods are verified to accelerate convergence process, enhance searching efficiency and solving precision as well as avoid low efficiency and local optimum.

• Periodical: Applied Mechanics and Materials (Volumes 401-403)
• Pages: 2037-2043
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.401-403.2037
• Online since: September 2013
• Authors: Ying Pan, Dong Juan Xue, Tian Yi Gao, Li Bin Zhou, Xiao Yu Xie
• Keywords: Adaptive Genetic Algorithm (AGA), Fitness Distribution Analysis, Flexible Job-Shop Scheduling Problem (FJSP), Iterative Generation

References

[1] M. Yazdani, M. Zandieh and M. Amiri, Flexible Job-shop Scheduling with Parallel Variable Neighborhood Search Algorithm, J. Expert Systems with Applications. 37(2010) 678-687.

DOI: 10.1016/j.eswa.2009.06.007

[2] G.H. Zhang, X. Y. Shao, P.G. Li and L. Gao, An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem, J. Computers & Industrial Engineering. 56(2009)1309-1318.

DOI: 10.1016/j.cie.2008.07.021

[3] Seyed Habib A, Rahmati and M. Zandieh, A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem, J. The International Journal of Advanced Manufacturing Technology. 58(2012)1115-1129.

DOI: 10.1007/s00170-011-3437-9

[4] Ling Wang, Gang Zhou, Ye Xu, Shengyao Wang and Min Liu, An effective artificial bee colony algorithm for the flexible job-shop scheduling problem, J. The International Journal of Advanced Manufacturing Technology. 60(2012)303-315.

DOI: 10.1007/s00170-011-3610-1

[5] C.Y. Zhang, Y.Q. Rao, P.G. Li and X.Y. Shao, Bi-level genetic algorithm for the flexible job-shop scheduling problem, J. Chinese Journal of Mechanical Engineering. 43(2007)119-124.

DOI: 10.3901/jme.2007.04.119

[6] Shun Cheng Fan and Jin Feng Wang, Scheduling for the Flexible Job-Shop Problem Based on Genetic Algorithm (GA), J. Advanced Materials Research. 1(2012)457-458, 616.

DOI: 10.4028/scientific5/amr.457-458.616

[7] Min Shuo Li and Ming Hai Yao, Research on Improved Genetic Algorithm Solving Flexible Job-Shop Problem, J. Advanced Materials Research. 2(2012) 479-481.

DOI: 10.4028/www.scientific.net/amr.479-481.1918

[8] Guo Hui Zhang, Liang Gao and Yang Shi, A Novel Variable Neighborhood Genetic Algorithm for Multi-Objective Flexible Job-Shop Scheduling Problems, J. Chinese Journal of Mechanical Engineering. 6 (2010)118-120.

DOI: 10.4028/www.scientific.net/amr.118-120.369

[9] Kacem I, Hammadi S and Borne P, Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems, C. The Proceeding of IEEE Transactions on Systems, Man and Cybernetics, Part C. 32(2002)408-419.

DOI: 10.1109/tsmcc.2002.1009117

[10] Paulli J A, Hierarchical approach for the FMS scheduling problem, J. European Journal of Operational Research. 86(2005)32-42.

DOI: 10.1016/0377-2217(95)00059-y

[11] Chen H, Ihlow J and Lehmann C A, Genetic algorithm for flexible Job-shop scheduling, C. IEEE international conference on robotics and automation. 24(1994) 656-667.

DOI: 10.1109/robot.1999.772512

[12] Zhang H P and Gen M, Multistage-based genetic algorithm for flexible job-shop scheduling problem, J. Complexity International. 11(2005)223-232.