Branch-and-bound algorithms for simple assembly line balancing problem

被引：0
作者：
S. B. Liu
K. M. Ng
H. L. Ong
机构：
[1] National University of Singapore,Department of Industrial & Systems Engineering
来源：
The International Journal of Advanced Manufacturing Technology | 2008年 / 36卷
关键词：
Branch-and-bound; Assembly line balancing; Destructive algorithm;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper, exact algorithms for solving the simple assembly line balancing type I problem are presented. The proposed algorithms consist of a constructive and two destructive algorithms. Several well-known lower-bound computational methods are also applied in these algorithms. Computational experiments were carried out to test the performance of the proposed algorithms based on a set of benchmark problem instances. The computational results show that the algorithms proposed in this paper are efficient in solving the simple assembly line balancing benchmark problem instances. Moreover, a problem instance whose optimal solution had previously been unknown is solved by one of the proposed algorithms.
引用
收藏
页码：169 / 177
页数：8
相关论文
共 25 条
[1]  
Talbot FB(1986)A comparative evaluation of heuristic line balancing techniques Manage Sci 32 430-454
[2]  
Patterson JH(2006)State-of-the-art exact and heuristic solution procedures for simple assembly line balancing Eur J Oper Res 168 666-693
[3]  
Gehrlein WV(1988)Optimally balancing large assembly lines with ‘FABLE’ Manage Sci 34 240-253
[4]  
Scholl A(1992)EUREKA: a hybrid system for assembly line balancing Manage Sci 38 39-47
[5]  
Christian B(1963)Assembly line balancing with a precedence matrix Manage Sci 9 551-562
[6]  
Johnson RV(2003)An enumerative heuristic and reduction methods for the assembly line balancing problem Eur J Oper Res 145 606-620
[7]  
Hoffmann TR(2003)Two bi-directional heuristics for the assembly line type II problem Int J Adv Manuf Technol 22 656-661
[8]  
Hoffmann TR(1997)SALOME: A bidirectional branch-and-bound procedure for assembly line balancing INFORMS J Comput 9 319-334
[9]  
Fleszar K(1999)Balancing assembly lines effectively - a computational comparison Eur J Oper Res 114 50-58
[10]  
Hindi KS(1999)A competitive branch-and-bound algorithm for the simple assembly line balancing problem Int J Prod Res 37 1787-1816
123