JOMI: Algoritmo heurístico tipo greedy para la solución de los problemas de líneas de ensamble J. Burgos-Meneses, L. Garzón-Aguirre y J. López-Pereira

Organización y dirección de empresas Organización de la producción

JOMI: ALGORITMO HEURÍSTICO TIPO GREEDY PARA LA SOLUCIÓN DE LOS PROBLEMAS DE LÍNEAS DE ENSAMBLE Jorge Burgos-Meneses, Joyce Michelle Burgos-Meneses, Luis Garzón-Aguirre y Jorge López-Pereira Universidad de Córdoba, Facultad de Ingenierías, Departamento de Ingeniería Industrial Cra 10wa # 14-83 Montería- Córdoba- Colombia. Tel. +3145059685. [email protected] Recibido: 22-ene-2013 -- Aceptado: 10-jul-2013 - DOI: http://dx.doi.org/10.6036/MN5714

JOMI: HEURISTIC ALGORITHM TYPE GREEDY TO SOLVE ASSEMBLY BALANCING PROBLEMS ABSTRACT:

RESUMEN:

This paper focus in the description and evaluation of a new Greedy heuristic to solve assembly line balancing problems type-I (SALBPs-1),which is based in sequence of activities and their operation time to have an approximation more adequate of work stations. Here we show a comparative evaluation of this heuristic with others 14 of same type, among these positional weight, biggest number of successor tasks, longest operation time and biggest number of successor immediate tasks. We used 269problems for the comparative evaluation, where each heuristic was codified in software MATLAB 2009b. Theresults show us that the JOMI heuristic generates very good solutions with the best average ofefficiency 90,24%; showing so other simple and feasible way to solve balancing line problems.

Este artículose basa en la descripcióny evaluación deuna nueva heurística Greedy para resolver problemas de equilibrado de líneas de ensamble tipo-1 (SALBPs-1),la cual se fundamenta en la sucesión de actividades y el tiempo de operación de estas para llegar a tener una aproximación más adecuada de las estaciones de trabajo. Aquí se muestra una evaluación comparativa entre esta heurística y otras 14 de este tipo, entre las cuales se encuentra el peso posicional, mayor número de tareas sucesoras, tiempo de operación más largo y mayor número de tareas sucesoras inmediatas. Se utilizaron269instancias para la prueba computacional ytodas las heurísticas fueron codificadas en el programa MATLAB 2009b. Gracias a los resultados se notó que la heurística JOMI genera muy buenas soluciones, arrojando consigo el mejor promedio de eficiencia con 90,24%; mostrando así otra forma sencilla y factible de resolver los problemas de líneas de ensamble.

Keywords: Balance, heuristic, assembly line, sequence, operation time.

Palabras clave: Balanceo, heurística, líneas de ensamble, secuencia, tiempo operación.

1.- INTRODUCCIÓN Las líneas de ensamble son sistemas productivos de gran importancia en la industria, ya que muchos artículos actuales (celulares, computadores, televisores, carros, etc.) resultan de ensamblar un grupo de elementos o partes a través de esta distribución, estas líneas se caracterizan por estar formadas por estaciones de trabajo, a través de las cuales circula el producto en proceso hasta ser terminado, pueden ser configuradas en serie o en paralelo ycuentan conuntiempoidéntico determinado, tiempo de ciclo, para realizar las operaciones asignadas.En estos sistemas, lafabricación de un producto se divide en un grupo de actividades,donde algunas pueden presentar relaciones de precedencia entre sí, lo cual, junto al tiempo de ciclo determina la forma en que se asignan a cada estación de trabajo. Así, el problema fundamental de las líneas de ensamble es determinar quéactividades asignar a las estaciones, cumpliendo las restricciones establecidas. Los problemas de balanceo de líneas de ensamble (ALBPs)hansido clasificados en dos tipos principales,simple assembly line balancingproblem (SALBP) y general assembly line balancingproblem(GALBP),esta clasificación se detalla en [1] donde se estudia el desarrollo de los SALBP a través del tiempo. Los SALBPs están limitados sólo por restricciones de precedencia y capacidad (tiempo), sus instancias se pueden representar de la siguiente manera; un grupo de actividadesi (i=1,...,n), las cuales son indivisibles, poseen una duración

Pag. 1 / 10 Publicaciones DYNA SL-- c) Mazarredo nº69 -3º -- 48009-BILBAO (SPAIN) Tel +34 944 237 566 – www.dyna-management.com - email: [email protected]

JOMI: Algoritmo heurístico tipo greedy para la solución de los problemas de líneas de ensamble J. Burgos-Meneses, L. Garzón-Aguirre y J. López-Pereira

Organización y dirección de empresas Organización de la producción

de procesamiento conocida ti y algunas presentan relaciones de precedencia entre sí; se distribuyen en un grupo de estaciones de trabajo Sj (j=1,...,m), las cuales presenta un tiempo idéntico (tiempo de ciclo “tc”). Entre los SALBPs se distinguen 4 tipos, como se puede observar en el amplio estado de arte [2] donde se detallan las investigaciones más sobresalientes de estos problemas.  SALBP-1, cuando se busca minimizar el número de estaciones dado el tiempo de ciclo.  SALBP-2, cuando se busca minimizar el tiempo de ciclo dado el número de estaciones.  SALBP-E, cuando se busca minimizar ambos el tiempo de ciclo y el número de estaciones.  SALBP-F, cuando se busca encontrar una factibilidad dados estos dos parámetros. Cabe destacar que para los SALBP uno de los objetivos fundamentales es maximizar la eficiencia del sistema, la cual se define como la división entre tiempo total de las actividades “Tt” y la multiplicación del número de estaciones con el tiempo de ciclo(1). (1) Los GALBPs,como se puede observar en [6] donde se realiza un completo estudio de las investigaciones relacionadas con este tipo de problema, son problemas más generalizados que consideran otras restricciones aparte del tiempo de ciclo y relaciones de precedencia, como el caso de estaciones en paralelo donde en [3] se define este tipo de problema y se propone un efectivo procedimiento de solución; líneas en forma de U donde en [4] este tipo de problema se introduce, modela y además se desarrolla un procedimiento para su solución; o incompatibilidad entre tareas donde en [5] se investiga este problema incluyendo una práctica industrial. Cabe destacar que aunque los GALBPs son problemas más generales y reales, los SALBPs son a los que la mayoría de investigadores han dedicado sus estudios ya que sus soluciones pueden ser adaptadas a las soluciones de los GALBPs. Los ALBPs han sido estudiados por muchos investigadores desde diferentes enfoques, y para su solución se han desarrollado múltiples métodos como se observa en el estado del arte[2] y el proyecto de clasificación de balanceo de líneas de ensamble [7]; estos métodos se pueden dividir en:Métodos heurísticos, los cualescomúnmente utilizan reglas de prioridad y generan buenas respuestas en tiempos computacionales muy cortos, como se puede observar en [8] donde se realiza un experimento computacional para evaluar la eficiencia de 26 heurísticas de decisión, en la sección siguiente se detallara este tipo de procedimiento; métodos basados en procedimientos de búsqueda exacta “branch and bound”, los cuales se caracterizan por generar las respuestas más eficientes aunque en tiempos de procesamiento más largos,entre estos se destacan los algoritmos FABLE [12] y SALOME [20]; y métodos basados en la implementación de metaheuristicas, como es el caso de [14] donde se describe el desarrollo de un algoritmo genético para la creación de múltiples soluciones en los ALBP;[15] en el cual se presenta un algoritmo de búsqueda tabú y se discuten sus diferencias con los otros algoritmos de este tipo encontrados en la literatura; y [16] el cual se basa en la aplicación del algoritmo de colonia de hormigas en un problema de balanceo de líneas de ensamble . En estainvestigación se presenta el diseño y la validación de una nueva heurística tipo greedyllamada JOMI, mediante su ejecución y comparación con otros métodos existentes del mismo tipo, todo esto con el fin de ofrecer un método alternativoen la solución de los SALBP-1.

Pag. 2 / 10 Publicaciones DYNA SL-- c) Mazarredo nº69 -3º -- 48009-BILBAO (SPAIN) Tel +34 944 237 566 – www.dyna-management.com - email: [email protected]

JOMI: Algoritmo heurístico tipo greedy para la solución de los problemas de líneas de ensamble J. Burgos-Meneses, L. Garzón-Aguirre y J. López-Pereira

Organización y dirección de empresas Organización de la producción

2.- HEURÍSTICAS GREEDY Pese a los progresos obtenidos en cuanto a la resolución exacta de los problemas de optimización combinatoria, particularmente los referentes al balanceo de líneas de ensamble, los procedimientos heurísticos siguen desempeñando un papel muy importante, puesto que permiten obtener soluciones adecuadas en tiempos de procesamiento relativamente cortos y son buenas alternativas para los problemas en que los métodos exactos no tienen éxito. En [26]se pueden observar las ventajas de este tipo de procedimientos. Las heurísticas tipo greedy, caracterizadas por utilizar los datos disponibles del problema para construir paso a paso una solución, son una de las más conocidas y prueba de ello se observa en como los investigadores las utilizan para basarse en el desarrollo de nuevos procedimientos. Tal es el caso de [22] donde se definen varios componentes comprendidos en GreedyRandomizedAdaptiveSearchProcedures (GRASP) y se demuestra paso por paso como desarrollar heurísticas para los problemas de optimización combinatoria; [23] donde se trata de determinar la mejor heurística greedy en un conjunto infinito de heurísticas de este tipo y consecuentemente se aplica al problema de balanceo de líneas de ensamble en [24]; [21] donde se propone un procedimiento de combinación de soluciones representadas por secuencias de reglas heurísticas greedy bajo un esquema scattersearch; y más recientemente [25] donde se presentan dos nuevas propuestas multi-objetivo basadas en optimización de colonias de hormigas y algoritmos greedy de búsqueda aleatoria para resolver extensiones más realistas de este problema. Profundizando en los problemas de balanceo de líneas de ensamble, a continuación se muestra en la fig. 1 un esquema general del funcionamiento de las heurísticas greedy aplicadas en los SALBPs-1 donde se describe paso a paso dicho procedimiento. Inicio del problema

Paso 1: crear una nueva estación.

Paso 2: mostrar listas de actividades candidatas.

Paso 7: Calcular el tiempo restante en la estación

Paso 3: ¿Existen actividades candidatas?

Paso 4: Asignar a la estación la actividad escogida por medio de la regla de prioridad establecida

Si

No

Paso 6: Eliminar la actividad escogida de la red del problema inicial

Paso 5: ¿Todas las actividades están seleccionadas?

Si

No

Paso 8: Guardar la solución final

Fin del problema

Fig. 1. Esquema de un procedimiento heurístico tipo greedy para la solución de los SALBP-1

Como se observa en el Paso 4, cada actividad se asigna a la estación en curso por medio de una regla de prioridad, la cual viene establecida por un algoritmo heurístico. A continuación, en la tabla 1 se enumeraran los algoritmos heurísticos más utilizados y conocidos en la literatura prueba de ello se observa en [8] y [21], además de la abreviatura que utilizaremos para cada uno de en el presente trabajo.

Pag. 3 / 10 Publicaciones DYNA SL-- c) Mazarredo nº69 -3º -- 48009-BILBAO (SPAIN) Tel +34 944 237 566 – www.dyna-management.com - email: [email protected]

JOMI: Algoritmo heurístico tipo greedy para la solución de los problemas de líneas de ensamble J. Burgos-Meneses, L. Garzón-Aguirre y J. López-Pereira

Heurísticas tipo greedy Nombre Mayor tiempo de operación [27] Mayor número de sucesoras inmediatas [29] Mayor número de sucesoras [8] Mayor peso posicional [28] Mayor peso medio posicional Menor cota superior [8] Menor : (cota superior/sucesoras) [8] Mayor: (tiempo de operación/cota superior) [8] Menor cota inferior [8] Menor holgura [8] Mayor: (Sucesoras/holgura) [8] Bhattcharjee & Sahu Kilbridge & Wester Menor tiempo de operación

Organización y dirección de empresas Organización de la producción

Abreviatura TOL MIS MS PP PMP MCS MCS/S TOL/CS MCI MH S/H B&S K&W TOC

Tabla 1. Definición de las heurísticas tipo greedy

3.- HEURÍSTICA JOMI La heurística propuesta hace parte del grupo de los algoritmos heurísticos greedy,cuya implementación está descrita en la fig.1, estableciendocomo regla de prioridad “escoger la primera actividad de la sucesión de actividades que genera menor tiempo ocioso en la estación”.Las sucesiones de actividades son un conjunto de actividades que se preceden entre sí formando una especie de cadena ypresentandoun tiempo de ejecución menor o igual que el tiempo disponible de la estación; pero ¿cómo se determinan estas sucesiones de actividades? Veamos la línea de ensamble de la fig. 2, la cual se pretende balancear con un tiempo de ciclo de 16, donde los nodos representan actividades, los grafos relaciones de precedencia y la duración de cada actividad se muestra dentro de cada nodo, un ejercicio similar al observado en [19] estudio que trae consigo el desarrollo de una nueva heurística de enfoque bidireccional.

Fig. 2. Línea de ensamble. Se crea la primera estación, la cual tiene un tiempo disponible ts igual al tiempo de ciclo tc=16. Luego, se determinan las sucesiones de actividades:  Primera sucesión A(6) + B(3) = 9, no se puede ingresar la actividad E(11) porque en este caso el tiempo de la sucesión tr sería 20 excediendots=16.  Segunda sucesión A(6) + C(3) = 9, no se puede ingresar la actividad F(11) porque en este caso tr sería 20 excediendots=16.  Tercera sucesión A(6) + D(4) + G(4) = 14, no se puede ingresar la actividad I(13) por dos razones, trsería 27 excediendots=16 y la actividad I(13) es precedida por otra actividad ajena a esta sucesión H(4).  Cuarta sucesión A(6) + D(4) + H(4) = 14, no se puede ingresar la actividad I(13) por dos razones,tr sería 27 excediendots=16 y la actividad I(13) es precedida por otra actividad ajena a esta sucesión G(4). Como se observa, se tienen cuatro sucesiones de actividadesA→Bcon tiempo ocioso to=5 (to=ts-tr), A→Ccon to=5, A→D→G con to=2yA→D→H con to=2; se presenta un empate entre dos sucesiones que generan menor to, por Pag. 4 / 10 Publicaciones DYNA SL-- c) Mazarredo nº69 -3º -- 48009-BILBAO (SPAIN) Tel +34 944 237 566 – www.dyna-management.com - email: [email protected]

JOMI: Algoritmo heurístico tipo greedy para la solución de los problemas de líneas de ensamble J. Burgos-Meneses, L. Garzón-Aguirre y J. López-Pereira

Organización y dirección de empresas Organización de la producción

tanto,siguiendo la regla “escoger la primera actividad de la sucesión de actividades que genere menor tiempo ocioso”, se escoge la primera actividad de una de estasdos sucesionesy se elimina de todas sus referencias en el problema inicial(cuando se presenta un empate entre actividades, se puede optar por escoger cualquiera de estas actividades o por agregar una regla adicional de desempate al algoritmo, más adelante se recomendara una regla adicional de desempate para estaheurísticas). En este casose asignaA(6) a la estación debido a que es la primera actividad en ambas sucesiones, luego se calcula el nuevo tiempo disponible(ts- ti=ts,donde ti es el tiempo de la actividad escogida)16-6=10 y se continua el ejercicio con dicho ts siguiendo los pasos anteriores, calculando las nuevas sucesiones (en este caso B, C, D→G y D→H), escogiendo la actividad por medio de la regla establecida (en este caso D), eliminando todas sus referencias del problema inicial, calculando el nuevo ts (en este caso 10-4=6) y continuando el ejercicio con este. NOTA:Si después de eliminar todas las referencias de una actividad y calcular el nuevo ts, las actividades o sucesiones de actividades existentes nocumplen con las restricciones de tiempo, se crea una nueva estación con tsigual a tc y se continúa el problema con este.Ahora por otro lado si después de eliminar todas las referencias de una actividad y calcular el nuevo ts, no existen más actividades, el problema ha sido resuelto y todas las actividades están asignadas a las estaciones de trabajo. Al finalizar el balanceo dela línea de ensamble observada en la fig. 2, se tiene una línea con 7 estaciones, como se observa en la fig. 3, dondela primera estación contienelas actividades A, D y G; la segunda estación las actividades B y E; la tercera estación las actividades J y H; la cuarta estación las actividades C e I; la quinta estación las actividades F y L; la sexta estación las actividades K y M; y la séptimaestación las actividades P, N, O y Q.

Fig. 3. Balanceo final de línea de ensamble utilizando la heurística JOMI. Como se puede observar en el ejemplo ilustrativo existen ocasiones en que se presenta un empate, es decir varias sucesiones de actividades generan el mínimo tiempo ocioso, cuando esto sucede y en dichas sucesiones la primera actividad es la misma no se presenta ningún problema y se escoge esta actividad, pero cuando en dichas sucesiones la primera actividad es diferente se propone una regla adicional de desempate,la cual esseleccionar de las actividades empatadas la que al ser seleccionada genere la sucesión de actividades con menor tiempo ocioso.

4.- EXPERIMENTO En los trabajos realizados por [28], [17], [13]se afirma que no existe un método de comparación de heurísticas que tenga una aceptación general, así que para demostrar la eficiencia de la heurística JOMI se realizó una prueba computacional de esta heurística y las descritas en la tabla 1 (por ser las más populares encontradas la literatura) utilizando la práctica más común, que se basa en utilizar las heurísticas que se desean comparar en un grupo relativamente numeroso de instancias.

4.1.- PRUEBA COMPUTACIONAL Las pruebas computacionales de los 15 algoritmos se realizaron en el programa MATLAB 2009b, el experimento fue realizado en un computador con procesador de 2.00 Ghz. Intel Core Duo y 1GB de memoria RAM,y las instancias Pag. 5 / 10 Publicaciones DYNA SL-- c) Mazarredo nº69 -3º -- 48009-BILBAO (SPAIN) Tel +34 944 237 566 – www.dyna-management.com - email: [email protected]

JOMI: Algoritmo heurístico tipo greedy para la solución de los problemas de líneas de ensamble J. Burgos-Meneses, L. Garzón-Aguirre y J. López-Pereira

Organización y dirección de empresas Organización de la producción

utilizadas (incluido los tiempos de ciclo) se encuentran en el “benchmark data set”para SALBP-1 del capítulo 7.1 de [11], disponibles para descargar en http://www.wiwi.uni-jena.de/Entscheidung/alb/. Un total de 269 instancias son puestas a prueba las cuales hacen parte de las más usadas en las investigaciones y los estudios de nuevos algoritmos para la solución de los SALBP-1, prueba de ello se observa en [30] estudio que presenta el desarrollo de un nuevo algoritmo heurístico basado en aproximación de la red Preti para solucionar este tipo de problema; y [31] estudio que expone una nueva heurística basada en aproximación bidireccional y el método de ruta crítica ampliamente utilizado en administración de proyecto.

4.2.- RESULTADOS Las instancias puestas a prueba se han dividido en 3 grupos, instancias pequeñas (con menos de 33 actividades), instancias medianas (con más de 33 actividades pero menos de 100 actividades) e instancias grandes (con más de 100 actividades), la tabla 2en donde “n” es el número de actividades de cada instancia y los algoritmos están dados por la abreviatura mostrada en la tabla 1, muestra los promedios de eficiencia de cada algoritmo en cada grupo de instancias, además del promedio de eficiencia en todas las instancias y el tiempo de procesamiento promedio de cada algoritmo. Al verificar cuál de los algoritmos genera mejor eficiencia, se encontró que el algoritmo heurístico JOMI genero los mejores resultados en todos los grupos de instancias con un promedio de eficiencia total de 90.24%, seguido de los algoritmos “B&S” con 89,96% y “TOL/CS” con 89,64%. Por otro lado en cuanto a lo relacionado con el tiempo de procesamiento se observa que la heurística que más tarda en procesar una solución es el algoritmo JOMI con una duración promedio de 0.4559 segundos, seguido del algoritmo S/H con una duración promedio de 0.1624 segundos. Tamaño de instancias Eficiencia Eficiencia promedio para promedio para instancias instancias Medianas Grandes (33