Scientia et Technica Año XVII, No 46, Diciembre 2010. Universidad Tecnológica de Pereira. ISSN 0122-1701
62
APLICACIÓN DE LA PROGRAMACIÓN DINÁMICA PARA RESOLVER EL PROBLEMA
SIMPLE DE BALANCEO DE LINEA DE ENSAMBLE.
Dynamic programming application to solve the simple assembly line balancing problem
RESUMEN
Este documento presenta en forma reducida la aplicación de un algoritmo
exacto parasolucionar un problema simple de balanceo de línea de ensamble,
el algoritmo utilizado es la programación dinámica, se muestran las ventajas y
desventajas de usar este método para solucionar problemas de tipo
combinatorial.
PALABRAS CLAVES: Estación, Tarea, Tiempo de ciclo, Algoritmo,
Programación dinámica.
ABSTRACT
This paper show reduced form the application of an exact algorithm to solve a
simpleassembly line balancing problem, the algorithm used is dynamic
programming, presents the advantages and disadvantages of use this method
to solve combinatorial problems..
KEYWORDS:
programming.
Workstation,
Task,
Cycle
time,
Algorithm,
1. INTRODUCCIÓN
El problema de las líneas de ensamble ha sido estudiado
por diferentes investigadores desde diferentes enfoques,
tratando de dar solución a esteproblema utilizando
algoritmos exactos y algoritmos heurísticos. La noción de
línea de ensamble existe desde hace varios siglos, cuando
se tenían líneas incipientes y rudimentarias para construir
embarcaciones en astilleros en Venecia; pero solo fue
hasta Henry Ford que se estudiaron las líneas de
ensamble de manera técnica y científica, desde ese
momento empieza la investigación y desarrollosobre el
equilibrado de las líneas de ensamble. La optimización de
las líneas de ensamble ha sido el objetivo de las
investigaciones en las cuales se han empleado diferentes
técnicas: heurísticas, meta-heurísticas, algoritmos
exactos, algoritmos genéticos. Entre otros.
La programación dinámica fue aplicada a este problema
por primera vez en el año de 1963 por Held, Karp y
Shareshian en el documento[5], en donde se realiza un
desarrollo matemático complejo para la aplicación de la
programación dinámica a la solución del problema de
balanceo de líneas, considerando restricciones de
precedencia, esta investigación se considera como base
para las investigaciones posteriores. En el año de 1978
Schrage y Baker [11] desarrollan un documento en el
Fecha Recepción: 9 de Septiembre de 2010
Fechaaceptación: 15 de Noviembre de 2010
ANDRES JARAMILLO GARZON
Ingeniero Industrial.
Desarrollo Físico Comfamiliar Risaralda
Estudiante
de
la
Maestría
en
Sistemas Integrados de Gestión de la Calidad
Facultad de Ingeniería Industrial
[email protected]
JORGE HERNAN RESTREPO CORREA
Ingeniero Industrial, M.Sc
Profesor Asistente
Universidad Tecnológica de Pereira
[email protected]
Dynamic
cual tomanconceptos del trabajo anteriormente descrito e
introducen detalles sobre procedimientos de enumeración
y se hacen comparaciones sobre tiempos de cómputo con
otros métodos. Posteriormente Kao y Queyranne en 1982
[8] Hacen recopilación de investigaciones anteriores y
describen el procedimiento en seudo código. Todos los
documentos anteriormente nombrados son artículos de
revistas de investigaciónque muestran de forma muy
general la utilización del método propuesto para la
solución del problema. Por esta razón surge la necesidad
de ampliar la investigación y aclarar las ventajas y
desventajas de la aplicación del método para resolver el
problema propuesto.
El problema de balanceo de líneas de ensamble, es uno
de los mas comunes en las fabricas y empresas
industriales, en términos generalestrata de optimizar los
recursos de la línea de ensamble, ya sea minimizando
estaciones de trabajo, o minimizando el tiempo de ciclo,
es decir, el problema de balanceo de línea de ensamble
trata de asignar las tareas en una secuencia ordenada de
las estaciones, satisfaciendo las relaciones de precedencia
y optimizando una función objetivo.
En este trabajo se resolverá concretamente un pequeño…
