改进猫群算法求解置换流水车间调度问题

PDF下载HTML

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 problem; cat swarm optimization; estimation of distribution algorithm; search mode; probability matrix; combination block; tracking mode; excellent 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.