求解带序列相关准备时间双边装配线平衡问题的改进模拟退火算法  

An improved simulated annealing algorithm for balancing two-sided assembly lines with sequence-dependent setup times

作　　者：赵瀚明 唐秋华 蒙凯 李梓响 张子凯 Zhao Hanming;Tang Qiuhua;Meng Kai;Li Zixiang;Zhang Zikai(Key Laboratory of Metallurgical Equipment and Control of Ministry of Education, Wuhan University ofScience and Technology, Wuhan 430081, China;Hubei Key Laboratory of Mechanical Transmission and Manufacturing Engineering, Wuhan University of Science and Technology, Wuhan 430081, China)

机构地区：[1]武汉科技大学冶金装备及其控制教育部重点实验室,湖北武汉430081 [2]武汉科技大学机械传动与制造工程湖北省重点实验室,湖北武汉430081

出　　处：《武汉科技大学学报》2021年第4期277-284,共8页Journal of Wuhan University of Science and Technology

基　　金：国家自然科学基金资助项目(51875421).

摘　　要：在实际生产线上,同一工位内连续两个装配任务之间可能存在序列相关准备时间。针对考虑序列相关准备时间的双边装配线平衡问题(TALBPS),提出一种改进的模拟退火算法。改进措施包括:①采用基于分级位置权重的初始化策略,以获得高质量的初始解;②对收敛准则进行改进,采用工位中序列相关空闲时间作为二级目标来指引算法进化方向,帮助算法跳出局部极值找到最优解。实验结果表明,两个改进算子是有效的,在求解不同规模的TALBPS标杆案例时,本文算法获得的结果与理论最小工位数目更为接近,并且与几种典型的群智能算法和局部搜索算法相比,本文算法在最小相对百分比偏差和平均相对百分比偏差两个指标上性能更优。In actual assembly lines,there may exist sequence-dependent setup times between two consecutive tasks at the same station.An improved simulated annealing algorithm is proposed to solve the two-sided assembly line balancing problem with sequence-dependent setup times(TALBPS).Firstly,the algorithm adopts an initialization strategy based on the ranked positional weight to acquire high-quality initial solutions.Then the convergence criterion is improved by using the sequence-dependent idle time of the station as the secondary goal to guide the evolution direction,which helps the algorithm jump out of local extreme values and find the optimal solution.Test results show that both improved operators are valid.For TALBPS benchmark instances with different sizes,the results obtained by the proposed algorithm are much closer to the theoretical minimum number of stations.Compared with several typical swarm intelligence algorithms and local search algorithms,the improved simulated annealing algorithm has better performance on two indicators,i.e.minimum relative percentage deviation and average relative percentage deviation.

关 键 词：双边装配线平衡 序列相关准备时间 模拟退火算法 分级位置权重 收敛准则 

分 类 号：TH186[机械工程—机械制造及自动化] TP18[自动化与计算机技术—控制理论与控制工程]