metaheurÍsticas multi-objetivo para equilibrado de … · propuesta basada en macs tras una...
TRANSCRIPT
METAHEURÍSTICAS MULTI-OBJETIVO PARA EQUILIBRADODE LÍNEAS DE MONTAJE:
OPTIMIZACIÓN CONJUNTA DE TIEMPO Y ESPACIO
Directores: Óscar Cordón, Joaquín Bautista, Sergio DamasAÑO 2011
TESIS DOCTORALManuel Chica Serrano
Tesis_Doctoral_M_Chica Página_2
Planteamiento
Las líneas de montaje son de vital importancia para la producción masiva de bienes genéricos de calidad.
Una línea de montaje estácompuesta por estacionesde trabajo.
A lo largo de estas estacionesse van realizando las tareasproductivas.
Tesis_Doctoral_M_Chica Página_3
Planteamiento
La configuración de una línea de montaje persigue la asignación óptima de tareas a estaciones de trabajo.
Minimizando la ineficienciade la línea y cumpliendo lasrestricciones impuestas.
Este tipo de problemas se conoce como:
Equilibrado de líneas de montaje(assembly line balancing, ALB )
Tesis_Doctoral_M_Chica Página_4
Planteamiento
Modelo SALBP: n tareas productivas. Cada tarea j necesitaun tiempo operativo tj y posee un conjunto de predecesoresdirectos.
El tiempo ciclo, C, determinará la tasa de producción de la línea. En cada línea existen un número de estaciones m.
Tesis_Doctoral_M_Chica Página_5
Planteamiento
El conjunto de problemas SALBP buscan agrupar esas n tareas en m estaciones de trabajo, minimizando el tiempo de ciclo (C) o el número total de estaciones (m).
Es un problema de secuenciación que puede ser tratado comoun problema de empaquetado con restricciones de dependencia [DW92].
estación 1
estación 2
estación 3
estación 4
Tesis_Doctoral_M_Chica Página_6
Planteamiento
El SALBP es un problema de optimización clásico quesiempre ha recibido gran atención [Sch99].
Sin embargo, tiene grandes limitaciones prácticas [Mil90]:
Variaciones en los productos.
Adopción de filosofías Just in Time.
Restricciones espaciales
…
Tesis_Doctoral_M_Chica Página_7
Planteamiento
Las restricciones espaciales no han sido consideradas y esun ejemplo claro de limitación del modelo.
La información espacial es importante debido a que:
El espacio para una estación es limitado.
Hay un espacio restringido para herramientas.
La evolución del producto genera nuevas restricciones.
¡El espacio es incluso más importante en la industriaautomovilística!
Tesis_Doctoral_M_Chica Página_8
Planteamiento
Tras observar la problemática existente en Nissan, Bautista y Pereira modelaron una nueva extensión al SALBP:
Time and Space Assembly Line Balancing (TSALBP)
Tesis_Doctoral_M_Chica Página_9
Planteamiento
Obtienen una versión simplificada de la realidad en la industria pero mucho más cercana que las anteriores.
Añaden al SALBP la componente espacial: Área para cada tarea, aj ; j=1,…,n.
Área disponible para cada estación, A.
El TSALBP es un marco de problemas multiobjetivo con 3 posibles variables a optimizar:
Tiempo de ciclo (C). Área disponible (A). Número de estaciones (m).
Tesis_Doctoral_M_Chica Página_10
Planteamiento
4 variantes multi-objetivo.
Tras el estudio en Nissan se ve como el TSALBP-1/3 es una de las variantes más realistas en la industria porque:
La producción anual (tiempo ciclo) se fija inicialmente.
Y obtener un óptimo de área y estaciones nos permite reducir costes y mejorar las condiciones de los trabajadores.
Tesis_Doctoral_M_Chica Página_11
Planteamiento
Con anterioridad a esta Tesis Doctoral no existían propuestas para ninguna variante multiobjetivo del TSALBP.
Respecto al SALBP existen:
Métodos exactos. Procedimientos constructivos y metaheurísticas.
Sí existen trabajos que han tratado de resolver una variante mono-objetivo del TSALBP:
ACO, Beam ACO… [BP07, BP06]
Tesis_Doctoral_M_Chica Página_12
Planteamiento
Dada la complejidad del TSALBP-1/3 (NP-completo) y su carácter multiobjetivo existe la necesidad de desarrollar metaheurísticas multiobjetivo:
Constructivas: colonias de hormigas
No constructivas: algoritmos genéticos
Híbridas:
algoritmos meméticos
Tesis_Doctoral_M_Chica Página_13
Planteamiento
Aparte de generar las mejores soluciones posibles tambiénes conveniente introducir conocimiento del experto a travésde preferencias para:
Facilitar el trabajo al decisorcon un número adecuadode soluciones.
Guiar la búsqueda hacia la zonadel frente de Pareto que sea de interés real.
Tesis_Doctoral_M_Chica Página_14
Planteamiento
Necesidad de aplicar los algoritmos a datos reales de la línea del motor del Nissan Pathfinder:747 piezas y 378 operaciones agrupadas en 140 tareas.
Fábrica Nissan en Barcelona
Tesis_Doctoral_M_Chica Página_15
Índice
1. Objetivos2. Propuesta de metaheurísticas
multiobjetivo3. Uso de preferencias del decisor4. Conclusiones5. Trabajos futuros
BLOQUE 1
OBJETIVOS
Tesis_Doctoral_M_Chica Página_17
Objetivos
Proponer métodos de resolución para el TSALBP-1/3 basados en metaheurísticas constructivas (MOACO).
Diseñar métodos basados en metaheurísticas no construtivas. Realizaremos un amplio estudio paradiseñar un MOGA adecuado a las características del problema.
Diseñar metaheurísticas híbridas utilizando la filosofíaMOMA.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_18
Objetivos
Incorporar preferencias a los algoritmos para dirigir la búsqueda:
Utilizando información para discriminar entre configuraciones con mismos objetivos.
Reduciendo el conjunto final de soluciones, centrándose en la parte de interés del frente de Pareto.
Validar los distintos métodos en instancias reales. En concreto, nos planteamos propondrá utilizar datos de la línea de montaje del motor del Nissan Pathfinder.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
BLOQUE 2
PROPUESTA DE METAHEURÍSTICAS
MULTIOBJETIVO
Tesis_Doctoral_M_Chica Página_20
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Metaheurísticas Multi-Objetivo
3 metaheurísticas en las que se basarán nuestros enfoques para resolver el TSALBP-1/3:
Algoritmos de Optimización Multiobjetivo basados en Colonias de Hormigas (MOACO).
Algoritmos Genéticos Multiobjetivo (MOGA).
Algoritmos Meméticos Multiobjetivo (MOMA).
Tesis_Doctoral_M_Chica Página_21
Propuesta basada en MACS
Por el gran número de restricciones del problema las metaheurísticas constructivas parecen ser más adecuadas.
Los algoritmos MOACO son metaheurísticas constructivas que suelen dar buenos resultados en estos problemas.
Nuestra propuesta se basa en el Multiple Ant Colony System(MACS) , extensión multiobjetivo del ACS [DG97].
Se elige por su gran rendimiento y diversidad en comparación con otros algoritmos MOACO [GCH07].
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_22
Propuesta basada en MACS
En el MACS, cada solución no dominada que encuentra el algoritmo se va almacenando en un fichero externo. La regla de transición es similar a la del ACS.
El rastro de feromona se asocia al par (tarea, estación) al seguir un enfoque orientado a la estación.
Existe una matriz de feromona y una matriz por información heurística. En nuestro caso dos heurísticas:
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_23
Propuesta basada en MACS
Tras una experimentación preliminar vimos cierta falta de convergencia del algoritmo.
Por eso incluimos un mecanismo novedoso para ir cerrando una estación dependiendo de lo llena que esté:
Esta probabilidad se va actualizando. Se va generandoun aleatorio para decidir a cada paso si cerrar o no la estación.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_24
Nuestro enfoque MACS
Necesidad de más diversidad: filosofía multi-colony.
Las hormigas de cada colonia se comportan de forma diferente (uso distintos umbrales de cierre de estación).
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_25
Propuesta inicial de MOGA
Inicialmente se propuso una extensión multi-objetivo paraun Algoritmo Genético mono-objetivo que ya existía parael SALBP [SET00].
Proponemos un nuevo MOGA llamado enfoque NSGA-II avanzado para el TSALBP-1/3 que intenta resolver los problemas de las anteriores propuestas.
Comportamiento no adecuado. ¡Falta diversidad!
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_26
Representación del nuevo MOGA
¡¡Una simple representación de orden no representa unasolución TSALBP completa!!
Proponemos el uso de una resentación de orden con separadores. El tamaño del individuo es dinámico, siendo el máximo 2n – 1 (n = número de tareas).
Los separadores son genes “dummies”que delimitan lastareas entre estaciones. El número separadores de cadaindividuo puede variar (<= n).
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_27
Representación del nuevo MOGA
Ejemplo de representación de un individuo:
Problema con 8 tareas (genes <= 8).
Se representa solución con 3 estaciones: 3, 3 y 2 tareas respectivamente.
Se han necesitado 2 separadores (genes verdes).
Las estaciones no pueden rebasar el tiempo ciclo disponible.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_28
Componentes clave del MOGA
Aparte de la novedosa representación, se incluyen 3 componentes clave que van a dar al MOGA la diversidadque necesita:
Operador de cruce con mecanismo de inducción de diversidad de Ishibuchi [INTN08].
Operador de mutación por mezcla.
Operador de mutación por división.
Se realizó una experimentación previa para ver la importancia de su uso individual en el algoritmo.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_29
Operador de cruce del MOGA
Operador de cruce de orden (PMX): 2 descendientes a partir de los padres de la siguiente forma:
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_30
Operador de cruce del MOGA
Los descendientes siempre satisfacen las precedencias.
Sin embargo es necesario un operador reparador que se aplica tras el cruce para revisar factibilidad. Su misión:
Redistribuir las tareas sobrantes de estaciones quesobrepasan tiempo de ciclo y moverlas a estaciones quelas admitan.
Eliminar estaciones vacías. Esto ocurre cuando hay dos genes separadores juntos.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_31
Operadores de mutación del MOGA
Operador de mutación por mezcla:
Para añadir más diversidad se introduce un segundooperador de mutación por división.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_32
Algoritmo Meméticos Multi-objetivo
Los Algoritmos Meméticos han demostrado su buencomportamiento en multitud de problemas por sucombinación de búsqueda global y optimizador local.
Presentamos distintos Algoritmos Meméticos Mutiobjetivo(MOMA) para el TSALBP-1/3 usando:
a) Las metaheurísticas ya validadas: MACS y NSGA-II avanzado.
b) Una búsqueda local MO con dos operadores de generación de vecinos, uno por objetivo.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_33
Estructura general del MOMA
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_34
Estructura general del MOMA
La función que tiene que ser optimizada por la búsquedalocal (BL) es una escalarización de las dos funcionesobjetivo:
Los pesos de la escalarización se crean aleatoriamente paracada solución generada por la búsqueda global: λ1, λ2
En nuestra propuesta se utiliza el enfoque de BL del MOGLS de Jazskiewicz para MOMAs [Jas02].
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_35
Operadores de la búsqueda local
Si λ1 > λ2 el operador de la BL se centra en el objetivo A. Si no, será el operador para el objetivo m. Si no se consigue minimizar con un operador, se lanza también el otro.
Ambos operadores se basan en la explotación de los vecindarios gracias a movimientos de tareas entre estaciones. Cada uno intentará minimizar su objetivo asociado.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_36
Integración de la búsqueda local
Uno de los aspectos más importantes en el diseño de un MOMA es cómo integrar los operadores de la BL en la estructura multi-objetivo.
Aspectos a considerar:
Equilibrio entre búsqueda local y global: aplicación a todas las soluciones o aplicación selectiva (1/16) [KS00].
Profundidad en la aplicación de la BL: número de iteraciones (20, 50 y 100).
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_37
Realizada sobre 10 instancias de la literatura del problema bi-objetivo*. Además, se aplica a la cadena de montajedel motor del Nissan Pathfinder.
Se realiza un análisis incremental.
¿Cómo comparamos? Métricas unarias: HVR, GD
y cardinalidad. Métricas binarias: I y C. Test estadístico Wilcoxon basado en métricas I y C. Representación gráfica de los frentes de Pareto.
Experimentación
* www.nissanchair.com
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_38
Comparativa MACS con distintas variantes heurísticas y feromona. Resultados de la métrica C:
Experimentación MACS
Variante sin heurísticapresenta los mejores
resultados
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_39
MACS frente a otros algoritmos: Aleatorio básico, extensión multiobjetivo NSGA-II para SALBP y MORGA.
Probabilidad de dominancia y test Wilcoxon sobre métrica C utilizados en la comparativa:
Experimentación MACS
MACS en su variante sin heurística mejora a los demás algoritmos
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_40
Las soluciones del frente de Pareto obtenidas por el MACS dominan a las soluciones de los demás algoritmos.La extensión multiobjetivo del NSGA-II sólo consigue una o dos soluciones no-dominadas en la parte izquierda.
Experimentación MACS
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_41
El diseño avanzado del NSGA-II para el TSALBP-1/3 obtiene muchos mejores resultados que MACS y la versión previa del NSGA-II.
Experimentación MOGA
Para Nissan, losmismos resultados
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_42
Experimentación MOGA
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_43
Integración búsqueda global-optimización local:
LS1: 20, todas solucionesLS2: 50, todas solucionesLS3: 100, todas solucionesLS4: 20, 1/16 % solucionesLS5: 50, 1/16 % solucionesLS6: 100, 1/16 % soluciones
Experimentación Meméticos
Variante MOMA siempre mejor que metaheurística básica.
Mejor aplicar BL a todas las soluciones.
MOGA, suficiente con 20 its., los demás algoritmos necesitan más its.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_44
Comparamos las mejores variantes MOMA de cada metaheurística entre sí: MACS LS2, GRASP LS3 y NSGAII LS1.Siempre mejores resultados NSGAII LS1, incluso en Nissan.
Experimentación Meméticos
Probabilidades de dominancia
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_45
Análisis global de rendimiento
El mejor MACS es el que trabaja sin información heurística, sólo feromona.
El diseño avanzado del NSGA-II, gracias al buen diseñode representación y operadores, consigue ser la mejormetaheurística de búsqueda global. También en Nissan.
La hibridación con mémeticos funciona mejor que lasmetaheurísticas básicas en todos los casos.
El MOGA memético es el método que consigue los mejores resultados para el TSALBP-1/3.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
BLOQUE 3
USO DE PREFERENCIAS DEL DECISOR
Tesis_Doctoral_M_Chica Página_47
Uso de preferencias
Uso de preferencias para guiar la búsqueda realizada porlas metaheurísticas multiobjetivo con dos propósitos:
Reducir el número de soluciones igualmente preferiblespara el decisor (espacio de decisión).
Proponer soluciones con lasconfiguraciones más interesantespara el decisor dependiendode su contexto económico y laboral.
Preferencias sólo aplicadas al MACS por el desarrollotemporal realizado.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_48
Reducción del número de soluciones
Los algoritmos pueden proporcionar muchas soluciones(configuraciones de línea) distintas con mismos objetivos (m,A).
La reducción de soluciones con mismos objetivos (m, A) eliminala necesidad de que el experto las examine todas.
Estableceremos reglas basadas en el conocimiento del expertode Nissan que usarán las metaheurísticas en su función objetivo(enfoque a priori).
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_49
Reducción del número de soluciones
A partir del estudio de la planta industrial de Nissan en Barcelona se observa que:
La carga de la planta debe estar balanceada en cadaestación menos conflictos y turnos de trabajadores.
El espacio requerido para las herramientas debe ser lo más parecido posible, siendo equitativos con los trabajadores y reduciendo desplazamientos.
Nueva métrica para soluciones de igual (m, A):
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_50
Reducción del número de soluciones
Establecemos nuevas relaciones de dominancia con preferencias para soluciones 1 y 2 con iguales m y A:
Def.1: 1domina parcialmente a 2 respecto a tiempo si:
Def.2: 1domina parcialmente a 2 respecto a espacio si:
Def.3: 1domina completamente a 2 en tiempo y espacio:
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_51
Reducción del número de soluciones
Nuevas relaciones de dominancia al MACS: Reduccióndrástica en el número soluciones. ¡Mejor convergencia!
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_52
Guía hacia las soluciones de interés
Objetivo: reducir el frente de Pareto de solucionesenfocándose sólo en la región de interés del decisor en términos de los valores de m y A.
Intereses del decisor definidos según factores económicosmundiales reales:
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_53
Guía hacia las soluciones de interés
A partir de los datos anteriores el experto puede definira priori la importancia de cada objetivo.
Proponemos dos métodos para ello:
Definición de preferencias mediante unidades de importancia [BKS01].
Definición de preferencias mediante metas para los objetivos [Deb99].
No todos los métodos de uso de preferencias existentes se pueden aplicar al MACS. La mayoría son para evolutivos.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_54
Preferencias por unidades de importancia
Se definen unidades de importancia por par de objetivos:
Se reemplazan los objetivos originales por los siguientes, manteniendo dominancia clásica:
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_55
Con el enfoque de Branke [BKS01], cada conjunto de preferencias consigue obtener soluciones en la parte deseada del Pareto:
Enfoque Branke para España
Preferencias por unidades de importancia
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_56
Preferencias por definición de metas
Las preferencias a priori son definidas mediante metas. Usamos el modelo de incorporación de preferencias de Deb, propuesto para MOGA [Deb99].
Enfoque de Deb: minimizar la desviación de la funciónobjetivo a la meta:
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_57
Preferencias por definición de metas
Agrupamos los 6 escenarios iniciales en 3:
España, con más importancia a los costes laborales (min m). Reino Unido, con menos coste de área industrial (min A). Japón, con más interés en un equilibrio entre A y m.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_58
Preferencias por definición de metas
Igual ocurre con las metas de Deb [Deb99]:
Enfoque Deb para Japón
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_59
Análisis global de resultados
Se ha conseguido reducir el número de soluciones con mismos objetivos. Aumenta la convergencia del algoritmo.
Enfoques correctos de la búsqueda a la parte del frentede Pareto preferida por el experto:
6 escenarios Nissan con distintas necesidades, consiguiendo devolver las soluciones deseadas.
Mismo resultado con metas y con unidades de importancia. La diferencia sólo estriba en la forma de expresarlas.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
BLOQUE 4
CONCLUSIONES
Tesis_Doctoral_M_Chica Página_61
Conclusiones
Hemos conseguido crear un marco de trabajo multiobjetivopara la aplicación de metaheurísticas al TSALBP-1/3.
Hemos diseñado la primera metaheurística efectiva: MOACO basado en MACS. Mejor la variante sin heurística.
A priori las metaheurísticas constructivas era más lasapropiadas. Sin embargo, también diseñamos un MOGA con adecuada representación y operadores.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_62
Conclusiones
Nuestro MOGA, un NSGA-II con un diseño avanzadoespecífico para TSALBP, mejoró los resultados existentes.
Se han diseñado unos nuevos operadores de BL paraconseguir una hibridación memética: búsqueda global + optimización local.
El MOMA que usaba al MOGA como búsqueda global ha sido el mejor de todos los algoritmos diseñados.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_63
Conclusiones
Hemos aplicado por primera vez métodos de resolución a datos multi-criterio de la línea del Nissan Pathfinder.
Hemos reducido drásticamente las soluciones de los algoritmos con igual valor en los objetivos mediante uso de preferencias del experto de Nissan.
Hemos incorporado 2 nuevos mecanismos para guiar la búsqueda del algoritmo MACS a la parte del frente de Pareto deseada en distintos escenarios de Nissan.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_64
Publicaciones
Publicaciones en revistas JCR:
M. Chica, O. Cordón, S. Damas, J. Bautista. Multiobjective memetic algorithms for time and space assembly line balancing. Engineering Applications of Artificial Intelligence, 2011. Impacto: 1,34 (1er cuartil).
M. Chica, O. Cordón, S. Damas. An advanced multi-objective genetic algorithm design for the time and space assembly line balancing problem. Computers and Industrial Engineering, 2011. Impacto: 1,54 (2º cuartil).
M. Chica, O. Cordón, S. Damas, J. Bautista. Incorporating different kinds of preferences into a multi-objective ant algorithm on different Nissan scenarios. Expert Systems with Applications, 2011. . Impacto: 1,92 (1er cuartil).
M. Chica, O. Cordón, S. Damas, J. Bautista. Multi-objective constructive heuristics for the 1/3 variant of the time and space assembly line balancing problem: ACO and random greedy search. Information Sciences, 2010. Impacto: 2,83 (1er cuartil).
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_65
Publicaciones
Publicaciones en otras revistas, libros y congresos:
M. Chica, O. Cordón, S. Damas, J. Bautista. A new diversity induction mechanism for a multi-objective ant colony algorithm to solve a real-world time and space assembly line balancing. Memetic Computing 3 (1) 15-24, 2011.
M. Chica, O. Cordón, S. Damas, J. Bautista. Adding diversity to multiobjectiveconstructive metaheuristics for time and space assembly line balancing. Frontiers of Assembly and Manufacturing, 2010, pp. 211-226.
M. Chica, O. Cordón, S. Damas, J. Pereira, J. Bautista. Incorporating preferences to a multi-objective ant algorithm for time and space assembly line balancing. Springer Lecture Notes on Computer Science 5217, 2011, pp. 331-338.
M. Chica, O. Cordón, S. Damas. Tackling the 1/3 variant of the time and space assembly line balancing problem by means of a multiobjective genetic algorithm. Proceedings of the IEEE Congress on Evolutionary Computation, New Orleans (USA), 2011, pp. 1367-1374 .
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_66
Publicaciones
M. Chica, O. Cordón, S. Damas and J. Bautista. A multiobjective memetic ant colony optimization algorithm for the 1/3 variant of the time and space assembly line balancing problem. Proceedings of the IEEE Workshop on Computational Intelligence in Production and Logistics Systems, Paris (France), 2011, pp. 31-37.
M. Chica, O. Cordón, S. Damas and J. Bautista. A multiobjective GRASP for the 1/3 variant of the time and space assembly line balancing problem. Proceedings of the IEA-AIE 2010, Córdoba (Spain), 2010. Springer Lecture Notes in Artificial Intelligence 6098, 2010, pp. 656–665.
M. Chica, O. Cordón, S. Damas and J. Bautista. A new diversity induction mechanism for a multi-objective ant colony algorithm to solve a real-world time and space assembly line balancing problem. Proceedings of the 2009 IEEE International Symposium on Assembly Lines and Manufacturing (ISAM 2009), Suwon (Korea), 2009, pp. 364-379.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_67
Publicaciones
M. Chica, O. Cordón, S. Damas and J. Bautista. Integration of an EMO-based Preference Elicitation Scheme into a Multi-objective ACO Algorithm for Time and Space Assembly Line Balancing. Proceedings of the 2009 IEEE International Conference on Multicriteria Decision Making (MCDM), EE.UU., 2009, pp.157-162.
M. Chica, O. Cordón, S. Damas, J. Pereira, J. Bautista. A Multiobjective Ant Colony Optimization Algorithm for the 1/3 Variant of the Time and Space Assembly Line Balancing Problem. International Conference IPMU, Málaga, 2008, pp. 1454-1461
M. Chica, O. Cordón, S. Damas, J. Bautista. Incorporando preferencias basadas en EMO a un algoritmo ACO multiobjetivo para el equilibrado de líneas de montajeconsiderando tiempo y espacio. In Proceedings Congreso Español sobreMetaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB), Valencia, 2010, pp. 277-284.
M. Chica, O. Cordón, S. Damas, J. Bautista, J. Pereira. Heurísticas constructivasmultiobjetivo para el problema de equilibrado de líneas de montaje considerandotiempo y espacio. In Proceedings Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB), Málaga, 2009, pp. 649-656.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
BLOQUE 5
TRABAJOSFUTUROS
Tesis_Doctoral_M_Chica Página_69
Trabajos futuros
Los resultados conseguidos en esta Tesis doctoral dejanabiertas las siguientes nuevas líneas de trabajo:
Aunque MOGA obtuvo mejores resultados, los enfoquesconstructivos son a priori más apropiados. Por tanto, realizaremos una comparativa entre los mejores algoritmosMOACO existentes.
Desarrollo de un MOACO a medida mediante el uso de una librería de componentes.
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
Tesis_Doctoral_M_Chica Página_70
Trabajos futuros
Uso de preferencias de tipo interactivo para guiarinteractivamente la búsqueda del algoritmo. En particular, g-dominancia [MSHD+09].
Desarrollo de nuevos modelos del TSALBP incluyendonuevas restricciones y características reales (agotamientode los trabajadores, limitaciones de área…).
BLOQUE 1Objetivos
BLOQUE 2Propuesta de MH MO1. MOACO 2. Algoritmos genéticos3. Algoritmos meméticos4. Experimentación
BLOQUE 3Uso de preferencias1. Reducción de soluciones2. Soluciones de interés
BLOQUE 4Conclusiones
BLOQUE 5Trabajos futuros
AGRADECIMIENTOS
TESIS DOCTORALManuel Chica Serrano
Ministerio de Ciencia e Innovación.SIMMRA: Metaheurísticas Mono y Multi-objetivo para Aplicaciones Reales.
TIN2009-07727