Hybrid Genetic Algorithm Based on Chaotic Migration Strategy for Solving Flow Shop Scheduling Problem with Fuzzy Delivery Time

Wen-Zhan Dai; Kai Xia

doi:10.20965/jaciii.2015.p0359

single-jc.php

« previous

JACIII Vol.19 No.3 pp. 359-364

doi: 10.20965/jaciii.2015.p0359

(2015)

Paper:

Views over last 60 days: 863

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

Received:

December 15, 2013

Accepted:

February 2, 2015

Published:

May 20, 2015

Keywords:

flow shop scheduling problem, genetic algorithm, chaotic migration, fuzzy delivery time

Abstract

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.

Cite this article as:

W. Dai and K. Xia, “Hybrid Genetic Algorithm Based on Chaotic Migration Strategy for Solving Flow Shop Scheduling Problem with Fuzzy Delivery Time,” J. Adv. Comput. Intell. Intell. Inform., Vol.19 No.3, pp. 359-364, 2015.

Data files:

References

[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] 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] Q.-D. Wu and W.-L. Wang, “Production scheduling intelligent algorithm and its application,” Master’s thesis, Beijing, 2007.
[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] 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] M. Gen and R. Cheng, “Genetic algorithms and engineering optimization,” Vol.7, John Wiley & Sons, 2000.
[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] D. W. Wang, J. W. Wang, R. Y. Zhang, and Z. Guo, “Intelligent Optimization Algorithm,” Higher Education Press, Beijing, 2007.
[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] 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] 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] 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] 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] 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 article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[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.