JACIII Vol.19 No.3 pp. 359-364
doi: 10.20965/jaciii.2015.p0359


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

December 15, 2013
February 2, 2015
Online released:
May 20, 2015
May 20, 2015
flow shop scheduling problem, genetic algorithm, chaotic migration, fuzzy delivery time

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.

  1. [1] 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.
  2. [2] T. Murata, H. Ishibuchi, and H. Tanaka, “Genetic algorithms for flowshop scheduling problems,” Computers & Industrial Engineering, Vol.30, No.4, pp. 1061-1071, 1996.
  3. [3] Q.-D. Wu and W.-L. Wang, “Production scheduling intelligent algorithm and its application,” Master’s thesis, Beijing, 2007.
  4. [4] G.-Q. Qu, “Bottleneck focused heuristic algorithm for flow shop scheduling problem,” Computer Integrated Manufacturing Systems, Vol.18, No.2, pp. 356-363, 2012.
  5. [5] 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.
  6. [6] M. Gen and R. Cheng, “Genetic algorithms and engineering optimization,” Vol.7, John Wiley & Sons, 2000.
  7. [7] 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.
  8. [8] D. W. Wang, J. W. Wang, R. Y. Zhang, and Z. Guo, “Intelligent Optimization Algorithm,” Higher Education Press, Beijing, 2007.
  9. [9] 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.
  10. [10] 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.
  11. [11] 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.
  12. [12] 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.
  13. [13] 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.
  14. [14] 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.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, IE9,10,11, Opera.

Last updated on May. 29, 2017