基于分支定界方法的双边装配线平衡

Balancing Two-sided Assembly Line Based on Branch and Bound Way

针对目前研究较少的双边装配线平衡问题,分析、研究了双边装配线的特点及其对平衡的特殊要求,建立双边装配线平衡问题的数学模型,并提出一种分支定界算法来最优化装配线的平衡。该算法采用基于任务、单步、深度优先的方法进行搜索,采用一系列启发式规则来控制分支节点搜索顺序,运用节点支配规则,下界规则,最大缓冲时间规则等对分支节点进行定界,以便迅速找到最优解,算例结果证明该算法具有较好的性能。

Aimed at the lack of research on two-sided assembly line balancing problem status in quo, the characteristics of two-sided assembly line were analyzed and the special requirements of balancing were studied, the mathematical model was built, then a balancing algorithm which was based on branch and bound was developed. The algorithm was based on task, single pass, depth first searching way. In order to find the optimal solution quickly, a series of heuristic rule were used to control the branch node searching sequence and the Node Dominance Rule, the Bound Rule and the Maximize Slack Time Rule were adopted to fathom the branch node. Experiments were carried out to demonstrate the performance of the proposed method. The results show that our procedure is promising in the solution quality.