Hybrid Genetic Algorithm Based on Chaotic Migration Strategy for Solving Flow Shop Scheduling Problem with Fuzzy Delivery Time
Wen-Zhan Dai and Kai Xia
School of Information and Electronic Engineering, Zhejiang Gongshang University
Hangzhou 310018, China
In this paper, a hybrid genetic algorithm based on a chaotic migration strategy (HGABCM) for solving the flow shop scheduling problem with fuzzy delivery times is proposed. First, the initial population is divided into several sub-populations, and each sub-population is isolated and evolved. Next, these offspring are further optimized by a strategy that combines NEH heuristic algorithm proposed by M. Navaz, J.-E. Enscore, I. Ham in 1983 with a newly designed algorithm that has excellent local search capability, thereby enhancing the strategy’s local search capability. Then, the concept of a chaotic migration sequence is introduced to guide the ergodic process of the migration of individuals effectively so that information is exchanged sufficiently among sub-populations and the process of falling into a local optimal solution is thereby avoided. Finally, several digital simulations are provided to demonstrate the effectiveness of the algorithm proposed in this paper.
-  S. M. Johnson, “Optimal two and three-stage production schedules with setup times included,” Naval Research Logistics Quarterly, Vol.1, No.1, pp. 61-68, 1954.
-  T. Murata, H. Ishibuchi, and H. Tanaka, “Genetic algorithms for flowshop scheduling problems,” Computers & Industrial Engineering, Vol.30, No.4, pp. 1061-1071, 1996.
-  Q.-D. Wu and W.-L. Wang, “Production scheduling intelligent algorithm and its application,” Master’s thesis, Beijing, 2007.
-  G.-Q. Qu, “Bottleneck focused heuristic algorithm for flow shop scheduling problem,” Computer Integrated Manufacturing Systems, Vol.18, No.2, pp. 356-363, 2012.
-  H. Ishibuchi, N. Yamamoto, T. Murata, and H. Tanaka, “Genetic algorithms and neighborhood search algorithms for fuzzy flowshop scheduling problems,” Fuzzy Sets and Systems, Vol.67, No.1, pp. 81-100, 1994.
-  M. Gen and R. Cheng, “Genetic algorithms and engineering optimization,” Vol.7, John Wiley & Sons, 2000.
-  Lin Dan, Li Shu Quan, Li Ming-Qiang, and Kou Ji Song, “The Basic Theory and Applications of Genetic Algorithm,” Master’s thesis, Beijing. [b7] D. M. Lei and X. P. Yan, “Multiobjective intelligent optimization algorithm and its application,” Science Press, Beijing, 2009.
-  D. W. Wang, J. W. Wang, R. Y. Zhang, and Z. Guo, “Intelligent Optimization Algorithm,” Higher Education Press, Beijing, 2007.
-  Y. Liu and C. Ye, “Improved PSO algorithm for flow shop scheduling problem with fuzzy delivery time,” J. of Harbin Institute of Technology, Vol.1, No.41, pp. 145-148, 2009.
-  B.-H. Shen, Y. Liu, and R.-F. Pan, “Modified PSO algorithm solving flow-shop scheduling problem with fuzzy delivery time,” Jisuanji Gongcheng yu Yingyong (Computer Engineering and Applications), Vol.42, No.34, pp. 36-38, 2006.
-  C. Jin and C. Ye, “Fuzzy flow-shop scheduling problem based on Quantum Particle Swarm Optimization,” Jisuanji Gongcheng yu Yingyong (Computer Engineering and Applications), Vol.48, No.2, pp. 238-240, 2012.
-  H.-B. Tang, C.-M. Ye, C.-P. Liu, and J. Ke, “Knowledge evolution particle swarm optimization for solving flow shop scheduling problem with fuzzy due date,” Computer Integrated Manufacturing Systems, Vol.18, No.4, pp. 807-812, 2012.
-  X.-F. Chen, W.-H. Gui, M. Wu, and Y.-L. Wang, “Chaotic migration-based pseudo parallel genetic algorithm and its application,” Kongzhi Lilun yu Yingyong/Control Theory & Applications (China), Vol.21, No.6, pp. 997-1002, 2004.
-  M. Nawaz, J.-E. Enscore, and I. Ham, “A heuristic algorithm for the m-machine, n-job flow shop sequencing problem,” Omega – The Int. J. of Management Science, Vol.11, No.1, pp. 91-95, 1983.