Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria

i Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. Autora: Belén Navarro García Tutor: Víctor Fernández-Viagas Escudero Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. Autora: Belén Navarro García Tutor: Víctor Fernández-Viagas Escudero Profesor Contratado Doctor Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 Trabajo Fin de Grado: Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocal/es: Secretario: Acuerdan otorgarle la calificación de: El Secretario del Tribunal Sevilla, 2020 Autora: Belén Navarro García Tutor: Víctor Fernández-Viagas Escudero i Agradecimientos Quiero agradecer el apoyo y la confianza de quienes me han animado en la realización de este proyecto que pone fin a una etapa de mi vida como estudiante. En especial a mi familia y amigos, cuya motivación y orgullo me han impulsado a perseguir mis metas; y a Álvaro, por estar a mi lado estos cuatro años, animándome siempre a continuar con su constante apoyo y comprensión. Gracias también a Víctor, la persona que me ha guiado durante este proceso haciendo posible la realización de este trabajo. Gracias por su tiempo, su confianza en mí y motivación constante, y por poner su mejor esfuerzo en iniciarme en la investigación, siendo un gran referente a seguir. A todo aquel que invierta su tiempo en leer este trabajo, gracias. Belén Navarro García Sevilla, 2020 iii Resumen Este Trabajo Fin de Grado aborda un problema de programación de la producción para un taller con una configuración de tipo Flow-Shop. Se presenta como restricción la permutación y la existencia de tiempos de set-up no anticipatorios dependientes de la máquina y la secuencia. Se pretende alcanzar una solución de calidad para el problema en un tiempo de cálculo razonable, buscando como objetivo la minimización del makespan. Los algoritmos utilizarán una pequeña modificación de la función objetivo genérica, priorizando en caso de empate las secuencias con menor tiempo ocioso entre el procesado de los trabajos. Los métodos aproximados propuestos para la resolución de este problema de secuenciación serán heurísticas constructivas basadas en la memoria. Incluirán una búsqueda local iterativa en cada paso de construcción de la secuencia, repitiendo las combinaciones de trabajos más prometedores en futuras iteraciones. Se han implementado cuatro heurísticas similares, realizando además una evaluación computacional con 1000 instancias para distintas versiones de ellas. Un total de 17 heurísticas han sido comparadas, que demuestran la eficiencia de las propuestas. xi ÍNDICE DE FIGURAS Figura 2.1. Diagrama APS, "Advanced Planning System". [Fuente: Elaboración propia] 5 Figura 2.2. Representación de los entornos, restricciones y objetivos. 6 Figura 2.3. Entornos clásicos de fabricación. 7 Figura 2.4. Representación del triángulo de hierro. [Fuente: Elaboración propia] 9 Figura 2.5. Esquema de flujo en un entorno Flow-Shop. 11 Figura 2.6. Diagrama de Gantt para el PFSP con tiempos de set-up. [Fuente: Elaboración propia] 11 Figura 2.7. Representación diagrama de Gantt: tiempos Anticipatorios y No Anticipatorios. 12 Figura 3.1. Ejemplo de diagrama de Gantt para F2|prmu, Sijk|Cmax. [Fuente: Elaboración propia] 14 Figura 4.1. Pseudocódigo de NEH para Fm|prmu|Cmax. [Fuente: Elaboración propia] 17 Figura 4.2. Diagrama Gantt resultado de la heurística NEH en el ejemplo 4.2.1. [Fuente: Elaboración propia] 19 Figura 4.3. Representación mínimos y máximos (locales y globales). [Fuente: Elaboración propia] 20 Figura 4.4. Diagrama de flujo para la búsqueda tabú. [Fuente: Adaptación al español de Abiri et al. (2009)] 21 Figura 5.1. Diagrama de flujo del procedimiento general propuesto. [Fuente: Elaboración propia] 24 Figura 5.2. Matriz de movimientos prometedores para V.1. [Fuente: Elaboración propia] 25 Figura 5.3. Pseudocódigo procedimiento V.1. [Fuente: Adaptación de Fernández-Viagas et al. (2018)] 26 Figura 5.4. Matriz de movimientos prometedores para V.2. [Fuente: Elaboración propia] 27 Figura 5.5. Pseudocódigo procedimiento V.2. [Fuente: Elaboración propia] 28 Figura 5.6. Lista de movimientos prometedores para V.3 y V.4. [Fuente: Elaboración propia] 29 Figura 5.7. Pseudocódigo procedimiento V.3. [Fuente: Elaboración propia] 31 Figura 5.8. Pseudocódigo procedimiento V.4. [Fuente: Elaboración propia] 32 Figura 6.1. ARPD contra ARPT. [Fuente: Elaboración propia] 37 1 1 INTRODUCCIÓN omo comienzo de este Trabajo Fin de Grado, se realiza una breve explicación de las razones que han llevado a la realización del presente documento, cuál es su propósito, ámbito, alcance, así como una pequeña introducción del proceso de resolución del problema que describe la metodología utilizada y las conclusiones que se esperan alcanzar. 1.1 Motivación La programación de la producción es una rama de la organización industrial de gran importancia. Una adecuada secuenciación de las tareas a procesar en un sistema productivo proporciona grandes ventajas, ya que se produce una gran optimización en cuanto al aprovechamiento de los recursos. La naturaleza de estos recursos y tareas es bastante amplia, dado que por ejemplo, un recurso productivo puede incluir desde una máquina hasta un conjunto de operarios (recursos humanos). Gracias a una programación de la producción ajustada se puede conseguir minimizar los costes y el tiempo, consiguiendo un mayor alcance y cumpliendo los objetivos marcados en la producción de manera eficiente. Como indica Pinedo (2012), esta secuenciación conlleva un alto volumen de decisiones centradas en la asignación de recursos a tareas en un determinado periodo temporal, con el fin de optimizar dicha colocación en base a uno o múltiples objetivos fijados. La secuenciación no solo aplica al ámbito industrial, sino que además juega un rol importante en cuanto a logística y distribución, o en cualquier servicio con una duración determinada. Su uso es fundamental para empresas con un volumen de tareas y recursos medio o elevado, permitiendo una competitividad en el mercado mucho mayor. Por ello, el interés de este Trabajo Fin de Grado reside en aprovechar la capacidad de los recursos de un taller de flujo regular con características específicas, para conseguir una producción óptima y reducir los tiempos de procesado de las tareas. 1.2 Objetivo y alcance del proyecto Por los motivos expuestos en el apartado anterior, el objetivo de este proyecto será el estudio de un problema de programación de la producción: un taller de flujo regular con restricción de permutación y con la existencia de tiempos de set-up (Fm|prmu, Sijk|Cmax). El taller de flujo regular es uno de los problemas más estudiados en la investigación operativa (Fernández-Viagas et al., 2018). Fundamentalmente se debe a dos aspectos: por un lado, es un problema muy presente en el sector industrial; y por otro lado, los algoritmos desarrollados para este problema se han demostrado muy eficientes en problemas similares a lo largo de los últimos años. Se buscan así métodos que simplifiquen la búsqueda y proporcionen soluciones cercanas al óptimo en estos problemas. Como resultado, la solución que se pretende obtener es una secuencia que contenga el orden de secuenciación de los trabajos a procesar en el taller. Ésta será de mayor calidad cuanto menor tiempo de proceso total conlleve (minimización de makespan). Al tratarse de un problema complejo (NP-hard), no se tratará de evaluar todas las combinaciones de soluciones posibles, sino que se emplearán métodos aproximados que proporcionen soluciones próximas al óptimo en un tiempo de cálculo razonable. Se pretenden combinar heurísticas constructivas con mecanismos propios de metaheurísticas de búsqueda local, con el objetivo de proporcionar mejores soluciones que la conocida C Introducción 2 heurística NEH (Nawaz, Enscore Jr & Ham, 1983). El funcionamiento de la búsqueda local seleccionada será similar al de la conocida búsqueda tabú, con la diferencia de que en lugar de conservar en una lista los movimientos prohibidos, se mantendrán las combinaciones más prometedoras que se hayan realizado durante el procedimiento de construcción de la secuencia. Estas combinaciones prometedoras se repetirán para conseguir soluciones de mayor calidad, y evitar que se descarten soluciones, que aunque a priori no sean las mejores, podrían llegar a serlo. Como se verá en el último capítulo del documento, se presentarán cuatro procedimientos de resolución del problema que proporcionan soluciones de buena calidad en un determinado tiempo. Generalmente cuando el tiempo que conlleve el cálculo sea mayor, se generarán mejores soluciones. 1.3 Estructura del documento El contenido del trabajo se distribuye en los siguientes capítulos: - Capítulo 1: Introducción. En este primer documento se describe el propósito del presente Trabajo Fin de Grado. Se comenta brevemente su interés de estudio, su aplicabilidad, sus objetivos, ámbito, alcance, así como la metodología aplicada y un pequeño avance de las conclusiones obtenidas tras la investigación. - Capítulo 2: Marco teórico. A modo introductorio, se trata de enmarcar el proyecto dentro del ámbito de la organización industrial, comentando algunos de los conceptos teóricos sobre la programación de la producción necesarios para la correcta comprensión del documento. Además, se realiza una breve introducción al problema objeto del proyecto. - Capítulo 3: Análisis del problema. En este tercer capítulo, se describe en profundidad el problema a resolver, con mayor nivel de detalle. Se exponen todas las características del entorno, restricciones, objetivos, y cualquier aspecto que ayude a comprender el problema en cuestión. - Capítulo 4: Análisis de la metodología En este capítulo se hace referencia a las metodologías existentes que suelen emplearse en la actualidad para la resolución de problemas similares al que se trata en este proyecto, comentando con mayor detalle aquellas que se usarán como base para la resolución del problema. - Capítulo 5: Aplicación de la metodología. Este apartado describe la metodología aplicada en la resolución del problema descrito en el capítulo 3. En concreto, se exponen los algoritmos aproximados que se han desarrollado, explicando detalladamente el funcionamiento de cada uno de ellos. - Capítulo 6: Evaluación computacional. En este capítulo se presentan los resultados obtenidos al resolver el problema haciendo uso de cada uno de los algoritmos descritos en el capítulo anterior (4 variantes), desarrollados en lenguaje de programación C#. Para ello, se especifica el conjunto de pruebas realizadas, y se muestra la comparativa de los resultados obtenidos en cuanto al nivel de calidad de la solución y al tiempo computacional del algoritmo. 3 3 Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. - Capítulo 7: Conclusiones. Para finalizar, este último capítulo recoge las conclusiones obtenidas con el desarrollo del presente Trabajo Fin de Grado, así como las posibles futuras líneas de investigación que se podrían seguir. Al final del documento se encuentran las referencias bibliográficas de la información consultada para su elaboración. 5 2 MARCO TEÓRICO on el objetivo de enmarcar el desarrollo del proyecto en el ámbito de la organización de la producción, en este capítulo se introducen los conceptos considerados necesarios para una adecuada comprensión del documento. 2.1 Introducción “La organización de la producción (Production Managment) es un proceso industrial consistente en la toma de un número elevado de decisiones a lo largo del tiempo para asegurar la entrega al cliente de los productos con la máxima calidad, mínimo coste, y mínimo tiempo de entrega.” [Framiñán, Leisten y Ruiz, 2014] En todo proceso productivo se realizan transformaciones sobre unas determinadas entradas con el fin de obtener las salidas deseadas, agregándole valor al producto mediante el uso de recursos. Todas las acciones de planificación y gestión que incluye cualquier proceso productivo son abarcadas por la organización de la producción. Esta engloba un gran volumen de decisiones diversas que aplican a distintos ámbitos y plazos de tiempo. Visualmente, en el siguiente esquema de la Figura 2.1 se recogen los bloques más comunes siguiendo la conocida estructura denominada “Advanced Planning System, APS”: Figura 2.1. Diagrama APS, "Advanced Planning System". [Fuente: Elaboración propia] Como se puede observar, entre todos los aspectos de planificación que engloba la organización de la producción, en concreto la programación de la producción (Manufacturing Scheduling) se sitúa en la toma de decisiones a corto plazo relativas al proceso de fabricación. Gracias a la programación de la producción, es posible establecer el periodo de tiempo asignado para la realización de cada una de las operaciones de transformación o transporte de material necesarias para la fabricación de un conjunto de productos, así como qué recursos de la empresa se emplean para ello (materia prima, mano de obra, maquinaria, logística…). C Marco teórico 6 Estos recursos con capacidad productiva para el transporte o transformación del producto objeto de la operación (denominado trabajo) se denominan máquinas. El concepto de máquina no solo representa a un objeto mecánico, sino también abarca a recursos humanos, como son los operarios o un grupo de objetos mecánicos que realicen una operación en su conjunto. De igual modo, el concepto de trabajo puede representar tanto a un único objeto, como a un grupo de objetos físicos. Toda operación se realiza durante una determinada duración temporal, que se conoce como tiempo de proceso (processing time). Dicho tiempo dependerá tanto del trabajo (job) a procesar como de la máquina (machine) en la que se realice la operación. Como resultado de la programación de la producción se obtiene el denominado programa (schedule), que recoge la asignación en la escala temporal concreta de las máquinas para el procesado de los trabajos. Es decir, el programa asigna las fechas de comienzo de cada trabajo en cada máquina, pero el orden en que cada trabajo comienza a procesarse en cada máquina viene dado por una secuencia (sequence). Para que un programa sea admisible debe cumplir con todas las restricciones y características del entorno productivo. Para conseguirlo, se emplean los algoritmos, que nos permiten obtener un programa factible que cumpla con los objetivos marcados. Cabe destacar la importancia de las decisiones relativas a la programación de la producción, que, a pesar de ser tomadas en cortos intervalos de tiempo, pueden influir en gran medida en el resultado final. Para la asignación de los recursos llevada a cabo, se requiere una serie de decisiones exhaustivas y precisas tomadas en el instante adecuado. Por este motivo, el tiempo es un factor muy importante para tener en cuenta a la hora de desarrollar un algoritmo, que a veces debe proporcionar decisiones instantáneas, incluso en tiempo real. Dichas decisiones vienen condicionadas por diversos factores que dependen del tipo de entorno en el que nos encontremos, las restricciones impuestas, o los objetivos fijados. Graham et al. (1979) propone una de las notaciones que más se usan en la actualidad con el fin de definir las características de un problema de programación de la producción, basada en el uso de tres parámetros de la siguiente forma: α | β | γ. Cada uno de ellos describe las características de las máquinas (entorno, α), de los trabajos (restricciones, β), y de la función objetivo (objetivos, γ), respectivamente (véase Figura 2.2). A continuación, se van a comentar con mayor detalle. Figura 2.2. Representación de los entornos, restricciones y objetivos. [Fuente: Temario Programación y Control de la Producción, Escuela Técnica Superior de Ingeniería] 7 7 Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. 2.2 Entornos (α) Existen distintos tipos de entornos de fabricación (layout) con distintas características en función del número, distribución y características de las máquinas. A continuación, se comentarán brevemente algunos de los entornos más frecuentes, englobados en la clasificación de la Figura 2.3. - Una máquina (Single Machine, α = 1). Es el modelo más sencillo, ya que solo dispone de una etapa con una máquina que procesa todos los trabajos uno a uno, una única vez, sin ruta posible. - Máquinas en paralelo (Parallel Machines). Es el mismo caso que el anterior, pero con mayor número de máquinas disponibles para procesar los trabajos, de nuevo sin ruta posible, ya que se trata de una única etapa. Según la velocidad de las máquinas, se diferencia entre: o Máquinas idénticas (α = Pm): todas las máquinas tienen la misma velocidad de procesado. o Máquinas uniformes (α = Qm): la velocidad de procesado de cada máquina es distinta. o Máquinas no relacionadas, (α = Rm): cada máquina procesa cada trabajo a una velocidad distinta, por lo que el tiempo de proceso dependerá de la máquina a la que se asigne. - Tipo taller: se dispone de varias máquinas en serie, donde cada una realiza una operación distinta sobre el trabajo, el cuál debe pasar por las máquinas del taller según su ruta de fabricación. Según el tipo de ruta que siguen los trabajos a la hora de ser procesados, se diferencian 3 tipos de talleres: o Taller de flujo regular (Flow Shop, α = Fm): todos los trabajos siguen la misma ruta de fabricación predeterminada. o Taller de trabajos (Job Shop, α = Jm): cada trabajo sigue una ruta predeterminada distinta. o Taller abierto (Open Shop, α = Om): la ruta de los trabajos es libre, no está predeterminada. - Híbridos/Flexibles (α = HFm, HJm, HOm). Se trata de un taller (de flujo regular, de trabajos, o abierto) formado por varias etapas, donde cada una corresponde a una sola máquina o varias máquinas paralelas. Figura 2.3. Entornos clásicos de fabricación. [Fuente: Fernández-Viagas, V. (s. f.)] Análisis del problema 14 Figura 3.1. Ejemplo de diagrama de Gantt para F2|prmu, Sijk|Cmax. [Fuente: Elaboración propia] 3.2 Complejidad del problema Como se comentó en el capítulo anterior, este tipo de problema pertenece a los conocidos como NP-hard. Por tanto, no es posible determinar el programa óptimo para este problema en un tiempo admisible, por lo que no se puede tener la certeza de que el programa dado como solución será mejor que cualquier otro programa admisible. Para la resolución de este problema se desarrollará un algoritmo que busque el vector secuencia que contenga la combinación de trabajos a procesar ordenados de forma que se obtenga el mínimo valor posible del makespan en un tiempo acorde. No se conocerá cuál sería el programa óptimo, ni cuánto se aproxima el valor de la función objetivo de la secuencia obtenida como solución en el algoritmo, al valor de la función objetivo correspondiente al programa óptimo. 3.3 Notación A modo recopilatorio, se presenta la siguiente Tabla 3.1, que contiene las notaciones mencionadas con anterioridad que se usarán a lo largo del documento. Tabla 3.1. Notación utilizada. Notación Descripción n Número de trabajos a procesar m Número de máquinas consideradas pij Tiempo de proceso del trabajo j en la máquina i Sijk Tiempo de set-up para el trabajo k, con el trabajo j como predecesor, en la máquina i Idle time Tiempo ocioso de las máquinas durante el procesado de trabajos Cij Tiempo de terminación del trabajo j en la máquina i Cmax Instante de terminación del último de los trabajos Fm Flow-shop de m máquinas prmu Restricción de permutación FO Función objetivo П Secuencia de trabajos 15 4 ANÁLISIS DE LA METODOLOGÍA l problema a abordar, al ser un problema de programación de la producción, es de tipo combinatorio, por lo que teóricamente evaluando todas las combinaciones posibles que componen el conjunto finito de soluciones sería suficiente para determinar cuál de ellas es la óptima para el objetivo fijado. Cuando se trata de problemas complejos o de gran tamaño cuyo conjunto finito de soluciones tiene un tamaño elevado, no es viable emplear este método para su resolución, ya que obtener la solución óptima implicaría un gran tiempo de cálculo. Por este motivo, para su resolución se emplean métodos de optimización que describen el procedimiento a seguir para acelerar la búsqueda de soluciones. Es muy común hacer uso de algoritmos en los que se codifica dicho procedimiento con un número finito de pasos y se ejecuta mediante un ordenador. Se diferencia entre algoritmos exactos, que alcanzan el óptimo del problema, y algoritmos aproximados, que proporcionan una solución aproximada. En este capítulo se comentarán algunos de los métodos generales empleados para la resolución de problemas de programación de la producción. 4.1 Procedimientos generales de resolución 4.1.1 Métodos exactos Los métodos exactos proporcionan la solución óptima del problema, ya que evalúan todas las combinaciones posibles del modelo, explícita o implícitamente. En cuanto a algoritmos exactos, se puede distinguir entre: - Algoritmos constructivos exactos. Resuelven problemas polinomiales, de clase P, evaluando todas las soluciones del modelo para obtener la óptima de ellas. Pertenecen a este grupo, entre otros, los conocidos algoritmos de Johnson, Lawler, Moore, y algunas reglas de despacho que especifican el orden de procesado de los trabajos, para problemas de programación muy sencillos, como por ejemplo: o First In First Out, FIFO: el primer trabajo que llega es el primero en ser procesado. Se obtiene así el óptimo para el problema 1|rj|Cmax . o Shortest Processing Time first, SPT: el orden de procesado de los trabajos es de menor a mayor tiempo de proceso. Esta regla de despacho resuelve de forma óptima los problemas: 1||∑Cj y Pm||∑Cj . o Earlier Due Date first, EDD: se procesan los trabajos en orden de menor a mayor fecha de entrega o due date. Obtiene el óptimo para los problemas 1||máx Tj y 1||máx Lj . o Weighted Shortest Processing Time first, WSPT: el orden en el que se procesan los trabajos viene dado por el valor del cociente entre el peso y tiempo de proceso del trabajo que se va a procesar, ordenados de mayor a menor. Proporciona el óptimo para el problema 1||∑wi Cj . o Shortest Remaining Processing Time on the Fastest Machine first, SRPT-FM: el trabajo de menor duración se procesa primero en la máquina más rápida, y el resto se comienzan a procesar en el resto de las máquinas disponibles. Cuando la máquina más rápida se queda libre, se analiza de nuevo cuál es el trabajo con menor tiempo de proceso restante, asignándolo de nuevo a la máquina más rápida, y así sucesivamente hasta completar todos los trabajos. Con esta regla se obtiene el óptimo para el problema Qm|pmtn|∑Cj . E Análisis de la metodología 16 16 - Algoritmos enumerativos. Aunque no evalúan todas las soluciones explícitamente, garantizan la obtención de la solución óptima. Las soluciones que no son evaluadas explícitamente se evalúan implícitamente, ya que existen evidencias que indican que la evaluación de esta implicaría un valor de la función objetivo igual o superior al de otra solución ya evaluada. Al ser de tipo No polinomial, sólo dan soluciones óptimas para problemas con instancias pequeñas. Pertenecen a este grupo la programación matemática (en concreto los modelos de programación lineal entera mixta), el método de ramificación y acotación conocido como Branch and Bound, y la programación dinámica. 4.1.2 Métodos aproximados Debido a la inviabilidad de hallar una solución óptima mediante un método exacto en un tiempo razonable, existen los métodos aproximados. Con ellos no existe certeza de que la solución alcanzada sea la óptima, ya que no se evalúa la totalidad del conjunto de soluciones posibles, sino parte de él, consiguiendo una buena solución en un tiempo aceptable. 4.1.2.1 Heurísticas “Las heurísticas son procedimientos simples, a menudo guiados por el sentido común, que están destinados a proporcionar soluciones buenas pero no necesariamente óptimas a problemas difíciles, de manera fácil y con rapidez.” [Zanakis y Evans, 1981] Son de gran utilidad para problemas que no requieran una solución óptima o en los que no se puedan aplicar métodos exactos por otros motivos. También suelen emplearse como paso previo a la aplicación de otro algoritmo o cuando los datos del problema tienen una alta variabilidad o no son fiables. Una de las heurísticas más usadas en la actualidad por su efectividad en la resolución del problema de Flowshop es la NEH propuesta por (Nawaz, Enscore Jr & Ham, 1983). Se trata de una heurística constructiva que consiste en construir la solución en un número finito de pasos, insertando uno a uno los trabajos aún sin secuenciar en la posición de la secuencia parcial que menor valor de la función objetivo proporcione. 4.1.2.2 Metaheurísticas Cuando se abordan problemas complejos para los que las heurísticas resultan ineficientes e inefectivas, se hace uso de las metaheurísticas. Se tratan de procedimientos heurísticos adecuados para realizar una búsqueda de soluciones eficaz y efectiva, encontrando el equilibrio adecuado entre intensificación y diversificación. Estas dos características de la búsqueda son muy importantes. Por un lado, la intensificación está relacionada con la explotación del espacio en la búsqueda local, centrándose en las que aparentan ser más prometedoras, consiguiendo así soluciones de mayor calidad. Por otro lado, la diversificación, consigue una apropiada exploración en la búsqueda global, abarcando un espacio mayor de soluciones variadas mediante la búsqueda en regiones que contrastan fuertemente con las regiones exploradas hasta el momento, no aleatoriamente, sino teniendo en consideración el proceso de búsqueda anterior. Es fundamental buscar el equilibrio correcto entre ambas características en el proceso de diseño de una metaheurística efectiva, ya que una falta de intensificación provoca que la exploración sea demasiado larga, y una falta de diversificación produce una rápida convergencia a mínimos locales. Los métodos metaheurísticos pueden presentar los siguientes enfoques: - Enfoque constructivo, basado en generar la solución paso a paso, tomando una decisión cada vez que se secuencia un trabajo, disminuyendo así el tamaño del problema en cada decisión al descartar posibles soluciones. - Enfoque iterativo, que realiza una búsqueda local en cada iteración, estudiando las soluciones del entorno de la solución que realiza. Este entorno se denomina vecindario, y se corresponde con el conjunto de soluciones formadas a partir de una modificación de una solución. Uno de los métodos más conocidos de este tipo de enfoque es la conocida búsqueda Tabú (Tabú Search). 17 17 Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. - Enfoque evolutivo, inspirado en mecanismos biológicos como son la selección y evolución natural, genera nuevas soluciones seleccionando, cruzando, o mutando las soluciones existentes en un conjunto denominado población inicial, obteniendo así soluciones de mayor calidad “evolucionadas” a partir de las existentes. 4.2 Metodología seleccionada Para el problema a resolver, Fm|prmu, Sijk|Cmax, se ha decidido emplear métodos aproximados, ya que como se mencionó, su solución óptima no se puede alcanzar en un tiempo razonable debido a su complejidad y número elevado de programas factibles. En concreto, se pretenden construir 4 algoritmos aproximados basados en dos de los métodos mencionados en el apartado 4.1.2: la Búsqueda tabú y la heurística NEH. Además, se hará uso también de una de las reglas de despacho: Longest Processing Time first (LPT), que consiste en procesar los trabajos según su tiempo de proceso, de mayor a menor, al contrario que en la SPT. 4.2.1 NEH En cuanto a la heurística constructiva NEH, a pesar de que rara vez se consigue obtener el óptimo con este procedimiento, proporciona muy buenos resultados para el problema Fm|prmu|Cmax, y aporta como ventajas su eficacia, sencillez y rapidez en la búsqueda de soluciones. Según su procedimiento de aplicación en un taller de flujo regular, en primer lugar se suman para cada uno de los trabajos, todos sus tiempos de proceso en todas las máquinas donde se procesan, y posteriormente se ordenan de mayor a menor. En función de estos tiempos totales de proceso de cada trabajo, se aplica la regla LPT, obteniendo así la secuencia de trabajos ordenada según este criterio. A continuación, comienza la fase de inserción, donde progresivamente se va construyendo la secuencia, incorporando uno a uno los trabajos en el orden previamente marcado por la regla LPT. Para ello se crea inicialmente una secuencia inicial compuesta por la mejor combinación entre los primeros dos trabajos, y se van insertando sucesivamente trabajos en la posición de la secuencia parcial generada que proporcione un mejor valor de la función objetivo, hasta secuenciar todos los trabajos. A continuación, en la Figura 4.1 se muestra el pseudocódigo correspondiente a este procedimiento. Figura 4.1. Pseudocódigo de NEH para Fm|prmu|Cmax. [Fuente: Elaboración propia] Si bien es cierto (como muestran Companys y Rivas, 2012), este procedimiento no siempre mejora la calidad de la secuencia, por lo que es recomendable evaluar siempre la secuencia inicial antes para compararla con la solución resultante del método y quedarse con la mejor, lo cual se tendrá en cuenta en el desarrollo de los algoritmos. Entrada: datos de la instancia Salida: П, Cmax Inicio 1 jj m i i Pp  = = ; П = ∅, J = { 1  ,…, n  } verificándose que 1 P  ≥ 2 P  ≥ … n P  ; П (1) = { 1  }; Para k = 2 hasta n hacer Insertar el trabajo k  en la posición de П (k) que conlleve el menor Cmax; Fin Devolver П, Cmax Fin Análisis de la metodología 18 18 A continuación se presenta un breve y sencillo ejemplo numérico de la aplicación este procedimiento para el problema a resolver descrito en el apartado 3.1 (Fm|prmu, Sijk|Cmax). Ejemplo 4.2.1. Hallar una solución aproximada mediante la heurística NEH para la siguiente instancia en el problema F2|prmu, Sijk|Cmax. Número de trabajos: n = 3 Tiempos de proceso (pij): n m 1 2 3 1 2 3 1 2 2 2 1 Fase 1: Secuencia inicial LPT. 1 m j ij i Pp = = 12 2 4P= + = → 2º 23 2 5P= + = → 1º 31 1 2P= + = → 3º Secuencia LPT = [2, 1, 3] Fase 2: inserción del trabajo seleccionado en la posición con menor Cmax. [1, 2] → Cmax = 13 [2, 1] → Cmax = 13 Como se puede observar, ambas combinaciones proporcionan el mismo resultado en cuanto al objetivo del problema (Cmax = 13). Por ello, en caso de empate, en las propuestas de resolución que se presentarán en el siguiente capítulo se analizará un método de desempate que evalúa el tiempo ocioso entre el procesado de los trabajos en las máquinas, usándolo como criterio para decidir qué combinación se elige en caso de empate. En este ejemplo, el idle-time de la primera combinación [1, 2] es de 3 unidades temporales, mientras que para la segunda combinación [2, 1] es de 2 unidades. La construcción de la secuencia se continuará con esta última secuencia parcial. Tiempos de set-up (sijk): Máquina 1 (i = 1): Máquina 2 (i = 2): k j 1 2 3 0 1 2 0 1 - 2 2 2 3 - 1 3 2 1 - k j 1 2 3 0 0 1 1 1 - 3 1 2 1 - 1 3 1 3 - 19 19 Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. [3, 2, 1] → Cmax = 13  Menor valor, solución del problema. [2, 3, 1] → Cmax = 14 [2, 1, 3] → Cmax = 15 Gráficamente se puede ver la solución obtenida representada en el diagrama de Gantt de la Figura 4.2. Figura 4.2. Diagrama Gantt resultado de la heurística NEH en el ejemplo 4.2.1. [Fuente: Elaboración propia] 4.2.2 Búsqueda Tabú La conocida metaheurística denominada búsqueda tabú, es una técnica de búsqueda local basada en la memoria que proporciona muy buenos resultados en problemas de optimización debido a su versatilidad. Se considera muy eficiente en la resolución de problemas combinatorios complejos, como es el conocido problema del viajero, problemas de rutas y envíos de productos, y por supuesto, problemas de secuenciación. Como se ha comentado en el apartado 4.1.2.2, el enfoque de este método es iterativo, ya que prohíbe determinados movimientos durante un número de iteraciones, consiguiendo así evitar que el procedimiento caiga en óptimos locales, lo cual presenta una favorable ventaja a la hora de seleccionar esta metodología. Inicialmente, la búsqueda tabú parte de una solución, generando otra nueva a partir de esta. Para ello transforma la solución inicial mediante la realización de movimientos, que pueden consistir en retirar de la secuencia un trabajo ya secuenciado y colocarlo en otra posición distinta, o simplemente intercambiar dos de los trabajos secuenciados. De esta forma puede crearse una solución que incluso será de menor calidad que la actual, pero gracias a ello se consigue escapar de óptimos locales y poder alcanzar el óptimo global del problema. Véase Figura 4.3. Para evitar probar ciclos de soluciones poco diversas, se define un conjunto de movimientos tabú (prohibidos), registrados en la denominada lista tabú. El tamaño de este conjunto viene definido por un parámetro denominado tamaño de la lista. En el caso en que el número de movimientos contenidos en la lista alcance el tamaño total de la lista tabú, antes de añadir un nuevo movimiento a la lista hay que eliminar uno de los que ya contiene. Para decidir qué movimiento se elimina, se establecen criterios de aspiración por defecto, donde se elimina el más antiguo (el movimiento que lleve más tiempo en la lista), o criterios de aspiración por objetivo, donde solo se admite el movimiento si produce una solución mejor a la obtenida hasta el momento. Este último suele ser el criterio mayoritariamente utilizado. La Figura 4.4 muestra el diagrama de flujo de la búsqueda tabú, donde MS representa la mejor solución hasta el momento, y AS la actual solución durante el proceso de búsqueda. Análisis de la metodología 20 20 Figura 4.3. Representación mínimos y máximos (locales y globales). [Fuente: Elaboración propia] Es importante encontrar el equilibrio correcto entre intensificación y diversificación, como se comentó en el apartado 4.1.2.2. En la búsqueda tabú generalmente se presenta un equilibrio estático, ya que cuando mayor sea el tamaño de la lista, se producirá una mayor diversificación, pero una menor intensificación. Es recomendable que el equilibrio sea oscilatorio entre ambas, por lo que una posible forma de conseguirlo sería cambiar dinámicamente el tamaño de la lista tabú. Basándose en esta metaheurística, la búsqueda tabú, para la resolución del problema en cuestión se ha decidido emplear el procedimiento inverso en cuanto a los movimientos introducidos en la lista. Como se va a explicar en el siguiente capítulo, los trabajos que se introducen en la lista tabú dejan de ser movimientos prohibidos, y pasan a ser movimientos prometedores, pasando a denominarse la lista prometedora (promise). Así, se mantendrán en la lista los movimientos más prometedores para volver a repetirlos en futuras iteraciones de la búsqueda, como proponen Fernández-Viagas, Molina-Pariente y Framiñán (2018). Con esto se consigue mantener las combinaciones que en un principio fueron descartadas por existir otra combinación que diese mejores resultados, pero en otro momento más avanzado de la búsqueda puedan proporcionar mejoras. 21 21 Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. Figura 4.4. Diagrama de flujo para la búsqueda tabú. [Fuente: Adaptación al español de Abiri et al. (2009)] 23 5 APLICACIÓN DE LA METODOLOGÍA na vez explicada la metodología que se ha tenido como base para la resolución del problema, se procede a comentar su aplicación. A continuación se explicarán detalladamente cada uno de los 4 procedimientos de resolución propuestos, para los cuales se ha implementado el algoritmo aproximado correspondiente en lenguaje de programación C# en el entorno de desarrollo Microsoft Visual Studio Community en su versión 2019. 5.1 Procedimiento propuesto Los métodos aproximados propuestos para resolver el problema se tratan de heurísticas constructivas basadas en la memoria, ya que están fundamentados en la combinación de la heurística NEH y una versión inversa de la metaheurística de búsqueda tabú (véase sección 4.2). Como se ha comentado en capítulos anteriores, la heurística constructiva NEH se guía únicamente por el criterio de minimización de la función objetivo para determinar cuál es la mejor secuencia parcial para continuar el proceso. Este criterio puede no ser fiable en los primeros pasos de la construcción donde la secuencia parcial está compuesta por un número bajo de trabajos, pudiendo dar lugar a elecciones erróneas. Por tanto, la adición de la búsqueda local desde un enfoque iterativo a la heurística constructiva se considera muy conveniente. Gracias a ella se vuelven a evaluar esas soluciones que han podido ser descartadas inicialmente por no ser las que mejor valor de la función objetivo han proporcionado, pero podrían serlo en una fase más avanzada del proceso de construcción de la secuencia. Además, la búsqueda local ayuda a escapar de óptimos locales ampliando la búsqueda, lo cual también es ventajoso. En base a lo anterior, las 4 versiones propuestas a continuación siguen un procedimiento común que consiste en construir la secuencia del mismo modo que la heurística NEH, incluyendo además en cada paso de dicha construcción (cada vez que se inserta un nuevo trabajo en la secuencia parcial) una búsqueda local a partir la vecindad de dicha solución parcial. Esta búsqueda se realiza generando vecinos mediante la reinserción de un trabajo en una posición distinta a la actual. Dicha posición viene determinada por una lista de movimientos prometedores, que al contrario que la lista tabú, contiene los movimientos (combinación de dos trabajos) que en iteraciones anteriores proporcionaban buenos resultados en cuanto a la función objetivo (5.1). Con esta función se tiene en cuenta principalmente el objetivo del problema (Cmax), pero además, en caso de empate en cuanto al valor del makespan de dos soluciones distintas, se tomará como criterio la minimización del tiempo ocioso (idle-time). El valor de N en la ecuación se corresponde con un número suficientemente alto. max idle time FO C N − =+ (5.1) En la siguiente Figura 5.1 se muestra un diagrama de flujo que representa el procedimiento general común en las 4 versiones presentadas, que varían en cuanto a la configuración de la lista de movimientos prometedores que se va a explicar a continuación. Además, cada una de las versiones tiene como entrada un parámetro que determinará la cantidad y calidad de los movimientos que se mantendrán y reinsertarán en el proceso de búsqueda. Este procedimiento inicialmente requiere de una solución inicial, la cual será dada por la regla LPT, que como se ha comentado con anterioridad, consiste en ordenar los trabajos decrecientemente según su tiempo de proceso total (suma de su tiempo de proceso en todas las máquinas que componen su ruta de fabricación). Esta secuencia inicial LPT determina el orden en el que se secuencian los trabajos, construyéndose una secuencia parcial con los trabajos de mayor duración en primer lugar, e insertando sucesivamente entre ellos los trabajos que implican un menor tiempo de proceso en cada paso de la construcción. Este método se conoce que proporciona buenos resultados para el problema de Flow-shop. U Aplicación de la metodología 30 30 de un nuevo trabajo, el valor de la mejor función objetivo hasta el momento (Objb) va incrementando, influyendo en que la desviación sea menor debido a que el denominador es mayor. Por tanto, cuando el valor de la función objetivo del movimiento candidato a entrar en la lista (ObjCandidato) presente realmente igual desviación respecto al mejor (Objb) en dos iteraciones distintas, el cálculo del incremento proporcionará un valor menor para el movimiento de la iteración más reciente. Por este razonamiento, se decide que ante caso de empate, se da preferencia a los ya existentes en la lista para compensar esa diferencia. Por último, respecto a la casuística que se sigue a la hora de decidir cuándo se realiza un movimiento de la lista, esta versión vuelve a reinsertar todos los movimientos contenidos en la lista tras la secuenciación de cada trabajo en la secuencia parcial. Cuando se produce una mejora con la repetición de uno de los movimientos, la lista se actualiza de modo que el movimiento realizado (que ahora forma parte de la mejor secuencia parcial) deje de formar parte de la lista, ocupando su lugar el movimiento recién desecho. El pseudocódigo correspondiente al procedimiento descrito se muestra en la Figura 5.7. 5.5 Versión 4 (V.4) Para la última de las versiones, se ha hecho uso como en el caso anterior, de una única lista que contiene los movimientos prometedores globales (Figura 5.6), pero en este caso no viene limitada por un tamaño, sino que su capacidad es infinita. En esta modificación, la condición que deben cumplir los movimientos candidatos a introducirse en la lista viene definida por un incremento máximo. Este límite se impone de forma que un movimiento solo entrará en la lista si proporciona un valor de la función objetivo que se desvíe una cantidad máxima del mejor valor encontrado hasta el momento. Esta diferencia se mide en cada iteración, de la misma manera que en la versión anterior, mediante el incremento determinado por la ecuación (5.2). Para determinar el valor del incremento límite en cada instante, se tiene en cuenta como principal factor el tiempo de set-up. Puesto que se trata de un taller de flujo regular con tiempos de set-up, cada vez que se añade un nuevo trabajo en la secuencia parcial, el valor de la función objetivo se verá incrementado por la suma de los tiempos de proceso de dicho trabajo en cada una de las maquinas que compongan el taller, más los tiempos de set-up de ese trabajo para cada máquina. Estos últimos, al depender de la secuencia, varían en función del trabajo que se ha procesado antes en la máquina en cuestión, por lo que la variación principal del valor de la función objetivo de una iteración respecto a la siguiente vendrá dada por la variación de los tiempos de ajuste. Por este razonamiento, el incremento límite se calcula en cada iteración de la siguiente forma: max **100 b aS IObj = (5.3) Donde: - a es el parámetro de entrada del algoritmo. - S es la media aritmética de todos los tiempos de set-up Sijk. - Objb es el valor de la función objetivo para la mejor secuencia parcial encontrada hasta el momento. De igual forma que en la tercera versión (V.3), se repiten todos los movimientos de la lista cada vez que se inserte un nuevo trabajo en la secuencia parcial, actualizando la mejor secuencia (y por tanto la lista) en caso de que se produzcan mejoras respecto a la función objetivo. El pseudocódigo correspondiente a la heurística V.4 se muestra en la Figura 5.8. 31 31 Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. Figura 5.7. Pseudocódigo procedimiento V.3. [Fuente: Elaboración propia] Entrada: datos de la instancia, parámetro t Salida: Пb, Objb Inicio 1 jj m i i Pp  = = ; J = { 1  ,…, n  } verificándose que 1 P  ≥ 2 P  ≥ … n P  ; Asignar a Obj el valor de la función objetivo para J; П (1) = { 1  }; capacidad_L = t * n; L = ∅; comentario: lista que contiene los movimientos prometedores, inicialmente vacía. Para k = 2 hasta n hacer Insertar el trabajo k  en todas las posibles posiciones j de П (k – 1), con j ∈ {1,…, k}; П (k) = secuencia obtenida insertando k  en la posición de П (k – 1) con menor valor de la FO (Objb); CL x (k) (con x ∈ {1,…, k}) = trabajo anterior a k  , tras evaluar k  en la posición x. Hacer que ObjCL x denote tal valor de la función objetivo; Para x = 2 hasta k hacer ICL x = (ObjCL x - Objb) / Objb * 100; Si ocupación_L < capacidad_L entonces Asignar movimiento (CL x (k), k  , ICL x) a L; Fin Por el contrario Imax = mayor incremento (I) contenido en L; Si ICL x < Imax entonces Reemplazar el movimiento contenido en L correspondiente al Imax por (CL x (k), k  , ICL x); Fin Fin Fin Si k > 2 entonces Para h = 0 hasta ocupación_L hacer П’ (k) = permutación obtenida realizando el movimiento h de la lista L en П (k). Asignar a Obj’ su valor de la función objetivo; Si Obj’ < Objb entonces Пb (k) = П’ (k); Objb = Obj’; Actualizar L (eliminar movimiento realizado de la lista e incluir el recién deshecho en su lugar); Fin Fin Fin Fin Si Obj < Objb entonces Objb = Obj; Пb = J; Fin Devolver Пb, Objb Fin Aplicación de la metodología 32 32 Figura 5.8. Pseudocódigo procedimiento V.4. [Fuente: Elaboración propia] Entrada: datos de la instancia, parámetro a Salida: Пb, Objb Inicio 1 jj m i i Pp  = = ; J = { 1  ,…, n  } verificándose que 1 P  ≥ 2 P  ≥ … n P  ; Asignar a Obj el valor de la función objetivo para J; П (1) = { 1  }; L = ∅; comentario: lista que contiene los t movimientos prometedores, inicialmente vacía. Para k = 2 hasta n hacer Insertar el trabajo k  en todas las posibles posiciones j de П (k – 1), con j ∈ {1,…, k}; П (k) = secuencia obtenida insertando k  en la posición de П (k – 1) con menor valor de la función objetivo (Objb); CL x (k) (con x ∈ {1,…, k}) = trabajo anterior a k  , tras evaluar k  en la posición x. Hacer que ObjCL x denote tal valor de la función objetivo; Ilimite = (a* S ) / Objb * 100; Para j = 2 hasta k hacer ICL x = (ObjCL x - Objb) / Objb * 100; Si ICL x < Ilimite entonces Asignar movimiento (CL x (k), k  , ICL x) a L; Fin Fin Si k > 2 entonces Para h = 0 hasta ocupación_L hacer П’ (k) = permutación obtenida realizando el movimiento h de la lista L en П (k). Asignar a Obj’ su valor de la función objetivo; Si Obj’ < Objb entonces Пb (k) = П’ (k); Objb = Obj’; Actualizar L (eliminar movimiento realizado de la lista e incluir el recién deshecho en su lugar); Fin Fin Fin Fin Si Obj < Objb entonces Objb = Obj; Пb = J; Fin Devolver Пb, Objb Fin 33 6 EVALUACIÓN COMPUTACIONAL partir de la implementación de las heurísticas anteriores, se han evaluado bajo las mismas condiciones un conjunto de instancias en cada uno de los cuatro algoritmos aproximados propuestos para la resolución del problema analizado. Se presentan a continuación los bancos de pruebas e indicadores usados para evaluar su desempeño, y los resultados obtenidos en la comparación, comentándolos brevemente. 6.1 Bancos de pruebas Para el problema objeto del estudio se definen los parámetros correspondientes al número de trabajos n, número de máquinas m, tiempos de proceso pij, y tiempos de set-up Sijk. Se generarán para ello un conjunto de instancias que contengan los datos de entrada para el problema, similar a las propuestas por Vallada y Ruiz (2011). El conjunto de instancias generadas se compone por la combinación de los siguientes números de trabajos y máquinas respectivamente: n = {50, 100, 150, 200, 250} y m = {10, 15, 20, 25, 30}. Respecto a los tiempos de proceso, se han generado aleatoriamente siguiendo una distribución uniforme con valores entre 1 y 99. Para los tiempos de set-up, al igual que los tiempos de proceso, se han generado aleatoriamente según una distribución U (1, γ). El parámetro γ de la distribución uniforme toma los valores 9, 49, 99 y 124, generando así 4 subconjuntos de datos: U (1, 9), U (1, 49), U (1, 99) y U (1, 124), respectivamente. Además, se han realizado 10 replicaciones para cada una de las posibles combinaciones anteriores, generando así un total de 1000 instancias para la comparación de las heurísticas propuestas. 6.2 Indicadores de desempeño Puesto que cada una de las 4 heurísticas a comparar proporcionarán soluciones con distinto nivel de calidad en un tiempo de cómputo distinto, se usarán indicadores que midan ambas magnitudes, como son: - Average Relative Percentage Deviation (ARPDh): mide la media de la calidad de las soluciones obtenidas por cada heurística (RPDih) para el conjunto de iteraciones evaluadas. 1 , 1,..., Iih hi RPD ARPD h H I = =  =  (6.1) - Average Computational CPU Times (ACT): mide el tiempo (T) que ha tardado cada heurística de media al evaluar las iteraciones. 1 , 1,..., Iih hi T ACT h H I = =  =  (6.2) Donde: - H es el número de algoritmos bajo comparación (   1,...,hH ) - I es el número de instancias (   1,...,iI ) A Evaluación computacional 34 34 La calidad de las soluciones se mide con la desviación del valor de la función objetivo obtenido con la heurística h para la iteración i (Objih) respecto al mejor valor obtenido entre todas las heurísticas para esa iteración, como se puede ver en la siguiente ecuación: *100, 1,..., ih i ih i Obj Mejor RPD h H Mejor − =  = (6.3) Para comparar los algoritmos aproximados en cuanto a su tiempo, se mide la desviación mediante el siguiente indicador: - Average Relative Percentage computation Time (ARPT): 1 1 , 1,..., Iih hi RPT ARPT h H I = = +  =  (6.4) Donde: , 1,..., ih i ih i T ACT RPT h H ACT − =  = (6.5) Siendo: 1 , 1,..., Hih ih T ACT i I I = =  =  (6.6) 6.3 Valores parámetros Cada una de las heurísticas requiere como dato de entrada el valor de un parámetro. Al influir el parámetro directamente en el esfuerzo computacional del algoritmo, se evaluarán los algoritmos para diferentes valores de los parámetros (ver Fernández-Viagas et al., 2020 para enfoques similares). Para comparar valores diversos de los parámetros que sean representativos y proporcionen resultados distantes en cuanto a calidad y tiempo, se ha decidido establecer los siguientes rangos de valores: - Versión 1: x = {0.2, 0.4, 0.6, 1}, siendo x el porcentaje de movimientos en tanto por uno de la iteración anterior que se reinsertan en cada iteración. - Versión 2: y = {0.02, 0.05, 0.15, 0.5}; al parámetro x se le ha dado un valor constante de 0.2. Se recuerda que el parámetro y indica la proporción de iteraciones que se tienen en cuenta a la hora de reinsertar movimientos de la lista. Los movimientos de la lista tienen una caducidad de (z = ⌊𝑦 ∗ 𝑛⌋) iteraciones. - Versión 3: t = {0.2, 0.8, 2.5, 5}, donde t determinaba el tamaño de la lista, (tamaño = ⌊𝑡 ∗ 𝑛⌋). - Versión 4: a = {0.1, 0.3, 0.5, 1}, siendo a un factor que multiplica la media de los tiempos de set-up en el cálculo del incremento límite de la ecuación (5.3). Así se compararán los 4 algoritmos con 4 parámetros distintos cada uno, resultando en 16 variantes de las heurísticas propuestas a comparar. Además, se ha incluido en la comparación la heurística NEH, para usarla como referencia en cuanto a los cambios producidos en calidad de la solución y tiempo de cómputo por el resto de las heurísticas propuestas en comparación con ella. 35 35 Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. 6.4 Resultados Todas las heurísticas han sido codificadas en lenguaje de programación C# usando Visual Studio en un Intel Core i7-7700 con 3.6GHz, 16 GB RAM, con Microsoft Windows 10 64 bit, y usando las mismas funciones y librerías de forma común. A continuación en la Tabla 6.1 se presentan los valores obtenidos de ARPD para cada heurística, agrupados por número de trabajos, máquinas, y parámetro γ. Tabla 6.1. Valores detallados de ARPD agrupados por n, m y γ. En relación a estos resultados se puede destacar que: - Las heurísticas funcionan mejor para una menor variabilidad de los tiempos de set-up (parámetro γ pequeño). A medida que la variabilidad de los tiempos de set-up aumenta, la calidad de la solución se ve reducida, excepto en el caso de la versión 4 (V.4), en la cual se ha tenido esto en cuenta a la hora de calcular el límite máximo (véase sección 5.5). - Por lo general, a mayor valor de los parámetros de entrada se obtienen mejores resultados, aunque requiere más tiempo computacional, ya que se prueban más combinaciones. No es el caso de la versión 1 (V.1) que para valores altos del parámetro x (cuando se repiten gran cantidad de movimientos prometedores de la iteración anterior), no solo no se aprecian mejoras significativas, sino que la solución llega a dispersarse y se obtienen peores soluciones (falta de intensificación, exceso de diversificación). Por esto se deduce que en esta versión no es conveniente probar en cada iteración más del 50% de los movimientos prometedores de la iteración anterior, para obtener mejores soluciones y no aumentar el tiempo de cómputo innecesariamente. - En cuanto a la versión 2 (V.2) puede observarse que por lo general funciona notablemente mejor para instancias con mayor número de trabajos. Esto se debe a que el parámetro y se ha establecido en relación a n, dando lugar a un mayor número de combinaciones cuanto mayor es n. - Por lo general, las heurísticas funcionan mejor cuando el taller de flujo se compone de un número mayor de máquinas, ya que existe un mayor número de posibles soluciones. Heurística n m γ Media 50 100 150 200 250 10 15 20 25 30 9 49 99 124 NEH 2,46 2,48 2,54 2,60 2,74 3,11 2,68 2,56 2,29 2,18 1,79 2,39 2,87 3,21 2,564 V.1 (0,2) 2,04 2,09 2,17 2,15 2,21 2,52 2,25 2,08 1,95 1,86 1,54 1,96 2,40 2,63 2,132 V.1 (0,4) 2,03 2,02 2,10 2,15 2,18 2,52 2,17 2,06 1,93 1,81 1,49 1,96 2,34 2,60 2,098 V.1 (0,6) 1,99 2,03 2,12 2,14 2,20 2,54 2,15 2,04 1,95 1,79 1,51 1,99 2,35 2,53 2,096 V.1 (1) 2,00 2,05 2,14 2,17 2,25 2,51 2,19 2,05 1,95 1,91 1,56 1,95 2,37 2,60 2,121 V.2 (0,02) 2,04 1,79 1,64 1,58 1,47 2,05 1,78 1,64 1,55 1,51 1,28 1,56 1,88 2,10 1,704 V.2 (0,05) 1,96 1,38 1,22 1,05 1,04 1,61 1,40 1,32 1,18 1,13 0,96 1,17 1,43 1,76 1,328 V.2 (0,15) 1,35 0,89 0,69 0,59 0,48 0,98 0,81 0,76 0,76 0,68 0,50 0,70 0,88 1,12 0,799 V.2 (0,5) 1,06 0,56 0,37 0,26 0,19 0,54 0,49 0,51 0,46 0,44 0,21 0,43 0,58 0,73 0,488 V.3 (0,2) 1,99 1,85 1,93 1,95 2,04 2,38 2,04 1,90 1,77 1,66 1,45 1,75 2,18 2,42 1,950 V.3 (0,8) 1,45 1,39 1,30 1,34 1,42 1,62 1,48 1,34 1,26 1,18 1,13 1,24 1,50 1,64 1,377 V.3 (2,5) 0,95 0,87 0,86 0,82 0,88 0,99 0,88 0,81 0,86 0,84 0,70 0,76 0,97 1,07 0,876 V.3 (5) 0,71 0,54 0,59 0,57 0,58 0,74 0,62 0,62 0,49 0,53 0,50 0,53 0,66 0,71 0,599 V.4 (0,1) 2,14 2,06 2,12 2,06 2,10 2,48 2,19 2,03 1,96 1,83 1,61 1,91 2,33 2,54 2,098 V.4 (0,3) 1,73 1,48 1,44 1,35 1,38 1,68 1,50 1,41 1,43 1,36 1,44 1,32 1,50 1,64 1,475 V.4 (0,5) 1,32 1,10 1,07 0,99 0,94 1,15 1,09 1,12 1,05 1,01 1,24 0,97 0,97 1,16 1,084 V.4 (1) 0,95 0,55 0,43 0,36 0,41 0,56 0,54 0,51 0,56 0,54 0,91 0,41 0,37 0,48 0,541 Evaluación computacional 36 36 En la Tabla 6.2 se presenta la recopilación de los indicadores de desempeño de calidad y tiempo. Tabla 6.2. Resumen de los resultados computacionales. Heurística ARPD ACT ARPT NEH 2,564 1,416 0,307 V.1 (0.2) 2,132 1,696 0,373 V.1 (0.4) 2,098 1,978 0,434 V.1 (0.6) 2,096 2,260 0,495 V.1 (1) 2,121 2,823 0,619 V.2 (0.02) 1,704 2,711 0,501 V.2 (0.05) 1,328 4,393 0,723 V.2 (0.15) 0,799 9,287 1,341 V.2 (0.5) 0,488 20,994 2,894 V.3 (0.2) 1,950 1,853 0,411 V.3 (0.8) 1,377 3,133 0,700 V.3 (2.5) 0,876 6,446 1,365 V.3 (5) 0,599 12,179 2,484 V.4 (0.1) 2,098 1,911 0,401 V.4 (0.3) 1,475 3,381 0,626 V.4 (0.5) 1,084 5,707 0,947 V.4 (1) 0,541 17,414 2,379 Como era previsto, los algoritmos conllevan un mejor tiempo para valores de sus parámetros más pequeños. Se puede observar en la tabla anterior cómo algunas heurísticas mejoran notablemente la calidad de la solución en comparación con la NEH sin incrementar el tiempo de cómputo en gran medida. Como se esperaba, el algoritmo más lento (V.2 para y = 0,5) es el que proporciona soluciones de mayor calidad. Para visualizar gráficamente la relación calidad-tiempo que presenta cada heurística se expone la siguiente Figura 6.1 donde el eje de abscisas se representa la desviación en cuanto a tiempo y en el eje de ordenadas la desviación en cuanto a calidad. Como se puede observar, todas las heurísticas propuestas mejoran en calidad a la solución proporcionada por la NEH para el problema estudiado, aunque requieren de mayor tiempo de cálculo. Por lo general, se obtienen mejores soluciones en un tiempo mayor. Dependiendo de la prioridad dada a cada aspecto (calidad de la función objetivo o esfuerzo computacional requerido), será más útil una heurística que proporcione resultados muy buenos en mayor tiempo, o se preferirá una solución rápida de una calidad intermedia. Adicionalmente, en la Tabla 6.3 se presentan las relaciones de dominancia existentes entre las distintas versiones que se han comparado. Cabe destacar, por ejemplo, que V.3(2.5) está dominada por V.2(0.15) pero esta última no está dominada, es decir, ninguna otra heurística presenta menor valor de ambos objetivos (Cmax y CPU time). Lo mismo ocurre con V.3(5) que está dominada por V.4(1), la cual no está dominada. Además, no hay ninguna heurística que domine a V.3(0.2), pero en cambio esta domina a V.1(0.4), V.1(0.6) y V.1(1). Otros dos casos más de heurísticas no dominadas son el de V.4(0.1), la cual domina a V.1(1) y V.1(0.4); y el de V.2(0.02), que domina a V.1(1). 37 37 Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria. Tabla 6.3. Relaciones de dominancia. Heurística Dominada por: Domina a: NEH - - V.1 (0.2) - - V.1 (0.4) V.3(0.2), V.4(0.1) V.1(1) V.1 (0.6) V.3(0.2) V.1(1) V.1 (1) V.1(0.4), V.1(0.6), V.2(0.02), V.3(0.2), V.4(0.1) - V.2 (0.02) - V.1(1) V.2 (0.05) - - V.2 (0.15) - V.3(2.5) V.2 (0.5) - - V.3 (0.2) - V.1(0.4), V.1(0.6), V.1(1) V.3 (0.8) - - V.3 (2.5) V.2(0.15) - V.3 (5) V.4(1) - V.4 (0.1) - V.1(1), V.1(0.4) V.4 (0.3) - - V.4 (0.5) - - V.4 (1) - V.3(5) Figura 6.1. ARPD contra ARPT. [Fuente: Elaboración propia] 39 7 CONCLUSIONES ara concluir, en este último capítulo del documento se comentan las conclusiones obtenidas con la realización del proyecto, incluyendo las posibles futuras líneas de investigación que podría tener. 7.1 Conclusiones Tras el estudio del problema objeto de este proyecto (Fm|prmu, Sijk|Cmax), se concluye que por su complejidad para obtener el óptimo en un tiempo admisible, el procedimiento más adecuado de resolución es mediante métodos aproximados. En vista de los resultados obtenidos, la combinación de una heurística constructiva con una búsqueda local de enfoque iterativo es una buena elección para resolver este problema. En concreto, la metodología propuesta para su resolución ha presentado mejoras en la calidad de las soluciones respecto a la heurística NEH usada como base para las modificaciones. Por lo general, existe relación entre calidad de la solución y tiempo computacional: las heurísticas desarrolladas proporcionan mejores soluciones en un mayor tiempo, mientras que las soluciones más rápidas son de menor calidad. Según el valor establecido para los parámetros de entrada a los algoritmos aproximados, la solución será mejor o peor, y requerirá de un mayor o menor tiempo. Valorando ambos criterios (tiempo y calidad), las mejores heurísticas se corresponden con: V.2 (0.05), V.3(0.8) y V.4(0.5). Además, la heurística V.4 proporciona muy buenos resultados para tiempos de set-up muy variables, ya que en su procedimiento trata de ajustar el criterio de movimientos prometedores en función de la media de estos tiempos. Respecto a los algoritmos propuestos, se podría concluir que no interesa un tamaño de lista estático, ya que para instancias con distintos volúmenes de trabajos no sería igual de eficiente. Aunque esto se ha tratado de evitar ajustando el tamaño en función del número de trabajos, no ha resultado del todo efectivo, ya que el tiempo de cálculo aumentaría a mayor volumen de trabajos. Por ello quizá sea conveniente ajustar dinámicamente el tamaño de la lista o el número de movimientos que se repiten en cada iteración, modificándolo en función de algún parámetro en cada iteración del algoritmo o según otro criterio. Además, cuando el tamaño de tamaño de lista es demasiado grande se podrían crear problemas de memoria y tiempo de cómputo. Por tanto, los resultados generados en el desarrollo de este proyecto se consideran satisfactorios, aunque existen diversas mejoras a realizar para los métodos de resolución propuestos que reducirían el tiempo de cómputo y quizá puedan proporcionar mejores soluciones. 7.2 Futuras líneas de investigación Respecto a las posibles líneas de investigación que da lugar este proyecto, se podrían presentar variantes de los métodos propuestos que incluyan mejoras en cuanto a la inserción de movimientos prometedores de forma más eficiente, o un mejor ajuste de los tamaños de las matrices o listas que contienen dichos movimientos. Además, como se ha comentado con anterioridad, en dos de las modificaciones planteadas (V.3 y V.4) se hace uso de un valor para medir la desviación respecto a la mejor función objetivo encontrada hasta el momento (I). El cálculo de dicho valor puede favorecer o perjudicar a las combinaciones de movimientos en función del instante en el que se calcula, provocando que en las primeras iteraciones del algoritmo el denominador sea mucho menor que en las últimas, causando una distorsión en la medida de la desviación. Sería conveniente estudiar esta medida, tratando de incluir en el cálculo un parámetro que compense este error en función de cada iteración. P