双边装配线平衡的一种分支定界算法

A Branch-and-bound Method for Balance of Two-sided Assembly Line

虽然单边装配线平衡问题的研究已取得大量的成果,但有关双边装配线平衡的研究却开展较少,而且,研究主要关注于启发式求解。现提出一种基于工位的分支定界算法来最优化双边装配线的平衡。首先,通过改进现有的工位枚举策略,并将其扩展用来生成基于工位的枚举树;其次,通过研究与应用相关定界方法来减少枚举树的大小,使平衡能快速达到最优解。通过对目前公开发表的实例验证表明,该算法具有较好的性能。

A great number of research results of balance of single-sided assembly line have been achieved. However, less research on the balance of two-sided assembly line has been performed. A station-oriented branch-and-bound algorithm to optimize the balance of two-sided assembly line is presented. First, the station-oriented enumerative procedure is improved and extended to generate the enumerative tree; second, the bounding rules are developed and applied to reduce the enumeration effort. As a result, the balance can be optimized rapidly. The verified instances that have been published demonstrate that the proposed algorithm is efficient.