[1]裴小兵,于秀燕.改进猫群算法求解置换流水车间调度问题[J].智能系统学报,2019,14(04):769-778.[doi:10.11992/tis.201804016]
 PEI Xiaobing,YU Xiuyan.Improved cat swarm optimization for permutation flow shop scheduling problem[J].CAAI Transactions on Intelligent Systems,2019,14(04):769-778.[doi:10.11992/tis.201804016]
点击复制

改进猫群算法求解置换流水车间调度问题(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第14卷
期数:
2019年04期
页码:
769-778
栏目:
出版日期:
2019-07-02

文章信息/Info

Title:
Improved cat swarm optimization for permutation flow shop scheduling problem
作者:
裴小兵 于秀燕
天津理工大学 管理学院, 天津 300384
Author(s):
PEI Xiaobing YU Xiuyan
School of Management, Tianjin University of Technology, Tianjin 300384, China
关键词:
置换流水车间调度猫群算法分布估计算法搜寻模式概率矩阵组合区块跟踪模式优秀解序列
Keywords:
permutation flow shop scheduling problemcat swarm optimizationestimation of distribution algorithmsearch modeprobability matrixcombination blocktracking modeexcellent solution sequence
分类号:
TP18
DOI:
10.11992/tis.201804016
摘要:
标准猫群算法(CSO)在求解最小化最大完工时间的置换流水车间调度问题(PFSP)时收敛速度较慢,同时,当问题规模变大时容易出现“维数灾难”。为加快寻优速度,同时避免“维数灾难”,提出了一种基于分布估计算法的改进猫群算法(EDA-CSO)。以猫群算法为框架,嵌入分布估计算法,在搜寻模式下,利用概率矩阵挖掘解序列中的优秀基因链组合区块,使用猫群算法中的跟踪模式更新猫的速度和位置,从而更新优秀解序列产生子群体。最后,通过对Carlier和Reeves标准例题集的仿真测试和结果比较,验证了该算法良好的鲁棒性和全局搜索能力。
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.

备注/Memo

备注/Memo:
收稿日期:2018-04-13。
基金项目:国家创新方法工作专项项目(2017IM010800).
作者简介:裴小兵,男,1965年生,教授,博士,天津工业工程学会理事,主要研究方向为生产调度、系统仿真。发表学术论文30余篇;于秀燕,女, 1992年生,硕士研究生,主要研究方向为生产调度、系统仿真。
通讯作者:于秀燕.E-mail:Yu_xiuyan1026@163.com
更新日期/Last Update: 2019-08-25