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

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

在实际生产线上,同一工位内连续两个装配任务之间可能存在序列相关准备时间。针对考虑序列相关准备时间的双边装配线平衡问题(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.