[1]PEI Xiaobing,ZHANG Chunhua.An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems[J].CAAI Transactions on Intelligent Systems,2019,14(3):541-550.[doi:10.11992/tis.201801041]
Copy

An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 14 Number of periods: 2019 3 Page number: 541-550 Column: 学术论文—机器学习 Public date: 2019-05-05
Title:
An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems
Author(s):
PEI Xiaobing;  ZHANG Chunhua
School of Management, Tianjin University of Technology, Tianjin 300384, China
Keywords:
production scheduling; combinatorial optimization; genetic algorithms; ant colony optimization; building block; artificial chromosome
CLC:
TP18
DOI:
10.11992/tis.201801041
Abstract:
Targeting the permutation flow-shop scheduling problem that minimizes maximum completion times, an improved block genetic algorithm combined with an ant colony algorithm is proposed. The algorithm uses a random mechanism and the improved opposition-based learning mechanism to generate the initial solution. It takes into account the diversity and quality of the initial population. Elite populations are generated through several generations of simple genetic algorithm operations. Based on the idea of using ant information density concentration’s statistical path and node information in the ant colony algorithm, the information carried by elite groups was counted. Position pheromone and dependent pheromone matrices were established. Mining blocks according to two matrices were developed and blocks were combined with non-blocks to form artificial chromosomes. Chromosomes were cut and recombined to increase chromosome quality. The binary race method was used to retain chromosomes with higher fitness. The algorithm was tested through the Reeves and Taillard instances, and the results were compared with other algorithms to verify effectiveness of the algorithm.
References:
[1] 周明, 孙树栋. 遗传算法原理及应用[M]. 北京:国防工业出版社, 1999:6.
[2] 夏小云, 周育人. 蚁群优化算法的理论研究进展[J]. 智能系统学报, 2016, 11(1):27-36 XIA Xiaoyun, ZHOU Yuren. Advances in theoretical research of ant colony optimization[J]. CAAI transactions on intelligent systems, 2016, 11(1):27-36
[3] 李金忠, 夏洁武, 曾小荟, 等. 多目标模拟退火算法及其应用研究进展[J]. 计算机工程与科学, 2013, 35(8):77-88 LI Jinzhong, XIA Jiewu, ZENG Xiaohui, et al. Survey of multi-objective simulated annealing algorithm and its applications[J]. Computer engineering and science, 2013, 35(8):77-88
[4] TAYEB F B S, BESSEDIK M, BENBOUZID M, et al. Research on permutation flow-shop scheduling problem based on improved genetic immune algorithm with vaccinated offspring[J]. Procedia computer science, 2017, 112:427-436.
[5] CHEN Rongchang, CHEN J, CHEN T S, et al. Synergy of genetic algorithm with extensive neighborhood search for the permutation flowshop scheduling problem[J]. Mathematical problems in engineering, 2017, 2017:3630869.
[6] BESSEDIK M, TAYEB F B S, CHEURFI H, et al. An immunity-based hybrid genetic algorithms for permutation flowshop scheduling problems[J]. International journal of advanced manufacturing technology, 2016, 85(9/10/11/12):2459-2469.
[7] GANGULY S, MUKHERJEE S, BASU D, et al. A novel strategy adaptive genetic algorithm with greedy local search for the permutation flowshop scheduling problem[M]//Swarm, Evolutionary, and Memetic Computing. Berlin, Heidelberg:Springer, 2012:687-696.
[8] 齐学梅, 王宏涛, 陈付龙, 等. 求解多目标PFSP的改进遗传算法[J]. 计算机工程与应用, 2015, 51(11):242-247 QI Xuemei, WANG Hongtao, CHEN Fulong, et al. Improved genetic algorithm for multi-objective of PFSP[J]. Computer engineering and applications, 2015, 51(11):242-247
[9] 崔琪, 吴秀丽, 余建军. 变邻域改进遗传算法求解混合流水车间调度问题[J]. 计算机集成制造系统, 2017, 23(9):1917-1927 CUI Qi, WU Xiuli, YU Jianjun. Improved genetic algorithm variable neighborhood search for solving hybrid flow shop scheduling problem[J]. Computer integrated manufacturing systems, 2017, 23(9):1917-1927
[10] CHANG P C, HUANG W H, WU J L, et al. A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. International journal of production economics, 2013, 141(1):45-55.
[11] JIN Jian. A hybrid discrete biogeography-based optimization for the permutation flow shop scheduling problem[J]. International journal of production research, 2016, 54(16):4805-4814.
[12] DORIGO M, GAMBARDELLA L M. Ant colony system:a cooperative learning approach to the traveling salesman problem[J]. IEEE transactions on evolutionary computation, 1997, 1(1):53-66.
[13] 陈慧芬. 基于链结学习的子群体进化算法求解多目标调度问题[D]. 天津:天津理工大学, 2017. CHEN Huifen. Sub-population evolutionary algorithm based on linkage learning for multi-objective scheduling problem[D]. Tianjin:Tianjin University of Technology, 2017.
[14] 裴小兵, 陈慧芬, 张百栈, 等. 改善式BVEDA求解多目标调度问题[J]. 山东大学学报(工学版), 2017, 47(4):25-30 PEI Xiaobing, CHEN Huifen, ZHANG Baizhan, et al. Improved bi-variables estimation of distribution algorithms for multi-objective permutation flow shop scheduling problem[J]. Journal of Shandong University (engineering science), 2017, 47(4):25-30
[15] 裴小兵, 赵衡. 基于二元分布估计算法的置换流水车间调度方法[J]. 中国机械工程, 2017, 28(22):2752-2759 PEI Xiaobing, ZHAO Heng. Permutation flow shop scheduling problem based on hybrid binary distribution estimation algorithm[J]. China mechanical engineering, 2017, 28(22):2752-2759
[16] 张敏, 汪洋, 方侃. 基于改进区块进化算法求解置换流水车间问题[J]. 计算机集成制造系统, 2018, 24(5):1207-1216 ZHANG Min, WANG Yang, FANG Kan. Improved block-based evolutionary algorithm for solving permutation flowshop scheduling problem[J]. Computer integrated manufacturing systems, 2018, 24(5):1207-1216
[17] CHANG P C, CHEN Menghui. A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft computing, 2014, 18(6):1177-1188.
[18] MILLER B L, GOLDBERG D E. Genetic algorithms, tournament selection, and the effects of noise[J]. Complex systems, 1995, 9(3):193-212.
[19] CHANG P C, CHEN S H, FAN C Y, et al. Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems[J]. Annals of operations research, 2010, 180(1):197-211.
[20] HSU C Y, CHANG P C, CHEN M H. A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem[J]. Computers & industrial engineering, 2015, 83:159-171.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems