改进樽海鞘群算法求解柔性作业车间调度问题

PDF下载HTML

Title:

Improved slap swarm algorithm for scheduling of flexible job shop

作者:

赵文超¹, 郭鹏^1,2, 王海波^1,2, 雷坤¹

1. 西南交通大学 机械工程学院, 四川 成都 610031;
2. 轨道交通运维技术与装备四川省重点实验室, 四川 成都 610031

Author(s):

ZHAO Wenchao¹, GUO Peng^1,2, WANG Haibo^1,2, LEI Kun¹

1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China;
2. Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Chengdu 610031, China

关键词:

柔性作业车间; 樽海鞘群算法; Lévy飞行; 离散化; 惯性权重; 关键路径; 模拟退火; 局部搜索

Keywords:

flexible job shop; salp swarm algorithm; Lévy flight; discretization; inertia weight; critical path; simulated annealing; local search

分类号:

TP18

DOI:

10.11992/tis.202103036

摘要:

针对以最小化最大完工时间的柔性作业车间调度问题，在标准樽海鞘群算法(salp swarm slgorithm, SSA)的基础上，提出一种改进的樽海鞘群算法。采用基于工序和基于设备的二维向量进行编码，并考虑设备负载进行种群初始化。基于Lévy飞行对领导者位置更新方式进行离散化改进；在追随者位置更新公式中引入自适应惯性权重,使算法的全局搜索和局部搜索能力得到更好的平衡。为提高搜索效率，设计了交叉算子和基于关键路径的变异算子来保证种群的多样性，同时引入模拟退火(simulated annealing，SA)策略，改善算法的局部搜索能力。通过采用标准算例进行对比计算，结果验证了所提算法的有效性。

Abstract:

To deal with the scheduling of a flexible job shop and minimize the maximum completion time, an improved salp swarm algorithm (SSA), based on the standard SSA, is proposed in this paper. Two-dimensional vectors based on the process and equipment are encoded, and the population is initialized with the consideration of the machine workload. Based on a Lévy flight, the leader position update method is discretely improved. The adaptive inertial weight is introduced into the follower position update formula to balance the global search and local search performance of the algorithm. To improve the search efficiency, the proposed SSA adopts crossover and mutation operators based on the critical path to guarantee population diversity. Moreover, simulated annealing is applied to improve the local search capacity of the algorithm. Standard examples are compared and calculated, and the results verify the effectiveness of the proposed algorithm.