Problemas de Asignación Generalizada: modelización, aplicaciones lógicas y métodos de solución

G ( UNIVERSIDAD DE VALLADOLID ESCUELA DE INGENIERIAS INDUSTRIALES Grado en Ingeniería en Organización Industrial Problemas de Asignación Generalizada: modelización, aplicaciones lógicas y métodos de solución Autor: Sesma Gutiérrez, Clara Tutor: Mata Crespo, Raquel DPTO: Estadística e Investigación Operativa Valladolid, Septiembre 2019. 3 AGRADECIMIENTOS Quisiera agradecer en primer lugar a Raquel Mata, mi tutora, pues sin su constante ayuda este trabajo no habría sido posible. Raquel me ha servido de guía durante estos últimos meses, siempre ha estado disponible ya sea mediante tutorías o correos. También considero importante mencionar al profesor Jesús Sáez, cuyas indicaciones contribuyeron a sentar las bases de este trabajo, además de las facilidades que me aportó para realizarlo. Otro tipo de aportación a este trabajo que considero de igual importancia es la ofrecida por mi familia y amigos, que, durante este trabajo y también durante todo el curso, me han dado su apoyo y consejos. 4 5 RESUMEN A lo largo de esta memoria se analizarán problemas de asignación generalizada (GAP) y sus diferentes variantes (embotellamiento o minimax, MGAP, EGAP, MRGAP, GMAP, GQAP, etc.) partiendo de un conjunto de máquinas o agentes para realizar un conjunto de tareas. Cada tarea debe ser asignada a una máquina o agente y existe la posibilidad de que una máquina realice más de un trabajo (tarea) sin sobrepasar la capacidad máxima disponible en cada máquina que no es necesariamente la misma para todas. Se tendrá en cuenta la productividad de la máquina al asignarle un trabajo o tarea. El problema de optimización consistirá en realizar una buena asignación de los trabajos a los recursos existentes, con objeto de maximizar la producción, teniendo en cuenta las distintas restricciones tanto de los trabajos como de las máquinas. Este modelo, y sus generalizaciones, se puede asociar a diversas circunstancias en múltiples contextos teniendo en cuenta su aplicación en Ingeniería de Organización para resolver situaciones de perfil muy amplio, por ejemplo, la asignación de personal a máquinas, herramientas a puestos de trabajos, candidatos a vacantes laborales, vendedores a zonas territoriales etc. En este trabajo, se ha centrado la atención en las aplicaciones logísticas del GAP a diferentes entornos como scheduling, transporte, planificación de la producción y telecomunicaciones, entre otros problemas de optimización combinatorial. Se abordarán métodos de solución exactos y heurísticos, presentándose los resultados experimentales obtenidos con Xpress Mosel. 6 PALABRAS CLAVE GAP, heurísticas, asignación, optimización, búsqueda local. 7 ÍNDICE PORTADA..................................................................................................................... 1 AGRADECIMIENTOS ................................................................................................... 3 RESUMEN .................................................................................................................... 5 PALABRAS CLAVE ...................................................................................................... 6 ÍNDICE .......................................................................................................................... 7 Lista de Figuras ........................................................................................................ 11 Lista de Tablas ......................................................................................................... 13 1. INTRODUCCIÓN Y OBJETIVOS ........................................................................ 15 1.1. Motivación ..................................................................................................... 17 1.2. Introducción del modelo ............................................................................. 18 1.3. Objetivos .................................................................................................... 21 2. DESARROLLO ................................................................................................... 23 2.1. Formulación del modelo .......................................................................... 25 2.2. Extensiones y variantes del GAP ............................................................ 27 2.2.1. BGAP ...................................................................................................... 28 2.2.2. GAP de restricciones de capacidad no lineales .............................. 28 2.2.3. GAP Multinivel ...................................................................................... 28 2.2.4. GAP Elástico .......................................................................................... 29 2.2.5. GAP Dinámico ....................................................................................... 30 2.2.6. GAP Estocástico ................................................................................... 30 2.2.7. GAP Multi-Recursos ............................................................................. 31 2.2.8. Problema de Multiasignación Generalizado .................................... 33 2.2.9. Problema de Asignación Cuadrático Generalizado ........................ 33 2.2.10. GAP con Conjuntos Ordenados Especiales TIPO II ....................... 34 2.2.11. GAP Biobjetivo .................................................................................... 36 8 2.3. Aplicaciones relacionadas con el GAP en la vida real ........................... 37 2.3.1. Aplicaciones en la programación ...................................................... 37 2.3.2. Aplicaciones en el Transporte y creación de rutas ......................... 38 2.3.3. Aplicaciones en Telecomunicaciones ............................................... 39 2.3.4. Aplicaciones en la Planificación de la Producción ......................... 39 2.3.5. Aplicaciones de Localización.............................................................. 42 2.3.6. Aplicaciones de Logísticas de cadena de suministro ..................... 42 2.3.7. Otras Aplicaciones ............................................................................... 44 2.3.8. Tabla resumen ...................................................................................... 45 2.4. Procedimientos de resolución del GAP .................................................... 47 2.4.1. Relajación lineal ................................................................................... 47 2.4.2. Heurística de redondeo ....................................................................... 48 2.4.3. Heurística MT de penalizaciones ....................................................... 49 2.4.4. Métodos de búsqueda local ............................................................... 50 3. ESTUDIO COMPUTACIONAL ............................................................................ 57 3.1. Implementación en Xpress-Mosel......................................................... 59 3.2. Introducción de datos al programa ...................................................... 60 3.3. Resultados ................................................................................................ 62 3.4. Calidad de los resultados .................................................................... 68 4. CONCLUSIONES ................................................................................................ 73 4.1. Resumen de promedios .......................................................................... 75 4.2. Análisis de los resultados ........................................................................ 76 4.3. Conclusiones ............................................................................................. 78 5. FUTURAS EXTENSIONES ................................................................................. 79 5.1. Soluciones aproximadas al GAP ............................................................... 81 5.1.1. Algoritmos de aproximación de tiempo polinomial ....................... 81 9 5.1.2. Algoritmo heurístico tipo Greedy ....................................................... 82 5.1.3. Algoritmos heurísticos de partición de conjuntos ........................... 82 5.1.4. Algoritmos heurísticos de relajación lagrangiana .......................... 83 5.1.5. Relajación mediante programación lineal basada en métodos heurísticos ........................................................................................................ 84 5.1.6. Otros métodos de obtención de una solución aproximada ........... 84 5.2. Algunas metaheurísticas ............................................................................ 86 5.2.1. Búsqueda tabú ..................................................................................... 86 5.2.2. Recocido simulado .............................................................................. 87 5.2.3. Algoritmo genético ............................................................................... 87 5.2.4. Redes neuronales ................................................................................ 88 5.2.5. Colonia de hormigas y GRASP .......................................................... 88 6. BIBLIOGRAFÍA .................................................................................................. 89 16 17 1.1. Motivación La asignación de recursos es un problema complejo que posee gran número de aplicaciones y en campos de trabajo distintos. El denominado Problema de Asignación Generalizado (GAP), y sus distintas variantes, proporciona modelos de optimización necesarios para la resolución de este tipo de problemas tan presentes en la vida cotidiana. Desde mi óptica personal, me empezaron a interesar las cuestiones sobre programación entera y optimización combinatoria en la asignatura de Métodos Cuantitativos en Ingeniería de Organización I, impartida en tercer curso. También utilicé ese mismo curso el entorno de programación de Xpress-Mosel, con el que trabajé durante la citada asignatura resolviendo problemas de optimización. Por otra parte, este curso, en Métodos Cuantitativos en Ingeniería de Organización II, profundizamos en la teoría de los métodos heurísticos de optimización. Estos métodos presentan, como es sabido, la posibilidad de que, aun no hallando la solución óptima del problema, se encuentre una alternativa muy interesante a los métodos exactos. Además, la asignatura de Estadística de primer curso me proporcionó las herramientas necesarias para el análisis de datos, estadísticos y representaciones gráficas del trabajo. Dado el gran número de aplicaciones que en la actualidad tiene el problema de asignación, la resolución de este problema es una importante herramienta para muchas más actividades prácticas relacionadas con este asunto. Dada la complejidad, no obstante, que pueden alcanzar este tipo de problemas, los métodos heurísticos son una herramienta ideal para su resolución, como decíamos anteriormente, puesto que pueden hallar una solución lo suficientemente buena de forma rápida, sencilla y probablemente la más barata. 18 1.2. Introducción del modelo La programación lineal es una herramienta de optimización (maximización y minimización) de gran relevancia para la toma de decisiones. Esta área de las matemáticas se emplea actualmente como apoyo imprescindible dentro del desarrollo empresarial. Tiene gran interés como herramienta financiera, y se utiliza también para la optimización de sistemas de producción, transporte, telecomunicación, servicios públicos etc. En resumen, la aplicación de la programación lineal como herramienta de optimización puede adaptarse a un gran número de campos de trabajo. El Problema de Asignación Generalizada (GAP) es un problema de programación entera cuya finalidad es buscar la asignación óptima de una serie de tareas a un conjunto de recursos de capacidad limitada. Todo problema de optimización incluye tres elementos que son: las variables de decisión, las restricciones que deben cumplir dichas variables y la función objetivo cuyo valor se quiere maximizar o minimizar. La formulación GAP es la siguiente: m: Número de agentes (índice i) n: Número de tareas (índice j) xij: Variables de decisión binarias (1= se asigna la tarea j al agente i, 0=no se asigna la tarea j al agente i) bj: Capacidad del recurso j rij: Necesidad resuelta si el agente i es asignado a la tarea j cij: Coste de asignar la tarea j al agente i 𝑀𝑖𝑛∑∑𝑐𝑖𝑗𝑥𝑖𝑗 (1) 𝑛 𝑗=1 𝑚 𝑖=1 19 s.a. ∑𝑟𝑖𝑗𝑥𝑖𝑗 ≤𝑏𝑖 𝑖 =1,...,𝑚 𝑛 𝑗=1 (2) ∑𝑥𝑖𝑗 =1 𝑚 𝑖=1 𝑗 =1,…,𝑛 (3) 𝑥𝑖𝑗 ∈{0,1} ∀ i,j (4) La función (1) es la función objetivo a minimizar y representa el coste total tras la asignación. En otros casos, la función objetivo es de maximización y, por lo tanto, los coeficientes cij indican los rendimientos. En cualquier caso, la función objetivo está sujeta a las restricciones (2), (3) y (4). La restricción (2) es una inecuación que limita la capacidad de asignar un agente a una determinada tarea. Por otro lado, las restricciones (3) y (4) establecen que toda tarea debe ser ejecutada por un único agente. La resolución del GAP puede alcanzarse mediante algoritmos exactos, obteniendo la solución óptima. Otra opción es el empleo de métodos heurísticos que, de forma más rápida y sencilla, son capaces de hallar una solución que sea suficientemente buena. Existen métodos heurísticos de búsqueda como el Greedy o algoritmo voraz y el algoritmo Martello - Toth. También se emplean heurísticas de mejora como la búsqueda local que, partiendo de una solución factible como puede haberse obtenido tras el empleo de un método de búsqueda como Greedy, mejoran el resultado acercándose al óptimo. Para la aplicación de la búsqueda es necesario definir estructuras de entornos para el problema, donde sobresalen los entornos shift y swap. Otros métodos heurísticos muy empleados son el recocido simulado, basado en la mecánica estadística o los algoritmos genéticos, que recrean la idea de la selección natural para hallar una buena solución. 20 Otra técnica muy empleada en la actualidad debido a su potencia computacional es el empleo de redes neuronales, cuyo objetivo es resolver problemas de igual manera que lo hace el cerebro humano. 21 1.3. Objetivos  Formular el Problema de Asignación Generalizada (GAP) y la definición de los componentes que lo conforman.  Analizar las distintas variantes y extensiones del GAP.  Enumerar las muchas aplicaciones del GAP dentro de diversos campos.  Desarrollar métodos heurísticos para la resolución del GAP de forma aproximada.  Manejar el software Xpress-Mosel para la obtención de resultados e implementación de las heurísticas del GAP.  Obtener soluciones a varios GAP bien conocidos.  Análisis estadístico de los resultados obtenidos con los métodos heurísticos en cuanto a tiempo computacional y calidad de la solución con Statgraphics.  Demostrar la eficacia de la heurística de mejora para hallar una solución al GAP muy próxima a la óptima de forma más rápida y sencilla en base al análisis estadístico de los datos obtenidos. 22 23 2. DESARROLLO 24 25 2.1. Formulación del modelo Existen un gran número de problemas con una estructura similar al GAP. Este hecho ha derivado en la creación de una serie de estudios que tratan de clasificarlos. En este trabajo se ha considerado al GAP como un caso especial del WAP (Weight Problem Assignament). El WAP encuentra la asignación óptima cuando cada tarea es asignada a un único agente. Además, cada tarea debe ser realizada en un determinado nivel de ejecución; introduciéndose la variable xijk , cuyo valor es igual a 1, solo si la tarea j es completada por el agente i al nivel de ejecución k, y 0 en caso contrario. La formulación del WAP es la siguiente: 𝑀𝑖𝑛 𝑓(𝑥)=∑∑ ∑ 𝑐𝑖𝑗𝑘𝑥𝑖𝑗𝑘 𝑘𝜖𝑘𝑖𝑗 𝑛 𝑖=1 𝑚 𝑗=1 (5) s.a. ∑ ∑ 𝑥𝑖𝑗𝑘 =1 𝑗 = 1,…,𝑛 (6) 𝑘∈𝑘𝑖𝑗 𝑚 𝑖=1 𝑎𝑖≤∑ ∑ 𝑟𝑥𝑖𝑗𝑘𝑥𝑖𝑗𝑘 𝑘∈𝑘𝑖𝑗 ≤𝑏𝑖 𝑖 = 1,…,𝑚 (7) 𝑛 𝑖=1 ∑ ∑ 𝑠𝑖𝑗𝑘 𝑘∈𝑘𝑗 𝑥𝑖𝑗𝑘             = 𝑒𝑗 𝑗 =1,…,𝑛 (8) 𝑚 𝑗=1 𝑥𝑖𝑗𝑘 ∈{0,1} ∀ i,j,k. (9) 32 disponibles las unidades de recurso biq y la tarea j requiere rijq unidades del recurso q usadas por el agente i. Una aplicación típica del MRGAP surge resolviendo el conocido Problema de Enrutamiento de Vehículos o VRP (Vehicle Routing Problem), donde la capacidad del vehículo se define por volumen y peso. Otras aplicaciones del MRGAP aparecen en sistemas de computación distribuida, programación “job shop”, diseño de red de telecomunicaciones o diseño de carga y almacén. Se ha estudiado el MRGAP dinámico, donde la demanda de tareas cambia a lo largo del tiempo y la capacidad de asignación es dinámica. Una variante sería el GAP de capacidad conjunta (CCGAP), en el que las diferentes restricciones de recursos están conjuntamente asociadas con todos los agentes en lugar de con cada agente de forma individual. Una aplicación de este GAP en la vida real se encuentra en el Problema de Asignación de Recursos donde el presupuesto y el equipo están conjuntamente restringidos para todos los agentes. Existe una extensión del MRGAP: el MRGAP con instalaciones (MRGAPS). La diferencia con el MRGAP reside en que el MRGAPS permite la división de lotes (tareas) entre las diferentes máquinas (agentes). La función objetivo de esta ampliación añade el efecto de la implantación de tiempos y costes. El MRGAPS tiene interés en ambientes de fabricación repetitivos. Otra aplicación del MRGAP es el problema de asignación de eliminación de nieve o SDAP (Snow Disponsal Assignment Problem). El problema intenta encontrar la óptima asignación de lo lugares donde remover la nieve y los lugares donde almacenarla. Los recursos necesarios para este problema son la capacidad de nieve anual y la tasa máxima de recepción. 33 2.2.8. Problema de Multiasignación Generalizado El Problema de Multiasignación Generalizado o GMAP (Generalized Multiassignment Problem) es una generalización del GAP. En el GMAP, las restricciones de asignación (2) del GAP son sustituidas por: ∑𝑥𝑖𝑗 ≥𝑡𝑗 𝑗 = 1,...,𝑛 𝑚 𝑖=1 (17) Donde tj es un parámetro tal que tj ≤ n para j=1, …, n. El Problema de multiasignación, por lo tanto, cuando tj = 1, se convierte en el GAP clásico. Para la resolución de este tipo de GAP se propone una Lagrangiana doble basada en el algoritmo de ramificación y poda. Este problema permite la asignación de un ítem a diferentes mochilas. Una aplicación real de este problema es un sistema de bases de datos distribuida donde cada carpeta es almacenada en múltiples lugares por motivos de seguridad y con rápida velocidad de respuesta. Otra aplicación desarrollada paralelamente sería el software de procesamiento de una instrucción múltiple, flujo de datos múltiple o MIMD (Multiple Instruction Multiple Data Stream). Se trata de un sistema informático donde múltiples copias de programas son ejecutadas desde distintos procesadores conectados en red. 2.2.9. Problema de Asignación Cuadrático Generalizado El Problema de Asignación Cuadrático Generalizado o GQAP (Generalized Quadratic Assignment Problem), trata la asignación de un conjunto de 34 instalaciones j=1, …, n a un conjunto de destinos i=1, …, m de modo que se minimiza el coste de asignación y de transporte y el peso total de todas las instalaciones asignadas al mismo destino, no pudiendo exceder su capacidad. En el GQAP la función objetivo (1) del GAP clásico es sustituido por la siguiente función: 𝑚𝑖𝑛∑∑𝑐𝑖𝑗 +𝛾 𝑛 𝑗=1 𝑚 𝑖=1 ∑∑∑∑𝛼𝑖𝑜𝛽𝑗𝑝𝑥𝑖𝑗𝑥𝑜𝑝 (18) 𝑛 𝑝=1 𝑚 𝑜=1 𝑛 𝑗=1 𝑚 𝑖=1 Donde αio es la distancia entre situaciones o e i, βjp es la intensidad de tráfico entre instalaciones p y j y γ es la unidad de coste de trasporte. Una aplicación real del GQAP se encuentra en la determinación de la localización de los equipos dentro de una industria, lo que marca el recorrido de las piezas y por lo tanto el coste de transporte: la función objetivo a minimizar. Otra aplicación del GQAP sería la gestión del patio de contenedores donde el problema es la localización del grupo de contenedores en el área de almacenamiento, de modo que se minimicen las maniobras de movimiento. 2.2.10. GAP con Conjuntos Ordenados Especiales TIPO II Un conjunto de variables (x1, x2, …, xn) es un conjunto especial ordenado de tipo II si xixj=0 siempre que |i-j| ≥ 2. El GAP con Conjuntos Ordenados Especiales de Tipo II, o GAPS2 (GAP Special Ordered Sets of Type II) trata de la asignación de tareas a periodos de tiempo. La variable de decisión xij indica 35 la fracción de tareas j asignadas a un periodo de tiempo i. El GAPS2 se obtiene reemplazando las restricciones (4) del GAP clásico por una de las siguientes funciones: {𝑥𝑖−1𝑗 =0 𝑎𝑛𝑑 𝑥𝑖+1𝑗 =1−𝑥𝑖𝑗} 𝑜𝑟 {𝑥𝑖+1𝑗 = 0 𝑎𝑛𝑑 𝑥𝑖−1𝑗 =1−𝑥𝑖𝑗} (19) Es importante resaltar que, en el GAPS2, cualquier tarea puede ser ejecutada dentro de un periodo de tiempo, pero también podría dividirse entre dos periodos de tiempo consecutivos. Una aplicación del GAPS2 sería la programación de la producción de cables de fibra óptica donde se permite compartir los trabajos entre periodos de tiempo adyacentes. Una propuesta de método de solución exacto para este problema se basa en aproximaciones poliédricas, con las cuales se han resuelto pequeños ejemplos de optimización. También se ha propuesto un sencillo método heurístico de programación lineal para la resolución del GAPS2. Una aplicación del GAPS2 podría surgir de la acumulación y/o distribución de la carga de vehículos donde está permitido dividir la carga entre dos localizaciones vecinas, pero no está permitido realizar sucesivas operaciones de carga/descarga en un viaje determinado. Este problema podría surgir debido a las restricciones del tiempo de operaciones de carga/descarga de bienes perecederos. 36 2.2.11. GAP Biobjetivo Para la resolución del GAP Biobjetivo o BiGAP (Biobjetive GAP), existe un método heurístico de programación lineal. La función objetivo de este problema es la siguiente: 𝑚𝑎𝑥∑∑𝑐𝑖𝑗 𝑙𝑥𝑖𝑗 𝑛 𝑗=1 𝑚 𝑖=1 𝑙 =1,2. (20) Una aplicación del BiGAP se encuentra en la planificación del sistema de producción, donde - c1ij y –c2ij representan respectivamente el coste y tiempo cuando el trabajo j es asignado a la máquina i. Otra aplicación sería en la planificación de las zonas de los servicios de emergencia, donde - c1ij y –c2ij representan respectivamente las ganancias y los costes de los transportes debidos a la asignación de la zona j (cliente) a la unidad de servicio i (vehículo). 37 2.3. Aplicaciones relacionadas con el GAP en la vida real Se han mencionado anteriormente varias aplicaciones del GAP. A continuación, se tratarán algunos de los problemas ya mencionados y otras aplicaciones que forman parte de problemas más densos. 2.3.1. Aplicaciones en la programación Muchas de las aplicaciones del GAP tienen lugar en los problemas de programación. Programación de empleados, máquinas, tareas de multiprocesadores, planificación de la mano de obra, aulas, lotes etc. Un problema de programación que incluye al GAP como un subproblema se desarrolla dentro de un proyecto de redes. Por ejemplo, en el Problema de Asignación del Trabajo con restricciones no preventivas de recursos. El objetivo es encontrar el coste mínimo de la asignación de un conjunto de recursos (trabajadores) a un periodo limitado de tiempo. Trabajos y recursos están considerados respectivamente como ítems y como mochilas. El Problema de Equilibrio de Carga es otra extensión del GAP. El problema es encontrar la asignación óptima de un conjunto de trabajos a un conjunto de máquinas. Pueden usarse diferentes tipos de función objetivo para este problema: la minimización del makespan, la minimización de la media del tiempo de flujo, o la maximización de la equidad en el trabajo asignado. Una propiedad importante de este problema es que cada trabajo se asume que tiene una unidad de tiempo de procesamiento. 38 2.3.2. Aplicaciones en el Transporte y creación de rutas A principios del siglo XX se empleó el GAP para el transporte de pacientes entre hospitales militares en los Estados Unidos. Con el GAP se determinó la asignación de pacientes con vuelos. La función objetivo buscaba minimizar molestias a los pacientes, sabiendo el número de días que los pacientes pasarían la noche en el hospital. El segundo objetivo para minimizar era el tiempo de vuelo o longitud de la ruta. El GAP aparece como subproblema en el conocido VPR (Problema de Enrutamiento de Vehículos), mediante la asignación de ciudades a posiciones preseleccionadas. También para el problema TSP (problema del vendedor viajero). Como aplicación dentro de la política de una empresa se propone el TP, un caso especial del problema de transporte y, por lo tanto, una variante del GAP. El TP se basa en que cada punto de demanda (cliente) requiere satisfacer sus necesidades (proveedor) de un único recurso, sin exceder la cantidad máxima de recursos que el proveedor puede suministrar. El objetivo es minimizar el coste total asociado al material transportado de los recursos asignados a los puntos de demanda. Para este caso, la restricción de que cada cliente debe ser asignado a un único recurso se cumple con la fórmula (3). Sin embargo, particularidad de este problema radica en que rj=rij para todo i=1, …, m y j=1, …, n. En 1997 surgió una variación del GAP a causa de las actividades de una industria en Nueva Zelanda: el Problema de Asignación Cubierto o CAP (Covering Assignment Problem). El problema se desarrolla por la demanda diaria de leche que las compañías suministraban de diferentes granjas. El CAP determinó la localización granjas (proveedores) a industrias (clientes), con el mínimo coste de transporte, de manera que cada granja fuera asignada a una única industria y la demanda de cada industria pudiera satisfacerse. En el CAP la restricción de los parámetros rj=rij para todo i=1, …, m y j=1, …, n se mantiene y la restricción (2) pasa a ser de tipo “≥”. 39 2.3.3. Aplicaciones en Telecomunicaciones La aplicación del GAP en telecomunicaciones tuvo lugar por primera vez en 2003 para optimizar el protocolo de vuelta de enlace de frontera o BGP (Border Gateway Protocol) y su uso en el enrutamiento de dominios minimizando el coste de enrutamiento del tráfico. El BGP juega un papel importante en el control del flujo de tráfico entre clientes y proveedores Otra aplicación del GAP en telecomunicaciones, creada como una extensión del GAP, es la máxima cobertura de multiplexación de código de acceso a red de telecomunicaciones con restricciones de capacidad (potencia y flujo). El problema trata de encontrar la asignación óptima de terminales a estaciones base. 2.3.4. Aplicaciones en la Planificación de la Producción Hay muchas aplicaciones del GAP dentro de la Planificación de la Producción. El problema NP-Complejo de Carga y Programación de Lotes, puede dividirse en dos problemas anidados: carga de lotes y programación de lotes. El Problema de Cargas por Lotes o BLP (Batch Loading Problem) con una secuencia de lotes determinada, halla la asignación óptima entre trabajos y lotes. El Problema de Programación de Lotes es el problema de secuenciación de lotes. El mencionado BLP es un caso especial del GAP con aij = rij donde aj es el volumen de trabajo j y b = bj donde b es del procesador, xij = 1 solo si el trabajo j es asignado al lote i. Sin embargo, la función del coste del BLP es mucho más complicada y difícil de manejar que la función de coste del GAP. 40 El GAP también tiene aplicaciones dentro de la Tecnología de Grupo o GT (Group Technology). Relacionado con la de asignación de máquinas y los problemas de formación de células. En el Problema de Asignación de Máquinas o MAP (Machine Assignment Problem) el objetivo es minimizar el coste de utilización del emplazamiento de las máquinas y el coste de movimiento entre células. La primera restricción del MAP sería que al menos un tipo de máquina debe estar ubicada en cada célula. La segunda restricción impondría que el tiempo total de operación del conjunto de máquinas asociadas a una máquina sea menor que el tiempo disponible de operación de la célula. Una de las soluciones factibles para el MAP se basa en la estructura del GAP, mediante la resolución de un problema mochila para cada célula. El objetivo de la función es cuadrático y minimiza el coste de los movimientos entre células. Las restricciones son exactamente las mismas que el GAP (2)-(4) con rij = 1. Una gran aplicación del GAP surge en GT donde la división eficiente de la fabricación de piezas en familias, llamado Problema de Formación de Grupos o GFP (Group Formation Problem), el cual juega un papel importante en todos los sistemas de evaluación. Este problema es una generalización del Problema de Generalizado de Formación de Grupos o GGFP, equivalente al GAP. Ambos, GFP y GGFP, intentan asignar cada pieza a una única familia de piezas, maximizando la suma total de similitudes entre piezas asignadas a una familia. Una variante del GAP encuentra aplicación en los sistemas de recuperación y almacenamiento automatizados (AS/AR). Suponiendo como datos conocidos al conjunto de tipos ítems pedidos y la frecuencia de procesamiento de pedidos durante el horizonte de planificación del conjunto de ítems, cada pedido se almacena independientemente a un tiempo y conjunto de movimientos determinados de la máquina de recuperación y almacenamiento. La máquina de recuperación y almacenamiento es capaz de realizar un movimiento simultáneo vertical y horizontal y cada localización de almacenamiento es uniforme y puede contener solo un tipo de ítem. 41 El Problema de Distribución de Almacenamiento consiste en optimizar la determinación de las localizaciones de los pedidos durante el horizonte de planificación, de modo que cada localización de almacenamiento contenga un único ítem y cada ítem i sea asignado a un número fijo de localizaciones. La función objetivo busca minimizar el total de tiempo de recogida de pedidos por periodo de la máquina de recuperación y almacenamiento. El Problema de Selección de Orden Multicriterio en Sistemas de Manufacturación Flexible (FMSs) trata de encontrar la asignación de un conjunto de pedidos a un conjunto de periodos minimizando costes debidos tanto al tiempo como a la subcontratación. Los costes por anticipación y por tardanza se calculan empleando la fecha de vencimiento. El coste de subcontratación se añade cuando el pedido no es asignado durante el horizonte de planificación (el conjunto de los periodos) por las restricciones de capacidad. Las restricciones de capacidad se deben a la capacidad de la máquina y del almacén de herramientas. Para adoptar técnicas de relajación Lagrangiana eficientes se ha propuesto una formulación de programación binaria del problema original, considerando la subcontratación añadiendo un periodo virtual al horizonte de planificación y redefiniendo por consiguiente los parámetros de la función objetivo. El Problema de Programación de Lote Económico para múltiples productos en procesadores paralelos idénticos o MELSP (Economic Lot Scheduling Problem) es otro problema donde el GAP actúa como un subproblema durante el proceso de solución. El MELSP determina el óptimo tamaño de lotes y programa para un número de productos, varios procesadores paralelos idénticos. Esto convierte al MELPS en un GAP no lineal. Para la resolución de este problema se propone un algoritmo heurístico, el cual resuelve el GAP clásico en cada iteración. 48 soluciones fraccionales obtenidas. Esta segunda opción lleva a la generación de un ciclo. Para hallar soluciones más precisas en la relajación lineal se utiliza el método de Ramificación y Acotamiento (Branch & Bound). Este algoritmo genera dos subproblemas a partir de la solución no factible (fraccionaria) mediante la adición de restricciones. El algoritmo continuará creando y descartando la solución de los subproblemas hasta dar con una solución óptima factible. En general la relajación lineal, al ser un problema de programación lineal, es mucho más fácil de resolver que el problema original de programación entera. En Xpress-Mosel, si en vez del óptimo entero estamos interesados en el óptimo lineal (o valor de la relajación lineal), para maximizar un objetivo con nombre ganancia_total basta sustituir el comando maximize(ganancia_total) por un comando como: maximize(XPRS LIN,ganancia_total). 2.4.2. Heurística de redondeo Esta heurística trata simplemente de buscar la solución menor entera al problema. Se trata de un algoritmo muy sencillo que no suele proporcionar una buena solución, de hecho, por lo general se suele encontrar una solución bastante alejada del óptimo. El pseudocódigo implementado dentro del programa es el siguiente: forall (i in maquinas, j in tareas) xp(i,j) := integer (floor (x(i,j).sol)) zp: = sum (i in maquinas, j in tareas) p(i,j) * xp(i,j) writeln ("\n\tzp = ",zp) Siendo floor una función propia de la librería de Xpress que toma la parte entera de la solución al problema (.sol). 49 2.4.3. Heurística MT de penalizaciones El método de penalizaciones se conoce también como el algoritmo Martello - Toth. Es una heurística voráz o greedy, la cual en cada paso escoge la solución óptima. La heurística greedy avanza sin tener en cuenta las consecuencias posteriores, únicamente toma la solución óptima en cada momento, por lo que se dice que es un algoritmo miope. Este método utiliza las siguientes notaciones: Conjunto de tareas: 𝑁 ={1,...,𝑛} Conjunto de agentes o máquinas: 𝑀 = {1,...,𝑚} Conjunto de tareas sin asignar: U ⊆ N Número de tareas asignadas: na Capacidad del agente i: bi Agente asignado a la tarea j: yj Valor objetivo de la solución heurística: z Variable binaria que indica si una solución es factible (1) o no (0): feas El algoritmo se desarrolla en tres etapas: 1. Inicialización. El algoritmo comienza con na = 0, z = 0 y feas =1. 50 2. Finalización. Si feas =1 y na = n el método da la solución final. Si feas = 0 el algoritmo termina sin haber hallado una solución factible. La tercera posibilidad se da cuando feas = 1 y na < n el algoritmo continúa con la siguiente etapa. 3. Penalizaciones. Si no hay ningún agente con la capacidad suficiente para realizar la tarea j (nkj = 0) entonces feas = 0 y el algoritmo termina sin haber encontrado una solución factible. Si nkj = 1 la penalización pj toma el valor ∞. Si nkj ≥ 2, pj se define como la diferencia entre el segundo menor y el menor coeficiente cij. La tarea j* con la penalización pj máxima se asigna entonces a la máquina i* con menor coeficiente cij. 2.4.4. Métodos de búsqueda local Los procedimientos de mejora basados en estrategias de búsqueda local son los más usados. Este tipo de métodos se encargan de buscar la mejora de una solución inicial factible, como la que puede obtenerse tras aplicar, por ejemplo, un método greedy como el anterior. El método se basa en la exploración de un entorno mediante movimientos. Estos movimientos son operaciones que el algoritmo emplea sobre la solución para hallar soluciones de su entorno. Para un problema de optimización que busca la minimización de una función f(x), se considera que el x pertenece al conjunto X que representa el conjunto de todas las soluciones factibles. Un mínimo global es una solución x* Є X cumpliendo que f(x∗) ≤ f(x), ∀x Є X. 51 Bases de la búsqueda local: 1. Definición de entorno: Cada solución x Є X es un mínimo local respecto del sistema de entornos N(x) ⊆ X, que denominaremos entorno de x. 2. Definición de mínimo local: Una solución x* Є X es un mínimo local respecto del sistema de entornos N(x), si se verifica que f(x*) ≤ f(x) ∀x Є N(x*). 3. Definición de movimiento: Dada una solución x Є X, cada solución en su entorno x’ Є N(x) puede obtenerse directamente a partir de x mediante la operación llamada movimiento. Un procedimiento de búsqueda local parte de una solución inicial x0, examina su entorno N(xo) y escoge una nueva solución x1 Є N(x0), es decir, realiza un movimiento. Este proceso puede aplicarse de forma reiterada, obteniendo una trayectoria: 𝑥1→𝑥2→ ... → 𝑥𝑛 Si un método de búsqueda por entornos solo permite movimientos en el entorno de la solución inicial para hallar el óptimo, se denomina un método de descenso. El método de descenso procede de la siguiente forma: 1. Se escoge x Є X para iniciar el proceso. 2. Se busca x’ Є N(x) tal que f(x’) < f(x). 52 3. Si no se puede encontrar un x’ Є N(x) tal que f(x’) < f(x), se termina, pues x es un óptimo local. 4. En otro caso, se sustituye x por x’ y se vuelve a la etapa 2. Un método de descenso finaliza en un óptimo local, que es mejor o igual que todas las soluciones de su entorno. El defecto de este método es que no garantiza la obtención de un óptimo global. Pueden existir un gran número de óptimos locales y el método de descenso no permite determinar si a su vez también se tratan de un óptimo global. *Imagen 2: Máximo global y local Existen distintas versiones del método de descenso. Una de estas versiones se trata del método de mayor descenso (steepest descent o best improvement). El método del mayor descenso requiere examinar completamente el entorno de la solución x para obtener el menor f(x’) sobre x’ Є X. Si N(x) contiene muchos elementos, puede ser preferible un método 53 llamado first improvement, que consiste en seleccionar el primer movimiento que produce una mejora de la solución actual. En cualquiera de sus versiones este método termina en un óptimo local. Para realizar un método de búsqueda local es necesario la definición previa de una o varias estructuras de entornos. Los entornos que se utilizan son: 1. Entorno Shift o de cambio. Este movimiento consiste en, dada solución, cambiar la asignación de una tarea a otro agente diferente. 2. Entorno Swap o de intercambio. Este movimiento consiste en el intercambio de las asignaciones a dos tareas. *Imagen 3: Explicación gráfica del entorno Shift *Imagen 4: Explicación gráfica del entorno Swap 54 La utilización de ambos entornos permite diseñar algoritmos heurísticos para el GAP, comenzando con la solución obtenida de la heurística de Martello-Toth y aplicando posteriormente la búsqueda local. En algunas ocasiones es posible garantizar que un óptimo local se trata a su vez de un óptimo global mediante un método de descenso. Si la función objetivo f(x) es convexa y el conjunto factibles X es convexo, todo mínimo local es un mínimo global y un método de descenso converge al mínimo global. Un método de búsqueda local necesita, además de la definición la estructura de los entornos, un criterio de selección de una solución dentro del entorno. La definición de entorno o movimiento depende de la estructura del problema a resolver y de como sea la función objetivo. El pseudocódigo del procedimiento de búsqueda local con intercambios y best-improvement en lenguaje Mosel es el siguiente: final:=0 while(final = 0)do mejora_max:=-M (siendo M un número suficientemente grande) forall(j, k in 1..n|x(j)=1 and x(k)=0)do x1(j):=0 x1(k):=1 forall(i in 1..n|i<>j and i<>k x1(i):=x(i) !se calcula f(x1) mejora:= f(x) - f(x1) if(mejora > mejora_max)then mejora_max:= mejora jmax:=j kmax:=k end-if 55 end-do if(mejora_max <=0)then final:=1 else ! se hace el intercambio: x(jmax):=0 x(kmax):=1 end-if end-do Donde f(x) es la función objetivo a minimizar y la solución está dada mediante un vector x Є {0,1}𝑛. En el caso de aplicar los dos entornos, pueden aplicarse de forma secuencial o con un método de descenso VNS o Búsqueda por entornos variables (Variable Neightbour Search). El método VNS se basa en: 1. Un mínimo local para una estructura de entornos no lo es necesariamente para otra. 2. Un mínimo global tiene que ser un mínimo local para todas las posibles estructuras de entornos. El método llamado “Búsqueda por Entornos Variables Descendientes” se trata de encontrar un mínimo local respecto a todas las estructuras de entorno. Se inicia con una solución x y se toma k = 1. Repetir hasta que k = p los pasos: 56 1. Exploración del entorno. Encontrar la mejor solución x’ del k-ésimo entorno NK(x). 2. Decisión de moverse o no. Si la solución obtenida x’ es mejor que x, se toma x = x’ y k = 1. En otro caso, se toma k = k + 1. Para este método se suelen emplear p=2 o p=3 entornos. Existen otras variantes como VNS Reducida, VNS Básica, VNS General o VNS Anidada. Sin embargo, de ninguna forma, este método garantiza que el óptimo local sea también el óptimo global del problema. El problema que presentan los métodos de búsqueda local es la posibilidad que quedarse atrapado en un óptimo local que se distancie enormemente del óptimo global del problema. Este hecho hace imprescindible añadir un mecanismo que impida la creación de ciclos, en el cual aparezcan soluciones ya obtenidas. También es necesario establecer un criterio de parada, pues el procedimiento podría iterar indefinidamente. Los procedimientos metaheurísticos solucionan los problemas anteriores y además son capaces de conducir la búsqueda de forma inteligente. Estos métodos suelen ser muy rápidos y proporcionan soluciones relativamente cerca del óptimo global. Además, se suelen emplear métodos de búsqueda local para inicializar otras metaheurísticas más complejas como la Búsqueda Tabú o el Recocido Simulado, que se considerarán en las futuras extensiones de esta memoria. 57 3. ESTUDIO COMPUTACIONAL 64  GAP2 (5 х 20) *Tabla 3: Resultados del GAP2 Método Solución óptima entera Relajación lineal Heurística de redondeo Heurística MT de penalizaciones Mejora Búsqueda local GAP2_1 Solución 434 444,03 414 393 413 Tiempo 0,015 0,022 0 0 0 GAP2_2 Solución 436 446,916 374 399 424 Tiempo 0,038 0,015 0 0 0 GAP2_3 Solución 420 425,133 384 373 422 Tiempo 0,031 0,016 0 0 0 GAP2_4 Solución 419 428,329 399 376 414 Tiempo 0,019 0,035 0 0 0 GAP2_5 Solución 428 431,828 428 402 418 Tiempo 0,019 0,018 0 0,001 0 Media Solución 427 435,2472 399,8 388,6 418,2 Tiempo 0,0244 0,0212 0 0,0002 0 65  GAP10 (10 х 40) *Tabla 4: Resultados del GAP10 Método Solución óptima entera Relajación lineal Heurística de redondeo Heurística MT de penalizaciones Mejora Búsqueda local GAP10_1 Solución 958 962,743 958 879 949 Tiempo 0,053 0,015 0 0,003 0,004 GAP10_2 Solución 963 973,219 938 836 954 Tiempo 0,292 0,015 0 0,003 0,008 GAP10_3 Solución 960 967,403 936 884 945 Tiempo 0,063 0 0 0,015 0 GAP10_4 Solución 947 950,689 901 833 937 Tiempo 0,063 0,016 0 0 0,015 GAP10_5 Solución 947 955,951 600 847 941 Tiempo 0,217 0,022 0,015 0 0 Media Solución 955 962,001 866,6 855,8 945,2 Tiempo 0,1376 0,0136 0,003 0,0042 0,0054 66  GAP11 (10 х 50) *Tabla 5: Resultados del GAP11 Método Solución óptima entera Relajación lineal Heurística de redondeo Heurística MT de penalizaciones Mejora Búsqueda local GAP11_1 Solución 1139 1145,03 1069 1004 1120 Tiempo 0,047 0,015 0 0,016 0 GAP11_2 Solución 1178 1183,87 1132 1028 1164 Tiempo 0,047 0,015 0 0,022 0,011 GAP11_3 Solución 1195 1197,45 1171 1085 1186 Tiempo 0,037 0,016 0 0,004 0,01 GAP11_4 Solución 1171 1179,68 1037 1011 1140 Tiempo 0,173 0,019 0 0,006 0,009 GAP11_5 Solución 1171 1176,46 1147 1014 1151 Tiempo 0,205 0,018 0,001 0,004 0,012 Media Solución 1170,8 1176,498 1111,2 1028,4 1152,2 Tiempo 0,1018 0,0166 0,0002 0,0104 0,0084 67  GAP12 (10 х 50) *Tabla 6: Resultados del GAP12 Método Solución óptima entera Relajación lineal Heurística de redondeo Heurística MT de penalizaciones Mejora Búsqueda local GAP12_1 Solución 1451 1454,07 1451 1320 1431 Tiempo 0,044 0,019 0 0,006 0,021 GAP12_2 Solución 1449 1453,84 1449 1308 1435 Tiempo 0,111 0,023 0 0,006 0,022 GAP12_3 Solución 1433 1436,83 1316 1266 1412 Tiempo 0,079 0,021 0,001 0,006 0,017 GAP12_4 Solución 1447 1450,06 1374 1301 1419 Tiempo 0,055 0,021 0,001 0,007 0,017 GAP12_5 Solución 1446 1451,91 1377 1293 1424 Tiempo 0,126 0,02 0 0,007 0,015 Media Solución 1445,2 1449,342 1393,4 1297,6 1424,2 Tiempo 0,083 0,0208 0,0004 0,0064 0,0184 68 3.4. Calidad de los resultados Para poder comparar la proximidad de los resultados es necesario contrastarlos con las soluciones óptimas reales. Las soluciones óptimas a los problemas considerados también se encuentran en la página web y se comprueba que coinciden con los resultados alcanzados con Xpress Mosel. Estas soluciones se resumen a continuación para cada grupo de problemas del estudio computacional: GAP1 GAP2 *Tabla 7: Solución óptima a GAP1 *Tabla 8: Solución óptima a GAP2 GAP10 GAP11 *Tabla 9: Solución óptima a GAP10 *Tabla 10: Solución óptima a GAP11 Problema Solución óptima GAP1_1 336 GAP1_2 327 GAP1_3 339 GAP1_4 341 GAP1_5 326 Problema Solución óptima GAP2_1 434 GAP2_2 436 GAP2_3 420 GAP2_4 419 GAP2_5 428 Problema Solución óptima GAP10_1 958 GAP10_2 963 GAP10_3 960 GAP10_4 947 GAP10_5 947 Problema Solución óptima GAP11_1 1139 GAP11_2 1178 GAP11_3 1195 GAP11_4 1171 GAP11_5 1171 69 GAP12 *Tabla 11: Solución óptima a GAP12 Los errores calculados para cada GAP se muestran en las tablas que aparecen a continuación, en las que se considera un porcentaje indicador del hueco de la solución, definido para las heurísticas como: Hueco= 𝑆𝑜𝑙𝑢𝑐𝑖ó𝑛 ó𝑝𝑡𝑖𝑚𝑎−𝑆𝑜𝑙𝑢𝑐𝑖ó𝑛 ℎ𝑒𝑢𝑟í𝑠𝑡𝑖𝑐𝑎 𝑆𝑜𝑙𝑢𝑐𝑖ó𝑛 ó𝑝𝑡𝑖𝑚𝑎 𝑥100 Y para la relajación como: Hueco= 𝑆𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑟𝑒𝑙𝑎𝑗𝑎𝑐𝑖ó𝑛−𝑆𝑜𝑙𝑢𝑐𝑖ó𝑛 ó𝑝𝑡𝑖𝑚𝑎 𝑆𝑜𝑙𝑢𝑐𝑖ó𝑛 ó𝑝𝑡𝑖𝑚𝑎 𝑥100 Por lo tanto, el resultado obtenido será el porcentaje en el que varía la solución obtenida mediante la heurística con la solución óptima siendo un 0% una coincidencia exacta. Problema Solución óptima GAP12_1 1451 GAP12_2 1449 GAP12_3 1433 GAP12_4 1447 GAP12_5 1446 70  GAP1 GAP1_1 GAP1_2 GAP1_3 GAP1_4 GAP1_5 Media Relajación lineal 2,26 3,79 3,15 2,76 3,00 2,99 Heurística de redondeo 14,58 0,00 54,28 0,00 78,53 29,48 Heurística MT de penalizaciones 9,82 3,98 7,96 5,57 9,20 7,31 Mejora. Búsqueda local 2,68 0,92 3,83 5,57 2,15 3,03 *Tabla 12: Media del error calculado en GAP1  GAP2 GAP2_1 GAP2_2 GAP2_3 GAP2_4 GAP2_5 Media Relajación lineal 2,31 2,50 1,22 2,23 0,89 1,83 Heurística de redondeo 4,61 14,22 8,57 4,77 0,00 6,43 Heurística MT de penalizaciones 9,45 8,49 11,19 10,26 6,07 9,09 Mejora. Búsqueda local 4,84 2,75 -0,48 1,19 2,34 2,13 *Tabla 13: Media del error calculado en GAP2 71  GAP10 GAP10_1 GAP10_2 GAP10_3 GAP10_4 GAP10_5 Media Relajación lineal 0,50 1,06 0,77 0,39 0,95 0,73 Heurística de redondeo 0,00 2,60 2,50 4,86 36,64 9,32 Heurística MT de penalizaciones 8,25 13,19 7,92 12,04 10,56 10,39 Mejora. Búsqueda local 0,94 0,93 1,56 1,06 0,63 1,03 *Tabla 14: Media del error calculado en GAP10  GAP11 GAP11_1 GAP11_2 GAP11_3 GAP11_4 GAP11_5 Media Relajación lineal 0,53 0,50 0,21 0,74 0,47 0,49 Heurística de redondeo 6,15 3,90 2,01 11,44 2,05 5,11 Heurística MT de penalizaciones 11,85 12,73 9,21 13,66 13,41 12,17 Mejora. Búsqueda local 1,67 1,19 0,75 2,65 1,71 1,59 *Tabla 15: Media del error calculado en GAP11 72  GAP12 GAP12_1 GAP12_2 GAP12_3 GAP12_4 GAP12_5 Media Relajación lineal 0,21 0,33 0,27 0,21 0,41 0,29 Heurística de redondeo 0,00 0,00 8,16 5,04 4,77 3,60 Heurística MT de penalizaciones 9,03 9,73 11,65 10,09 10,58 10,22 Mejora. Búsqueda local 1,38 0,97 1,47 1,94 1,52 1,45 *Tabla 16: Media del error calculado en GAP12 73 4. CONCLUSIONES 80 81 5.1. Soluciones aproximadas al GAP 5.1.1. Algoritmos de aproximación de tiempo polinomial El primer algoritmo de aproximación conocido para el GAP fue propuesto en 1993. El GAP se definió como un problema de programación de una máquina en paralelo donde el objetivo es encontrar el mínimo coste al asignar cada trabajo j a una única máquina i, en un tiempo de procesamiento rij y un coste de procesamiento cij, de tal modo que la restricción de capacidad (tiempo disponible) de la máquina i, bi, no sea excedido. Dado un valor C, se ideó un plan de aproximación de tiempo polinomial el cual o prueba la no existencia de una asignación factible (programa) con coste C o la generación de una asignación (programa) de coste máximo C donde la capacidad de uso de cada máquina i sea como máximo de 2bi unidades. Otra variante del GAP trata de, dado un conjunto de mochilas con diferentes capacidades y un conjunto de ítems de pesos diferentes y valores diferentes para cada mochila, encontrar un subconjunto de ítems que pueda asignarse a la mochila y que maximice el valor. Para su solución se propone un algoritmo basado en programación lineal con una aproximación e/e – 1 + ε donde ε es una constante positiva y es la base de la función logarítmica natural. Otro caso especial del GAP similar al anterior sería el máximo beneficio del GAP con beneficio fijo. En este caso, cada ítem j tiene un beneficio fijo pj cada mochila i. Por lo tanto, la función objetivo es la siguiente: 𝑚𝑎𝑥∑∑𝑝𝑗𝑥𝑖𝑗 (20) 𝑛 𝑗=1 𝑚 𝑖=1 El algoritmo de aproximación propuesto para este problema es (1 – 1/e). 82 5.1.2. Algoritmo heurístico tipo Greedy Este método surge de considerar una medida de conveniencia de maximizar el problema (fij) de asignar una tarea j a un agente i. El algoritmo heurístico considera de forma iterativa todas las tareas no asignadas y escoge una tarea j que tenga la máxima diferencia entre los dos fij menores. Esta tarea será asignada a un agente buscando el menor fij. Tras la aplicación de este algoritmo heurístico, se emplea un plan de mejora mediante cambios locales de la solución actual. Se propone emplear 4 tipos de medidas distintas para obtener la mejor solución posible. Otra propuesta para resolver el GAP sería mediante la aplicación de un algoritmo dual. Primeramente, resolver una versión más sencilla del problema ignorando las restricciones de capacidad (2). Una vez asignados agentes y tareas, localizar las tareas que exceden las restricciones de capacidad para asignarlas a otros agentes cumpliendo así las restricciones y minimizando tanto como sea posible el coste total de asignación 5.1.3. Algoritmos heurísticos de partición de conjuntos Un problema de partición de conjuntos está basado en las técnicas de generación de columnas con límites superiores e inferiores propuestos. El GAP formulado como un problema de partición de conjuntos (SPP) donde cada columna corresponde con una asignación factible de un subconjunto de tareas a un agente. Mediante la generación de columnas, se halla una solución del problema de la mochila para cada agente. 83 5.1.4. Algoritmos heurísticos de relajación lagrangiana Existen seis propuestas de relajaciones utilizando métodos heurísticos mediante la lagrangiana y mediante un sustituto de relajación de la formulación del GAP. Ambos surgen de la relajación de las restricciones de capacidad (2). Para resolver ambos, se ha empleado el método del subgradiente. Un nuevo método de relajación heurística surge con la utilización de múltiples relajaciones y métodos heurísticos constrictivos. Este método se conoce como relajación lagrangiana/sustituto. Se basa en relajar las restricciones de capacidad (2), las restricciones de semi-asignación (3) y las restricciones de descomposición lagrangiana. La relajación lagrangiana/sustituto puede dar mejores resultados que los métodos heurísticos de relajación lagrangiana usando el método de optimización subgradiente con relajaciones lagrangianas tradicionales. La descomposición de la relajación lagrangiana basada en métodos heurísticos se realiza sustituyendo yij = rijxij y reduciendo las restricciones del GAP original. Otro método heurístico lagrangiano que encuentra y mejora las soluciones factibles al GAP se basa en utilizar la restricción de capacidad (2) como una dualidad y aplicar el procedimiento de optimización del método subgradiente. En cada iteración del método heurístico lagrangiano, previamente se emplea un método heurístico de aproximación para encontrar una asignación inicial. Los problemas de relajación lagrangiana basados en métodos heurísticos de búsqueda espacial combinan la habilidad de realizar búsquedas iterativas del método de optimización subgradiente y el plan de búsqueda del espacio del problema de perturbación. Se lleva a cabo tomando las restricciones de capacidad (2) como una dualidad y aplicando el procedimiento de optimización subgradiente. Para hallar una solución factible se proponen tres métodos heurísticos de restauración viables. Para incrementar las 84 posibilidades de obtener una buena solución de los métodos heurísticos se adopta la técnica metaheurística de búsqueda en espacios (PSS). El PSS genera problemas artificiales próximos que perturban temporalmente los datos del problema. 5.1.5. Relajación mediante programación lineal basada en métodos heurísticos Mediante la exploración de la estructura clásica, este método heurístico iterativamente elimina las variables redundantes (las variables xij que corresponden a rij con rij > bi), resuelve la relajación con las variables restantes, fija las variables con xij = 1 y actualiza las capacidades y elimina los trabajos asignados. Este procedimiento se repite hasta haber eliminado todas las variables redundantes. Al final de este método se aplica una operación de intercambio basada en un plan de mejora. 5.1.6. Otros métodos de obtención de una solución aproximada Para la resolución de un GAP de gran escala se propone el uso de una solución aproximada agregada/desagregada. Este método se realiza agregando el problema inicial y desagregando la solución óptima obtenida para obtener una solución factible del problema original. 85 Existe una metodología basada en técnicas de búsqueda por entornos orientada a objetos para resolver problemas de asignación (ATP) incluyendo al GAP (método descendente, búsqueda tabú, proceso de intercambio, recocido simulado). En otras palabras, se trata de software base que puede ser empleado para cualquier problema de asignación. De acuerdo con su definición, los problemas de asignación consisten en restricciones de semiasignación (3) y en otras restricciones. La restricción de semi-asignación asegura la asignación de un ítem a una única mochila. 86 5.2. Algunas metaheurísticas 5.2.1. Búsqueda tabú La búsqueda tabú (TS) es un plan de búsqueda local o por vecindades el cual comienza con una solución inicial que se traslada hasta una nueva solución seleccionada entre un conjunto de soluciones vecinas que no necesariamente mejoran la función objetivo. Para prevenir un movimiento indeseado de la solución se emplean estructuras de memoria. Los algoritmos TS conservan durante un corto periodo de memoria de los atributos de algunos movimientos en la lista tabú. Los atributos que permanecen en la lista tabú son utilizados para prohibir algunas soluciones que ya fueron aceptadas en un cierto número de iteraciones. Estos atributos se denominan “tabú-activos” mientras que las soluciones que los contengan se denominan “tabú”. Dicho de otra forma, las restricciones TS se definen en los atributos que se encuentran en la lista tabú. La estrategia denominada “cadenas de eyección” ha dado buenos resultados para la realización de la búsqueda tabú. Adoptando la aproximación “path relinking” en el algoritmo de “cadenas de eyección” mejoran los resultados obtenidos. Se proponen dos fases para realizar el algoritmo “path relinking”. En la primera fase el conjunto de soluciones se obtiene mediante la programación lineal de la formulación del GAP, reduciendo el problema y aplicando la búsqueda local. La segunda fase aplica el algoritmo “path relinking” el cual es una generalización de “scatter search” o búsqueda dispersa que opera con una combinación muy pequeña de soluciones. 87 5.2.2. Recocido simulado El recocido simulado (SA) está basado en la analogía entre el recocido de sólidos y la resolución de problemas de optimización combinatorios. SA es una estrategia de búsqueda local el cual evita evita la salida de un óptimo local usando estrategias de selección y aceptación aleatorias. Mediante la aceptación aleatoria las soluciones más desfavorables son aceptadas con cierta probabilidad, la cual es controlada por un parámetro relacionado con la temperatura. La actualización de este parámetro proviene de un proceso de enfriamiento. 5.2.3. Algoritmo genético El algoritmo genético (GA) es un algoritmo de búsqueda probabilístico que simula el proceso de la evolución. Un GA toma un conjunto de soluciones y reproduce nuevas soluciones utilizando operadores genéticos. Las soluciones reproducidas son evaluadas y las mejores soluciones son seleccionadas para su reproducción. El algoritmo se ejecuta hasta que no sea posible encontrar una solución mejor o hasta que se haya excedido un límite de tiempo. GA trata con un conjunto de soluciones descritos por unos parámetros conocidos como genes. El conjunto de estos parámetros forma cadenas de valores conocidos como cromosomas. La representación de los cromosomas es imprescindible para el desarrollo del GA. 88 5.2.4. Redes neuronales Las redes neuronales (NN) son principalmente procesos de aprendizaje adaptativo que actualizan constantemente algunos pesos hasta llegar a un punto aceptable, es decir, cuando se alcanza una solución casi factible o factible. Durante las últimas décadas un gran número de investigaciones han estudiado el uso de las NN para resolver problemas de optimización combinatoria. El primer intento de resolver el GAP usando una competición basado en redes neuronales consistía en una matriz m×n donde cada posición ocupada por una neurona que compite por volverse activa. Otra aplicación de una red neuronal intentó cuatro métodos diferentes para estructurar la función de energía de la red neuronal: método de función de penalización exterior, método de lagrangiano aumentado, método dual lagrangiano y método de función de penalización interior. El método de lagrangiano aumentado proporciona mejores soluciones que otros métodos con respecto a la integridad de la medida manteniendo la viabilidad y medida de estabilidad. 5.2.5. Colonia de hormigas y GRASP Esta metaheurística está basada en una aproximación híbrida. Una de las metaheurísticas propuestas podría ser la colonia de hormigas MAX-MIN la cual es una mejora de la colonia de hormigas. La colonia de hormigas muestra un procedimiento adaptativo, que tiene en cuenta la experiencia adquirida de iteraciones anteriores. También se podría proponer un método GRASP (Greedy Ramdomized Adaptative Search Procedure) cuyo funcionamiento es similar al algoritmo de búsqueda por vecindades que emplea un plan de mejora local en varios tiempos, cada uno con diferentes soluciones factibles al comienzo. Las soluciones iniciales que emplea el algoritmo son generadas mediante un procedimiento aleatorio. 89 6. BIBLIOGRAFÍA