TY - JOUR
T1 - A dynamic programming based heuristic for the assembly line balancing problem
AU - Bautista, Joaquín
AU - Pereira, Jordi
N1 - Funding Information:
The authors greatly appreciate the collaboration of Nissan Spanish Industrial Operations as well as the Nissan Chair UPC for partially funding this research. This work was also partially funded by projects DPI2004-03475 and DPI2007-63026 from the Spanish government.
PY - 2009/5/1
Y1 - 2009/5/1
N2 - The simple assembly line balancing problem is the simplification of a real problem associated to the assignment of the elementary tasks required for assembly of a product in an assembly line. This problem has been extensively studied in the literature for more than half a century. The present work proposes a new procedure to solve the problem we call Bounded Dynamic Programming. This use of the term Bounded is associated not only with the use of bounds to reduce the state space but also to the reduction of such space based on heuristics. This procedure is capable of obtaining an optimal solution rate of 267 out of 269 instances, which have been used in previous works, thus obtaining the best-known performance for the problem. These results are an improvement from any previous procedure found in the literature even when using smaller computing times.
AB - The simple assembly line balancing problem is the simplification of a real problem associated to the assignment of the elementary tasks required for assembly of a product in an assembly line. This problem has been extensively studied in the literature for more than half a century. The present work proposes a new procedure to solve the problem we call Bounded Dynamic Programming. This use of the term Bounded is associated not only with the use of bounds to reduce the state space but also to the reduction of such space based on heuristics. This procedure is capable of obtaining an optimal solution rate of 267 out of 269 instances, which have been used in previous works, thus obtaining the best-known performance for the problem. These results are an improvement from any previous procedure found in the literature even when using smaller computing times.
KW - Assembly line balancing
KW - Bounded Dynamic Programming
KW - Car manufacturing
KW - Production
UR - http://www.scopus.com/inward/record.url?scp=55149094562&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2008.01.016
DO - 10.1016/j.ejor.2008.01.016
M3 - Article
AN - SCOPUS:55149094562
SN - 0377-2217
VL - 194
SP - 787
EP - 794
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 3
ER -