基于分枝定界法的装配线第一类平衡问题研究

Branch-and-bound algorithm for assembly line balancing typeⅠproblem

在生产节拍给定的条件下,针对装配线平衡的数学模型,提出一种求解装配线第一类平衡问题的改进分枝定界法,该方法将较好的解存储起来,最后归纳可得到最优解的装配序列,避免了传统方法只能输出一个最优解的缺点。同时运用3种分枝规则加速寻找最优解;使用了两种定界方法的最大下界规则,节点控制规则和最大闲置时间规则被用来剪掉不能获得最优解的分枝,减小搜索空间。并且将影响算法性能的要素作了简要的分析,实验结果表明该算法具有良好的性能。

A branch-and-bound algorithm are proposed to solve the assembly line type-Ⅰbalancing problem,in which the cycle time is given.The better solutions are saved,and then conclude the assembly sequences which can obtain the optimal solutions in the method.The shortcoming of former method in which only one optimal solution can be obtained is avoided.Meanwhile,three branching rules are used to speed up finding the optimal solution.The maximal lower bound rule in which two bounding methods are used,node controlling rules and maximal idle time rule are applied to cut the branch which cann’t obation the optimal solutions to diminish the searching space.And factors which influenced the algorithm performance are analyzed briefly.The experimental results testify that the algorithm is efficient.