[1]PEI Xiaobing,YU Xiuyan.Improved cat swarm optimization for permutation flow shop scheduling problem[J].CAAI Transactions on Intelligent Systems,2019,14(4):769-778.[doi:10.11992/tis.201804016]
Copy

Improved cat swarm optimization for permutation flow shop scheduling problem

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 14 Number of periods: 2019 4 Page number: 769-778 Column: 学术论文—机器学习 Public date: 2019-07-02
Title:
Improved cat swarm optimization for permutation flow shop scheduling problem
Author(s):
PEI Xiaobing;  YU Xiuyan
School of Management, Tianjin University of Technology, Tianjin 300384, China
Keywords:
permutation flow shop scheduling problem; cat swarm optimization; estimation of distribution algorithm; search mode; probability matrix; combination block; tracking mode; excellent solution sequence
CLC:
TP18
DOI:
10.11992/tis.201804016
Abstract:
The standard cat swarm optimization (CSO) has a slow convergence rate in solving the permutation flow shop scheduling problem (PFSP) to minimize the maximum completion time. Meanwhile, the "dimension disaster" is prone to occur when the scale of the problem is large. To speed up the optimization and avoid the "dimension disaster," a CSO algorithm based on the estimation of distribution algorithms is proposed in this paper. Based on the cat swarm algorithm, the distribution estimation algorithm is embedded. In the search mode, the probability matrix is used to mine the excellent gene chain combination blocks in the solution sequence, and the tracking mode in the cat swarm algorithm is used to update the speed and position of the cat, thus updating the excellent solution sequence to generate a subpopulation. Finally, through the simulation test and comparison result of Carlier and Reeves standard example set, the good robustness and global searching ability of the algorithm are verified.
References:
[1] GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of operations research, 1976, 1(2):117-129.
[2] 李小缤, 白焰, 耿林霄. 求解置换流水车间调度问题的改进遗传算法[J]. 计算机应用, 2013, 33(12):3576-3579 LI Xiaobin, BAI Yan, GENG Linxiao, et al. Improved genetic algorithm for solving permutation flow shop scheduling problem[J]. Journal of computer applications, 2013, 33(12):3576-3579
[3] CHU Shuchuan, TSAI P W, PAN J S. Cat swarm optimization[C]//Proceedings of the 9th Pacific Rim International Conference on Artificial Intelligence. Guilin, China, 2006, 4099:854-858.
[4] GANAPATI P, PRADHAN P M, MAJHI B. ⅡR system identification using cat swarm optimization[J]. Expert systems with applications, 2011, 38(10):12671-12683.
[5] PRADHAN P M, PANDA G. Solving multiobjective problems using cat swarm optimization[J]. Expert systems with applications, 2012, 39(3):2956-2964.
[6] GUO Lei, MENG Zhuo, SUN Yize, et al. A modified cat swarm optimization based maximum power point tracking method for photovoltaic system under partially shaded condition[J]. Energy, 2018, 144:501-514.
[7] PAPPULA L, GHOSH D. Cat swarm optimization with normal mutation for fast convergence of multimodal functions[J]. Applied soft computing, 2018, 66:473-491.
[8] TSAI P W, PAN J S, CHEN S M, et al. Parallel cat swarm optimization[C]//Proceedings of 2008 International Conference on Machine Learning and Cybernetics. Kunming, China, 2008:3328-3333.
[9] 刘琼, 范正伟, 张超勇, 等. 基于多目标猫群算法的混流装配线排序问题[J]. 计算机集成制造系统, 2014, 20(2):333-342 LIU Qiong, FAN Zhengwei, ZHANG Chaoyong, et al. Mixed model assembly line sequencing problem based on multi-objective cat swarm optimization[J]. Computer integrated manufacturing system, 2014, 20(2):333-342
[10] BOUZIDI A, RIFFI M E. Cat swarm optimization to solve flow shop scheduling problem[J]. Journal of theoretical and applied information technology, 2015, 72(2):239-243.
[11] BOUZIDI A, RIFFI M E. Cat swarm optimization to solve job shop scheduling problem[C]//Proceedings of the Third IEEE International Colloquium in Information Science and Technology. Tetouan, Morocco, 2015:202-205.
[12] 马邦雄, 叶春明. 利用猫群算法求解流水车间调度问题[J]. 现代制造工程, 2014(6):12-15, 71 MA Bangxiong, YE Chunming. The research of flow-shop scheduling problem based on cat swarm optimization[J]. Modern manufacturing engineering, 2014(6):12-15, 71
[13] 陶新民, 徐鹏, 刘福荣, 等. 组合分布估计和差分进化的多目标优化算法[J]. 智能系统学报, 2013, 8(1):39-45 TAO Xinmin, XU Peng, LIU Furong, et al. Multi-objective optimization algorithm composed of estimation of distribution and differential evolution[J]. CAAI transactions on intelligent systems, 2013, 8(1):39-45
[14] TZENG Y R, CHEN C L, CHEN C L. A hybrid EDA with ACS for solving permutation flow shop scheduling[J]. The international journal of advanced manufacturing technology, 2012, 60(9/10/11/12):1139-1147.
[15] CHANG P C, HUANG W H, TING C J. Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems[J]. Expert systems with applications, 2010, 37(3):1863-1878.
[16] KIM D, HALDAR J P. Greedy algorithms for nonnegativity-constrained simultaneous sparse recovery[J]. Signal processing, 2016, 125:274-289.
[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] RAUTRAY R, BALABANTARAY R C. Cat swarm optimization based evolutionary framework for multi document summarization[J]. Physica a:statistical mechanics and its applications, 2017, 477:174-186.
[19] CARLIER J. Ordonnancements à contraintes disjonctives[J]. RAIRO-operations research, 1978, 12(4):333-350.
[20] REEVES C R. A genetic algorithm for flowshop sequencing[J]. Computers and operations research, 1995, 22(1):5-13.
[21] LIU Hongcheng, GAO Liang, PAN Quanke. A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem[J]. Expert systems with applications, 2011, 38(4):4348-4360.
Similar References:

Memo

-

Last Update: 2019-08-25

Copyright © CAAI Transactions on Intelligent Systems