第Ⅰ类双边装配线平衡问题的改进蚁群算法

Improved Ant Colony Algorithm for Two-Sided Assembly Line Balancing Problem of Type Ⅰ

为克服传统算法求解大规模双边装配线平衡问题计算时间长、性能不稳定的缺陷,针对第Ⅰ类双边装配线平衡问题,应用综合信息素搜索规则与全局信息素更新规则,提出了一种先产生任务排列序列、后按启发式分配规则产生可行解的蚁群算法,可有效脱离陷入局部最优解.用改进蚁群算法对30个不同规模的问题进行求解,并与标准蚁群算法和禁忌搜索算法进行了对比.结果表明:改进蚁群算法求出29个最优解,比普通蚁群算法、禁忌搜索算法分别能多求得6个和3个最优解;应用于汽车双边装配线算例,在保持平衡效率的条件下,改进蚁群算法计算时间为21.01 s,比普通蚁群算法减少了9.14 s,计算效率提高了30.3%.

To overcome the disadvantages of traditional algorithms in solving large-scale two-sided assembly line balancing problems （TALBPs）, such as long computing time and unstable results, an improved ant colony algorithm （ACO） was proposed for solving the TALBP of type I. In the proposed algorithm, a task sequence was generated first, and a feasible solution was then obtained by the heuristic assignment method; in addition, the pheromone summation rule and a global pheromone updating rule were adopted to avoid the ants falling into the locally optimal solutions. A series of numerical experiments were conducted on 30 test problems of different size using the proposed ACO algorithm, the standard ant colony algorithm, and the tabu search algorithm for comparison. The results indicate that the proposed ACO algorithm obtained 29 optimal solutions for the 30 test problems, and obtained 6 and 3 more optimal solutions than the standard ant colony algorithm and the tabu search algorithm, respectively. Finally, the proposed ACO algorithm was applied to a real car assembly line and obtained the satisfactory solutions within 21.01 s, saving 9.14 s and improving the computational efficiency by 30.3% when compared with the traditional ACO under the same line efficiency.