基于粒子群算法的U型装配线平衡问题研究.docVIP

 基于粒子群算法的 U 型装配线平衡问题研 究# 朱兴涛 ，张则强 ，胡俊逸 5 10 15 20 25 30 35 40 （ 西南交通大学机械工程学院，成都 610031 ) 摘要：针对给定节拍最小化工作站数的第一类 U 型装配线平衡问题，提出了一种改进的粒 子群算法。由于粒子群算法不能直接用于求解离散空间的组合优化问题，故文章采用基于 优先权的粒子群算法来求解，通过对任务赋以的权重的大小来选择任务，并具体说明了粒 子速度和位置的更新。最后，对大量测试问题集进行了验证，说明了算法的有效性。 关键词：U 型装配线;平衡；粒子群算法；启发式方法 中图分类号：T Particle Swarm Optimization Algorithm for U-shaped Assembly Line Balancing Problem ZHU Xingtao , ZHANG Zeqiang , HU Junyi ( School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031 ) Abstract: The paper proposed an improved particle swarm optimization algorithm which minimized the number of stations for a given cycle time in the type 1 of the U-shaped Assembly Line Balancing Problem (UALBP-1). Because particle swarm algorithm cannot be directly used to solve the combinatorial optimization problem of discrete space, the article solved it by particle swarm algorithm based on priority which choosed task throughing the size of the weight of the task. And the paper illustrated the method of updating velocity and location of particle. Finally, the proposed algorithm was testing and compared with literature test question, and the result showed the effectiveness of the proposed algorithms. Key words: U-shaped assembly line; Balancing; Particle swarm algorithm;Heuristic algorithm 0 引言 装配线平衡问题（Assembly Line Balancing Problem,ALBP）是制造领域的一个重要问题， 对生产效率的提高至关重要。同时ALBP是公认的NP-hard组合优化问题，问题的复杂度随任 务数目的增加呈指数级增长，因而难以在合理的时间里找到最优解[1-2]。随着制造业激烈的 外部环境的改变，越来越多的企业推崇精益生产，而精益生产所带来的重大改变使越来越多 的生产线采用U型布局代替直线型布局。 U型装配线平衡问题（U-shaped Assembly Line Balancing Problem,UALBP ）是对简单装 配线平衡问题的延伸，与直线型生产线相比，U型布局的本质关键在于装配线的出口和入口 在同一个位置，布局更紧凑，从而可以实现弹性作业人数。而在装配线分配作业到工作站时， U型装配线可以按照从前到后或者从后到前的顺序单方向进行，也可以从两个方向同时进 行。直线型的装配线上，只能按照单方向分配作业元素的顺序。由于U型装配线分配作业的 灵活性，使得U型装配线的分配结果中工作站的个数一般不会超过直线型装配线上的工作站 基金项目：高等学校博士学科点专项科研基金资助课题(200806131014) 作者简介：朱兴涛（1989-），男，硕士研究生，主要从事拆卸线平衡的研究 通信联系人：张则强(1978-)，男，博士、副教授，主要从事制造系统与智能优化等的研究. E-mail: zhangzeqiang@ - 1 -  的个数，故U型装配线的平衡效率更高。 相对于直线型装配线平衡问题来说，对U型装配线平衡问题的研究比较少。文献[3, 4] 45