programaciÓn lineal entera mixta para el problema de
TRANSCRIPT
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
PROGRAMACIÓN LINEAL ENTERA MIXTA PARA EL PROBLEMA DE
BALANCEO DE LINEA EN U (UALBP-E) MINIMIZANDO EL COSTO DE
PROCESO DE LAS TAREAS Y MAXIMIZANDO LA EFICIENCIA DE LA LÍNEA
MAESTRIA EN INGENIERÍA INDUSTRIAL
JUAN DAVID MORA PABÓN
200912354
Asesor:
JOSE FIDEL TORRES DELGADO
UNIVERSIDAD DE LOS ANDES
DEPARTAMENTO DE INGENIERÍA INDUSTRIAL
NOVIEMBRE DE 2015
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
Tabla de Contenido 1. Introducción ................................................................................................................................ 1
2. Importancia y relevancia del proyecto ........................................................................................ 2
3. Objetivos del proyecto ................................................................................................................ 3
3.1 General ..................................................................................................................................... 3
3.2 Específicos: ............................................................................................................................... 4
4. Revisión Bibliográfica................................................................................................................. 4
4.1 SALBP ................................................................................................................................ 7
4.2 GALBP ............................................................................................................................... 8
5. Descripción del problema y conceptos ...................................................................................... 10
5.1 Eficiencia .......................................................................................................................... 11
5.2 Costos flexibles de operación de las tareas .................................................................... 11
5.3 Costos de holgura del sistema ........................................................................................ 13
5.4 Costos del tiempo de ciclo ............................................................................................... 14
6. Modelos matemáticos ................................................................................................................ 15
6.1 Descripción supuestos, parámetros, conjuntos y variables de decisión de los
modelos ..................................................................................................................................... 15
6.2 Modelo matemático SALBP-E Mefi ............................................................... 22
6.3 Modelo matemático UALBP-E Mufi .................................................................. 24
6.4 Modelo de costos Mcos ............................................................................................. 27
7. Metodología .............................................................................................................................. 29
7.1 Fase I ............................................................................................................................ 30
7.2 Fase II ........................................................................................................................... 34
7.3 Fase III ......................................................................................................................... 35
7.4 Fase IV .......................................................................................................................... 35
7.5 Fase V ........................................................................................................................... 36
8. Resultados Computacionales ..................................................................................................... 36
8.1 Resultados SALBP-E Mefi ......................................................................................... 36
8.2 Resultados UALBP-E Mufi ........................................................................................ 40
8.3 Resultados de la Metodología propuesta con el modelo de costos Mcos ................ 44
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
9. Conclusiones y trabajo futuro ................................................................................................... 48
10. Bibliografía ........................................................................................................................... 50
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
1
1. Introducción
El problema de balanceo de línea, o como se conoce en la literatura por sus siglas en ingles
ALBP (Assembly Line Balancing Problem) es un problema que en las últimas décadas ha
sido tratado desde varios enfoques; desde los más simples como el SALBP (Simple Assembly
Line Balancing Problem) (Scholl & Becker, 2006)(Esmaeilbeigi & Naderi, 2015)(Restrepo,
P, & Cruz, 2008)(Fattahi & Turkay, 2015) hasta los más complejos como el SALDBP (Setup
Assembly Line Balancing and Scheduling Problem)(Scholl, Boysen, & Fliedner, 2013).
Siendo ampliamente estudiados, principalmente en su forma más simple (SALBP) (Becker
& Scholl, 2006).
Dada su naturaleza combinatoria, estos problemas son categorizados como problemas NP-
Hard (Betancourt & Moreno, 2004) por lo que son considerados problemas difíciles de
resolver a optimalidad y en el caso de problemas industriales, su solución se dificulta debido
al gran número de tareas y restricciones que componen un proceso productivo (Boysen,
Fliedner, & Scholl, 2007). Como extensión al SALBP, existen diferentes enfoques de
solución al problema de balanceo de línea, como el SALBP-E (Simple Assembly Line
Balancing Problem TypeE), en el cual se busca realizar un balanceo de línea maximizando
la eficiencia del sistema y el UALBP (U-Type Assembly Line Balancing Problem), en el
cual se considera la posibilidad de realizar el balanceo de la línea en forma de U para también
mejorar la eficiencia del sistema, que constituye uno de los objetivos del presente trabajo.
Para este tipo de problemas, se tienen posibilidades de estudio de los costos asociados al
tiempo de ejecución de tareas, que al ser variables logran una mejora en términos de costos
con un cambio asociado al tiempo de ciclo y la eficiencia del sistema.
En el presente trabajo, se busca proponer una programación matemática para maximizar la
eficiencia del sistema con una asignación apropiada de las tareas en las líneas de producción
en el enfoque simple (SALBP-E) y en el enfoque en U (UALBP-E). Como extensión a los
problemas básicos, se tendrán en cuenta los costos de procesos de las tareas con el fin de
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
2
proponer una solución al problema de balanceo de línea minimizando los costos asociados a
la operación de tareas y a la eficiencia de la línea.
2. Importancia y relevancia del proyecto
En este trabajo, se plantea una aproximación al problema de balanceo de línea simple
(SALBP) y en U (UALBP) con un enfoque de costos que permita mejorar la eficiencia del
sistema. Para esto, se va a realizar la comparación del modelo básico de eficiencia (SALBP-
E) y la configuración en U (UALBP-E) con una propuesta relacionada a la extensión de
costos. Este trabajo cuenta con un enfoque que linealiza los problemas no lineales (SALBP-
E Y UALBP-E) (T. Urban, 1998) y un modelo nuevo de costos que contempla características
adicionales como la búsqueda de minimización de costos del sistema. Para lograr lo anterior,
se busca maximizar la eficiencia del sistema (la cual tiene un costo asociado) y minimizar el
costo asociado al tiempo de procesamiento de las tareas y los costos asociados al tiempo de
ciclo.
En los últimos años, se ha venido generalizando cada vez más la adopción de políticas de
manufactura esbelta como el enfoque Just in Time (JIT) que busca mejorar la eficiencia de
los sistemas al utilizar los recursos de la mejor forma posible para las empresas
manufactureras (Toksari, Işleyen, Güner, & Baykoç, 2008). Al analizar algunos casos reales,
se ha comprobado que este enfoque es adecuado en empresas cuyos modelos de producción
incluyen trabajos repetitivos o líneas de producción ya que mejora la productividad, la
calidad de los productos/procesos y finalmente termina representando mayores utilidades
económicas para las empresas (Gökçen & Aǧpak, 2006).
Dado que en la vida real es importante el enfoque Just in Time en el estudio de la líneas de
producción, el enfoque en U (UALBP) que se le va a dar al problema genera un mayor campo
de acción que el modelo SALBP. Este tipo de enfoque en U tiene varias ventajas sobre el
enfoque tradicional de línea recta, puesto que se ha podido demostrar que la configuración
en U mejora la eficiencia de las líneas de producción en comparación con las líneas
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
3
tradicionales (Kriengkorakot & Pianthong, 2007). Adicionalmente, este tipo de
configuración es más compleja que el SALBP porque las tareas se pueden asignar
moviéndose hacia adelante o hacia atrás en la secuencia de las tareas.
Por otra parte, las empresas buscan disminuir los costos asociados a las operaciones en sus
líneas de producción (Amen, 2006). Algunas industrias tienen la capacidad de modificar los
tiempos de procesamiento de las operaciones, lo que podría llevar a una mejora en el tiempo
de ciclo. En muchas industrias, mejorar el tiempo de ciclo es importante ya que es posible
mejorar la tasa de producción (Scholl & Becker, 2005). Sin embargo, aumentar la velocidad
de las tareas conlleva un costo que puede llevar a problemas en el largo plazo, puesto que se
pueden empezar a presentar problemas de desgaste, corrosión, fatiga y daño lo cual reduciría
su tiempo de vida útil y aumentarían los costos de mantenimiento de las máquinas (Hamta,
Fatemi Ghomi, Jolai, & Bahalke, 2011). Por esta razón, el enfoque que se da en este trabajo
puede generar una oportunidad para mejorar el tiempo de ciclo aumentando la eficiencia del
sistema. Lo anterior, se puede modelar si se tienen en cuenta los costos asociados a reducir
los tiempos de las tareas, buscando un balance entre los costos de las tareas, los costos
asociados a la eficiencia y el tiempo de ciclo de todo el sistema.
Por lo anterior, en este trabajo se plantea un nuevo enfoque de estudio que agrupe las
características de costos en el enfoque de balanceo simple y de balanceo en U para poder
comparar los modelos y determinar los beneficios y ventajas de cada uno de ellos como una
aproximación del problema de balanceo de línea.
3. Objetivos del proyecto
3.1 General
Proponer una formulación para la programación lineal entera mixta para el
problema de balanceo de línea simple (SALBP-E) y en U (UALBP-E) que
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
4
maximice la eficiencia del sistema con un modelo de costos que minimice los
costos asociados a los tiempos de ejecución de las tareas, el tiempo de ciclo y
maximice la eficiencia del sistema.
3.2 Específicos:
Modelar el problema de balanceo de lineal SABLP-E y UALBP-E que permita
obtener mejores resultados computacionales en tiempo computacional.
Modelar el problema de costos como una extensión que permita obtener mejores
resultados en términos de eficiencia y costos.
Generar una solución iterativa entre los modelos de balanceo línea y de costos que
permitan encontrar una mejor solución que maximice la holgura del sistema y
minimice a su vez los costos del mismo.
Codificar y solucionar en Gurobi – Python el problema planteado.
Comparar los resultados obtenidos en la solución del problema planteado con los
resultados de la literatura y los modelos básicos SALBP-E y UALBP-E.
4. Revisión Bibliográfica
Las líneas de producción, han sido un elemento fundamental en muchos sistemas de
producción desde los inicios de la era industrial. Este concepto apareció de acuerdo a las
ideas de la división del trabajo para la creación de partes de manera repetitiva, el cual fue
utilizado o propuesto por Eli Whitney quién en 1799 inventó el sistema de manufactura
americano, concepto base que en 1913 Henry Ford utilizó para la creación de la primera línea
de montaje móvil con el propósito de disminuir costos de producción (Betancourt & Moreno,
2004). Desde ese momento, las empresas de producción se vieron obligadas a evolucionar en
sus aspectos funcionales, con el fin de adaptarse a un mercado más competitivo y exigente,
el cual llevó al mejoramiento de los procesos de manufactura en cuanto a la optimización de
recursos, costos, mejoras de calidad y eficiencia.(Restrepo et al., 2008).
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
5
Del mejoramiento de los procesos productivos en línea nació el concepto y el problema de
balanceo de líneas de producción, el cual consiste en distribuir las tareas necesarias para
realizar un proceso a través de un conjunto de estaciones que componen una línea de
producción. Este concepto en la literatura se conoce como ALBP (Assembly Line Balancing
Problem), que considera diferentes restricciones dependiendo del objetivo que se trabaje.
Estos problemas cuentan con un conjunto de tareas o actividades con un grafo de
precedencias1 asociado como se puede ver en la Ilustración 1.
Ilustración 1. Ejemplo de grafo de precedencia del problema Jackson 11
En la ilustración anterior, se presenta la secuencia de actividades para un sistema de la
literatura de 11 actividades. En este grafo, se puede observar que cada una de las tareas tiene
restricciones de precedencia, por lo que un adecuado balanceo de línea para este problema
debe respetar la secuencia de tareas predefinida al momento de definir la cantidad de
estaciones y las tareas que se procesan en las mismas. Estos grafos de precedencia están
asociados a cualquier problema de balanceo de línea, desde los más simples hasta los más
complejos, puesto que esto constituye uno de los supuestos básicos para estos estudios
(Baybars, 1986).
1 Grafo dirigido que representa el orden de tareas que se debe seguir en un proceso.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
6
Los enfoques clásicos de este problema, consideran diferentes supuestos en los sistemas, por
lo que todos los problemas de este tipo fueron categorizados en 1986 como SALBP (Baybars,
1986). Existen diferentes enfoques de estudio, como los que buscan minimizar el número de
estaciones del sistema dado un tiempo de ciclo definido (SALBP-1), minimizar el tiempo de
ciclo dado un número de estaciones (SALBP-2), maximizar la eficiencia del sistema
(SALBP-E) o buscar una solución factible a un problema dado un número de estaciones y un
tiempo de ciclo determinado (SALBP-F) (Betancourt & Moreno, 2004). Por otra parte, en la
literatura existe otro concepto asociado al balanceo de línea, el cual es conocido como
GALBP (General Assembly Line Balancing Problem). El GALBP, engloba y generaliza
todos los problemas de balanceo de línea que no son simples y que buscan otro tipo de
objetivos, ie, estaciones en paralelo, líneas en U, modelos mixtos, tiempos de procesos
variables, entre otros (Baybars, 1986)(Becker & Scholl, 2006)(Scholl & Becker,
2006)(Betancourt & Moreno, 2004).
En el siguiente diagrama, se muestra un resumen de la clasificación de los problemas de
balanceo de línea propuestas por Baybars (1986), Ghosh y Gagnon (1989), Graves y Lamar
(1983), Scholl (2013), Becker y Scholl( 2006).
Ilustración 2. Resumen de los problemas de balanceo de línea
Esta ilustración, muestra un resumen de algunos de los problemas que se han trabajado en la
literatura y la clasificación de los mismos desde los enfoques simples hasta los más
complejos.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
7
4.1 SALBP
El problema de balanceo de línea simple (SALBP), consiste en asignar tareas a una secuencia
ordenada de estaciones de manera que las relaciones de precedencia entre las tareas se
cumplan y sea posible evaluar alguna medida de desempeño. Este problema ha sido estudiado
desde la década de los 50’s, siendo definido en primera instancia por Bryton en 1954 y
formulado matemáticamente por Salverson en 1955 (Aǧpak & Gökçen, 2005).
Posteriormente Gutjahr y Nemhauser 1964 establecieron que el SALBP es un problema de
optimización combinatorio NP-Hard, por lo que cualquier problema que tenga como base el
SALBP es NP-Hard, llevando a que muchos más investigadores decidieran empezar a
estudiarlo a fondo (Erel & Gokcen, 1999).
Existen diferentes formas en que se puede enfocar la solución de este problema, siendo las
más tradicionales:
SALBP-1: Busca minimizar el número de estaciones dada una tasa de producción
acordada.
SALBP-2: Partiendo de un número de estaciones predefinido, se busca distribuir las
tareas u operaciones de tal forma que se minimice el tiempo de ciclo de todo el
sistema.
SALBP-E: Es la unión de los dos anteriores, el cual busca maximizar la eficiencia del
sistema, buscando minimizar el número de estaciones y tiempo de ciclo de forma
simultánea(Boysen et al., 2007).
SALBP-F: Este problema busca alguna solución factible para la combinación de un
número de estaciones y un tiempo de ciclo definidos (Betancourt & Moreno, 2004).
La mayoría de los estudios se han hecho para SALBP-1 y SALBP-2, teniendo un gran
número de investigaciones. Entre éstas, se encuentran el primer modelo matemático
planteado y el uso de la programación entera por parte de Salverson, la programación
dinámica de Jackson para el SALBP-1, los modelos matemáticos de variables binarias de
Bowman, el uso de programación entera mixta por parte de Essafi, Delorme, Dolgui y
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
8
Guschinskaya (Wei & Chao, 2011), algoritmos exactos como los que presenta Bayrbars
(1986) y metaheurísticas como algoritmos genéticos (Chong, Omar, & Bakar, 2008)(Hamta
et al., 2011).
Mientras tanto, el modelo SALBP-E, ha tenido una menor intensidad de investigación
posiblemente debido a su complejidad. A pesar de esto, se ha llegado a métodos heurísticos,
en los cuales se utiliza primero el modelo SALBP-1 para encontrar una cota superior para el
número mínimo de estaciones, luego de implementa iterativamente el modelo SALBP-2 al ir
disminuyendo en uno el número de estaciones (Wei & Chao, 2011) (Hamta et al., 2011
)(Plans & Corominas, 1999) (Amen, 2006). Igualmente, existen otros estudios en los cuales
se han realizado modelos de programación matemáticas para la solución este problema (Plans
& Corominas, 1999)(Esmaeilbeigi & Naderi, 2015)(Graves & Lamar, 1983). Por otra parte
al ser este un problema de mayor complejidad, en los últimos años, los investigadores se han
enfocado en el uso de metaheurísticas como algoritmos genéticos (Yolmeh & Kianfar, 2012)
(Zhang, Xu, & Gen, 2014) (Hamta et al., 2011) (Amen, 2000), colonia de hormigas
(Kucukkoc & Zhang, 2015)(Ze-qiang, Tang, & Bin, 2007), enfriamiento simulado (Cakir,
Altiparmak, & Dengiz, 2011), entre otras.
4.2 GALBP
El General Assembly Line Balancing Problem (GALBP) propuesto por Baybars en 1986 es
la generalización de los problemas clásicos (SALBP), en donde se busca la solución de
objetivos diferentes a los tradicionales de acuerdo a objetivos de costos como primera
aproximación a este concepto (Baybars, 1986). En 1989, Gnosh y Gagnon extendieron el
concepto propuesto en 1986, considerando un mayor número de restricciones, esto con el fin
de considerar un mayor número de características y enfoques de solución al balanceo de línea
(Ghosh & Gagnon, 1989). Del concepto general del GALBP se han generado diferentes
enfoques de trabajos como los presentados en la Ilustración 2.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
9
Uno de los enfoques más representativos del GALBP, es el U-Type Assembly Line
Balancing Problem (UALBP), este tipo de problemas es uno de los más trabajados en la
literatura debido a que el balanceo de línea no necesariamente puede realizarse en línea recta.
Para los sistemas de producción actuales, las líneas en forma de U han sustituido cada vez
más las líneas tradicionales como resultado de la filosofía (JIT) just-in-time (T. L Urban,
1998). Por otra parte, muchos investigadores coinciden en que la disposición en forma de U
es uno de los componentes más importantes para una implementación exitosa de la
producción JIT (J. Miltenburg, 2001)(Burns & Tou, 1989). La diferencia principal que se
puede observar entre las líneas de ensamble tradicionales y las líneas en U, es la entrada y
salida de los productos, ya que el producto sale del sistema por el mismo lugar en el que
ingresó (Burns & Tou, 1989)(Manavizadeh, Hosseini, Rabbani, & Jolai, 2013) por lo que se
tiene un caso de estudio diferente si se trabaja con el problema de balanceo de línea o el
balanceo de línea en U (UALBP).
En la literatura, algunos autores han trabajado el enfoque de línea en U con los mismos
objetivos que en el SALBP, por lo que se tienen enfoques que buscan minimizar el número
de estaciones (UABLP-1), y el tiempo de ciclo del sistema (UABLP-2) y maximizar la
eficiencia (UALBP-E), siendo los dos primeros los más trabajados (Gökçen & Aǧpak,
2006)(Kriengkorakot & Pianthong, 2007). Por otra parte, el enfoque de eficiencia no ha sido
ampliamente trabajado debido al tamaño y la dificultad de los problemas.
Los problemas tradicionalmente son orientados al tiempo, lo que quiere decir que su objetivo
se basa en minimizar tiempos (tiempo de ciclo, tiempos ociosos, etc.) por lo cual no tienen
en cuenta factores de costos como los asociados a salarios y a maquinaría(Amen, 2006). Así,
al buscar simplicidad para la resolución de los problemas estos tienden a ser altamente
restrictivos en sus supuestos y por tanto pueden no representar la realidad industrial. Esto
ocurre en líneas de producto de gran tamaño y volumen o en líneas, como las de bienes de
consumo duradero, donde se necesita gran intensidad de mano de obra (Betancourt &
Moreno, 2004). Por esta razón, han surgido un mayor número de investigaciones que buscan
plantear un balanceo de línea orientada a los costos cuyo objetivo sea minimizar los costos
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
10
por unidad de producto (Amen, 2006)(Amen, 2000)(Hamta et al., 2011)(Scholl & Becker,
2005).
5. Descripción del problema y conceptos
El presente trabajo se dividirá en tres modelos. Cada modelo va a trabajar un tipo de problema
diferente. Los problemas a trabajar son el SALBP-E, el UALBP-E y un modelo de costos
asociado al tiempo de proceso de las tareas (utiliza como base la solución de los primeros
modelos). Al definir los modelos, se va a utilizar una metodología iterativa para alcanzar el
objetivo del presente trabajo el cual es minimizar los costos del sistema y maximizar la
eficiencia de la línea (Ver sección 7 Metodología).
Para el primer problema (SALBP-E), se va proponer un modelo de programación entera
mixta basada en el trabajo desarrollado por Esmaeilbeigi & Nader (2015), proponiendo
pequeños cambios al cálculo de algunos de los parámetros propuestos en la literatura con el
fin de reducir el tiempo computacional de la propuesta los cuales se explicaran más adelante.
Este problema, originalmente es un modelo no lineal, por lo que se utilizará como base la
linealización propuesta por Esmaeilbeigi. Este modelo busca realizar una asignación factible
de las tareas que minimice la holgura del sistema.
Para el segundo problema (UALBP-E), se va a proponer una extensión del modelo simple
(problema 1) que tenga en cuenta la posibilidad de ejecutar tareas en forma de U como se
observa en la ilustración 5.
Adicionalmente, el tercer modelo es un problema en el cual se busca minimizar los costos
del sistema. Para este caso, los costos que se van a tener en cuenta están asociados a los
tiempos de ejecución de cada tarea, los costos por holgura en el sistema y los costos por el
incumplimiento del tiempo de ciclo original.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
11
Para entender los modelos que se van a proponer se tendrán en cuenta los siguientes
conceptos.
5.1 Eficiencia
La eficiencia de las líneas de producción es uno de los factores más importantes (Kucukkoc
& Zhang, 2015), ya que busca utilizar los recursos disponibles de la mejor forma, con el fin
de obtener los mejores resultados en el proceso.
En los modelos clásicos SALBP-E y UALBP-E, se busca mejorar la eficiencia del sistema
como el producto del número de estaciones por el tiempo de ciclo, lo que hace que estos
problemas sean no lineales (Plans & Corominas, 1999)(Becker & Scholl, 2006). Como
solución alterna a maximizar la eficiencia, se puede buscar la minimización de la holgura2
del sistema. La búsqueda de este objetivo asegura que se logre maximizar la eficiencia del
sistema. Con esta solución, se puede solucionar el problema de no linealidad del modelo
(Esmaeilbeigi & Naderi, 2015) para el caso en que no se tengan definidos la cantidad de
estaciones o el tiempo de ciclo del sistema.
En este documento se va a trabajar con la holgura del sistema con el fin de maximizar la
eficiencia, teniendo en cuenta que la cantidad de estaciones y el tiempo de ciclo del sistema
no están definidos.
5.2 Costos flexibles de operación de las tareas
En los problemas de balanceo de línea se tienen secuencias de. En las instancias de la
literatura, los tiempos de las actividades fueron definidos al momento de la creación de las
mismas, sin embargo en los sistemas reales, los tiempos de tareas son definidos de acuerdo
2 Diferencia entre el tiempo de ciclo de las estaciones del sistema y el tiempo real de ejecución de todas las tareas en cada estación.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
12
al estudio del sistema y del proceso de cada una de las actividades que se realizan en el
mismo.
Dependiendo de las necesidades de las empresas, los tiempos de las tareas pueden variar de
acuerdo a las características que tengan. En ciertos casos, el tiempo de las tareas puede
reducirse con el fin de mejorar el tiempo de ciclo del sistema y así aumentar la tasa de
producción (Amen, 2000), pero para lograrlo se debe incurrir en un costo. El esfuerzo
realizado para la reducción de tiempos puede generar costos adicionales como la capacitación
de los operarios (en manufactura con mano de obra), costos de mantenimiento, ajuste,
corrosión de las máquinas, entre otros (Hamta et al., 2011). Es importante aclarar que los
tiempos de las tareas que se pueden reducir varían de sistema a sistema debido a las
características intrínsecas de cada uno, por lo que no se tiene un estándar en la magnitud en
que se pueden disminuir estos tiempos. Sin embargo, en sistemas productivos con estudios
eficientes de tiempos se pueden definir los tiempos mínimos de operación de las actividades
por las características de las tareas, y a su vez, se pueden establecer los máximos tiempos que
están dispuestos a tener las compañías en las diferentes tareas de acuerdo al estudio realizado.
Lo anterior es importante para las empresas, puesto que el tiempo de ciclo se ve afectado por
el tiempo de procesamiento de las tareas y esto afecta directamente las tasas de producción.
En este trabajo, los costos de las tareas se van a calcular con base al trabajo realizado por
Hamta et al. (2011). Los costos de las tareas van a ser definidos en función del tiempo, donde
el costo superior del proceso se da en el tiempo original de la tarea (instancias de la literatura)
y va a ser considerado como el costo en el tiempo mínimo de procesamiento según los
estudios de tiempo, por otra parte, el costo inferior se presenta en el máximo permitido por
la empresa para el procesamiento de una tarea (tiempo superior al original). Se va a tener en
cuenta una relación lineal para estos costos cómo se presenta en la Ilustración 3.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
13
Ilustración 3. Ejemplo. Relación lineal entre tiempo de la tarea y costos de procesamiento de la tarea
Cómo se muestra en la Ilustración 3, se busca modelar el comportamiento de los costos de
los tiempos de proceso de las tareas. Para esto, se tendrán en cuenta los límites superiores e
inferiores para los costos y los tiempos de las tareas los cuales se propondrán más adelante.
5.3 Costos de holgura del sistema
En los sistemas de producción, la eficiencia puede tener un enfoque relacionado con la
holgura3, por lo que en este trabajo se busca minimizar la holgura del sistema con el fin de
maximizar la eficiencia del mismo.
Para el funcionamiento de una línea de producción, es necesario tener en cuenta la asignación
de las tareas para realizar los procesos productivos. Las compañías normalmente buscan tener
un proceso que sea lo más eficiente posible y que tenga una tasa de producción alta, pero en
los casos prácticos esto no siempre se puede lograr, ya sea por restricciones reales o porque
se prefiere tener una tasa de producción mayor sacrificando la eficiencia de todo el sistema.
3 Ejemplo. Un sistema con holgura 0 es una línea con eficiencia de 100%,
7
3
Tli TUi
Tiempo de tarea
Costo de
cada tarea
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
14
Según Pinto, Dannenbring, & Khumawala (1983), en un sistema de producción no solo se
debe tener en cuenta el tiempo total de trabajo, sino también el tiempo libre de cada estación
como medida de eficiencia de las alternativas de diseño, por lo que ese tiempo ocioso afecta
directamente los costos de la línea. A razón de lo anterior, se tendrá en cuenta un costo
asociado al tiempo de holgura del sistema, en el cual las empresas están incurriendo en costos
por el trabajo de recursos que no están en uso durante todo el tiempo de ciclo, por lo que
están incurriendo en costos adicionales al tener recursos que no están operando.
5.4 Costos del tiempo de ciclo
En este trabajo, se va a considerar un costo asociado al tiempo de ciclo del sistema. Este
costo, está relacionado con el tiempo disponible que tiene la línea de producción para
completar todas las actividades de un producto. Este tiempo de ciclo se puede asociar
directamente con la tasa de producción de las empresas, que a su vez se relaciona con los
niveles de producción deseados por la empresa.
En la práctica, las compañías buscan definir un tiempo de ciclo que les permita cumplir o
superar las tasas de producción al menor costo posible, por lo que cualquier tiempo de ciclo
mayor al nivel deseado generará porcentajes de sobre tiempo, lo que implica que las empresas
deben pagar niveles de salarios más altos (Betancourt & Moreno, 2004).
En estos modelos, se considera un costo asociado al cambio en el tiempo de ciclo del sistema
de cada una de las líneas de producción. Lo anterior se refiere a que este costo va a estar
asociado a la diferencia entre el tiempo de ciclo deseado por las empresas (tiempo mínimo
de procesamiento de las tareas) Tc1 y el tiempo de ciclo obtenido al modificar los tiempos de
las tareas Tc2 (Ver sección 5.2). Este costo se puede considerar en el modelo ya que al no
cumplir con tiempo de ciclo definido las empresas pueden llegar a tener un costo por no
cumplir la tasa de producción esperada.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
15
6. Modelos matemáticos
Como anteriormente se mencionó, en la presente investigación se trabajará con 3 modelos.
En esta sección se van a definir cada uno de los modelos que se van a utilizar, adicionalmente
se van a presentar los supuestos, conjuntos y parámetros que se van a utilizar en cada modelo.
Los modelos son los siguientes:
Mefi: Modelo matemático entero mixto SALBP-E.
Mufi: Modelo matemático entero mixtoUALBP-E.
Mcos: Modelo matemático entero de costos.
6.1 Descripción supuestos, parámetros, conjuntos y variables de decisión de los
modelos
En esta sección se van a presentar los supuestos, parámetros, conjuntos y variables de
decisión para los modelos que se van a trabajar. Los supuestos generales van a ser para todos
los modelos, sin embargo los parámetros, conjuntos y variables de decisión no son los
mismos para todos aunque compartan algunos de ellos, por lo que en esta sección se va a
discriminar que datos utiliza cada modelo.
6.1.1 Supuestos Generales
Los supuestos que se van a trabajar en los tres modelos son los siguientes.
Los tiempos de operación de las tareas son conocidos.
Las relaciones de precedencia de las tareas son conocidas.
Cada tarea debe llevarse a cabo sólo una vez en cada corrida de producción.
Se va a tener en cuenta el caso de un solo producto.
No se consideran los tiempos de setup de las máquinas.
Se permite el tiempo de holgura en las estaciones.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
16
Sólo puede procesarse una tarea al mismo tiempo en cada estación.
Todas las tareas deben realizarse para completar el proceso de producción.
Una tarea solo se puede hacer en una única estación.
Se va a considerar que existe un grafo fantasma de tareas para el modelo de balanceo
de línea con forma de U.
Se van a tener en cuenta costos por unidad de tiempo de operación para cada tarea.
Se va a considerar un costo por cada unidad de holgura del sistema.
Se va a considerar un costo asociado al incumplimiento del tiempo de ciclo base.
6.1.2 Parámetros
Para los 3 modelos matemáticos, se van a utilizar las instancias de la literatura recuperadas
de http://alb.mansci.de. En estas instancias solo se tienen definido el número de tareas, las
relaciones de precedencia, los tiempos de las tareas y el límite inferiores del número de
estaciones del sistema.
Los demás parámetros que se van a utilizar en los modelos, se van a calcular de acuerdo a
los valores iníciales de las instancias. La descripción de los parámetros se puede ver en la
Tabla 1. En esta tabla, se puede ver cuales parámetros van a ser calculados y utilizados en
cada uno de los modelos.
Los parámetros 1 y 2 son valores obtenidos de las instancias, mientras que del 3 al 5 son
parámetros calculados de acuerdo al parámetro 2 (Ver ejemplo en la Tabla 1). Para el número
mínimo de estaciones, que en este caso es el parámetro 6, se utilizó el valor calculado en las
instancias. El número máximo de estaciones, que en este caso es el parámetro 7, se calculó a
partir de los parámetros 4 y 5. Para calcular los límites del tiempo de ciclo (8) y (9) se hizo
uso del modelo SALBP-2 (Minimiza el tiempo de ciclo de acuerdo a un número de estaciones
dado).
Los demás parámetros se calcularon a partir de los conjuntos que se definen en la Tabla2.
Con lo anterior, los parámetros 10 y 11 se calcularon respecto a los conjuntos que se definen
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
17
en la sección 6.1.3, que a su vez sirvió para calcular las estaciones más tempranas y tardías
en las que pueden iniciar las tareas (parámetros 12 y 13).
Los parámetros del 1 al 13 son parámetros calculados con base al trabajo de Esmaeilbeigi &
Naderi ( 2015). Sin embargo, se hizo una pequeña modificación a los parámetros 12 y 13
como se muestra en (Scholl & Becker, 2006).Los parámetros del 14 al 17, únicamente los
utiliza el modelo Mufi. Estos parámetros, también calculan las estaciones más tempranas y
más tardías en las que puede iniciar una tarea pero en el grafo fantasma.
Los parámetros del 18 al 23 son parámetros para el modelo de costos únicamente, sin
embargo para poder comparar los tres modelos se van a usar en los modelos Mefi y Mufi.
Para los modelos Mefi y Mufi los parámetros 18 y el 19 representa el tiempo de proceso de
cada tarea obtenido de las instancias, sin embargo, para el modelo Mcos el tiempo de proceso
de cada tarea cambia y se tiene en cuenta el tiempo de la holgura obtenida en los modelos
Mefi y Mufi para el cálculo del parámetro 19.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
18
Tabla 1. Parámetros de los modelos
Parámetros Mefi Mufi Mcos
1 x x x
2 x x
3 x x
4 x x
5 x x
6 x x x
7 x x x
8 x x x
9 x x x
x x12
13 x x
10 x x
11 x x
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
19
19 xx x
x
x x x
22
23
x x
20 x x x
21 x x x
x x x18
x16
x17
14 x
15 x
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
20
6.1.3 Conjuntos
En cada uno de los modelos se trabajará con varios conjuntos. . El conjunto 1 representa el
conjunto de tareas, las estaciones se separaron entre mínimas (conjunto 2), máximas
(conjunto 3) y un conjunto de estaciones totales (conjunto 4). El conjunto 5 representa las
precedencias de las tareas, el 6 y el 7 representan conjuntos con las precedencias directas e
indirectas de cada una de las tareas. Los conjuntos 8 y 9 se crearon con el fin de reducir la
cantidad de variables a crear en el modelo, ya que no todas las tareas se pueden hacer en
todas las estaciones.
Los conjuntos del 10 al 14 son conjuntos que solo utiliza el modelo Mufi y se calculan igual
que los conjuntos del 1 al 9, pero en este caso se tiene en cuenta que se calculan respecto al
grafo fantasma.
Los conjuntos 15 y 16 son conjuntos para el modelo Mcos, los cuales se generan respecto a
la solución obtenida de los modelos Mufi y Mefi. Para estos conjuntos se tiene en cuenta el
valor (1,0) de la asignación de las tareas a las estaciones creadas.
Estos conjuntos se crearon con base al trabajo de Esmaeilbeigi & Naderi (2015)y se pueden
ver en la Tabla 2. Conjuntos de los modelos.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
21
Tabla 2. Conjuntos de los modelos
Conjuntos Mefi Mufi Mcos
1 x x x
2 x x x
4 x x x
16 x
14 x
15 x
12 x
13 x
10 x
11 x
x
9 x x
x x
8
7 x x
x
6
x x x3
5 x x
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
22
6.1.4 Variables de decisión
Las variables de decisión que se van a usar en los diferentes modelos son las siguientes:
Tabla 3. Variables aleatorias de los modelos
En la Tabla 3. Variables aleatorias de los modelos se presentan como se definen las variables
que se van a utilizar en los diferentes modelos.
6.2 Modelo matemático SALBP-E Mefi
El modelo que se va a utilizar para maximizar la eficiencia del sistema y el cual se va a
modelar minimizando la holgura de la línea basado en el trabajo de (Esmaeilbeigi &
Naderi, 2015) es el siguiente:
min ∑ ℎ𝑘 (1)
𝑘 ∈𝑆𝑒𝑡𝐾
𝒔 . 𝒂
∑ 𝑥𝑖𝑘 = 1 ∀ 𝑖 ∈ 𝑇𝑎𝑟𝑒𝑎𝑠 (2)
𝑘 ∈ 𝐹𝑠𝑖
∑ 𝑘𝑥𝑖𝑘 ≤ ∑ 𝑘𝑥𝑗𝑘
𝑘 ∈ 𝐹𝑠𝑗
∀(𝑖, 𝑗) ∈ 𝑃𝐷 (3)
𝑘 ∈ 𝐹𝑠𝑖
∑ 𝑡𝑖𝑥𝑖𝑘 + ℎ𝑘 = 𝑐 ∀ 𝑘 ∈ 𝐾𝑖𝑛𝑓 (4)
𝑖 ∈ 𝐹𝑡𝑘
Variables de decisión Mefi Mufi Mcos
3 x x x
4 x x x
6 x
7 x
x x
x
5 x
x
1
2
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
23
∑ 𝑡𝑖𝑥𝑖𝑘 + ℎ𝑘 ≤ 𝑐 ∀ 𝑘 ∈ 𝐾𝑠𝑢𝑝 (5)
𝑖 ∈ 𝐹𝑡𝑘
∑ 𝑡𝑖𝑥𝑖𝑘 + ℎ𝑘 ≥ 𝑐 + 𝑐𝑠𝑢𝑝(𝑢𝑘 − 1) ∀ 𝑘 ∈ 𝐾𝑠𝑢𝑝 (6)
𝑖 ∈ 𝐹𝑡𝑘
∑ 𝑡𝑖𝑥𝑖𝑘 + ℎ𝑘 ≤ 𝑐𝑠𝑢𝑝𝑢𝑘 ∀ 𝑘 ∈ 𝐾𝑠𝑢𝑝 (7)
𝑖 ∈ 𝐹𝑡𝑘
𝑢𝑘+1 ≤ 𝑢𝑘 ∀ 𝑘 ∈ 𝐾𝑠𝑢𝑝 ∪ 𝑚𝑖𝑛𝑓 (8)
ℎ𝑘 ≥ 0 ∀ 𝑘 ∈ 𝑆𝑒𝑡𝐾 (9)
𝑐𝑖𝑛𝑓 ≤ 𝑐 ≤ 𝑐𝑠𝑢𝑝 𝑐 ∈ ℤ+ (10)
𝑥𝑖𝑘 ∈ {0,1} ∀𝑖, 𝑘 ∈ 𝑃𝐷 (11)
𝑢𝑘 ∈ {0,1} ∀ 𝑘 ∈ 𝑆𝑒𝑡𝐾 (12)
En el modelo SABLP-E, la función objetivo (1) busca minimizar la holgura del sistema, esto
se hace para todas las estaciones. Se busca minimizar la holgura ya que la minimización de
esta variable asegura que se maximice la eficiencia del sistema. La restricción (2), asegura
que cada tarea debe estar asignada a una estación. La restricción (3), se encarga de probar
que la asignación de las tareas a las estaciones respete las relaciones de precedencia de las
tareas. Las restricciones (4), (5), (6), y (7) capturan la holgura del sistema cuando se tiene el
número mínimo de estaciones y cuando se llega al límite superior de estas. La restricción (4)
se tiene en cuenta solo para las estaciones que se van a crear siempre, es decir las que son el
mínimo de estaciones en el sistema y capturar así la holgura. Por otra parte las restricciones
(5, 6 y 7) capturan la holgura únicamente para las estaciones adicionales al mínimo, esto
sucede puesto que el modelo va a decidir que estaciones van a crearse y por cada estación
adicional creada se captura la holgura de la estación. Lo anterior se hizo con el fin de reducir
el número de variables al tener fijo un número de estaciones a crear (minf), por lo que se
reduce el número de variables en una cantidad igual a minf.
La restricción (8), se encarga de que si la estación k no existe la estación k+1 no se va a
crear. Finalmente, las restricciones (9), (10), (11) y (12) se encargan de definir las variables
objetivo del modelo.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
24
6.3 Modelo matemático UALBP-E Mufi
Este modelo es una extensión del modelo SALBP-E el cual tiene una categoría diferente en
la literatura (GALBP). En este modelo se va a considerar la existencia de un grafo fantasma
de las actividades, el cual se presenta en Ilustración 4.
Ilustración 4. Representación del grafo fantasma en la instancia Jackson 11(T. Urban, 1998)
En la ilustración anterior, se observa la representación del diagrama de precedencias con el
grafo fantasma y el original. En el lado derecho de la gráfica, se muestra el grafo original con
la secuencia de las tareas A-K. En el lado izquierdo, se presenta el grafo fantasma en el cual
la secuencia de las tareas se hace de forma inversa de las tareas K-A. Con el grafo fantasma,
se generan nuevas relaciones de precedencia en la línea, lo anterior se hace para modelar la
línea en forma de U, debido a que en este tipo de línea es posible que la última tarea pueda
realizarse en la misma estación que la primera tarea.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
25
Ilustración 5. Ejemplo de asignación Jackson 11 maximizando la eficiencia. (a) Balanceo simple. (b) Balanceo en U
En la gráfica anterior, se presenta la diferencia de asignaciones de las tareas dependiendo si
se hace el balanceo de la línea simple o en U (con el grafo fantasma). Se puede observar que
en el balanceo en U, las últimas tareas se pueden asignar a las primeras estaciones siempre y
cuando las relaciones de precedencia originales se cumplan (Kriengkorakot & Pianthong,
2007).
En este modelo, la cantidad de las variables se va a duplicar, debido a que se van a tener en
cuenta las relaciones de precedencia para el grafo fantasma (G. Miltenburg & Winjngaard,
2001), por lo que el tiempo computacional del modelo aumenta. Sin embargo, en este modelo
se va a reducir el número total de variables aleatorias que representan el grafo fantasma,
puesto que se van a definir nuevos conjuntos, los cuales van a tener la información de qué
tareas son factibles a realizarse en la estación seleccionada (ver conjuntos 13 y 14 en la Tabla
2). Estos conjuntos se definen de acuerdo a los valores originales de las instancias y las
precedencias del grafo fantasma.
Este modelo se plantea debido a que en casos reales se ha comprobado que el balanceo en U
está ligado al concepto Just in Time, por lo que es posible obtener una mejora en la eficiencia
del sistema (Sparling, 1998).
A B F H I J
G C D K
E
A H F B G
K J E I D C
(b)
Estación 1 Estación 2 Estación 3
Estación 1 Estación 2 Estación 3
(a)
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
26
Es importante decir que este modelo es una extensión al trabajo de Esmaeilbeigi & Naderi
(2015) ya que se va a trabajar con líneas en U, problema que no se trató en el trabajo original.
El modelo propuesto para realizar el balanceo de línea en U minimizando la eficiencia del
sistema es el siguiente:
min ∑ ℎ𝑘 (13)
𝑘 ∈𝑆𝑒𝑡𝐾
𝒔 . 𝒂 (8), (9), (10), (11), (12)
∑ 𝑥𝑖𝑘 + ∑ 𝑦𝑖𝑘
𝑘 ∈ 𝐹𝐹𝑠𝑖
= 1 ∀ 𝑖 ∈ 𝑇𝑎𝑟𝑒𝑎𝑠 (14)
𝑘 ∈ 𝐹𝑠𝑖
∑ (𝑚𝑠𝑢𝑝 − 𝑘 + 1)(𝑥𝑖𝑘 − 𝑥𝑗𝑘) ≥ 0 ∀(𝑖, 𝑗) ∈ 𝑃𝐷 (15)
𝑘 ∈ 𝐹𝑠𝑖
∑ (𝑚𝑠𝑢𝑝 − 𝑘 + 1)(𝑦𝑖𝑘 − 𝑦𝑗𝑘) ≥ 0 ∀(𝑖, 𝑗) ∈ 𝑃𝐷𝐹 (17)
𝑘 ∈ 𝐹𝐹𝑠𝑖
∑ 𝑡𝑖𝑥𝑖𝑘 + ∑ 𝑡𝑖𝑦𝑖𝑘
𝑖 ∈𝐹𝐹𝑇𝑘
+ ℎ𝑘 = 𝑐 ∀ 𝑘 ∈ 𝐾𝑖𝑛𝑓 (18)
𝑖 ∈ 𝐹𝑇𝑘
∑ 𝑡𝑖𝑥𝑖𝑘 + ∑ 𝑡𝑖𝑦𝑖𝑘
𝑖 ∈FF𝑇𝑘
+ ℎ𝑘 ≤ 𝑐 ∀ 𝑘 ∈ 𝐾𝑠𝑢𝑝 (19)
𝑖 ∈ 𝐹𝑇𝑘
∑ 𝑡𝑖𝑥𝑖𝑘 + ∑ 𝑡𝑖𝑦𝑖𝑘
𝑖 ∈FF𝑇𝑘
+ ℎ𝑘 ≥ 𝑐 + 𝑐𝑠𝑢𝑝(𝑢𝑘 − 1) ∀ 𝑘 ∈ 𝐾𝑠𝑢𝑝 (20)
𝑖 ∈ 𝐹𝑇𝑘
∑ 𝑡𝑖𝑥𝑖𝑘 + ∑ 𝑡𝑖𝑦𝑖𝑘
𝑖 ∈𝐹𝐹𝑇𝑘
+ ℎ𝑘 ≤ 𝑐𝑠𝑢𝑝𝑢𝑘 ∀ 𝑘 ∈ 𝐾𝑠𝑢𝑝 (21)
𝑖 ∈ 𝐹𝑇𝑘
𝑦𝑖𝑘 ∈ {0,1} ∀ 𝑘 ∈ 𝑆𝑒𝑡𝐾 (22)
En el modelo UABLP-E (Mufi) la función objetivo (13) busca minimizar la holgura del
sistema. La restricción (14), asegura que cada tarea deba estar asignada a una estación, para
esta restricción se tiene en cuenta la asignación de las tareas en el grafo fantasma. Las
restricciones (15) y (17), se encargan de probar que la asignación de las tareas a las estaciones
respete las relaciones de precedencia de las tareas. En estas restricciones se tienen en cuenta
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
27
las asignaciones en el grafo fantasma por lo que las tareas deben cumplir sus precedencias
hacia adelante y hacia atrás en el grafo (Ver conjuntos 6 y 10 de la Tabla 2).
Las restricciones (18), (19), (20), y (21) capturan la holgura del sistema cuando se tiene el
número mínimo de estaciones y cuando se llega al límite superior. De igual manera se tiene
en cuenta la posible asignación que se hace en el grafo fantasma. Estas restricciones se
proponen de la misma forma en que se hizo en el modelo Mefi. Finalmente, la restricción
(22) se encarga de definir las variables objetivo del modelo para el grafo fantasma. Se debe
tener en cuenta que los conjuntos adicionales propuestos que se utilizan, buscan reducir el
número de variables a crear en el modelo.
6.4 Modelo de costos Mcos
Para este modelo, se va a utilizar el tiempo de las tareas 𝑡𝑒𝑖 como una variable, ya que se
pretende minimizar el costo asociado a los tiempos de tareas en el sistema. El modelo va a
utilizar las asignaciones de los modelos anteriores como parámetros para la solución del
mismo, esto con el fin de realizar una mejora al sistema enfocada a costos a la solución que
maximiza la eficiencia de la línea. Con esta asignación, se soluciona el problema de no
linealidad que puede resultar al tratar los tiempos de las tareas y las asignaciones de las
mismas como variables. Adicional a lo anterior, la cantidad de variables que utiliza el modelo
se va a reducir y se puede obtener un resultado adicional al modelo básico de balanceo.
Con este modelo se busca proponer mejoras a un balanceo de línea teórico que no tiene en
cuenta los costos de trabajo, por lo que la idea es proponer mejoras según los resultados del
modelo que puedan llevar al sistema a tener la mayor eficiencia posible reduciendo costos.
Para este modelo, se va a utilizar el supuesto de que el costo de las tareas disminuirá de forma
lineal (como se explicó en la sección 5.2), es decir que entre mayor sea el tiempo de
procesamiento de la tarea menor es el costo de la tarea(Amen, 2000)(Amen, 2006)(Hamta et
al., 2011). Lo anterior se hace bajo el supuesto de que entre más rápido se termine una tarea
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
28
se va incurrir en mayores costos. Por otra parte, se tiene el supuesto de un costo asociado al
tiempo de holgura en el sistema. Los costos de las tareas y de la holgura se van a proponer
en este trabajo. De otro lado, se tiene un costo asociado al tiempo de ciclo en el que se incurre
si este no se cumple al momento de mejorar la eficiencia del sistema (como se explicó en la
sección 5.3).
Este modelo va a ser utilizado para el balanceo de línea simple y el balanceo en U con el fin
de comparar los resultados de las configuraciones (Conjuntos 15 y 16 de la Tabla 2.
Conjuntos de los modelos).
Para el modelo se debe tener en cuenta lo siguiente:
El tiempo de ciclo sigue siendo variable y puede llegar a aumentar.
El número de estaciones y las asignaciones de las tareas no se modificará en este
modelo. El modelo va a utilizar los resultados de los modelos SALBP-E y UALBP-
E propuestos.
Los costos de las tareas pueden llegar a modificar el tiempo de holgura del sistema,
buscando maximizar la eficiencia minimizando los costos de la línea.
El modelo propuesto de costos es el siguiente:
min ∑ ℎ𝑘𝑐𝑜𝑠𝑡𝑜ℎ + ∑ 𝑐𝑜𝑠𝑡𝑜𝑝𝑖
𝑖 ∈𝑡𝑎𝑟𝑒𝑎𝑠
+ 𝐶𝑜𝑠𝑡𝑜𝑡𝑐(𝑐𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑐𝑖𝑐𝑙𝑜 𝑀𝑒𝑓𝑖 𝑜 𝑀𝑢𝑓𝑖 − 𝑐) (23)
𝑘 ∈𝑆𝑒𝑡𝐾
𝒔 . 𝒂 (9), (10)
∑ tei + ℎ𝑘 = 𝑐 ∀ 𝑘 ∈ 𝐾𝑖𝑛𝑓 (24)
𝑖 ∈ 𝑎𝑠𝑖𝑔𝑖𝑘
∑ tei + ℎ𝑘 ≤ 𝑐 ∀ 𝑘 ∈ 𝐾𝑠𝑢𝑝 (25)
𝑖 ∈ 𝑎𝑠𝑖𝑔𝑖𝑘
∑ tei + ℎ𝑘 ≥ 𝑐 + 𝑐𝑠𝑢𝑝(e𝑢𝑘 − 1) ∀ 𝑘 ∈ 𝐾𝑠𝑢𝑝 (26)
𝑖 ∈ 𝑎𝑠𝑖𝑔𝑖𝑘
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
29
∑ tei + ℎ𝑘 ≤ 𝑐𝑠𝑢𝑝𝑒𝑢𝑘 ∀ 𝑘 ∈ 𝐾𝑠𝑢𝑝 (27)
𝑖 ∈ 𝑎𝑠𝑖𝑔𝑖𝑘
𝑐𝑜𝑠𝑡𝑜𝑝𝑖 =(𝑠𝑢𝑝𝑐𝑜𝑠𝑡𝑜𝑖 − 𝑖𝑛𝑓𝑐𝑜𝑠𝑡𝑜𝑖)
(𝑖𝑛𝑓𝑡𝑖 − 𝑠𝑢𝑝𝑡𝑖)(tei − 𝑖𝑛𝑓𝑡𝑖) + 𝑠𝑢𝑝𝑐𝑜𝑠𝑡𝑜𝑖 ∀ 𝑖 ∈ 𝑇𝑎𝑟𝑒𝑎𝑠 (28)
sup𝑡𝑖 ≤ 𝑡𝑒𝑖 ≤ 𝑖𝑛𝑓𝑡𝑖 ∀ 𝑖 ∈ 𝑇𝑎𝑟𝑒𝑎𝑠 (29)
𝑡𝑒𝑖 𝑡𝑒𝑖 ∈ ℤ+ (30)
𝑐𝑜𝑠𝑡𝑜𝑝𝑖 ∈ ℤ+ (31)
En el modelo de costos, la función objetivo (23) busca minimizar los costos del sistema
dándole una ponderación a los costos la holgura del sistema, los costos del tiempo de
procesamiento de las tareas y los costos asociados a incumplir con el tiempo de ciclo base de
la línea (solución original del tiempo de ciclo del modelo Mefi o Mufi). Las restricciones
(24), (25), (26), y (27) capturan la holgura del sistema cuando se tiene el número mínimo de
estaciones y cuando se llega al límite superior de estaciones. Estas restricciones, ya tienen en
cuenta la asignación de las tareas que es un parámetro para este modelo. La restricción (28)
define el comportamiento de la variable de costos de procesamiento de las tareas. En esta
restricción, se tiene la relación de la función de tiempo vs costos como factor para asignar un
costo al tiempo asignado a la tarea en el modelo, en caso de no existir un cambio en el tiempo
el costo asociado va a ser el original (costo superior), esta restricción se hizo con base al
trabajo de Hamta et al. ( 2011). Las restricciones (29), (30) y (31) definen las variables del
tiempo de proceso de las tareas y el costo por proceso de las mismas.
7. Metodología
Para este trabajo, se va proponer una metodología de trabajo entre el cálculo de los
parámetros, conjuntos y la solución de los modelos. La metodología del trabajo va a ser de
forma iterativa entre los modelos, por lo que cada uno de los modelos se va a alimentar de
los resultados de otro.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
30
Es importante hacer iterativo el proceso con el fin de explorar nuevas soluciones en la
iteración i de acuerdo a lo encontrado en la iteración i-1. El trabajo se va a dividir en dos
procesos iterativos diferentes. El primero va a ser para la solución del problema SALBP-E,
por lo que se va a iterar entre los modelos Mefi y Mcos. Cada uno de estos modelos se va a
alimentar de los resultados del otro. Por otra parte, el segundo proceso va a ser para resolver
el problema UALBP-E y se va a realizar el proceso iterativo entre los modelos Mufi y Mcos.
Es importante recordar, que para la iteración 0 del modelo Mefi o Mufi los parámetros y
conjuntos son calculados únicamente con la información de la instancia, pero desde la
iteración 1 el cálculo de estos valores iniciales va a ser una combinación entre la instancia y
el resultado del modelo Mcos.
Es muy importante recordar que este tipo de problema es NP-Hard por lo que el tiempo
computacional es muy alto en las instancias más grandes por lo que se propone un criterio de
parada de 900 segundos para cada una de las instancias.
Para explicar mejor lo anterior, la metodología se va a dividir en 5 fases:
Fase I. Cálculo de parámetros y conjuntos Mefi o Mufi.
Fase II. Implementación del modelo matemático Mefi o Mufi.
Fase III. Cálculo de parámetros y conjuntos Mcos.
Fase IV. Implementación del modelo matemático Mcos.
Fase V. Comparar con la Fase II (vuelve a la Fase I si hay un cambio en la solución del
modelo Mcos, termina de lo contrario)
7.1 Fase I
La primera fase del trabajo, es el cálculo de los parámetros y los conjuntos para los modelos
Mefi o Mufi. esta fase es muy importante ya que con estos cálculos se va a reducir la cantidad
de variables a crear en los modelos (Ver Tabla 1. Parámetros de los modelos y Tabla 2.
Conjuntos de los modelos).
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
31
En esta fase se definen y se calculan todos los parámetros y conjuntos por iteración, sin
embargo, existen diferencias en algunos parámetros en los modelos Mefi y Mufi que se
explicarán a continuación.
7.1.1 Fase I Mefi
Para esta fase, en la primera iteración el cálculo se va a realizar únicamente con los valores
obtenidos de la instancia (Parámetros 1, 2 y 6 - Conjunto 5). Con los valores de la instancia
se procede a calcular los 9 parámetros restantes y a definir los 8 conjuntos adicionales para
el modelo Mefi. Desde la iteración 2 el parámetro 2 cambia por el resultado del tiempo de
las tareas del modelo Mcos. Para el cálculo de los parámetros ver Tabla 1. Parámetros de los
modelos del 1 al 12 y para los conjuntos ver Tabla 2. Conjuntos de los modelos Conjuntos
del 1 al 9.
En esta fase, las modificaciones que se hicieron al trabajo propuesto por (Esmaeilbeigi &
Naderi, 2015) fueron en la definición de los conjuntos 8 y 9 y en el método de búsqueda que
se utiliza. El autor originalmente generaba los conjuntos en listas y el método de búsqueda
era exhaustivo. La propuesta de este trabajo fue generar los conjuntos como tuplas con el fin
de realizar una búsqueda denominada Sparse, donde se buscan solo los términos de las tuplas
y permite una búsqueda más rápida que la exhaustiva (“Tutorial: Modeling with the Gurobi
Python Interface - YouTube,” n.d.).
La velocidad de búsqueda en los conjuntos afecta el tiempo computacional de los modelos
propuestos por lo que fue importante hacer este cambio en el cálculo y búsqueda de los
parámetros y los conjuntos al momento de definirlos y al usarlos en la implementación de los
modelos.
Adicionalmente, se va a hacer uso del modelo SALBP-2 para el cálculo de los parámetros 8
y 9 ya que cada vez que se aumenten los tiempos de las tareas los tiempos de ciclo que son
parámetros del problemas se van a ajustar. Para más información del problema SALBP-2 ver
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
32
(Restrepo et al., 2008). Este modelo también va a tener el mismo criterio de parada de 900
segundos ya que también es un problema NP-Hard.
7.1.2 Fase I Mufi
Para el modelo Mufi en esta fase, la primera iteración se va a realizar únicamente con los
valores obtenidos de la instancia (Parámetros 1, 2 y 6 - Conjunto 5). Con los valores de la
instancia se procede a calcular los 14 parámetros restantes y a definir los 13 conjuntos
adicionales para el modelo Mufi. Desde la iteración 2, el parámetro 2 cambia por el resultado
del tiempo de las tareas del modelo Mcos. Es importante recordar que el modelo UALBP-E
es una extensión del modelo SALBP-E por lo que el modelo Mufi utiliza los mismos
conjuntos y parámetros que el modelo Mefi y se deben considerar los datos adicionales del
nuevo enfoque con el grafo fantasma. Para el cálculo de los parámetros ver Tabla 1 y para
el cálculo de los conjuntos ver la Tabla 2.
En esta fase, las modificaciones que se hicieron al trabajo propuesto por Esmaeilbeigi &
Naderi (2015) fueron en la definición de los conjuntos 8 y 9 como se explicó anteriormente
y se agregó el cálculo de los conjuntos 11 y 12 que representan la extensión al modelo en U.
En la Ilustración 6. Predecesores directos e indirectos en el grafo fantasma se muestra un
ejemplo de cómo se definieron los conjuntos de los predecesores directos e indirectos en el
grafo fantasma (conjunto 11).
Ilustración 6. Predecesores directos e indirectos en el grafo fantasma
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
33
Para definir los predecesores directos e indirectos, se proponen 3 reglas. La primera es para
los nodos finales (que no tienen otra conexiones salientes a nodos reales como el nodo K
fantasma) los cuales van a tener conexión con los nodos iníciales (que no tienen conexiones
entrantes de nodos fantasma como el nodo A real). i.e, El nodo final K (fantasma) es
predecesor al nodo inicial A (real). La segunda regla es para los nodos iniciales como el nodo
A fantasma (en caso de que exista más de una), los cuales van a tener como precedencias
directas e indirectas a todos los nodos con conexión hasta llegar a los nodos finales como el
K fantasma. La tercera regla, es para los nodos intermedios los cuales van a tener
precedencias únicamente hasta el nodo final fantasma (k fantasma).
Lo anterior se puede ver en la Ilustración 6. En rojo se presenta el ejemplo de la primera
regla, en verde el ejemplo de la segunda regla y la tercera regla se puede ver en amarillo en
donde un nodo intermedio solo tiene precedencias hasta el nodo final. Se definieron estas
reglas con el fin de reducir el número de variables del modelo al momento de calcular el
parámetro 19 que permiten saber cuáles son las estaciones más tempranas en las que se puede
realizar la tarea en el grafo fantasma.
Ilustración 7. Sucesores directos e indirectos en el grafo fantasma
Por otra parte, para definir el conjunto 12 se definieron dos reglas. La primera regla para
definir el conjunto de los sucesores directos e indirectos de las tareas, es que los nodos reales
que no tengan conexiones reales entrantes (línea continua) tienen como sucesores todos los
nodos fantasmas con conexiones. La segunda regla es que para todos los nodos intermedios
fantasmas, sus sucesores son todos los nodos con conexiones hasta llegar a un nodo final
fantasma.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
34
En la Ilustración 7 se muestra la representación de un ejemplo para el cálculo del conjunto
12. En esta gráfica, se puede ver en verde el ejemplo de la primera regla y en amarillo el
ejemplo de la segunda regla definida. Al igual que con los predecesores, se definieron estas
reglas con el fin de reducir el número de variables del modelo al momento de calcular el
parámetro 17 que permiten saber cuáles son las estaciones más tardías en las que se puede
realizar la tarea.
Adicionalmente, se va a hacer uso del modelo UALBP-2 para el cálculo de los parámetros 8
y 9 ya que cada vez que se aumenten los tiempos de las tareas los tiempos de ciclo que son
parámetros del problemas se van a ajustar. Para más información del problema UALBP-2
ver (Timothy L. Urban & Chiang, 2006)(T. Urban, 1998). Este modelo también va a tener el
mismo criterio de parada de 900 segundos ya que también es un problema NP-Hard.
7.2 Fase II
La fase dos consiste en la implementación de los modelos Mefi o Mufi. Esta implementación
se va a realizar para cada uno de los modelos por separado. Por lo anterior es importante
realizar la fase I de manera adecuada para cada modelo por separado.
Para el modelo Mefi los 12 parámetros y los 9 conjuntos permiten una implementación del
modelo Mefi que permita minimizar la holgura del sistema maximizando así la eficiencia del
mismo.
Para el modelo Mufi los 14 parámetros y los 13 conjuntos permiten una implementación del
modelo Mefi que permita minimizar la holgura del sistema maximizando así la eficiencia del
mismo. La cantidad de variables en este problema aumenta por el grafo fantasma, sin
embargo se logró una reducción a partir del cálculo de los parámetros y conjuntos explicados
en la fase I.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
35
7.3 Fase III
Esta fase no es muy compleja pero es necesaria para la implementación de la fase IV. En esta
fase se definen los conjuntos que se van a utilizar en el modelo de costos de acuerdo a los
resultados de los modelos Mefi y Mufi.
De acuerdo a los resultados de las asignaciones de las tareas a las estaciones obtenidas en los
modelos Mefi y Mufi se definen los conjuntos 15 y 16. Estos conjuntos son importantes ya
que el modelo Mcos va a utilizar una solución inicial (sea SALBP-E o UALBP-E).
Por otra parte, para el modelo de costos es importante el valor de la holgura que es uno de
los resultados de los modelos Mefi y Mufi, esto es relevante ya que este valor de holgura a
va a permitir tomar la decisión de la variación en los tiempos de las tareas (ver parámetro
19).
7.4 Fase IV
En esta fase se implementa el modelo de costos Mcos. Para esta fase es necesario la fase III
en la cual se calculan los parámetros y los conjuntos necesarios para la decisión del modelo.
El modelo Mcos busca reducir los costos de la línea (explicados en la sección 5) variando el
tiempo de las tareas entre un rango específico pero con la mayor eficiencia posible. El rango
en que varían los tiempos de las tareas son, el tiempo original de procesamiento ti (de las
instancias) y un tiempo superior el cual se propone en este modelo como ti + holgura
promedio del sistema (del modelo Mefi o Mufi). Lo anterior se hace bajo el supuesto que las
empresas tienen la posibilidad de aumentar el tiempo de las tareas y disminuir los costos
asociados al tiempo de procesamiento de estas.
Este modelo da como resultado los costos mínimos de acuerdo a una asignación fija, por lo
que es necesario comprobar si existe una mejor asignación con los nuevos tiempos de tareas
que el modelo Mcos genera. Esta comprobación se realiza mediante el recalculo de la
asignación de las tareas a las estaciones que maximicen la eficiencia del sistema.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
36
7.5 Fase V
La última fase de la metodología es hacer una comparación de los resultados obtenidos en la
Fase II y la Fase IV. En caso de que los costos obtenidos con la asignación de los modelos
Mefi o Mufi con el modelo Mcos sean diferentes se procede a hacer un proceso iterativo y
comenzar nuevamente con la fase I, lo que incluye nuevamente el cálculo de los parámetros.
Por el contrario si los resultados de costos de la Fase II y la Fase IV son los mismos se detiene
el proceso y se termina la metodología del trabajo. Esto equivale al criterio de parada puesto
que continuar iterando entre los modelos no va a mejorar los resultados.
8. Resultados Computacionales
En esta sección se evalúa el desempeño de los modelos matemáticos. Los modelos se han
codificado y compilado en Gurobi 6.5 con lenguaje Python API en un computador con
procesador Intel (R) Core (TM)i7-4702MQ 2.20 GHz 16 GB RAM.
Como se dijo anteriormente para los modelos 3 matemáticos, se van a utilizar las instancias
de la literatura recuperadas de http://alb.mansci.de.
En esta sección se va a realizar un análisis de los modelos Mefi y Mufi por separado con el
fin de compararlos con los resultados óptimos de la literatura. Adicionalmente, se van a
realizar las pruebas de la metodología propuesta para el modelo de costos con el fin de probar
la validez del trabajo iterativo que se propone.
8.1 Resultados SALBP-E Mefi
De las instancias obtenidas en la literatura, se tienen instancias de tamaño pequeño (menos
de 30 tareas), medio (entre 30 y 70 tareas) y grande (más de 70 tareas).
Inicialmente para el modelo SALBP-E se va a hacer una comparación con los resultados
óptimos obtenidos en las instancias. La idea de esto es probar si el modelo matemático llega
al óptimo en cada uno de los problemas que están propuestos en la literatura.
Adicionalmente, se va a hacer la comparación con el trabajo de (Esmaeilbeigi & Naderi,
2015) quien propuso 4 modelos diferentes para el SALBP-E que son comparables por la
función objetivo que trabajan (minimizar la holgura del sistema). La comparación se va a
realizar en tiempo computacional, nodos de búsqueda y valor del GAP obtenido por los
modelos propuestos en el trabajo de Esmaeilbeigi.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
37
Para la primera comparación con los resultados óptimos conocidos de las instancias se tienen los
siguientes resultados del modelo propuesto en este trabajo.
Tabla 4. Comparación de los resultados de la asignación del modelo Mefi con los resultados de las instancias
Mefi
Tamaño de la
instancia
NOMBRE DE LA
INSTANCIA # Tareas
# Estaciones
Tiempo de Ciclo (Seg)
Holgura
Cumple el valor
Optimo obtenido
en la literatura
Eficiencia (%)
Pequeña
Mertens 7 3 10 1 SI 96,55
Bowman 8 5 17 10 SI 86,67
Jaeschke 9 3 13 2 SI 94,59
Jackson 11 3 16 2 SI 95,65
Mansoor 11 3 62 1 SI 99,46
Mitchell 21 5 21 0 SI 100,00
Roszieg 25 3 42 1 SI 99,20
Heskiaoff 28 4 256 0 SI 100,00
Buxey 29 3 108 0 SI 100,00
Sawyer 30 3 108 0 SI 100,00
Mediana
Lutz1 32 4 3574 156 SI 98,90
Gunther 35 3 161 0 SI 100,00
Kilbridge 45 6 92 0 SI 100,00
Hahn 53 5 2823 89 SI 99,37
Warnecke 58 3 516 0 SI 100,00
Tonge 70 3 1170 0 SI 100,00
Grande
Wee-Mag 75 3 500 1 SI 99,93
Arcus1 83 4 18927 1 SI 100,00
Lutz2 89 3 162 1 SI 99,79
Lutz3 89 3 548 0 SI 100,00
Arcus2 111 3 50133 0 SI 100,00
Barthold 148 3 1878 0 SI 100,00
Barthol2 148 3 1412 2 NO 99,95
Scholl 297 3 23219 2 NO 99,99
En la tabla anterior se puede observar que para todas las instancias pequeñas y medianas el
modelo matemático propuesto llega al óptimo conocido para cada una de ellas. Por otra
parte, para las instancias grandes, no se alcanza el óptimo (GAP 100%) de las dos más
grandes, superior a 140 tareas. La tabla 4 presenta el número de estaciones, el tiempo de
ciclo, la holgura y la eficiencia puesto que son los valores que el modelo Mefi calcula al
minimizar la holgura del sistema. De estos resultados, se puede observar que para algunas de
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
38
las instancias no se obtiene una asignación con una eficiencia del 100%, por lo que esta es la
razón de proponer un modelo de costos que busque aumentar la eficiencia de la línea al tener
en cuenta que los tiempos de las tareas pueden ser variables.
Adicionalmente, la asignación realizada con el modelo Mefi es adecuada y se tiene la
posibilidad de implementar el modelo en ejemplos reales con el fin de optimizar la asignación
de las tareas maximizando la eficiencia de las líneas de producción.
Por otra parte, se realiza la comparación con el trabajo realizado por Esmaeilbeigi con el fin
de hacer una comparación del desempeño del modelo propuesto por el autor y el modelo que
se trabajó en este documento. Es importante recordar que el autor trabajo con 4 modelos para
la solución del problema. Tres de los modelos propuestos por el autor (FE1-FE2-FE3) los
utilizó para probar las instancias hasta 45 tareas. Para las demás instancias de tamaño
mediano y grande el autor utilizo los modelos (FE3-FE4). El autor hizo uso de varios modelos
con el fin de reducir el tiempo computacional agregando restricciones de enteros (FE2),
desigualdades asociadas a la holgura (FE3) y restricciones adicionales para reducir el número
de variables que crea el modelo para su solución (FE4).
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
39
Tabla 5. Comparación de los resultados computacionales del modelo Mefi con el autor Esmaeilbeigi. Instancias pequeñas y medianas
Tabla 6. Comparación de los resultados computacionales del modelo Mefi con el autor Esmaeilbeigi. Instancias medianas y grandes
Tamaño de
la instanciaINSTANCIA # Tareas
Tiempo
Computacional
(segundos)
GAP# Nodos
Explorados
Tiempo
Computacional
(segundos)
GAP# Nodos
Explorados
Tiempo
Computacional
(segundos)
# Nodos
Explorados
Tiempo
Computacional
(segundos)
# Nodos
Explorados
Mertens 7 0,023 0% 1 0,1 0% 103 0,1 68 0.1 68
Bowman 8 0,016 0% 0 0,1 0% 13 0,1 14 0.1 5
Jaeschke 9 0,032 0% 40 0,1 0% 100 0,1 69 0.2 23
Jackson 11 0,083 0% 438 0,2 0% 460 0,2 270 0.1 32
Mansoor 11 0,049 0% 54 0,1 0% 107 0,1 89 0.1 15
Mitchell 21 0,11 0% 682 0,4 0% 381 0,8 774 0.4 100
Roszieg 25 0,28 0% 187 3,5 0% 3850 3,6 4470 0.8 485
Heskiaoff 28 0,1 0% 0 289,2 0% 696182 27,7 55220 17.4 20775
Buxey 29 0,25 0% 1290 207,7 0% 169244 45,9 32853 7.8 4883
Sawyer 30 0,18 0% 455 714,6 25% 528396 44,7 44816 34 31361
Lutz1 32 7,38 0% 10291 57,6 0% 27324 46,1 23975 8,8 5550
Gunther 35 0,09 0% 0 301,8 0% 132851 67,6 35008 19,3 8185
Kilbridge 45 3,47 0% 7559 647,9 33% 861801 5 3091 2,7 1025
Promedio 0,93 0,00 1615,15 171,02 4,5% 186216,31 18,62 15439,77 16,20 5577,46
Mefi FE1. FE2. FE3.
Pequeña
Mediana
Tamaño de
la instanciaINSTANCIA # Tareas
Tiempo
Computacional
(segundos)
GAP# Nodos
Explorados
Tiempo
Computacional
(segundos)
GAP# Nodos
Explorados
Tiempo
Computacional
(segundos)
GAP# Nodos
Explorados
Hahn 53 0,98 0% 1150 1,5 0% 531 1,5 0% 379
Warnecke 58 0,182 0% 0 1380 69% 79959 1157,8 56% 200129
Tonge 70 1,27 0% 1105 1781,1 85% 553871 1650,6 84% 533367
Wee-Mag 75 48,2 0% 9694 1557,7 79% 135882 1444,3 71% 111403
Arcus1 83 144,38 0% 281831 1679,7 54% 275812 1663,9 53% 447361
Lutz2 89 103,007 0% 12243 1488,2 66% 39710 1438,9 61% 140658
Lutz3 89 0,144 0% 0 833,5 14% 81564 386,1 0% 67547
Arcus2 111 23,93 0% 4060
Barthold 148 0,22 0% 0
Promedio 35,81 0,00 34453,67 1245,96 52% 166761,29 1106,16 46% 214406,29
FE3. FE4.
Mediana
Grande
Mefi
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
40
De las tablas anteriores, se puede observar que el modelo Mefi trabajado en este documento
obtiene mejores resultados computacionales para los problemas SALBP-E que los reportados
en el trabajo de Esmaeilbeigi & Nader (2015). En todas las instancias probadas, se puede
observar que el tiempo computacional es menor en promedio un 96%, por otra parte el
número de nodos explorados en promedio es menor en un 85%. En la tabla 6, se puede ver
que el modelo propuesto en este trabajo llega al óptimo, mientras que el autor reporta un
GAP de más del 60% en las instancias medianas y grandes, adicionalmente en este trabajo
se presentan resultados de las instancias grandes (111-148 tareas) de la literatura. No se pudo
obtener resultados de la instancia de 297 tareas por el tamaño del problema y el tiempo
computacional asociado a este.
Esta comparación se realiza debido a que el trabajo propuesto por el autor buscaba reducir
el tiempo computacional y la cantidad de nodos a explorar con sus modelos propuestos. En
este trabajo, la modificación hecha para el cálculo de los parámetros y el tipo de búsqueda
realizada permitió una mejora en tiempo computacional. Sin embargo, es importante aclarar
que la mejora en los tiempos y en la búsqueda no se hizo únicamente con el tipo de búsqueda
utilizada, el autor utilizó Cplex para correr los modelos y en este trabajo se utilizó Gurobi
por lo que existe una diferencia de 1,6 veces en la velocidad de solución de los problemas
debido a que el optimizador utilizado en este trabajo es mejor en términos de tiempo
computacional y búsqueda (“Gurobi 5.1 Performance Benchmarks vs. CPLEX and XPRESS
- Benchmarks 5.1b.pdf,” n.d.). Por otra parte, se tiene una diferencia en el equipo utilizado
por el autor y este trabajo ya que hay una diferencia en la capacidad de la memoria (4 GB
RAM Vs. 16 GB RAM) y en el procesador utilizado (Single-Core 2,5 GHz Vs. I7 2,2 GHz)
lo que también permite explicar la diferencia en el tiempo computacional de este trabajo.
De lo anterior, se puede observar que el modelo básico trabajado en este documento con los
cambios en el cálculo de algunos de los parámetros permite obtener resultados óptimos en
tiempos computacionales razonables hasta las instancias de 148 tareas por lo que es un
modelo apropiado para utilizar.
8.2 Resultados UALBP-E Mufi
De la implementación del modelo de programación entera mixta propuesta en este trabajo
para el problema de balanceo de línea en U se obtuvieron los siguientes resultados.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
41
Tabla 7. Resultados computacionales Modelo Mufi
Ilustración 8. Número de estaciones en las soluciones de los modelos Mefi y Mufi
Tamaño de
la instancia
NOMBRE
DE LA
INSTANCIA
# Tareas
Tiempo
Computaci
onal
(segundos)
# EstacionesTiempo de
Ciclo (Seg)Holgura
Eficiencia
(%)
Mertens 7 0,02 3 10 1 96,55
Bowman 8 0,02 5 17 10 86,67
Jaeschke 9 0,18 3 13 2 94,59
Jackson 11 1,79 3 16 2 95,65
Mansoor 11 0,08 3 62 1 99,46
Mitchell 21 0,17 3 35 0 100
Roszieg 25 1,11 5 25 0 100
Heskiaoff 28 1,46 4 256 0 100
Buxey 29 0,26 3 108 0 100
Sawyer 30 0,03 3 108 0 100
Lutz1 32 87,01 3 4714 2 99,99
Gunther 35 0,04 3 161 0 100,00
Kilbridge 45 0,32 4 138 0 100,00
Hahn 53 33,23 3 4676 2 99,99
Warnecke 58 1,31 4 387 0 100,00
Tonge 70 1,71 3 1170 0 100,00
Wee-Mag 75
Arcus1 83
Lutz2 89 35,27 5 97 0 100
Lutz3 89 56,21 3 548 0 100
Arcus2 111 7,89 3 50133 0 100
Barthold 148 68,68 3 1878 0 100
Barthol2 148
Scholl 297
Mufi
Pequeña
Mediana
Grande
2
3
4
5
6
Mer
ten
s
Bo
wm
an
Jaes
chke
Jack
son
Man
soo
r
Mit
chel
l
Ro
szie
g
Hes
kiao
ff
Bu
xey
Saw
yer
Lutz
1
Gu
nth
er
Kilb
rid
ge
Hah
n
War
ne
cke
Ton
ge
Wee
-Mag
Arc
us1
Lutz
2
Lutz
3
Arc
us2
Bar
tho
ld
Bar
tho
l2
Sch
oll
Estaciones
Mefi Mufi
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
42
De la tabla anterior se puede observar que el modelo en U propuesto como extensión al
balanceo simple genera soluciones para casi todas las instancias. En las instancias más
grandes por el tamaño del problema y por la cantidad de variables que se crean en el modelo
no se logra obtener un resultado, pero este modelo permite obtener buenos resultados incluso
en instancias de 148 tareas por lo que podría ser utilizado en ejemplos reales de un tamaño
mediano y pequeño.
El problema UALBP-E casi no ha sido estudiado en la literatura ya que se centran
principalmente en la solución de los problemas para minimizar el tiempo de ciclo (UALBP-
2) y el cálculo del número de estaciones (UALBP-1) por lo que no se tiene un Benchmark
adecuado para realizar una comparación. Sin embargo, al utilizar las instancias de la literatura
se puede hacer un símil entre los resultados del modelo simple SALBP-E (Mefi) y la
extensión propuesta UABLP-E (Mufi) en términos de tiempo computacional y solución
(asignación de estaciones, tiempo de ciclo y eficiencia del sistema). Para poder hacer esta
comparación, primero se realizó manualmente la prueba de las relaciones de precedencia ya
que no se tiene una base comparativa de las soluciones. De la revisión de las restricciones de
precedencia en la configuración en U de las tareas para todas las instancias probadas, se
encontró que cada una cumplía sus precedencias, por lo que se puede decir que la solución
es factible. Por otra parte se obtuvo un GAP del 0% para todas las instancias por lo que el
modelo encontró el óptimo para el problema trabajado en todas las instancias con resultados.
En la tabla 7 se pueden observar unos cambios entre la solución del modelo Mefi (tablas 4-5
-6) y el modelo Mufi. La primera diferencia radica en los tiempos computacionales de los
modelos, puesto que al tener el grafo fantasma en el modelo en U la cantidad de restricciones
y variables de cada uno de los modelos aumenta y el tiempo computacional aumenta de la
misma forma, pero con el trabajo previo del cálculo de los parámetros la diferencia no es tan
grande. Al trabajar el modelo básico propuesto por Urban y tener en cuenta el grafo fantasma
la cantidad de variables aumentaba al doble (T. Urban, 1998), lo que no sucede en este caso,
ya que el modelo Mufi crea variables de acuerdo a los resultados de los parámetros 16 y 17.
Lo anterior se puede observar en la tabla 8 donde se presentan los resultados de la creación
de variables de los modelos Mefi y Mufi. La tabla 8 presenta que la cantidad de variables
creadas para la solución del modelo en U ya no es el doble al modelo simple. Con el
tratamiento de los parámetros se logró en promedio la creación de 1,88 variables y 1,84
restricciones al modelo simple sin afectar la calidad de la solución en U.
En la tabla 7 (en verde) y en la ilustración 8, se puede observar que la solución del modelo
en U genera diferencias en la cantidad de estaciones y tiempo de ciclo en algunas de las
instancias. Lo anterior se da debido a la mejora obtenida en la holgura (color azul) y la
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
43
eficiencia de las instancias (amarillo) ya que el modelo Mufi trata de maximizar por defecto
la eficiencia en el sistema (Toksari et al., 2008) y esa mejora se logra con la asignación de
las tareas en U aumentando en algunos casos la cantidad de estaciones utilizadas.
Tabla 8. Comparación del número de variables y restricciones de los modelos
Mefi Mufi
Tamaño de la
instancia
NOMBRE DE LA
INSTANCIA # Tareas # Variables
# Restricciones
# Variables #
Restricciones
Pequeña
Mertens 7 39 25 67 42
Bowman 8 25 25 51 72
Jaeschke 9 65 40 112 68
Jackson 11 83 44 146 74
Mansoor 11 58 34 93 56
Mitchell 21 183 76 351 130
Roszieg 25 244 89 466 157
Heskiaoff 28 292 99 563 168
Buxey 29 387 109 731 188
Sawyer 30 402 106 765 194
Mediana
Lutz1 32 336 106 644 108
Gunther 35 456 124 885 215
Kilbridge 45 495 143 963 252
Hahn 53 430 163 733 263
Warnecke 58 1761 240 3425 440
Tonge 70 1600 240 3133 446
Grande
Wee-Mag 75
Arcus1 83
Lutz2 89 4382 395 8662 703
Lutz3 89 2011 291 3975 495
Arcus2 111 2987 387 5939 660
Barthold 148 2245 375 4373 1378
De los resultados de este modelos se puede ver que en algunos de ellos existe una mejora en
eficiencia generando en algunos casos (depende de la instancia o el problema) la creación
de estaciones adicionales. Sin embargo, el obtener una mayor eficiencia podría ser benéfico
para algunas empresas por lo que el modelo propuesto es adecuado y se podría utilizar ya
que cumple los requerimientos de factibilidad y genera un resultado óptimo.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
44
8.3 Resultados de la Metodología propuesta con el modelo de costos Mcos
Para la metodología propuesta, se va a realizar una comparación de los resultados de los modelos
Mefi y Mufi con la solución del modelo de costos para cada una de las instancias. Inicialmente, se
va realizar una prueba con costos propuestos para probar si existe una mejora asociada a la
eficiencia y a los costos de todo el sistema.
Para esta prueba se va utilizar un costo de holgura de 848 (parametrizable), un costo mínimo para
realizar una tarea de 5000 y un máximo de 14000. Sin embargo, se va a realizar un análisis de
sensibilidad para estos costos.
Tabla 9. Comparación modelo Mefi con el modelo de costos Mcos
Tabla 10. Comparación modelo Mufi con el modelo de costos Mcos
Las tablas 9 y 10 muestran los resultados de la metodología propuesta en este trabajo con los
parámetros de costos mencionados anteriormente. En las tablas, se puede observar un
resumen de las instancias en las que aplicando la metodología se obtiene un mejor resultado
en términos de costos y de eficiencia en el sistema. Es importante recordar, que al
implementar los modelos básicos Mefi y Mufi, algunos de los resultados de las instancias ya
llegaban a una eficiencia del 100 % (12 instancias con el modelo Mefi y 13 instancias con
el modelo Mufi de un total de 22 instancias) por lo que la metodología no genera mejores
resultados cuando se tiene una eficiencia del 100%.
La tabla 9 muestra los resultados de la metodología en relación al modelo Mefi y la tabla 10
respecto al modelo Mufi. Todos los resultados obtenidos se presentan en las instancias que
tenían holgura. Adicionalmente, se puede observar que entre mayor es la holgura la cantidad
de iteraciones que se necesitan para tener el mínimo costo con la mayor eficiencia aumenta.
Se puede observar, que el trabajo propuesto genera mejores resultados en la configuración
en U en las instancias pequeñas lo cual muestra que la propuesta puede ser implementada.
Tamaño de
la instanciaINSTANCIA # Tareas # Estaciones
Tiempo de
Ciclo (Seg)Holgura Costo Total
Eficiencia
(%)
#
Iteraciones# Estaciones
Tiempo de
CicloHolgura Costo Final
Eficiencia
Final (%)
Pequeña Bowman 8 5 17 10 120480 86,67 5 5 22 0,00 118360 100,00
Mediana Lutz1 32 4 3574 156 580288 98,90 1 4 3.574 0,00 411964 100,00
Mediana Hahn 53 5 2823 89 817472 99,37 2 5 2.898 0,00 683957 100,00
Mefi Mcos
Tamaño de
la instanciaINSTANCIA # Tareas # Estaciones
Tiempo de
Ciclo (Seg)Holgura Costo Total
Eficiencia
(%)
#
Iteraciones# Estaciones
Tiempo de
CicloHolgura Costo Final
Eficiencia
Final (%)
Mertens 7 3 10 1 98.848 96,55 0 3 10 0 89.000 100
Bowman 8 5 17 10 120.480 86,67 2 4 25 0 122.176 100
Jaeschke 9 3 13 2 127.696 94,59 1 3 13 0 126.000 100
Jackson 11 3 16 2 155.696 95,65 1 3 16 0 154.000 100
Mansoor 11 3 62 1 154.848 99,46 0 3 62 0 145.000 100
Lutz1 32 3 4714 2 449.696 99,99 1 3 4714 0 448.000 100
Hahn 53 3 4676 2 743.696 99,99 1 3 4676 0 742.000 100 Mediana
Mufi Mcos
Pequeña
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
45
Variación de los costos Metodología Mefi-Mcos
Para la metodología se hizo un análisis de los costos de holgura en el modelo y los
costos de procesamiento de las tareas. Para lo anterior, se probaron los siguientes
valores en el costo de holgura (0, 500, 848, 100 y 2000) ya que es un parámetro
propuesto para este trabajo y que puede cambiar dependiendo del sistema que se esté
estudiando. Por otra parte, para el costo de las tareas se utilizaron los siguientes
rangos (100-200, 1000-5000, 5000-14000), estos rangos representan el costo de las
tareas por unidad de tiempo en variación permitida para cada tarea (Ver sección 5.2).
Las pruebas se hicieron para la instancia Hahn de 53 tareas. La prueba se realizó en
esta instancia porque es la instancia donde se puede observar mejor el
comportamiento de la metodología debido a la holgura inicial al correr el modelo
Mefi. De las pruebas realizadas para la instancia, se obtuvo el resultado de aumentar
la eficiencia del sistema a un 100%, sin embargo, se tuvieron algunos cambios en los
resultados por el cambio del parámetro de los costos. Los cambios observados se
presentaron en el tiempo de proceso de todas las tareas y la cantidad de iteraciones
realizadas por la metodología. Lo anterior se puede observar en las ilustraciones 9 y
10.
Ilustración 9. Iteraciones por instancia según el costo de holgura Metodología Mefi
En la ilustración 9 se puede observar el cambio en la cantidad de iteraciones de la
metodología con el cambio de los costos de la holgura. La grafica presenta que a
menor costo de holgura mayor es la cantidad de las iteraciones necesarias para tener
0
2
4
6
8
10
12
14
16
CostoHolgura 0
CostoHolgura 500
CostoHolgura 848
CostoHolgura 1000
CostoHolgura 2000
# iteraciones
Variación de los costos de Holgura del sistema
Hahn 100-2000
Hahn 1000-5000
Hahn 5000-14000
Rangos del costo de las
operaciones
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
46
una eficiencia del 100%, sin embargo, la cantidad de iteraciones no cambia de forma
significativa al variar los costos de operación de las tareas, por lo que se puede decir
que para cualquier configuración de costos la metodología busca el mejor resultado
sin aumentar los cálculos. A su vez, En el modelo de costos se puede observar que a
menor costo de holgura el modelo buscará aumentar el tiempo de proceso de las tareas
para minimizar los costos del sistema (no tiene gran influencia el parámetro del costo
de las operaciones).
Ilustración 10. Cambio porcentual en el tiempo total de las operaciones según el costo de holgura Metodología Mefi
En la ilustración 10 se muestra el aumento porcentual en el tiempo total de las
operaciones del sistema en relación a la solución original obtenida con el modelo
Mefi. De la gráfica, se puede observar que entre menor sea el costo de holgura, el
tiempo de proceso de las tareas va a aumentar en mayor proporción. De lo anterior,
se puede ver que la variación de los costos de las tareas no presenta un efecto
significativo en la variación del tiempo de las operaciones.
Variación de los costos Metodología Mufi-Mcos
Para la metodología con relación a la configuración de la línea en U, se hicieron las
mismas pruebas para la instancia Hahn, sin embargo en esta configuración no se
observa mejoras aparentes con la metodología ya que al aplicar el modelo Mufi la
holgura del sistema es pequeña (holgura de 2). Esto se puede observar en las
ilustraciones 11 y 12.
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
CostoHolgura 0
CostoHolgura
500
CostoHolgura
848
CostoHolgura
1000
CostoHolgura
2000
Cambio porcentual en el tiempo total de las
operaciones
Variación de los costos de Holgura del sistema
Hahn 1000-5000
Hahn 5000-14000
Hahn 100-2000
Rangos del costo de las
operaciones
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
47
Ilustración 11.Iteraciones por instancia según el costo de holgura Metodología Mufi
En la ilustración 11, se puede ver que no hay ningún cambio en la cantidad de
iteraciones de la metodología para ninguna de las configuraciones de costos. La
metodología se implementa y se consigue una eficiencia del 100%, pero no es
necesario hacer más cálculos ya que el resultado del modelo Mufi ya está muy cerca
de una eficiencia del 100%.
Ilustración 12. Cambio porcentual en el tiempo total de las operaciones según el costo de holgura Metodología Mefi
De la ilustración 12, se puede observar que no existe un cambio evidente en el
aumento de los tiempos de las tareas. Lo anterior se presenta debido a que el tiempo
0
1
2
3
4
5
CostoHolgura 0
CostoHolgura 500
CostoHolgura 848
CostoHolgura 1000
CostoHolgura 2000
# iteraciones
Variación de los costos de Holgura del sistema
Hahn 100-2000
Hahn 1000-5000
Hahn 5000-14000
0
0,0001
0,0002
0,0003
0,0004
0,0005
0,0006
0,0007
0,0008
0,0009
0,001
CostoHolgura 0
CostoHolgura
500
CostoHolgura
848
CostoHolgura
1000
CostoHolgura
2000
Cambio porcentual en el tiempo total de las
operaciones
Variación de los costos de Holgura del sistema
Hahn 1000-5000
Hahn 5000-14000
Hahn 100-2000
Rangos del costo de las
operaciones
Rangos del costo de las
operaciones
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
48
de holgura del sistema obtenido originalmente con el modelo Mufi es pequeño. Existe
una variación en los tiempos y se obtienen mejores costos con la metodología y
debido a la configuración en U no se presenta una variación en los tiempos de las
tareas y el tiempo de ciclo (Ver Tabla 10) tan grande como ocurre al utilizar la
metodología con el modelo Mefi.
9. Conclusiones y trabajo futuro
En este trabajo, se presentó un modelo matemático entero mixto para la el problema de
balanceo de líneas en U (UALBP-E), que busca maximizar la eficiencia del sistema como
extensión al modelo simple (SALBP-E) trabajado por Esmaeilbeigi y presentado en este
trabajo con modificaciones en el cálculo de algunos parámetros con los que se mejoraron los
tiempos computacionales del modelo original. Adicionalmente, se propuso un modelo de
costos que tiene en cuenta costo de los procesos de las operaciones, el costo de holgura del
sistema y un costo asociado al tiempo de ciclo deseado por el sistema que busca maximizar
la eficiencia del sistema variando los tiempos de trabajo de las tareas.
Con los tres modelos desarrollados, se propuso una metodología para la solución de los
modelos de balanceo de línea y costos, con el fin de buscar una mejor configuración de los
sistemas que permitieran disminuir los costos totales del sistema y maximizar a su vez la
eficiencia del sistema.
Para el modelo simple de balanceo de línea (Mefi), se propusieron cambios en el cálculo de
los parámetros 12 y 13 (en el tipo de búsqueda utilizada), generando como resultado una
mejora en el tiempo computacional (96%), nodos explorados (86%) y GAP (en las instancias
grandes se logró el óptimo) en comparación con el trabajo propuesto por Esmaeilbeigi.
En la implementación del modelo de línea en U (Mufi), se pudo observar una mejora en la
eficiencia de los sistemas en comparación a los resultados obtenidos en el modelo Mefi. La
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
49
mejora en la eficiencia es el resultado de la configuración en U y en el cambio que se presentó
en algunas instancias por la cantidad de estaciones a utilizar (disminuyeron).
Para el modelo Mufi, se realizó la extensión al modelo simple y se propusieron 3 reglas para
el cálculo de los parámetros 14 y 15, con lo que se logró una disminución en la creación de
variables y restricciones. Esta comparación se pudo realizar ya que en los modelos originales
de líneas en U (Urban, 1998) la creación de variables y restricciones de los modelos en U
eran del doble a la de los modelos simples, en este trabajo se logró disminuir en promedio a
1,88 variables y a 1,84 restricciones lo que reduce el tiempo computacional del modelo
propuesto. Por otra parte se obtuvo resultados incluso en las instancias de más de 70 tareas
por lo que es un modelo apropiado para ser utilizado.
Para los modelos Mefi y Mufi las pruebas se realizaron para 22 instancias y se encontraron
los óptimos para 20, las 2 restantes son instancias grandes mayores a 100 tareas.
La metodología propuesta, utiliza los modelos Mefi-Mcos y Mufi-Mcos para solucionar los
problemas de balanceo simple y en U con un enfoque de costos asociado al tiempo de trabajo
de las tareas. Para cada problema, se utilizó la metodología iterando entre los modelos
propuestos con el fin de obtener la mejor configuración de costos y eficiencia al variar los
tiempos de las tareas. Para los dos tipos de problemas, se encontraron nuevas asignaciones
para las instancias que permiten mejorar los costos del sistema y la eficiencia del mismo. Se
obtuvo una mejora mayor en el balanceo simple debido a que tiene una mayor oportunidad
de mejora que el balanceo en U (por defecto maximiza la eficiencia del sistema).
Para futuras investigaciones, se recomienda la prueba de la metodología en sistemas reales
en los que se pueda estimar de manera apropiada los costos de holgura de los sistemas, los
costos de operación de las tareas y los rangos de variación de los tiempos de las operaciones
que en este trabajo fueron propuestos. Por otra parte se puede generar un método alternativo
para la solución de las instancias más grandes,
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
50
10. Bibliografía
Aǧpak, K., & Gökçen, H. (2005). Assembly line balancing: Two resource constrained cases. International Journal of Production Economics, 96(1), 129–140. http://doi.org/10.1016/j.ijpe.2004.03.008
Amen, M. (2000). Heuristic methods for cost-oriented assembly line balancing: A survey. International Journal of Production Economics, 68(1), 1–14. http://doi.org/10.1016/S0925-5273(99)00095-X
Amen, M. (2006). Cost-oriented assembly line balancing: Model formulations, solution difficulty, upper and lower bounds. European Journal of Operational Research, 168(3), 747–770. http://doi.org/10.1016/j.ejor.2004.07.026
Baybars, I. (1986). A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem. Management Science, 32(8), 909–
932. http://doi.org/10.1287/mnsc.32.8.909
Becker, C., & Scholl, A. (2006). A survey on problems and methods in generalized assembly line balancing. European Journal of Operational Research, 168(3), 694–715. http://doi.org/10.1016/j.ejor.2004.07.023
Betancourt, L. C., & Moreno, R. P. (2004). Generación de secuencias de montaje y equilibrado de líneas.
Boysen, N., Fliedner, M., & Scholl, A. (2007). A classification of assembly line balancing problems. European Journal of Operational
Research, 183(2), 674–693. http://doi.org/10.1016/j.ejor.2006.10.010
Burns, N., & Tou, K. (1989). Book Reviews. International Journal Of Production Research, 36(3), x.
http://doi.org/10.1080/14616700220145650
Cakir, B., Altiparmak, F., & Dengiz, B. (2011). Multi-objective optimization of a stochastic assembly line balancing: A hybrid simulated
annealing algorithm. Computers & Industrial Engineering, 60(3), 376–384. http://doi.org/10.1016/j.cie.2010.08.013
Chong, K. E., Omar, M. K., & Bakar, N. A. (2008). Solving Assembly Line Balancing Problem using Genetic Algorithm with Heuristics-
Treated Initial Population. Engineering, II, 1–5.
Erel, E., & Gokcen, H. (1999). Shortest-route formulation of mixed-model assembly line balancing problem. European Journal of
Operational Research, 116(1), 194–204. http://doi.org/10.1016/S0377-2217(98)00115-5
Esmaeilbeigi, R., & Naderi, B. (2015). The type E simple assembly line balancing problem : A mixed integer linear programming formulation. Computers & Operations Research, 64, 1–22.
Fattahi, A., & Turkay, M. (2015). On the MILP model for the U-shaped assembly line balancing problems. European Journal of Operational Research, 242(1), 343–346. http://doi.org/10.1016/j.ejor.2014.10.036
Ghosh, S., & Gagnon, R. (1989). A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems. International Journal of Production Research, 27(4), 637.
Gökçen, H., & Aǧpak, K. (2006). A goal programming approach to simple U-line balancing problem. European Journal of Operational Research, 171(2), 577–585. http://doi.org/10.1016/j.ejor.2004.09.021
Graves, S. C., & Lamar, B. W. (1983). An Integer Programming Procedure for Assembly System Design Problems. Operations Research, 31(3), 522–545. http://doi.org/10.1287/opre.31.3.522
Gurobi 5.1 Performance Benchmarks vs. CPLEX and XPRESS - Benchmarks 5.1b.pdf. (n.d.). Retrieved November 8, 2015, from http://www.sat-ag.com/Benchmarks 5.1b.pdf
Hamta, N., Fatemi Ghomi, S. M. T., Jolai, F., & Bahalke, U. (2011). Bi-criteria assembly line balancing by considering flexible operation times. Applied Mathematical Modelling, 35(12), 5592–5608. http://doi.org/10.1016/j.apm.2011.05.016
Kriengkorakot, N., & Pianthong, N. (2007). The U-line Assembly Line Balancing. KKKU Enginnering Journal, 34(June), 267–274.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
51
Kucukkoc, I., & Zhang, D. Z. (2015). Type-E parallel two-sided assembly line balancing problem: Mathematical model and ant colony
optimisation based approach with optimised parameters. Computers & Industrial Engineering, 84, 56–69.
http://doi.org/10.1016/j.cie.2014.12.037
Manavizadeh, N., Hosseini, N. S., Rabbani, M., & Jolai, F. (2013). A Simulated Annealing algorithm for a mixed model assembly U-line
balancing type-I problem considering human efficiency and Just-In-Time approach. Computers and Industrial Engineering, 64(2), 669–685. http://doi.org/10.1016/j.cie.2012.11.010
Miltenburg, G., & Winjngaard, J. (2001). The U-Line Balancing Problem. Issn: 00178012, Volume: 65(Issue:), Pages: 43–59.
Miltenburg, J. (2001). U-shaped production lines : A review of theory and practice. Int. J. Production Economics, 70(September 1999),
201–214. http://doi.org/10.1016/S0925-5273(00)00064-5
Pinto, P. a, Dannenbring, D. G., & Khumawala, B. M. (1983). Assembly Line Balancing With Processing Alternatives: an Application.
Management Science, 29(7), 817–830. http://doi.org/10.1287/mnsc.29.7.817
Plans, J., & Corominas, a. (1999). Modelling and solving the SALBP-E problem. Proceedings of the 1999 IEEE International
Symposium on Assembly and Task Planning, (July), 356–360.
Restrepo, J., P, M., & Cruz, E. (2008). Assembly balancing line problem SALBP-1 and SALBP-2 : a case of study. Scientia Et Technica,
(40), 105–110.
Scholl, A., & Becker, C. (2005). A note on “an exact method for cost-oriented assembly line balancing.” International Journal of
Production Economics, 97(3), 343–352. http://doi.org/10.1016/j.ijpe.2004.09.009
Scholl, A., & Becker, C. (2006). State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European
Journal of Operational Research, 168(3), 666–693. http://doi.org/10.1016/j.ejor.2004.07.022
Scholl, A., Boysen, N., & Fliedner, M. (2013). The assembly line balancing and scheduling problem with sequence-dependent setup
times: Problem extension, model formulation and efficient heuristics. OR Spectrum, 35(1), 291–320. http://doi.org/10.1007/s00291-011-0265-0
Sparling, D. (1998). Balancing just-in-time production units: The N U-line balancing problem. Infor, 36(4), 215–237. Retrieved from http://eserv.uum.edu.my/login?url=http://search.ebscohost.com/login.aspx?direct=true&db=bth&AN=1599606&site=ehost-
live&scope=site
Toksari, M. D., Işleyen, S. K., Güner, E., & Baykoç, Ö. F. (2008). Simple and U-type assembly line balancing problems with a learning
effect. Applied Mathematical Modelling, 32(12), 2954–2961. http://doi.org/10.1016/j.apm.2007.10.007
Tutorial: Modeling with the Gurobi Python Interface - YouTube. (n.d.). Retrieved November 1, 2015, from
https://www.youtube.com/watch?v=aKsfqB-ONfk
Urban, T. (1998). Optimal Balancing of U-Shaped Assembly Lines. Management Science, 44(5), 4.
Urban, T. L. (1998). Note. Optimal balancing of U-shaped assembly lines. Management Science, 44(5), 738–741.
Urban, T. L., & Chiang, W. C. (2006). An optimal piecewise-linear program for the U-line balancing problem with stochastic task times.
European Journal of Operational Research, 168(3), 771–782. http://doi.org/10.1016/j.ejor.2004.07.027
Wei, N.-C., & Chao, I.-M. (2011). A solution procedure for type E simple assembly line balancing problem. Computers & Industrial
Engineering, 61(3), 824–830. http://doi.org/10.1016/j.cie.2011.05.015
Yolmeh, A., & Kianfar, F. (2012). An efficient hybrid genetic algorithm to solve assembly line balancing problem with sequence-
dependent setup times. Computers & Industrial Engineering, 62(4), 936–945. http://doi.org/10.1016/j.cie.2011.12.017
Ze-qiang, Z., Tang, C. W., & Bin, L. Z. (2007). Ant Algorithm with Summation Rules for Assembly Line Balancing Problem, (2006),
369–374.
FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL SEMESTRE 2015-20
52
Zhang, W., Xu, W., & Gen, M. (2014). Hybrid Multiobjective Evolutionary Algorithm for Assembly Line Balancing Problem with
Stochastic Processing Time. Procedia Computer Science, 36(3), 587–592. http://doi.org/10.1016/j.procs.2014.09.058