Programación de Operaciones en Procesos de Fabricación Aditiva

fvsv Equation Chapter 1 Section 1 Trabajo Fin de Grado Ingeniería de Tecnologías Industriales Programación de Operaciones en Procesos de Fabricación Aditiva Autor: Enrique Hernández Malfeitos Tutor: Jose Manuel Framiñán Torres Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Sevilla, 2022 iii Trabajo Fin de Grado Ingeniería de Tecnologías Industriales Programación de Operaciones en Procesos de Fabricación Aditiva Autor: Enrique Hernández Malfeitos Tutor: Jose Manuel Framiñán Torres Catedrático de Universidad Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2022 v Trabajo Fin de Grado: Programación de Operaciones en Procesos de Fabricación Aditiva Autor: Enrique Hernández Malfeitos Tutor: Jose Manuel Framiñán Torres El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2022 El Secretario del Tribunal vii A mi madre, por todo el apoyo y cariño que ha mostrado hacia mi persona toda mi vida. ix Resumen En el este proyecto se analiza la tecnología de fabricación aditiva estudiando sus principales ventajas e inconvenientes. Una vez examinado dicho método de fabricación y las características de la maquinaria con la que se fabrican las piezas, se detecta que uno de los problemas que presenta es el alto tiempo que se necesita invertir en la fabricación de las piezas. Por lo tanto, se trata de solucionar dicho problema llevando a cabo una propuesta de un algoritmo el cual realice la programación de las operaciones para ofrecer así una solución que consiste en aportar una secuencia de trabajos en los cuales se definen que piezas van agrupadas en lotes y en que máquina deben procesarse dichos lotes, con el objetivo de minimizar el tiempo total de finalización (Makespan). En dicho problema intervienen distintos factores que son explicados convenientemente, como, por ejemplo, las características de las máquinas y de las piezas. Para su resolución se elabora una metaheurística del tipo de búsqueda de vecindario variable la cual incluye distintos algoritmos. Una vez confeccionada, se estudian los resultados obtenidos para una serie de instancias y se proponen distintas alternativas diferentes para así llevar a cabo una comparativa y finalmente decidir qué alternativa proporciona mejores resultados según los objetivos del usuario. ÍNDICE DE FIGURAS Ilustración 1. Gráfico del aumento de interés por la fabricación mediante impresión 3D [6]. 2 Ilustración 2. Concepto de fabricación sustractiva comparado con AM [7] 5 Ilustración 3. Procedimiento para la elaboración de una pieza mediante fabricación aditiva [8]. 6 Ilustración 4. Esquema de problema de empaquetado. Elaboración propia. 13 Ilustración 5. Diagrama del algoritmo NFDH. Elaboración propia. 15 Ilustración 6. Diagrama del algoritmo FFDH. Elaboración propia. 16 Ilustración 7. Diagrama del algoritmo BFDH. Elaboración propia. 17 Ilustración 8. Ejemplo de vecino de tipo Flip. Elaboración propia. 18 Ilustración 9. Ejemplo vecino tipo Swap. Elaboración Propia. 18 Ilustración 10. Ejemplo vecindad tipo Job Alloc 1. Elaboración propia. 19 Ilustración 11. Diagrama de algoritmo Q-Learning. Elaboración propia. 21 Ilustración 12. Metaheurística completa. Elaboración propia. 23 Ilustración 13.Diagrama de Gantt del ejemplo numérico. Elaboración propia. 32 Ilustración 14. Modificación de la vecindad Flip. Elaboración propia. 34 Ilustración 15. Comparación de vecindades Swap. Elaboración propia. 35 Ilustración 16. Ejemplo de vecindad tipo Job Alloc 2. Elaboración propia. 36 Ilustración 17. Ejemplo de vecindad tipo Job Alloc modificada. Elaboración propia. 36 xvii 1 1 OBJETO DEL PROYECTO l objeto de este proyecto es el desarrollo de una metaheurística con la cual se consiga programar una serie de trabajos a procesar en un conjunto de impresoras 3D de diferentes características con el objetivo de terminar todos los trabajos lo antes posible. En este proyecto se estudia la mejor manera de agrupar las piezas en lotes de trabajo para ser procesadas por un conjunto de máquinas de fabricación aditiva (de diferentes especificaciones), así como las máquinas por las que serán fabricadas, mediante la elaboración de algoritmos. La agrupación de piezas en lotes es necesaria debido a que las máquinas tienen la capacidad de conformar varias piezas simultáneamente en una bandeja de fabricación. En dicho análisis intervienen una serie de parámetros, como por ejemplo las capacidades de las máquinas, a nivel de área de procesamiento, o el tiempo de formación por unidad de volumen, que definen los tiempos de fabricación de cada grupo de partes. La metaheurística estudiada tiene base en estudios previos de la literatura [1] y se elaboran diversas variaciones, de modo que se pueda hacer una comparación final en la cual se seleccione el programa que obtiene mejores resultados dependiendo de los objetivos que se tengan. El método en cuestión consta de dos fases: una fase inicial en la cual se elabora una agrupación de piezas en lotes y, a continuación, se inicia una segunda fase en la cual se realiza una búsqueda local iterada en la cual se estudian soluciones similares con el fin de reducir el tiempo total de fabricación de los trabajos. Para el diseño del programa se ha hecho uso del lenguaje de programación Python [2] en el entorno de desarrollo Anaconda® [3] y de conceptos de la librería Scheptk [4]. En cuanto a las metodologías usadas tanto para el problema de empaquetado, como para la búsqueda de vecinos, se ha tomado como referencia lo descrito en [1] así como para el algoritmo Q-Learning, que permite realizar el proceso iterativo de búsqueda local de manera más eficiente. 1.1 Motivación de la elección del problema La fabricación aditiva (AM, Additive Manufacturing) es una tecnología en desarrollo capaz de revolucionar la industria manufacturera, ya que su principal característica es la polivalencia que posee este sistema a la hora de imprimir objetos con un nivel de detalle muy alto, aparte de simplificar todas las operaciones de elaboración del producto en una sola máquina. Además, mediante dicha tecnología, es posible explotar una amplia variedad de materiales para crear productos que van desde prótesis médicas hasta componentes de la industria aeroespacial. Sin embargo, la mencionada tecnología, como toda tecnología primeriza, tiene desventajas frente a otras tecnologías de fabricación, y la principal es el tiempo invertido en la fabricación de los productos, cuya solución es mejorar las prestaciones de las máquinas, refinando diferentes partes de su proceso, añadiendo técnicas nuevas de conformado, herramientas distintas, reglas de diseño innovadoras, etc. como se muestra en [5] . Pero también se puede llegar a optimizar la fabricación, en términos de tiempo de fabricación, con este tipo de maquinaria de forma significativa haciendo hincapié en la programación de las operaciones que se llevan a cabo. En la ilustración 1 [6] se representa el aumento del uso de la fabricación AM en los últimos años. E Objeto del proyecto 2 2 Ilustración 1. Gráfico del aumento de interés por la fabricación mediante impresión 3D [6]. Como se presenta en [1], en torno a dicho método de fabricación, normalmente las contribuciones científicas se suelen especializar en diferentes decisiones del proceso, como, por ejemplo, determinar la orientación de las piezas a la hora de ser procesadas, el orden de estas, o el problema de empaquetado previo para ahorrar tiempos de Set-Up, por lo que es interesante desarrollar un método que trate de aportar una buena solución desde una perspectiva de inicio a fin del procedimiento. Otra característica que hace de interés dicho problema es que se trata de la formulación más genérica en cuanto a fabricación aditiva, esto quiere decir que, la solución a dicho problema abarca tanto el entorno en cuestión (disposición de máquinas 3D con diferentes especificaciones en paralelo) como el problema de máquinas 3D idénticas en paralelo o el problema de una única máquina 3D. 1.2 Definición de los capítulos del trabajo El proyecto se desarrolla en seis capítulos: Objeto del Proyecto, Descripción del Problema, Descripción de la metodología, Implementación de la metodología, Variantes propuestas y Resultados y Conclusión. En el primer capítulo, “Objeto del Proyecto”, se introduce el problema de programación de operaciones aplicado a la fabricación aditiva. También se explica en qué consiste, concretando los pasos que se han seguido para obtener la resolución y aquellas variables que intervienen. A continuación, se explica el motivo por el cual se pretende abarcar el trabajo en cuestión y la importancia que tiene en su entorno. Finalmente, se presenta un breve resumen del contenido de cada uno de los bloques de los que dispone el documento con el objetivo de facilitar al lector el temario de una manera sencilla. El segundo capítulo, “Descripción del Problema”, está enfocado en el estado del arte de la fabricación aditiva, en el cual se exponen los distintos modos de fabricación con impresoras 3D, los pros y contras de dicha tecnología, y una revisión de la literatura para obtener referencias y resultados con los que comparar nuestra metaheurística y el porqué de su elección. En el tercer capítulo, “Descripción de la metodología”, se explican las diferentes maneras de resolver el problema, sus ventajas e inconvenientes, y el método elegido, así como su correspondiente justificación y explicación detallada. En el cuarto capítulo, “Implementación de la metodología”, se expone toda la información necesaria para la correcta comprensión de la metodología utilizada, como las decisiones que se han tomado a priori, o las hipótesis que influyen en el desarrollo de la técnica. Este bloque, para ser mejor comprendido, se basa en todo momento en un ejemplo de un problema a solucionar. 3 Programación de Operaciones en Procesos de Fabricación Aditiva En el quinto capítulo, “Variantes propuestas”, se introducen diferentes modificaciones que afectan a la metaheurística con el objetivo de mejorarla en función de los objetivos que se tengan y de comparar finalmente todas las alternativas. En el sexto capítulo, “Resultados y conclusión”, se presenta un resumen de los resultados obtenidos con la metaheurística elaborada, así como de las diferentes variaciones que se han llevado a cabo tomando como base la metaheurística principal, la comparación de las mismas con diferentes criterios, y una conclusión generalizada acerca del problema en cuestión, de la metaheurística y los resultados obtenidos, y de los posibles caminos que podrían tomar los problemas de estas características en un futuro. Objeto del proyecto 4 4 5 2 DESCRIPCIÓN DEL PROBLEMA 2.1 Introducción a la fabricación aditiva Para modificar la forma de un material existen distintas técnicas de fabricación: la fabricación sustractiva, la fabricación por deformación, y la fabricación por adicción. En la fabricación sustractiva las formas se obtienen mediante la exclusión de material de un volumen de material mayor. En la fabricación por deformación, la geometría se consigue al dar forma a un bloque de material mediante una matriz con una cavidad con la figura que se quiere obtener. Y finalmente, mediante la fabricación por incremento de material (o adicción), la geometría se obtiene mediante la manipulación del material de forma minuciosa y depositarlo de forma muy precisa para construir el sólido. Las impresoras 3D implementan la última forma de fabricación descrita a escala micrométrica. En la ilustración 2 [7] se puede observar gráficamente la diferencia entre la fabricación aditiva y la fabricación sustractiva. Ilustración 2. Concepto de fabricación sustractiva comparado con AM [7] 2.1.1 Procedimiento de fabricación de piezas mediante impresión 3D Una vez se conoce el fundamento principal de la fabricación aditiva, se procede a definir, a rasgos generales, el proceso que siguen las impresoras 3D para conformar los productos [8]. Para comenzar, se necesita un modelo digital 3D que normalmente se obtiene con programas informáticos, como por ejemplo Autodesk® o SolidWorks®. Una de las características que hacen a dicha tecnología tan interesante es que, de manera digital, se pueden llegar a obtener geometrías muy complejas que mediante técnicas tradicionales jamás se conseguirían. Además, también cabe la posibilidad de llevar a cabo ingeniería inversa, es decir, obtener el modelo digital de una forma física mediante un escaneado 3D. A continuación, se convierte el modelo anteriormente formado en un fichero estandarizado para la lectura en la máquina. Este formato, por regla general es el .STL, aunque los tipos de fichero soportados por las impresoras 3D evolucionan de manera muy rápida al igual que las propias máquinas. Descripción del problema 6 En el siguiente paso, mediante un programa informático denominado “slicer” se prepara el fichero .STL para el procesamiento en la impresora 3D. En dicho procedimiento se establecen valores para los distintos parámetros de fabricación, como, por ejemplo, la temperatura de conformado, la adición de material de soporte si fuera necesario, las capas de material o la orientación de la pieza. Finalmente, una vez preparado el archivo para su procesamiento con todos sus valores ajustados e información necesaria, se introduce en la impresora 3D para la fabricación de la pieza. Además, las máquinas también cuentan con la posibilidad de variar la configuración de los parámetros, en caso de que fuera necesario, durante el procedimiento de conformado. Dependiendo de la máquina usada o la finalidad de la pieza obtenida, el resultado puede ser final o no, y en caso de que no fuese definitivo, pasa por procesos de post-procesado para refinar su forma. A modo de resumen, se puede observar en la ilustración 3 [8] el proceso genérico que se lleva a cabo desde principio a fin a la hora de fabricar una pieza en una impresora 3D. Ilustración 3. Procedimiento para la elaboración de una pieza mediante fabricación aditiva [8]. 2.1.2 Técnicas de fabricación aditiva Aunque el proceso de fabricación genérico para la fabricación aditiva es el descrito anteriormente, existen diferentes tecnologías de fabricación aditiva [7, 9, 10] que tienen ciertas peculiaridades. Según la norma UNE- EN ISO/ASTM 52900:2017 los procesos de AM vienen clasificados en siete grupos: • Inyección Aglutinante (BJ): se trata de una técnica en la cual se conforma el objeto mediante la deposición de un líquido aglutinante sobre un lecho de polvo, de manera que el líquido se queda adherido al polvo dando la forma del objeto. Para el conformado total del objeto se repite dicho proceso en varias capas. Usada principalmente para objetos de gran tamaño y con formas complejas. • Deposición Directa de Energía (Directed Energy Deposition, DED): se le da la forma deseada al producto en una atmósfera inerte mediante alimentación continua de material metálico en un punto focal de un láser formando una deposición de un material fundido. • Proyección de material (Material Jetting): la fabricación de formas mediante esta técnica tiene base en la impresión con inyección de tinta, sin embargo, a diferencia de las impresoras convencionales de dos 7 Programación de Operaciones en Procesos de Fabricación Aditiva dimensiones, en aquellas de fabricación aditiva se depositan y posteriormente se solidifican gotas de material, capa a capa, para formar un objeto en tres dimensiones. • Fusión de Lecho en Polvo (Powder Bed Fusion, PBF): este método de fabricación es similar al de deposición directa de energía, con la diferencia de que el material depositado ha sido fundido previamente, mientras que en la técnica DED se hace a la vez que se realiza la alimentación. Para el conformado de las piezas, se deposita en un plano una capa de polvo del material, después se fija dicho polvo con la forma de la pieza y se calienta la superficie deseada para así formar una capa. Repitiendo el proceso capa a capa se consigue la forma final del objeto que se desea imprimir. Dentro de la clasificación PBF, las técnicas más conocidas son la Selective Laser Sintering (SLS) y la Selective Laser Melting (SLM), donde esta última se caracteriza por tener una mayor capacidad de producir objetos con mayor complejidad, de manera más compacta y con mayor rapidez debido al uso de láseres mucho más potentes. También se encuentran otros tipos de fabricación de tipo PBF como la técnica Electron Beam Melting (EBM), que se caracteriza por usar un haz de electrones en vez de un láser para la fusión. • Laminado de Hojas (Sheet Lamination): en este proceso la forma general del objeto se consigue con la superposición de cierto material, y el exceso de material, para definir los detalles de la forma se eliminan cortándolo con un láser o mecánicamente. • Fotopolimerización en cuba (VAT Photoplymerization, VP): aquí, una luz (ya sea ultravioleta, o digital de alta definición) es proyectada sobre una resina fotosensible para ser solidificada. Capa a capa, el componente, a medida que se va solidificando, va formando la estructura tridimensional. Las técnicas más usadas de las del grupo de VP son la Estereolitografía (Stereolithography, SLA), que es también una de las técnicas de fabricación aditiva más antiguas, y la de Procesado por Luz Digital (Digital Light Processing, DLP). • Extrusión de material (Material Extrusion): es la técnica que más crecimiento ha logrado últimamente debido a que posee las grandes ventajas que presentan el resto de las técnicas. Dentro de dicho método de fabricación aditiva existen numerosas variantes, dentro de las cuales la más difundida es el modelado por deposición fundida (Fused Filament Modeling, FDM), este método consiste en ir fabricando el objeto depositando el material fundido en forma de finas líneas de material que forman capas y finalmente el objeto completo. 2.1.3 Ventajas y desventajas de la fabricación aditiva La tecnología de fabricación aditiva está ganando mucho terreno en el ámbito industrial y está experimentando un gran desarrollo debido a sus notables ventajas frente a las otras técnicas de fabricación ya mencionadas en el inicio de la sección presente, por ello, se van a mostrar los principales pros y contras de la tecnología de fabricación aditiva [7,9]. En primer lugar, esta técnica tiene la gran ventaja de que existe una muy alta precisión al igual que personalización a un coste bajo. En segundo lugar, también es importante destacar que todo el procedimiento de conformado del objeto viene atribuido a un solo proceso en una única máquina, mientras que en las técnicas de manufactura convencionales son necesarios distintos pasos en distintos equipos hasta llegar a la forma final. Esto significa un gran ahorro en maquinaria, mantenimiento y personal. A parte de la unificación de todo el proceso de fabricación, es una gran ventaja la flexibilidad de dicha técnica para modificar los diseños de los productos sin costes adicionales y sin generar retrasos en la producción. En tercer lugar, como se lleva a cabo una producción bajo demanda, se reducen costes de almacenamiento, logística y transporte. Finalmente, en cuanto al ámbito medioambiental, es una técnica muy limpia ya que se generan muy pocos residuos y cabe la posibilidad de reciclarlos in-situ. Por el contrario, a pesar de ser un sistema innovador y con un gran potencial, la fabricación aditiva tiene dos principales problemas. El primero se relaciona con la alta inversión que se tiene que realizar para tener un sistema de fabricación de este tipo debido al alto coste de los equipos, dicha cuestión será solucionada en el futuro si se normaliza este tipo de técnica de fabricación y aumenta la demanda de las impresoras 3D, reduciéndose así tanto su coste como su mantenimiento. La segunda está asociada al elevado tiempo de procesamiento de los trabajos Descripción de la metodología 14 Una vez se tiene el grupo de variables auxiliares comentado en el párrafo anterior se unen en otra lista, de manera que nuestra solución codificada tiene una forma tal que así: Donde las partes ik realmente, a la hora de programar, son un tipo de variable especial correspondiente a una clase que contiene todas las características de la pieza en cuestión. 15 Programación de Operaciones en Procesos de Fabricación Aditiva Ilustración 5. Diagrama del algoritmo NFDH. Elaboración propia. Descripción de la metodología 16 Ilustración 6. Diagrama del algoritmo FFDH. Elaboración propia. 17 Programación de Operaciones en Procesos de Fabricación Aditiva Ilustración 7. Diagrama del algoritmo BFDH. Elaboración propia. Descripción de la metodología 18 3.3 Búsqueda de vecindario variable Tras haber solucionado el problema de agrupamiento de piezas en grupos y haber obtenido una solución inicial, se procede a estudiar las opciones factibles similares a dicha solución, para ello se van a introducir los tres tipos de vecinos que se van a incluir en la metaheurística. En primer lugar, se explica cómo funciona la vecindad de tipo Flip. En este método se traslada una parte de cualquier trabajo a otro, dando igual a que máquina pertenezcan los trabajos. Un ejemplo de la obtención de un vecino de este tipo es el correspondiente a la ilustración 8. Ilustración 8. Ejemplo de vecino de tipo Flip. Elaboración propia. En segundo lugar, se describe la vecindad de tipo Swap. Para formar un vecino de una solución mediante esta técnica, se escogen dos partes de dos trabajos distintos y se intercambian, dando igual la máquina a la que pertenezcan. Un ejemplo de este tipo sería el mostrado en la ilustración 9. Ilustración 9. Ejemplo vecino tipo Swap. Elaboración Propia. Finalmente se detalla el funcionamiento de la vecindad del tipo Job Alloc. En este caso se eligen dos partes, independientemente de en qué máquina se sitúen, y se trasladan a un nuevo trabajo, localizado en cualquiera de las máquinas que haya. En la ilustración 10 se puede observar un ejemplo de vecino de este tipo. 19 Programación de Operaciones en Procesos de Fabricación Aditiva Ilustración 10. Ejemplo vecindad tipo Job Alloc 1. Elaboración propia. Es necesario cuantificar la cantidad de vecinos que se obtienen dependiendo del tipo de vecindad para analizar en detalle las vecindades, por lo que se va a demostrar cuantos vecinos tiene una solución dependiendo de la técnica que se use para obtener nuevas soluciones similares. En cuanto a la vecindad del tipo Flip se tiene un número total de vecinos igual a la ecuación 12 siendo n el número de partes de la instancia y k el número de trabajos de la solución. Esto se debe a que cada una de las partes puede ir destinada al resto de trabajos en los que no está situada. 𝑛∙(𝑘−1) (12) La vecindad tipo Swap cuenta con tantos vecinos como se calculan en la ecuación 13 puesto que cada parte se puede intercambiar con el resto de las partes. Aunque hay vecinos irrelevantes debido a que cambiar partes dentro de un mismo trabajo no modifica la solución del problema. 𝑛∙(𝑛−1) (13) La vecindad del tipo Job Alloc tiene tantos vecinos como se muestran en la ecuación 14, siendo m el número de máquinas al que puede ir destinado el nuevo trabajo y haciendo referencia el “2” de la ecuación a que se forman siempre parejas. En este caso no habrá vecinos que sean irrelevantes, porque eliminar dos partes de un mismo trabajo (cualesquiera de ellas) e introducirlas en uno nuevo influye en la solución. (𝑛 2) ∙ 𝑚. (14) 3.4 Algoritmo de autoaprendizaje Al tener distintos tipos de vecinos, es necesario implementar un algoritmo cuya función sea detectar qué tipo de vecindad es más rentable explorar, por lo tanto, se ha elegido el algoritmo Q-Learning [16]. Dicho algoritmo se basa en el autoaprendizaje y a medida que se van haciendo iteraciones indica que, con cierta probabilidad, con un tipo de vecindad se obtienen mejores resultados que con otra. Para comprender el funcionamiento de dicho algoritmo se describen primero sus variables principales: • Matriz de indicadores de mejora. Es una matriz cuadrada con un número de filas y columnas igual al número de tipos de vecindades que se tienen. El contenido de dicha matriz indica la mejora que se obtiene si vamos del estado i (fila) al estado j (columna), es decir, si se pasa de un tipo de vecindad a otra. Inicialmente todos los elementos de esta matriz son cero. • Q(i,j). Valor que ofrece una estimación del beneficio que se obtiene si se pasa de la vecindad i (fila) a la vecindad j (columna). • Best_sol. Variable que contiene la mejor solución obtenida hasta el momento. Descripción de la metodología 20 • A. Vector que indica qué tipos de vecindades pueden ser exploradas. Inicialmente todas sus componentes son 1, ya que todas las vecindades están disponibles. • R. Diferencia entre el Makespan de Best_sol y el mejor vecino de la vecindad a. El algoritmo está en funcionamiento siempre que haya vecindades que puedan mejorar la solución. Y se debe inicializar con un estado t igual a una vecindad que se considere oportuna. Cuando no haya vecindades disponibles, es decir, cuando el vector A esté vacío, el proceso de búsqueda de vecindario variable de la iteración i finaliza. En primer lugar, dentro de la fila t, con probabilidad ε se elige una vecindad aleatoria (columna de la matriz de indicadores de mejora) de entre las que haya disponibles, y con probabilidad 1 - ε se selecciona aquella que contenga el máximo Q (t, a). De manera que el estado a (la próxima vecindad para estudiar) depende de la probabilidad ε. En segundo lugar, una vez seleccionada la vecindad a, se explora por completo y se elige aquel vecino que permita obtener una mejor función objetivo. Posteriormente se compara el valor de la función objetivo del vecino seleccionado con aquel que se tiene guardado con la mejor solución que se ha obtenido en las anteriores iteraciones (Best_sol). En tercer lugar, si se mejora el valor de la función objetivo (R < 0), se guarda el vecino obtenido como la mejor solución en Best_sol y se procede a reiniciar el vector A, estableciendo todas sus componentes de nuevo a 1. Si por el contrario R > 0 se elimina la vecindad a de A haciendo 0 su correspondiente componente del vector A. Finalmente, se establece el valor de a (vecindad que se ha explorado) a la variable t (vecindad en la que se sitúa), además se actualizan los valores de la matriz Q(t, a) siguiendo la siguiente ecuación 15 : 𝑄(𝑡,𝑎)= 𝑄(𝑡,𝑎)+𝛼[𝑅+𝛾∙𝑚𝑎𝑥𝑎′𝜖𝐴{𝑄(𝑎,𝑎′)−𝑄(𝑡,𝑎)}] (15) Donde α es un parámetro entre 0 y 1 que indica la velocidad de aprendizaje y γ es una variable que indica el factor de descuento aplicado a la variable Q que acompaña en la fórmula. El algoritmo de autoaprendizaje Q-Learning se explica de manera esquemática con un diagrama en la ilustración 11. 21 Programación de Operaciones en Procesos de Fabricación Aditiva Ilustración 11. Diagrama de algoritmo Q-Learning. Elaboración propia. Descripción de la metodología 22 3.5 Perturbación de la solución A la hora de explorar distintas soluciones a partir de una solución inicial aleatoria mediante la búsqueda del mejor vecino posible usando el algoritmo de autoaprendizaje se corre el riesgo de encontrar una solución que sea un óptimo local, por lo tanto, es necesario modificar periódicamente, de una manera brusca, la solución con la que se está trabajando para abarcar así un mayor número de soluciones posibles. Con el objetivo de alcanzar la mayor cantidad de soluciones exploradas, el algoritmo se encarga de elaborar una solución totalmente aleatoria de la misma manera en que se inicializa la metaheurística: se forma una solución previa que se encargue de distribuir las partes a máquinas, posteriormente se ordenan las partes según su altura y finalmente se lleva a cabo el problema de empaquetado para obtener la nueva solución distinta. 3.6 Criterio de parada del algoritmo La mayoría de las metaheurísticas basan su criterio de parada en un número máximo de iteraciones del algoritmo implementado en cada caso, sin embargo, tomando como referencia [1], en la metaheurística desarrollada se implementa un criterio de parada probabilístico. El criterio propuesto tiene la finalidad de ahorrar tiempos computacionales altos de manera innecesaria, por una parte, y de asegurar, por otra, que la solución a la que se ha llegado es lo suficientemente buena como para dejar de seguir buscando mejores soluciones. Para ello, se diseña una técnica [19] en la cual se detecta la capacidad del algoritmo de conseguir soluciones mejores a las ya exploradas y, cuando dicha posibilidad de mejorar la solución es muy baja, se deja de iterar. El fundamento teórico [19] de dicho criterio de parada se basa en que los valores de la función objetivo del problema (Makespan) siguen una distribución desconocida, pero se trata de conocer su comportamiento mediante otra variable aleatoria. Esto es debido a que, siendo Z un conjunto de los valores de Makespan, se asume que, al estar minimizando dicho valor, la mayor parte de los valores de Makespan estarán en el intervalo [μ, max(Z)], siendo μ la media de dicho conjunto. Por lo tanto, se comprueba en [19] que, formando la variable aleatoria presentada en la ecuación 16, se comprueba que sigue una distribución probabilística positiva con una cola a la izquierda, asumiéndose que es una distribución Gamma de parámetros desconocidos (θ y k). Ẑ=max(Z)− z (16) Entonces, para calcular la probabilidad de que en una iteración se encuentre una solución mejor (z) a la aquella que ha aportado mejor resultado de todas las que se han explorado en todo el proceso anterior (z*), se usa un conjunto de valores de z para estimar los parámetros de la función Gamma y posteriormente, a partir de dicha solución, la probabilidad de obtener una mejor solución sería: 𝑝 = 𝑃[𝑧 < 𝑧∗]=𝑃[max(𝑍)−Ẑ≤ 𝑧∗]=𝑃[Ẑ≥max(Z)−𝑧∗] =1−𝑃[Ẑ≤ max(Z)−𝑧∗] =1−𝐹Ẑ(max(𝑍)−𝑧∗) (17) Por lo tanto, el procedimiento en el algoritmo es el siguiente: Primero, se guarda un conjunto de valores de Makespan en Z correspondientes a un número predefinido de iteraciones q. Una vez que se completa el conjunto Z se construye el conjunto Ẑ cuyas componentes vendrán dadas por la ecuación 16. Tras formar el conjunto Ẑ se realiza una estimación de los parámetros de la distribución Gamma (θ y k) haciendo uso de los valores de dicho conjunto. Y finalmente, en cada iteración posterior a las q primeras en la cual se mejore la solución, se calcula la probabilidad de mejorar la solución en la siguiente iteración haciendo uso de la ecuación 17, tal que, p=1−𝐹Ẑ(max(Z)−𝑧∗). De modo que, si al comienzo de la iteración la probabilidad de mejora es menor que el umbral que se establezca (τ), el algoritmo finalizará. A parte del criterio de parada probabilístico se impone un tiempo computacional máximo. Esto se debe a que las instancias son diferentes, por lo que unas necesitan un tiempo más elevado que otras para hacer una iteración a consecuencia de la cantidad de máquinas y partes que se tienen en cada problema. Los grupos de instancias con sus características y su procedencia se explican detalladamente en la sección 4.2. Entonces, en aquellas instancias en las que se detecta que se requiere un tiempo alto para realizar una iteración (entre 10 y 20 segundos) se establece un límite de tiempo de 600 segundos que corresponden con el grupo R de instancias. En aquellas instancias que se requieren entre 5 y 10 segundos para realizar una iteración se establece un tope de 300 segundos. Y finalmente, para aquellas instancias que son más sencillas y tienen un número de partes y máquinas 23 Programación de Operaciones en Procesos de Fabricación Aditiva bajo se establece un límite de 60 segundos. Estos dos últimos grupos de instancias contienen instancias tanto de los grupos B y C. 3.7 Resumen de la metaheurística Con intención de aclarar todo el proceso, se muestra en la ilustración 12 un diagrama en el cual se muestra el transcurso que conlleva la metaheurística de principio a fin, en el cual aparecen todos los conceptos que se han comentado en las diferentes secciones del presente capítulo. Ilustración 12. Metaheurística completa. Elaboración propia. Implementación de la metaheurística 30 Tabla 9. Ejemplo numérico. Vecindad de tipo Swap. Máquina 1 Máquina 2 Makespan (h) Trabajo 1 Trabajo 2 Trabajo 3 Trabajo 4 Trabajo 5 P11, P4, P13, P5 P14 P9, P2 P3, P6, P10, P12, P15, P7 P1, P8 205.56 P4, P13, P5, P2 P14 P9, P11 P3, P6, P10, P12, P15, P7 P1, P8 216.75 P4, P13, P5, P3 P14 P9, P2 P6, P10, P12, P15, P7, P11 P1, P8 224.21 P4, P13, P5, P6 P14 P9, P2 P3, P10, P12, P15, P7, P11 P1, P8 238.71 P4, P13, P5, P10 P14 P9, P2 P3, P6, P12, P15, P7, P11 P1, P8 198.83 P4, P13, P5, P12 P14 P9, P2 P3, P6, P10, P15, P7, P11 P1, P8 212.57 P4, P13, P5, P15 P14 P9, P2 P3, P6, P10, P12, P7, P11 P1, P8 221.41 P4, P13, P5, P7 P14 P9, P2 P3, P6, P10, P12, P15, P11 P1, P8 210.68 P4, P13, P5, P1 P14 P9, P2 P3, P6, P10, P12, P15, P7 P8, P11 216.10 P11, P13, P5, P2 P14 P9, P4 P3, P6, P10, P12, P15, P7 P1, P8 216.75 P11, P13, P5, P3 P14 P9, P2 P6, P10, P12, P15, P7, P4 P1, P8 211.56 P11, P13, P5, P6 P14 P9, P2 P3, P10, P12, P15, P7, P4 P1, P8 226.94 P11, P13, P5, P12 P14 P9, P2 P3, P6, P10, P15, P7, P4 P1, P8 206.17 P11, P13, P5, P15 P14 P9, P2 P3, P6, P10, P12, P7, P4 P1, P8 215.02 P11, P13, P5, P7 P14 P9, P2 P3, P6, P10, P12, P15, P4 P1, P8 204.28 P11, P13, P5, P1 P14 P9, P2 P3, P6, P10, P12, P15, P7 P8, P4 222.49 P11, P4, P5, P2 P14 P9, P13 P3, P6, P10, P12, P15, P7 P1, P8 215.79 P11, P4, P5, P3 P14 P9, P2 P6, P10, P12, P15, P7, P13 P1, P8 213.57 P11, P4, P5, P6 P14 P9, P2 P3, , P10, P12, P15, P7, P13 P1, P8 228.95 P11, P4, P5, P7 P14 P9, P2 P3, P6, P10, P12, P15, P13 P1, P8 206.29 Tras explorar por completo la vecindad de tipo swap, se encuentra que el mejor vecino es el situado en la fila 5 de la tabla 9, el cual proporciona un Makespan de 198.83 h. Finalmente, se exponen las soluciones obtenidas mediante la exploración de la vecindad de tipo Job Alloc. Ésta, como se explica en la sección 3.3, tiene tantos vecinos como se muestran en la ecuación 14 por lo que en el caso del ejemplo numérico se tienen un total de 420 vecinos, de los cuales 380 de ellos son factibles. En la tabla 10, se pueden observar 19 vecinos factibles de este tipo. 31 Programación de Operaciones en Procesos de Fabricación Aditiva Tabla 10. Ejemplo numérico. Vecindad de tipo Job Alloc. Máquina 1 Máquina 2 Makespan (h) Trabajo 1 Trabajo 2 Trabajo 3 Trabajo aux1 Trabajo 4 Trabajo 5 Trabajo aux2 P11, P4, P13, P5 P14 P9, P2 P3, P6, P10, P12, P15, P7 P1, P8 205.56 P11, P4, P13, P5 P14 P9, P2 P3, P10, P12, P15, P7 P1 P8, P6 213.95 P4, P13, P5 P14 P9, P2 P10, P11 P3, P6, P12, P15, P7 P1, P8 223.93 P11, P13, P5 P14 P9, P2 P10, P4 P3, P6, P12, P15, P7 P1, P8 223.93 P11, P13, P5 P14 P9, P2 P3, P6, P12, P15, P7 P1, P8 P10, P4 229.66 P11, P4, P5 P14 P9, P2 P13, P10 P3, P6, P12, P15, P7 P1, P8 222.97 P11, P4, P5 P14 P9, P2 P3, P6, P12, P15, P7 P1, P8 P13, P10 226.686 P11, P4, P13 P14 P9, P2 P10, P5 P3, P6, P12, P15, P7 P1, P8 222.80 P11, P4, P13 P14 P9, P2 P3, P6, P12, P15, P7 P1, P8 P10, P5 266.97 P11, P4, P13, P5 P2, P9 P10, P14 P3, P6, P12, P15, P7 P1, P8 216.38 P11, P4, P13, P5 P2, P9 P3, P6, P12, P15, P7 P1, P8 P10, P14 244.28 P11, P4, P13, P5 P14 P2 P10, P9 P3, P6, P12, P15, P7 P1, P8 222.23 P11, P4, P13, P5 P14 P2 P3, P6, P12, P15, P7 P1, P8 P10, P9 229.76 P11, P4, P13, P5 P14 P9 P10, P2 P3, P6, P12, P15, P7 P1, P8 222.80 P11, P4, P13, P5 P14 P9 P3, P6, P12, P15, P7 P1, P8 P10, P2 214.08 P11, P4, P13, P5 P14 P9, P2 P10, P3 P6, P12, P15, P7 P1, P8 257.27 P11, P4, P13, P5 P14 P9, P2 P6, P12, P15, P7 P1, P8 P10, P3 213.96 P11, P4, P13, P5 P14 P9, P2 P10, P6 P3, P12, P15, P7 P1, P8 271.77 P11, P4, P13, P5 P14 P9, P2 P3, P12, P15, P7 P1, P8 P10, P6 213.96 P11, P4, P13, P5 P14 P9, P2 P10, P12 P3, P6, P15, P7 P1, P8 244.50 P11, P4, P13, P5 P14 P9 P3, P6, P10, P12, P15, P7 P8 P2, P1 204.37 Es importante recalcar que los trabajos que están vacíos, a la hora de programar, no se consideran como tales, es decir, habría un trabajo menos en la solución. Por ejemplo, en los vecinos de la fila 10 y 11 solo habría 5 trabajos, en el caso del vecino de la fila 10, por ejemplo, 3 trabajos en la primera máquina y 2 en la segunda. Tras explorar la vecindad al completo, se consigue un vecino que ofrece un Makespan de 204.37 h, el cual es el Implementación de la metaheurística 32 último que aparece en la tabla 10. 4.4.3 Ejemplo numérico. Resultados Tras poner en funcionamiento el programa al completo, el mejor valor de Makespan obtenido tras 43 segundos de tiempo computacional y 200 iteraciones es 195.435 h. Dicho valor del Makespan resulta de la solución contenida en la tabla 11. Tabla 11. Ejemplo numérico. Resultados. Máquina 1 Máquina 2 Trabajo Partes Trabajo Partes J1 P15, P7, P5 J4 P11, P6, P4, P13, P12, P3, P10 J2 P14 J5 P2, P8 J3 P9, P1 El diagrama de Gantt correspondiente a la solución obtenida en el entorno de Unrelated Machines en el que se encuentra es el que aparece en la imagen siguiente (ilustración 13). Ilustración 13.Diagrama de Gantt del ejemplo numérico. Elaboración propia. 33 5 VARIANTES PROPUESTAS na vez analizados los resultados obtenidos con la metaheurística, incluidos en el anexo B, teniendo como referencia los proporcionados en [1], se observa que los tiempos computacionales son altos, mientras que las soluciones obtenidas son relativamente semejantes, tanto para instancias de tipo pequeño como de tipo grande (dicha caracterización de instancias se explica en el segundo párrafo del capítulo 6). Los resultados se estudian de una manera más exhaustiva en el capítulo 6 de este documento, en concreto en la sección 6.1. Teniendo la metaheurística confeccionada como base, se intenta reducir el tiempo computacional renunciando a una solución más cercana al óptimo. Para conseguir esto, se pretende reducir el número de vecinos investigados mediante una modificación de los tres tipos de vecindades haciendo uso de reglas de despacho cuya funcionalidad es estudiada con la obtención de los resultados para cada una de las variantes y la posterior comparación con los calculados con el algoritmo base. 5.1 Variante 1. Modificación 1 de la vecindad “Flip” Con el objetivo de reducir la cantidad de vecinos de tipo Flip sin que la solución final se vea en gran medida afectada, dicha vecindad se modifica de manera que, a diferencia de la original, en la cual, como se explica en la sección 3.3, una parte de un trabajo se traslada a otro trabajo cualquiera, independientemente de la máquina, ahora dicha parte va destinada al trabajo con menor número de partes de cada máquina. En el caso en el que en una máquina haya dos o más trabajos con el mismo número de partes y este resulte ser el mínimo, la parte puede ir destinada a cada uno de estos trabajos, es decir, se exploran, por cada parte, tantos vecinos como trabajos con ese número mínimo de partes se tengan. Dicha regla de despacho se ha fundamentado en que cambiar una parte de un trabajo a otro dentro de una misma máquina tiene poca repercusión en el tiempo de procesamiento. Por lo tanto, se trata de focalizar dicha vecindad en estudiar en que trabajo sería más rentable situar la parte dentro de una máquina, para así, reducir el número de vecinos de este tipo haciendo que cada parte pueda trasladarse únicamente a un trabajo de cada máquina. La conclusión a la que se llega es que lo más lógico es hacer uso de los trabajos con menor número de partes, ya que éstos, en su mayoría, serán aquellos que tengan menor volumen ocupado, lo que significa que la parte va a aquel trabajo con menor tiempo de procesamiento asociado al invertido en el volumen total de las piezas. Para explicar de un modo más esquemático el cambio de la vecindad se utiliza un ejemplo. En una solución formada por tres grupos de trabajos asociado cada uno a una máquina (ilustración 14) se tiene una cantidad total de tres vecinos por parte, lo que significa que el total de vecinos es de 48, que resulta ser 𝑛∙𝑚 siendo n el número de partes y m el número de máquinas, esto se debe a que solo se le puede añadir la parte correspondiente a un trabajo por máquina (el de menor número de partes). Por el contrario, con la vecindad de tipo Flip original se tiene una cantidad de vecinos bastante mayor, ya que cada parte tendría la libertad de ser añadida a cualquier trabajo. El número total de vecinos para el ejemplo es de 112, correspondiente a la multiplicación del número de partes por el número de trabajos a los que pueden ir añadidas. Por lo tanto, en un U Variantes propuestas 34 problema en el cual se tenga una solución como la del ejemplo (ilustración 14), se reduce en gran medida el tiempo invertido en explorar la vecindad de tipo swap, lo que conlleva a un ahorro de tiempo computacional y de trabajo del equipo. En la ilustración 14 se muestra el funcionamiento de la vecindad una vez introducida la modificación, por ello, la parte i1 solamente tendría tres destinos posibles, el trabajo 3, el trabajo 5 y el trabajo 8, aquellos con menor número de partes en cada máquina. Ilustración 14. Modificación de la vecindad Flip. Elaboración propia. 5.2 Variante 2. Modificación 2 de la vecindad “Flip” Por el mismo motivo que se explica en el primer párrafo de la sección 5.1, se lleva a cabo una segunda modificación de la vecindad de tipo Flip. Se trata en este caso, a diferencia del anterior, de situar la parte intercambiada de trabajos en aquel trabajo que tenga menor área ocupada para así, de una manera distinta, intentar situar la parte en aquellos trabajos que tengan el menor volumen ocupado. Con esta variación de la vecindad se consigue reducir el número de vecinos de la misma manera que en la variante explicada en el punto 5.1 ya que también se tienen tantos vecinos por parte como máquinas haya, es decir, 𝑛∙𝑚 vecinos. Por lo tanto, puede hacerse uso del ejemplo explicado al final la sección 5.1 y de la ilustración 14 para explicar por qué se produce una reducción importante en la cantidad de vecinos explorados. Para hacer uso de la figura 14, se debe suponer que los trabajos 3, 5 y 8 son aquellos que menor área ocupada tienen, ya que serán los únicos trabajos posibles a los que pueden ir destinadas las piezas. 5.3 Variante 3. Modificación de la vecindad “Swap” Para reducir el número de soluciones exploradas en la búsqueda de vecindario variable, también se modifica la vecindad de tipo Swap. Dicha vecindad, originalmente, intercambia dos partes de distintos trabajos independientemente de la máquina a la que estén asociados, de manera que dos partes de distintos trabajos de 35 Programación de Operaciones en Procesos de Fabricación Aditiva una misma máquina pueden ser intercambiados. En la variante propuesta se intenta reducir el número de vecinos posibles introduciendo la restricción de que las máquinas tienen que ser distintas también. La restricción añadida se fundamenta en que los cambios en el tiempo total de funcionamiento más significativos se darán si se intercambian partes entre distintas máquinas, ya que el tiempo de procesamiento se ve afectado tanto por las características de las partes como por las especificaciones de las máquinas, por lo que intercambiando partes entre trabajos de la misma máquina no se modifican las componentes del tiempo de procesamiento asociadas a las características de las máquinas. Para explicar en qué consiste la modificación de dicha vecindad, al igual que en la sección 5.1, se hace uso de un ejemplo en el que se comparan la vecindad original y la vecindad con el cambio propuesto. En una solución formada por dieciséis partes agrupadas en ocho trabajos, que a su vez están distribuidos en tres máquinas (ilustración 15), por un lado, con la modificación, se tienen un total de 168 vecinos, que se corresponden con cambiar cada parte de una máquina con el resto de las partes de distintas máquinas. Por ejemplo, de intercambiar la parte uno con otra parte se obtendrían 10 vecinos, tantos como partes haya en distintas máquinas. Por otro lado, con el tipo de vecindad Swap original se producen un total de 218 vecinos ya que ahora cada parte puede ser intercambiada con otra de un trabajo distinto de la misma máquina. Por ejemplo, la vecindad obtendría de intercambiar la parte uno con el resto de las partes posibles un total de 13 vecinos. En la ilustración 15 se puede observar, en primer lugar, la demostración de la cantidad de vecinos que se obtienen a partir de la parte 1 en caso de usar la vecindad de manera original y, en segundo lugar, los vecinos formados a partir de la primera parte una vez introducida la modificación de la vecindad. Ilustración 15. Comparación de vecindades Swap. Elaboración propia. 5.4 Variante 4. Modificación de la vecindad “Job Alloc” Para reducir significativamente las soluciones formadas en la vecindad de tipo Job Alloc se modifica dicha vecindad improvisando una regla de despacho la cual consiste en que cada par de partes que van a ir destinadas a un nuevo trabajo se sitúen en la máquina que menos trabajos tenga. La vecindad original tiene, por cada pareja de partes distintas, tantos vecinos como máquinas haya, sin embargo, al introducir la modificación explicada, el número de vecinos por cada par de partes únicamente es uno. El objetivo de dicha regla de despacho es situar el nuevo trabajo creado en aquella máquina que menos trabajos tenga para así, tener un equilibrio entre todas las máquinas de inversión en tiempos de set-up, ya que, mientras menos trabajos haya en una máquina menos tiempo se invierte en preparar la máquina para el procesamiento de las piezas. En caso de que haya 2 máquinas que contengan el mismo número de trabajos y este resulte ser el mismo, la pareja nueva de trabajos va destinada a ambas, es decir, se exploran los dos vecinos distintos. Al igual que se ha hecho en las anteriores variantes, la modificación de esta vecindad se explica con un ejemplo: Suponiendo una solución formada por dieciséis partes, agrupadas en ocho trabajos, a su vez divididos en tres máquinas, la vecindad proporciona tantos vecinos como parejas de partes se puedan formar, es decir, 78, ya que todos los nuevos trabajos formados con este par de partes van destinados únicamente a una máquina. Sin embargo, si se usa la vecindad sin la modificación propuesta habrá 78∙3 vecinos, es decir, 234, ya que cada pareja de partes puede situarse en cualquiera de las 3 máquinas que existen. En el caso de usar la vecindad original se tiene un número de vecinos correspondientes a la ecuación 14, situada en la sección 3.3, mientras que Variantes propuestas 36 en el caso de usar la alternativa propuesta solamente habría un total de (𝑛 2) vecinos. En la ilustración 16 se demuestra como una pareja de partes forma menos vecinos en la variación de la vecindad Job Alloc propuesta y se compara con los vecinos que resultan de una pareja haciendo uso de la vecindad sin modificación (ilustración 17). Ilustración 16. Ejemplo de vecindad tipo Job Alloc 2. Elaboración propia. Ilustración 17. Ejemplo de vecindad tipo Job Alloc modificada. Elaboración propia. 5.5 Variante 5. Modificación del problema de empaquetado La metaheurística, a la hora de realizar el problema de empaquetado de las partes, se organiza siguiendo tres algoritmos distintos y posteriormente seleccionando aquel con el cual se obtiene mejor Makespan. Sin embargo, según [22] la calidad de la solución de estos algoritmos se puede cuantificar mediante un indicador de rendimiento y se llega a la conclusión de que el algoritmo NFDH, con un rendimiento de 2 es peor que el FFDH y el BFDH. Los algoritmos FFDH y BFDH satisfacen la misma relación de rendimiento (17/10), sin embargo, el algoritmo BFDH trata de maximizar la utilización del trabajo tal y como se explica en la sección 3.2 del presente documento. Debido a todo lo comentado en el primer párrafo, se considera interesante estudiar el efecto que causa hacer uso de solamente un algoritmo para el problema de empaquetado ya que supone un impacto en el tiempo computacional a la hora de realizar las iteraciones en las que se perturba la solución, que es en el momento en el que el algoritmo de empaquetado entra en acción. Por lo tanto, debido a todo lo explicado en el primer párrafo, en esta variante se selecciona la técnica BFDH como único algoritmo para realizar el problema de empaquetado. 37 Programación de Operaciones en Procesos de Fabricación Aditiva 5.6 Variantes 6 y 7. Combinación de diferentes modificaciones Una vez analizado el comportamiento del algoritmo y los resultados obtenidos se cree conveniente unificar las diferentes modificaciones explicadas en las secciones anteriores del presente capítulo para, finalmente sacar una conclusión firme acerca de la metaheurística elaborada junto con las diferentes alternativas propuestas. La variante 6 unifica las modificaciones correspondientes a las variantes 1, 3, 4 y 5, es decir, los tres tipos de vecindades se ven afectados al igual que el algoritmo de empaquetado. Mientras que la variante 7 incorpora los cambios de las variantes 2, 3, 4 y 5, la diferencia con la variante 6 es que la modificación de la vecindad de tipo Flip incorporada es la de la alternativa 2. Variantes propuestas 38 39 6 RESULTADOS Y CONCLUSIONES os resultados obtenidos se han dividido, para cada metaheurística, en distintos bloques según el tipo de instancias con las que se ha trabajado, por lo tanto, se han elaborado 3 tablas de resultados en cada caso. Las tablas asociadas a los grupos de instancias de tipo B y C se asocian a aquellas instancias consideradas de tamaño pequeño y mediano, y aquellas tablas relacionadas con las instancias de tipo R se refieren a instancias de tamaño grande. Dicha distinción entre tipos de instancias se lleva a cabo mediante un periodo de prueba en la que el algoritmo se pone en funcionamiento para cada instancia y se estudia cómo reacciona frente a ella, de modo que a aquellas instancias en las cuales se ha requerido mayor tiempo computacional se les ha denominado grandes, y de igual manera, en aquellas en las que la metaheurística ha tardado poco tiempo en calcular la solución se les caracteriza como pequeñas, de igual manera se desarrolla para las de tamaño mediano. En la sección 3.6 se explica que se establecen distintos tiempos computacionales límites para cada tipo de instancias dependiendo de cuanto tarda en realizar una iteración el programa, por lo tanto, la determinación de que tipo de instancia se trata en cada caso tiene base en este criterio también para la decisión de que instancias se consideran pequeñas, medianas y grandes. Aquellas en las que se ha establecido un tiempo límite de 60 segundos se consideran pequeñas y se corresponden con las instancias incluidas entre las B15 y B27 y aquellas situadas entre C39 y C51 de las baterías de instancias B y C respectivamente. Cuando una instancia precisa de 300 segundos de tiempo límite se considera mediana, y son aquellas comprendidas entre B28 y B38 y aquellas dispuestas entre C52 y C62. Mientras que las instancias establecidas como grandes son todas aquellas contenidas en el grupo R, y para las mismas se establece un límite de tiempo computacional de 600 segundos. Con el objetivo de conocer si resulta de interés el uso de la metaheurística elaborada se lleva a cabo una comparación entre las soluciones obtenidas de entre todas las elaboradas en este documento y las ya propuestas en la literatura. Además de cómo solucionar los posibles errores cometidos o mejorar la solución propuesta. En [1] se comparan resultados de una metaheurística elaborada semejante a la confeccionada en este proyecto con un solucionador exacto denominado CPLEX y se llega a la conclusión de que, para este tipo de problemas, la aplicación CPLEX resulta demasiado tediosa de usar debido a que las soluciones obtenidas necesitan demasiado tiempo computacional. Debido a ello, la metaheurística trabajada toma como referencia los resultados obtenidos en dicho artículo mediante únicamente la metaheurística confeccionada por los autores. Para la comparación mencionada se utilizan diversos indicadores, el más importante es el promedio de DEV, que mide la diferencia relativa, expresada en tanto por ciento, entre un valor de la función objetivo y el mejor valor obtenido por cualquiera de los algoritmos, en este caso entre los resultados de la metaheurística elaborada y los proporcionados en [1]. Además, se calcula la desviación típica del conjunto de valores obtenidos (indicada a continuación del valor medio), con el objetivo de obtener la dispersión que tienen las variaciones de Makespan. La ecuación con la cual se obtiene dicho indicador es la siguiente: 𝐷𝐸𝑉 =𝑂𝐹𝑉− 𝑀𝐸𝐽𝑂𝑅 𝑂𝐹𝑉 𝑀𝐸𝐽𝑂𝑅 𝑂𝐹𝑉 ∙100 (18) L Resultados y conclusiones 46 47 REFERENCIAS [1] Alicastro, M., Ferone, D., Festa, P., Fugaro, S., & Pastore, T. (2021). A reinforcement learning iterated local search for makespan minimization in additive manufacturing machine scheduling problems. Computers & Operations Research, 131, 105272. [2] Van Rossum, G., & Drake, F. L. (2009). Python 3 Reference Manual. Scotts Valley, CA: CreateSpace. [3] Anaconda Software Distribution (2016). Conda (Version 2-2.4.0) [Computer Software]. [4] Framiñán Torres, J. M. (2022). Libreria Scheptk (Nº de versión 0.0.6). Windows-Mac. Sevilla. [5] Haro González, J. V. (2012). Desarrollo de un procedimiento de diseño óptimo para fabricación de componentes mediante tecnologías aditivas. [6] Ligon, S. C., Liska, R., Stampfl, J., Gurr, M., & Mlhaupt, R. (2017). Polymers for 3D printing and customized additive manufacturing. Chemical reviews, 117(15), 10212-10290. [7] Zahera, M. (2012). La fabricación aditiva, tecnología avanzada para el diseño y el desarrollo de productos. XVI Congreso Internacional de Ingeniería de Proyectos Valencia, 11-13 de julio de 2012. Fundación Cotec. [8] Hernández-Castellano, P. M., Martínez-Rivero, M., Gutiérrez-Barcenilla, A., Suárez-García, L., & Marrero-Alemán, M. (2019). Fabricación Aditiva: material didáctico interactivo (No. COMPON- 2019-CINAIC-0057). [9] Lago, J. (2020). Revisión de las Técnicas de Fabricación Aditiva y sus Aplicaciones. Escuela Superior de Ingeniería y Tecnología Universidad de La Laguna. [10] Tofail, S. A., Koumoulos, E. P., Bandyopadhyay, A., Bose, S., O’Donoghue, L., & Charitidis, C. (2018). Additive manufacturing: scientific and technological challenges, market uptake and opportunities. Materials today, 21(1), 22-37. [11] Hartmanis, J. (1982). Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson). Siam Review, 24(1), 90. [12] Li, Q., Kucukkoc, I., & Zhang, D. Z. (2017). Production planning in additive manufacturing and 3D printing. Computers & Operations Research, 83, 157-172. [13] Kucukkoc, I. (2019). MILP models to minimise makespan in additive manufacturing machine scheduling problems. Computers & Operations Research, 105, 58-67. [14] Pérez González, P., Fernández-Viagas Escudero, V., & Framiñán Torres, J. M. (2020). Programación de la Producción. Sevilla: Sección de Publicadores, Escuela Técnica Superior de Ingeniería, Universidad de Sevilla. Referencias 48 [15] Cplex, I. I. (2009). V12. 1: User’s Manual for CPLEX. International Business Machines Corporation, 46(53), 157. [16] Dos Santos, J. P. Q., de Melo, J. D., Neto, A. D. D., & Aloise, D. (2014). Reactive search strategies using reinforcement learning, local search algorithms and variable neighborhood search. Expert Systems with Applications, 41(10), 4939-4949. [17] Martello, S., & Toth, P. (1990). Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. [18] Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & operations research, 24(11), 1097-1100. [19] Felici, G., Ferone, D., Festa, P., Napoletano, A., & Pastore, T. (2017, June). A grasp for the minimum cost sat problem. In International Conference on Learning and Intelligent Optimization (pp. 64-78). Springer, Cham. [20] Raybaut, P. (2022). Spyder (Nº de versión 5). Windows-Mac. MIT: Spyder Project Contributors. [21] López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., & Sttzle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3, 43-58. [22] Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., & Graham, R. L. (1974). Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on computing, 3(4), 299-325. 49 7 ANEXO A. EJEMPLO NUMÉRICO. PROCEDIMIENTO DE ALGORITMOS DE EMPAQUETADO Partes ordenadas de mayor a menor altura: Tabla 18. Ejemplo numérico. Partes ordenadas de menor a mayor altura por máquina. Partes asociadas a la máquina 1: Parte - Altura - Área - Volumen 1 - 27.94 - 56.85 - 272.92 2 - 18.99 - 89.68 - 683.06 3 - 17.61 - 146.57 - 617.98 4 - 10.77 - 269.75 - 1928.6 5 - 9.18 - 728.33 - 1193.36 6 - 3.0 - 615.12 - 722.91 7 - 2.18 - 178.34 - 214.79 Partes asociadas a la máquina 2: Parte - Altura - Área - Volumen 1 - 29.58 - 273.83 - 840.17 2 - 26.67 - 258.54 - 1375.9 3 - 17.38 - 50.02 - 125.7 4 - 17.04 - 99.53 - 703.08 5 - 14.38 - 114.56 - 989.53 6 - 13.22 - 179.75 - 641.7 7 - 4.27 - 122.62 - 102.83 8 - 3.5 - 454.89 - 683.48 7.1 Procedimiento del algoritmo NFDH ---Se inicia el algoritmo NFDH para la máquina 1 --- Área máxima permitida en la máquina: 800.0 Área ocupada en el trabajo 1: 0 Área que se ocuparía en el trabajo 1 introduciendo la parte 1: 56.85 Se añade la parte 1 al trabajo 1 Anexo A. Ejemplo numérico. Procedimiento de algoritmos de empaquetado 50 Área ocupada en el trabajo 1: 56.85 Área que se ocuparía en el trabajo 1 introduciendo la parte 2: 146.53 Se añade la parte 2 al trabajo 1 Área ocupada en el trabajo 1 : 146.53 Área que se ocuparía en el trabajo 1 introduciendo la parte 3 : 293.1 Se añade la parte 3 al trabajo 1 Área ocupada en el trabajo 1 : 293.1 Área que se ocuparía en el trabajo 1 introduciendo la parte 4 : 562.85 Se añade la parte 4 al trabajo 1 Área ocupada en el trabajo 1 : 562.85 Área que se ocuparía en el trabajo 1 introduciendo la parte 5 : 1291.18 Se excede el área máxima de la máquina Se añade la parte 5 a un nuevo trabajo 2 Área ocupada en el trabajo 2 : 728.33 Área que se ocuparía en el trabajo 2 introduciendo la parte 6 : 1343.45 Se excede el área máxima de la máquina Se añade la parte 6 a un nuevo trabajo 3 Área ocupada en el trabajo 3 : 615.12 Área que se ocuparía en el trabajo 3 introduciendo la parte 7 : 793.46 Se añade la parte 7 al trabajo 3 --Finaliza el algoritmo NFDH en la máquina 1— Resultados del algoritmo NFDH en la máquina 1: Tabla 19. Resultados del algoritmo NFDH en la máquina 1. Partes asociadas al trabajo 1 Altura - Área - Volumen 27.94 - 56.85 - 272.92 18.99 - 89.68 - 683.06 17.61 - 146.57 - 617.98 10.77 - 269.75 - 1928.6 Partes asociadas al trabajo 2 Altura - Área - Volumen 9.18 - 728.33 - 1193.36 Partes asociadas al trabajo 3 Altura - Área - Volumen 3.0 - 615.12 - 722.91 2.18 - 178.34 - 214.79 51 Programación de Operaciones en Procesos de Fabricación Aditiva ---Se inicia el algoritmo NFDH en la máquina 2 --- Área máxima permitida en la máquina: 1000.0 Área ocupada en el trabajo 1: 0 Área que se ocuparía en el trabajo 1 introduciendo la parte 1: 273.83 Se añade la parte 1 al trabajo 1 Área ocupada en el trabajo 1: 273.83 Área que se ocuparía en el trabajo 1 introduciendo la parte 2: 532.37 Se añade la parte 2 al trabajo 1 Área ocupada en el trabajo 1: 532.37 Área que se ocuparía en el trabajo 1 introduciendo la parte 3: 582.39 Se añade la parte 3 al trabajo 1 Área ocupada en el trabajo 1: 582.39 Área que se ocuparía en el trabajo 1 introduciendo la parte 4: 681.92 Se añade la parte 4 al trabajo 1 Área ocupada en el trabajo 1 : 681.92 Área que se ocuparía en el trabajo 1 introduciendo la parte 5: 796.48 Se añade la parte 5 al trabajo 1 Área ocupada en el trabajo 1: 796.48 Área que se ocuparía en el trabajo 1 introduciendo la parte 6: 976.23 Se añade la parte 6 al trabajo 1 Área ocupada en el trabajo 1 : 976.23 Área que se ocuparía en el trabajo 1 introduciendo la parte 7 : 1098.85 Se excede el área máxima de la máquina Se añade la parte 7 a un nuevo trabajo 2 Área ocupada en el trabajo 2: 122.62 Área que se ocuparía en el trabajo 2 introduciendo la parte 8: 577.51 Se añade la parte 8 al trabajo 2 ---Fin del algoritmo NFDH en la máquina 2 --- Anexo A. Ejemplo numérico. Procedimiento de algoritmos de empaquetado 52 Resultados del algoritmo NFDH en la máquina 2: Tabla 20. Resultados del algoritmo NFDH en la máquina 2. Partes asociadas al trabajo 1 Altura - Área - Volumen 29.58 - 273.83 - 840.17 26.67 - 258.54 - 1375.9 17.38 - 50.02 - 125.7 17.04 - 99.53 - 703.08 14.38 - 114.56 - 989.53 13.22 - 179.75 - 641.7 Partes asociadas al trabajo 2 Altura - Área - Volumen 4.27 - 122.62 - 102.83 3.5 - 454.89 - 683.48 7.2 Procedimiento del algoritmo FFDH ---Inicio del algoritmo FFDH en la máquina 1 --- Área máxima permitida en la máquina: 800.0 Área ocupada en cada trabajo: [0] Se comprueba si la parte 1 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 56.85 Se añade la parte 1 al trabajo 1 Área ocupada en cada trabajo: [56.85] Se comprueba si la parte 2 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 146.53 Se añade la parte 2 al trabajo 1 Área ocupada en cada trabajo: [146.53] Se comprueba si la parte 3 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 293.1 Se añade la parte 3 al trabajo 1 Área ocupada en cada trabajo: [293.1] Se comprueba si la parte 4 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 562.85 Se añade la parte 4 al trabajo 1 53 Programación de Operaciones en Procesos de Fabricación Aditiva Área ocupada en cada trabajo: [562.85] Se comprueba si la parte 5 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1: 1291.18 Se crea un nuevo trabajo, el trabajo 2 Área ocupada en cada trabajo: [562.85, 728.33] Se comprueba si la parte 6 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 1177.97 Se comprueba si la parte 6 cabe en el trabajo 2 Área que se ocuparía en el trabajo 2 : 1343.45 Se crea un nuevo trabajo, el trabajo 3 y se añade la parte 6 Área ocupada en cada trabajo: [562.85, 728.33, 615.12] Se comprueba si la parte 7 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 741.19 Se añade la parte 7 al trabajo 1 ---Fin algoritmo FFDH en la máquina 1 --- Tabla 21. Resultados del algoritmo FFDH en la máquina 1. Partes asociadas al trabajo 1 Altura - Área - Volumen 27.94 - 56.85 - 272.92 18.99 - 89.68 - 683.06 17.61 - 146.57 - 617.98 10.77 - 269.75 - 1928.6 2.18 - 178.34 - 214.79 Partes asociadas al trabajo 2 Altura - Área - Volumen 9.18 - 728.33 - 1193.36 Partes asociadas al trabajo 3 Altura - Área - Volumen 3.0 - 615.12 - 722.91 ---Inicio del algoritmo FFDH en la máquina 2 --- Área máxima permitida en la máquina: 1000.0 Área ocupada en cada trabajo: [0] Se comprueba si la parte 1 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 273.83 Se añade la parte 1 al trabajo 1 Anexo A. Ejemplo numérico. Procedimiento de algoritmos de empaquetado 54 Área ocupada en cada trabajo: [273.83] Se comprueba si la parte 2 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 532.37 Se añade la parte 2 al trabajo 1 Área ocupada en cada trabajo: [532.37] Se comprueba si la parte 3 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 582.39 Se añade la parte 3 al trabajo 1 Área ocupada en cada trabajo: [582.39] Se comprueba si la parte 4 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 681.92 Se añade la parte 4 al trabajo 1 Área ocupada en cada trabajo: [681.92] Se comprueba si la parte 5 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 796.48 Se añade la parte 5 al trabajo 1 Área ocupada en cada trabajo: [796.48] Se comprueba si la parte 6 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 976.23 Se añade la parte 6 al trabajo 1 Área ocupada en cada trabajo: [976.23] Se comprueba si la parte 7 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 1098.85 Se crea un nuevo trabajo, el trabajo 2 y se añade la parte 7 Área ocupada en cada trabajo: [976.23, 122.62] Se comprueba si la parte 8 cabe en el trabajo 1 Área que se ocuparía en el trabajo 1 : 1431.12 Se comprueba si la parte 8 cabe en el trabajo 2 Área que se ocuparía en el trabajo 2 : 577.51 Se añade la parte 8 al trabajo 2 ---Fin del algoritmo FFDH en la máquina 2 --- 55 Programación de Operaciones en Procesos de Fabricación Aditiva Resultados del algoritmo FFDH en la máquina 2: Tabla 22. Resultados del algoritmo FFDH en la máquina 2. Partes asociadas al trabajo 1 Altura - Área - Volumen 29.58 - 273.83 - 840.17 26.67 - 258.54 - 1375.9 17.38 - 50.02 - 125.7 17.04 - 99.53 - 703.08 14.38 - 114.56 - 989.53 13.22 - 179.75 - 641.7 Partes asociadas al trabajo 2 Altura - Área - Volumen 4.27 - 122.62 - 102.83 3.5 - 454.89 - 683.48 7.3 Procedimiento del algoritmo BFDH ---Inicio del algoritmo BFDH en la máquina 1 --- Área máxima permitida en la máquina: 800.0 El área ocupada de cada trabajo es: [0] El área libre de cada trabajo es: [800.0] La diferencia mínima es: 800.0 Se añade la parte 1 al trabajo 1 El área ocupada de cada trabajo es: [56.85] El área libre de cada trabajo es: [743.15] La diferencia mínima es: 743.15 Se añade la parte 2 al trabajo 1 El área ocupada de cada trabajo es: [146.53] El área libre de cada trabajo es: [653.47] La diferencia mínima es: 653.47 Se añade la parte 3 al trabajo 1 El área ocupada de cada trabajo es: [293.1] El área libre de cada trabajo es: [506.9] La diferencia mínima es: 506.9 Se añade la parte 4 al trabajo 1 El área ocupada de cada trabajo es: [562.85] El área libre de cada trabajo es: [237.14999999999998] Anexo B. Resultados de la metaheurística 62 Tabla 27. Metaheurística básica. Resultados de instancias de tipo R. Instancia Makespan Ttb (s) Nº Mejoras Flip Nº Mejoras Swap Nº Mejoras Job Alloc Makespan [1] Ttb [1] DEV (%) R01 379.42 292.63 12 9 4 367.67 0.23 3.19 R02 1014.78 600.00 32 10 12 1004.25 34.52 1.05 R03 487.42 600.00 18 21 15 480.98 1.66 1.34 R04 1926.21 532.84 15 18 13 1908.18 30.33 0.94 R05 870.52 600.00 4 7 6 861.54 23.38 1.04 R06 567.23 600.00 12 12 19 426.02 36.42 33.15 R07 4126.57 530.00 2 18 0 4112.98 23.33 0.33 R08 287.36 600.00 10 7 24 289.06 18.41 -0.59 R09 548.84 600.00 13 16 18 514.06 29.24 6.76 R10 979.81 600.00 11 8 16 931.26 38.42 5.21 R11 1483.53 600.00 14 5 13 1465.57 28.81 1.23 R12 257.01 600.00 6 16 23 232.69 28.00 10.45 R13 236.33 556.22 15 17 23 232.96 1.60 1.45 R14 687.23 600.00 3 6 22 602.09 32.99 14.14 R15 209.85 600.00 9 21 13 203.98 26.71 2.88 R16 2408.60 242.00 10 16 2 2397.33 25.50 0.47 R17 403.54 600.00 13 5 20 306.46 25.92 31.68 R18 447.33 600.00 8 20 13 432.92 32.60 3.33 R19 1206.89 600.00 4 13 1 1195.61 16.75 0.94 R20 669.15 260.41 6 10 6 650.70 31.20 2.84 R21 2416.19 600.00 2 26 2 2404.41 29.10 0.49 R22 352.57 600.00 8 11 15 338.62 30.24 4.12 R23 463.85 600.00 9 4 21 398.80 14.31 16.31 R24 561.43 600.00 6 2 19 478.96 33.86 17.22 R25 488.10 600.00 9 12 3 488.10 0.03 0.00 R26 512.39 516.03 13 20 18 507.71 9.23 0.92 R27 773.03 600.00 13 11 24 706.12 29.39 9.48 R28 350.49 600.00 4 14 5 350.48 0.01 0.00 R29 567.16 600.00 6 5 26 466.19 23.34 21.66 R30 763.00 600.00 10 10 14 693.75 29.24 9.98 R31 698.84 600.00 5 7 14 675.53 28.15 3.45 R32 380.25 600.00 7 21 12 379.52 6.12 0.19 R33 2563.60 600.00 18 14 10 2560.00 26.70 0.14 R34 478.50 600.00 5 13 8 454.26 28.41 5.34 R35 437.49 600.00 9 10 7 428.43 25.56 2.12 R36 2278.04 600.00 14 30 1 2274.81 39.73 0.14 R37 132.40 600.00 31 27 24 128.12 0.18 3.34 R38 2003.44 600.00 21 27 6 1992.41 44.64 0.55 R39 292.33 600.00 25 13 13 280.55 33.00 4.20 R40 797.44 600.00 7 16 16 739.64 20.59 7.81 439 548 521 63 9 ANEXO C. RESULTADOS DE LAS VARIANTES PROPUESTAS n este anexo se presentan los resultados obtenidos mediante las diferentes variantes propuestas a la metaheurística. El anexo se divide en siete secciones en las cuales los datos son representados mediante tablas, las cuales contienen, en la columna 1. el nombre de la instancia. en la columna 2, el Makespan obtenido, en la columna 3 el tiempo hasta llegar a la mejor solución, en las columnas 4. 5 y 6 se presentan las mejoras obtenidas mediante cada tipo de vecindad, en la columna 7 se presenta el Makespan obtenido mediante la metaheurística principal, dichos datos se presentan en las tablas del anexo B, para la comparación entre los distintos algoritmos, y en la columna 8 se presentan los valores del parámetro DEV, tomando como datos para su cálculo los valores del Makespan obtenidos con la metaheurística correspondiente y los obtenidos con la metaheurística principal. E Anexo C. Resultados de las variantes propuestas 64 9.1 Resultados de variante 1 Tabla 28. Variante 1. Resultados de instancias de tipo B. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) B15 202.40 0.31 3 8 1 197.51 2.48 B16 207.63 4.61 3 6 2 205.08 1.25 B17 390.65 3.17 7 6 1 390.47 0.05 B18 409.42 2.58 8 4 2 397.89 2.90 B19 385.71 8.33 5 15 2 380.23 1.44 B20 392.46 7.00 4 11 3 386.71 1.49 B21 284.06 11.18 2 5 2 283.90 0.06 B22 299.67 7.80 3 6 2 296.98 0.91 B23 418.44 15.22 4 7 2 416.31 0.51 B24 441.39 3.17 3 9 3 437.52 0.88 B25 443.90 18.91 5 7 1 439.18 1.07 B26 460.90 21.62 4 15 5 457.16 0.82 B27 442.95 3.34 6 7 4 440.10 0.65 B28 467.03 28.06 5 9 1 458.44 1.87 B29 358.04 21.65 8 7 2 352.67 1.52 B30 372.15 56.07 4 3 1 364.71 2.04 B31 348.32 82.72 6 4 2 342.59 1.67 B32 361.15 137.50 11 5 3 358.06 0.87 B33 376.99 72.25 7 9 5 371.53 1.47 B34 394.19 206.00 9 2 5 386.17 2.08 B35 367.91 182.22 8 4 8 367.91 0.00 B36 383.72 50.20 9 14 5 378.21 1.46 B37 448.62 101.23 16 15 8 442.95 1.28 B38 457.85 143.89 13 18 9 456.95 0.20 153 196 79 65 Programación de Operaciones en Procesos de Fabricación Aditiva Tabla 29. Variante 1. Resultados de instancias de tipo C. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) C39 196.71 3.20 2 2 1 195.44 0.65 C40 204.77 1.03 5 5 1 201.22 1.76 C41 389.75 4.45 3 4 3 388.63 0.29 C42 401.26 4.67 2 5 3 381.39 5.21 C43 381.10 4.53 4 8 3 373.68 1.99 C44 388.75 1.76 5 12 5 388.75 0.00 C45 291.73 4.76 5 4 2 290.47 0.43 C46 298.16 2.96 6 7 4 296.54 0.55 C47 428.32 10.37 2 10 6 424.97 0.79 C48 436.47 6.02 4 2 5 433.82 0.61 C49 453.68 3.72 6 10 7 446.28 1.66 C50 458.68 8.63 9 6 7 454.94 0.82 C51 315.34 31.07 10 10 8 300.49 4.94 C52 311.20 47.25 5 5 5 305.57 1.84 C53 359.83 53.23 11 12 6 357.49 0.65 C54 370.27 53.24 10 9 6 362.74 2.08 C55 354.10 53.59 11 18 5 349.65 1.27 C56 356.46 37.47 14 19 3 349.91 1.87 C57 389.75 81.07 9 14 5 380.12 2.53 C58 384.39 100.18 6 8 4 372.84 3.10 C59 377.59 285.75 8 6 7 371.73 1.58 C60 384.78 61.36 7 7 4 377.38 1.96 C61 450.47 300.00 7 9 6 447.09 0.76 C62 461.23 300.00 5 12 7 454.32 1.52 156 204 113 Anexo C. Resultados de las variantes propuestas 66 Tabla 30. Variante 1. Resultados de instancias de tipo R. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) R01 381.54 292.63 10 22 16 379.42 0.56 R02 1060.12 600.00 16 22 24 1014.78 4.47 R03 497.82 600.00 14 28 19 487.42 2.13 R04 1940.24 365.51 18 23 17 1926.21 0.73 R05 878.61 95.62 12 14 14 870.52 0.93 R06 589.04 600.00 4 10 9 567.23 3.84 R07 4134.11 530.00 7 13 10 4126.57 0.18 R08 345.27 600.00 7 15 5 287.36 20.15 R09 550.01 600.00 6 11 7 548.84 0.21 R10 1014.61 600.00 7 6 7 979.81 3.55 R11 1512.87 600.00 8 17 18 1483.53 1.98 R12 310.76 600.00 2 3 6 257.01 20.91 R13 266.05 386.08 7 19 11 236.33 12.58 R14 718.61 600.00 4 8 7 687.23 4.57 R15 232.27 600.00 11 7 12 209.85 10.68 R16 2425.60 138.94 3 10 10 2408.60 0.71 R17 466.35 600.00 4 13 13 403.54 15.57 R18 482.09 600.00 7 17 24 447.33 7.77 R19 1212.52 38.87 12 21 21 1206.89 0.47 R20 683.97 143.07 13 14 11 669.15 2.22 R21 2417.34 600.00 7 6 7 2416.19 0.05 R22 401.85 600.00 12 26 12 352.57 13.98 R23 494.40 600.00 2 9 11 463.85 6.59 R24 605.48 600.00 15 20 12 561.43 7.85 R25 488.10 182.22 7 15 15 488.10 0.00 R26 525.25 140.87 9 13 12 512.39 2.51 R27 816.37 600.00 5 7 6 773.03 5.61 R28 368.79 133.28 9 11 6 350.49 5.22 R29 652.79 600.00 4 7 4 567.16 15.10 R30 784.54 600.00 3 20 10 763.00 2.82 R31 734.12 600.00 5 14 19 698.84 5.05 R32 420.87 164.74 8 13 14 380.25 10.68 R33 2576.32 185.95 6 7 13 2563.60 0.50 R34 501.52 600.00 13 6 14 478.50 4.81 R35 448.11 331.81 5 17 15 437.49 2.43 R36 2300.86 174.20 16 20 7 2278.04 1.00 R37 164.35 516.35 12 17 18 132.40 24.14 R38 2033.62 456.44 8 14 12 2003.44 1.51 R39 297.33 434.40 22 7 20 292.33 1.71 R40 816.84 600.00 10 7 19 797.44 2.43 350 549 507 67 Programación de Operaciones en Procesos de Fabricación Aditiva 9.2 Resultados de variante 2 Tabla 31.Variante 2. Resultados de instancias de tipo B. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) B15 201.59 1.94 4 3 3 197.51 2.06 B16 209.76 1.31 2 6 1 205.08 2.28 B17 398.32 4.06 5 6 2 390.47 2.01 B18 404.45 1.59 4 4 3 397.89 1.65 B19 384.72 6.42 0 11 5 380.23 1.18 B20 392.00 3.31 4 3 3 386.71 1.37 B21 286.81 8.09 5 7 3 283.90 1.03 B22 298.79 8.12 4 5 0 296.98 0.61 B23 423.31 23.10 5 3 1 416.31 1.68 B24 441.62 9.44 6 4 0 437.52 0.94 B25 441.07 12.16 4 5 4 439.18 0.43 B26 457.16 1.17 5 4 2 457.16 0.00 B27 441.99 8.01 6 8 4 440.10 0.43 B28 467.54 7.78 3 4 3 458.44 1.99 B29 354.03 44.88 6 4 6 352.67 0.38 B30 367.63 35.27 3 15 5 364.71 0.80 B31 348.34 43.15 4 7 4 342.59 1.68 B32 359.97 145.31 8 9 4 358.06 0.54 B33 381.25 215.92 4 9 3 371.53 2.62 B34 390.31 81.28 7 12 4 386.17 1.07 B35 373.70 220.53 5 5 5 367.91 1.57 B36 380.62 193.21 11 10 5 378.21 0.64 B37 451.29 300.00 4 8 7 442.95 1.88 B38 467.82 300.00 9 18 10 456.95 2.38 118 170 87 Anexo C. Resultados de las variantes propuestas 68 Tabla 32. Variante 2. Resultados de instancias de tipo C. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) C39 201.98 0.52 3 2 3 195.44 3.35 C40 201.48 0.59 2 6 1 201.22 0.13 C41 391.29 4.44 4 5 0 388.63 0.68 C42 401.73 4.12 2 5 2 381.39 5.33 C43 378.38 7.95 3 9 5 373.68 1.26 C44 388.75 1.94 4 5 2 388.75 0.00 C45 292.15 5.33 2 4 3 290.47 0.58 C46 297.19 5.19 1 4 0 296.54 0.22 C47 428.26 6.24 3 5 4 424.97 0.77 C48 439.03 3.50 5 5 3 433.82 1.20 C49 453.25 12.14 3 6 6 446.28 1.56 C50 459.64 5.89 7 11 3 454.94 1.03 C51 308.46 70.98 10 10 4 300.49 2.65 C52 309.50 36.36 6 2 6 305.57 1.29 C53 357.49 33.42 6 2 7 357.49 0.00 C54 370.30 31.42 5 7 4 362.74 2.08 C55 351.81 171.67 5 8 6 349.65 0.62 C56 354.26 131.67 7 13 3 349.91 1.24 C57 382.59 46.17 6 4 6 380.12 0.65 C58 388.32 83.55 8 6 5 372.84 4.15 C59 377.96 153.54 10 9 4 371.73 1.68 C60 378.23 242.24 9 16 10 377.38 0.23 C61 452.14 183.94 7 10 13 447.09 1.13 C62 459.36 193.74 9 16 9 454.32 1.11 127 170 109 69 Programación de Operaciones en Procesos de Fabricación Aditiva Tabla 33. Variante 2. Resultados de instancias de tipo R. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) R01 379.42 307.01 6 17 16 379.42 0.00 R02 1036.30 600.00 16 17 29 1014.78 2.12 R03 497.82 567.56 9 31 19 487.42 2.13 R04 1968.31 379.05 13 24 14 1926.21 2.19 R05 878.61 120.84 9 11 11 870.52 0.93 R06 575.24 600.00 6 9 14 567.23 1.41 R07 4126.57 600.00 8 16 14 4126.57 0.00 R08 326.49 532.44 4 20 10 287.36 13.62 R09 552.50 600.00 4 15 11 548.84 0.67 R10 1014.61 600.00 2 7 12 979.81 3.55 R11 1501.50 487.45 6 16 20 1483.53 1.21 R12 312.52 600.00 1 5 2 257.01 21.60 R13 246.39 600.00 12 23 13 236.33 4.26 R14 707.24 600.00 3 3 5 687.23 2.91 R15 232.27 600.00 8 7 15 209.85 10.68 R16 2463.52 204.67 8 11 13 2408.60 2.28 R17 439.58 600.00 9 12 15 403.54 8.93 R18 478.45 489.60 2 16 21 447.33 6.96 R19 1212.52 63.55 17 17 21 1206.89 0.47 R20 694.57 178.42 9 19 9 669.15 3.80 R21 2425.64 537.58 9 7 10 2416.19 0.39 R22 369.67 600.00 17 30 11 352.57 4.85 R23 489.38 600.00 5 5 13 463.85 5.50 R24 605.48 600.00 18 22 11 561.43 7.85 R25 511.13 257.60 3 12 11 488.10 4.72 R26 525.25 114.24 10 14 12 512.39 2.51 R27 788.34 600.00 9 2 10 773.03 1.98 R28 375.11 176.67 10 7 7 350.49 7.02 R29 637.41 600.00 3 7 5 567.16 12.39 R30 796.34 569.70 1 16 13 763.00 4.37 R31 716.74 600.00 6 19 22 698.84 2.56 R32 400.09 341.72 6 9 17 380.25 5.22 R33 2604.01 295.34 5 11 11 2563.60 1.58 R34 512.54 600.00 15 11 19 478.50 7.11 R35 448.11 295.59 3 15 20 437.49 2.43 R36 2288.35 301.31 16 24 12 2278.04 0.45 R37 164.35 516.35 15 15 18 132.40 24.14 R38 2071.46 600.00 11 13 15 2003.44 3.40 R39 305.83 524.41 24 10 19 292.33 4.62 R40 814.94 600.00 9 3 21 797.44 2.19 347 548 561 Anexo C. Resultados de las variantes propuestas 70 9.3 Resultados de variante 3 Tabla 34. Variante 3. Resultados de instancias tipo B. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) B15 200.38 3.23 6 3 2 197.51 1.46 B16 206.09 1.28 1 2 2 205.08 0.49 B17 394.60 8.00 2 5 1 390.47 1.06 B18 399.18 10.19 11 5 6 397.89 0.33 B19 380.44 2.59 3 2 3 380.23 0.06 B20 387.83 4.91 3 2 5 386.71 0.29 B21 285.19 8.48 5 3 3 283.90 0.46 B22 299.80 4.67 8 1 2 296.98 0.95 B23 421.10 22.80 10 4 3 416.31 1.15 B24 442.12 7.11 1 5 2 437.52 1.05 B25 441.30 13.95 2 3 1 439.18 0.48 B26 460.29 4.81 0 2 1 457.16 0.69 B27 442.12 11.07 17 13 5 440.10 0.46 B28 460.50 3.87 6 4 1 458.44 0.45 B29 352.67 44.03 9 15 5 352.67 0.00 B30 365.58 50.06 15 14 4 364.71 0.24 B31 346.99 28.20 7 5 6 342.59 1.29 B32 359.44 23.57 9 11 2 358.06 0.39 B33 376.77 240.39 12 13 4 371.53 1.41 B34 386.17 169.28 19 16 6 386.17 0.00 B35 368.37 300.00 25 15 8 367.91 0.12 B36 381.60 167.47 13 10 6 378.21 0.90 B37 446.77 232.23 24 13 4 442.95 0.86 B38 456.95 300.00 9 7 3 456.95 0.00 217 173 85 71 Programación de Operaciones en Procesos de Fabricación Aditiva Tabla 35. Variante 3. Resultados de instancias de tipo C. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) C39 196.71 0.78 3 3 2 195.44 0.65 C40 203.83 4.94 5 4 4 201.22 1.29 C41 390.71 3.60 4 2 1 388.63 0.54 C42 391.39 6.27 3 4 1 381.39 2.62 C43 388.12 8.50 6 3 2 373.68 3.87 C44 391.22 8.00 5 4 2 388.75 0.64 C45 298.75 11.69 8 9 2 290.47 2.85 C46 305.36 8.20 5 4 2 296.54 2.97 C47 438.93 12.93 8 3 6 424.97 3.29 C48 449.63 7.65 6 3 1 433.82 3.64 C49 449.63 5.69 6 4 4 446.28 0.75 C50 456.34 16.24 5 6 2 454.94 0.31 C51 308.59 52.39 7 7 4 300.49 2.70 C52 307.44 18.84 3 6 5 305.57 0.61 C53 359.12 95.11 4 3 4 357.49 0.46 C54 369.16 98.35 3 4 5 362.74 1.77 C55 351.72 97.96 10 16 4 349.65 0.59 C56 358.39 104.25 9 8 4 349.91 2.42 C57 382.87 90.07 17 6 7 380.12 0.73 C58 386.16 300.00 12 12 3 372.84 3.57 C59 380.42 300.00 15 10 3 371.73 2.34 C60 382.75 300.00 11 10 5 377.38 1.42 C61 453.40 300.00 10 3 2 447.09 1.41 C62 454.32 92.92 17 11 7 454.32 0.00 182 145 82 Anexo C. Resultados de las variantes propuestas 78 Tabla 42. Variante 5. Resultados de instancias de tipo R. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) R01 379.42 192.75 9 8 9 379.42 0.00 R02 1027.01 600.00 29 15 13 1014.78 1.20 R03 497.64 600.00 13 27 11 487.42 2.10 R04 1926.21 532.84 12 20 8 1926.21 0.00 R05 881.14 600.00 9 5 5 870.52 1.22 R06 602.38 600.00 7 10 18 567.23 6.20 R07 4126.57 410.83 4 14 4 4126.57 0.00 R08 420.72 600.00 8 12 30 287.36 46.41 R09 557.29 144.20 10 11 23 548.84 1.54 R10 1013.29 246.47 9 12 14 979.81 3.42 R11 1502.34 600.00 9 6 12 1483.53 1.27 R12 298.88 600.00 6 11 22 257.01 16.29 R13 241.91 478.99 11 17 20 236.33 2.36 R14 717.31 268.33 5 9 24 687.23 4.38 R15 225.20 600.00 9 16 13 209.85 7.32 R16 2408.60 109.10 6 11 3 2408.60 0.00 R17 492.50 600.00 10 10 20 403.54 22.05 R18 483.86 600.00 10 15 15 447.33 8.17 R19 1214.05 395.55 3 8 2 1206.89 0.59 R20 669.15 260.41 10 8 5 669.15 0.00 R21 2416.19 533.21 3 24 6 2416.19 0.00 R22 398.54 398.54 11 10 17 352.57 13.04 R23 493.22 600.00 9 5 18 463.85 6.33 R24 561.43 600.00 8 7 20 561.43 0.00 R25 488.24 588.24 6 11 5 488.10 0.03 R26 516.82 516.03 11 17 14 512.39 0.86 R27 779.96 600.00 12 6 22 773.03 0.90 R28 359.97 359.96 6 10 7 350.49 2.71 R29 567.16 600.00 10 4 21 567.16 0.00 R30 781.94 600.00 6 9 19 763.00 2.48 R31 719.88 600.00 9 10 14 698.84 3.01 R32 391.59 391.59 11 16 14 380.25 2.98 R33 2563.60 600.00 15 14 6 2563.60 0.00 R34 504.41 504.40 2 18 13 478.50 5.41 R35 442.95 442.95 12 12 12 437.49 1.25 R36 2278.04 469.70 9 30 6 2278.04 0.00 R37 142.62 143.62 34 25 21 132.40 7.72 R38 2025.59 600.00 20 24 10 2003.44 1.11 R39 306.04 306.04 21 18 15 292.33 4.69 R40 817.91 600.00 10 12 17 797.44 2.57 414 527 548 79 Programación de Operaciones en Procesos de Fabricación Aditiva 9.6 Resultados de variante 6 Tabla 43. Variante 6. Resultados de instancias de tipo B. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) B15 203.40 0.98 4 1 1 197.51 2.98 B16 206.03 0.71 0 2 1 205.08 0.47 B17 396.27 1.86 3 5 0 390.47 1.49 B18 401.93 0.26 0 1 0 397.89 1.02 B19 385.71 2.13 0 4 3 380.23 1.44 B20 388.73 7.05 6 15 3 386.71 0.52 B21 284.98 3.83 1 3 2 283.90 0.38 B22 300.17 26.81 3 4 2 296.98 1.08 B23 428.84 5.27 4 4 1 416.31 3.01 B24 453.79 3.14 3 3 0 437.52 3.72 B25 440.26 8.12 2 4 1 439.18 0.25 B26 468.39 2.40 1 2 0 457.16 2.46 B27 449.43 11.89 6 5 2 440.10 2.12 B28 467.70 28.73 1 4 0 458.44 2.02 B29 358.03 16.76 7 8 0 352.67 1.52 B30 366.90 21.55 2 3 3 364.71 0.60 B31 353.54 19.87 5 8 0 342.59 3.20 B32 360.39 24.91 4 11 1 358.06 0.65 B33 378.58 44.04 4 8 1 371.53 1.90 B34 395.07 264.45 15 16 5 386.17 2.31 B35 369.76 93.37 2 9 3 367.91 0.50 B36 389.20 73.06 7 8 0 378.21 2.91 B37 447.22 99.76 3 2 1 442.95 0.96 B38 475.54 238.96 12 6 3 456.95 4.07 95 136 33 Anexo C. Resultados de las variantes propuestas 80 Tabla 44. Variante 6. Resultados de instancias de tipo C. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) C39 196.60 0.85 2 3 0 195.44 0.60 C40 203.49 0.77 1 3 0 201.22 1.13 C41 394.52 2.01 5 5 1 388.63 1.52 C42 396.06 0.95 0 2 1 381.39 3.85 C43 377.57 4.45 3 1 1 373.68 1.04 C44 392.45 1.20 2 2 0 388.75 0.95 C45 293.45 1.15 2 1 0 290.47 1.03 C46 298.87 3.20 2 5 0 296.54 0.79 C47 427.07 8.04 2 2 0 424.97 0.50 C48 437.23 2.04 1 1 1 433.82 0.79 C49 454.36 25.70 2 1 3 446.28 1.81 C50 465.37 12.93 3 2 1 454.94 2.29 C51 312.31 15.40 6 7 5 300.49 3.93 C52 319.35 18.36 6 8 4 305.57 4.51 C53 365.29 58.45 10 13 2 357.49 2.18 C54 372.98 38.96 1 4 2 362.74 2.82 C55 351.95 9.87 1 5 0 349.65 0.66 C56 359.97 59.35 6 12 2 349.91 2.88 C57 386.27 41.69 6 6 4 380.12 1.62 C58 372.84 134.79 13 11 3 372.84 0.00 C59 382.46 47.11 1 4 0 371.73 2.89 C60 389.54 68.63 4 8 0 377.38 3.22 C61 458.13 189.37 6 7 4 447.09 2.47 C62 460.29 110.22 7 8 1 454.32 1.31 92 121 35 81 Programación de Operaciones en Procesos de Fabricación Aditiva Tabla 45. Variante 6. Resultados de instancias de tipo R. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) R01 380.52 109.41 12 13 9 379.42 0.29 R02 1018.38 388.04 27 44 12 1014.78 0.36 R03 493.49 214.99 13 16 12 487.42 1.25 R04 1927.55 283.21 12 17 6 1926.21 0.07 R05 874.39 69.63 9 8 5 870.52 0.44 R06 873.47 600.00 22 18 15 567.23 53.99 R07 4136.32 370.02 22 24 4 4126.57 0.24 R08 352.85 600.00 11 10 13 287.36 22.79 R09 912.55 600.00 17 7 13 548.84 66.27 R10 1017.31 600.00 12 5 16 979.81 3.83 R11 1486.65 600.00 23 28 7 1483.53 0.21 R12 419.12 600.00 14 8 13 257.01 63.08 R13 245.76 99.36 11 15 4 236.33 3.99 R14 733.88 600.00 7 7 11 687.23 6.79 R15 216.21 579.75 25 40 16 209.85 3.03 R16 2419.42 101.16 11 14 5 2408.60 0.45 R17 509.35 600.00 33 34 15 403.54 26.22 R18 449.57 600.00 25 27 16 447.33 0.50 R19 1209.08 41.92 8 12 1 1206.89 0.18 R20 681.46 101.73 18 14 7 669.15 1.84 R21 2421.79 386.57 16 21 7 2416.19 0.23 R22 355.53 446.58 16 39 8 352.57 0.84 R23 503.50 600.00 12 5 12 463.85 8.55 R24 652.47 600.00 11 8 19 561.43 16.22 R25 488.24 110.29 12 11 7 488.10 0.03 R26 521.12 69.39 7 9 10 512.39 1.70 R27 866.76 600.00 10 10 16 773.03 12.12 R28 350.58 121.20 7 11 8 350.49 0.03 R29 600.59 600.00 10 11 13 567.16 5.89 R30 937.77 600.00 11 5 15 763.00 22.90 R31 707.06 582.30 15 19 13 698.84 1.18 R32 388.27 75.50 8 16 6 380.25 2.11 R33 2573.40 107.83 8 20 1 2563.60 0.38 R34 480.15 431.24 16 12 12 478.50 0.34 R35 441.90 217.47 21 16 15 437.49 1.01 R36 2290.68 104.83 4 16 1 2278.04 0.56 R37 138.41 517.45 40 21 22 132.40 4.54 R38 2021.31 267.52 18 26 4 2003.44 0.89 R39 305.16 334.80 10 25 13 292.33 4.39 R40 977.98 600.00 10 7 9 797.44 22.64 594 669 411 Anexo C. Resultados de las variantes propuestas 82 9.7 Resultados de variante 7 Tabla 46. Variante 7. Resultados de instancias de tipo B. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) B15 204.97 1.12 1 3 1 197.51 3.78 B16 205.69 1.35 3 4 2 205.08 0.30 B17 396.79 2.54 4 4 2 390.47 1.62 B18 408.51 1.29 1 2 1 397.89 2.67 B19 380.44 1.86 4 4 1 380.23 0.06 B20 387.83 1.53 3 3 1 386.71 0.29 B21 285.10 3.64 3 4 1 283.90 0.42 B22 300.16 2.24 1 2 3 296.98 1.07 B23 421.00 5.12 5 3 0 416.31 1.13 B24 445.26 6.74 5 3 3 437.52 1.77 B25 442.04 28.49 1 4 3 439.18 0.65 B26 466.65 2.05 0 1 1 457.16 2.08 B27 446.55 40.46 10 5 2 440.10 1.47 B28 467.02 10.64 11 6 1 458.44 1.87 B29 356.28 44.96 5 8 0 352.67 1.02 B30 370.09 29.29 10 15 1 364.71 1.47 B31 350.27 41.85 8 13 5 342.59 2.24 B32 358.06 37.39 3 11 1 358.06 0.00 B33 379.06 46.54 5 12 1 371.53 2.03 B34 396.83 37.42 7 6 2 386.17 2.76 B35 376.29 78.90 5 8 2 367.91 2.28 B36 386.30 99.70 13 11 0 378.21 2.14 B37 451.00 214.59 12 12 3 442.95 1.82 B38 464.09 300.00 11 31 5 456.95 1.56 131 175 42 83 Programación de Operaciones en Procesos de Fabricación Aditiva Tabla 47. Variante 7. Resultados de instancias de tipo C. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) C39 195.44 1.26 2 5 0 195.44 0.00 C40 207.16 3.29 8 3 2 201.22 2.95 C41 392.93 4.87 9 4 4 388.63 1.11 C42 400.05 1.54 5 1 0 381.39 4.89 C43 377.98 2.86 5 5 1 373.68 1.15 C44 390.53 1.40 1 3 1 388.75 0.46 C45 293.13 3.67 0 4 2 290.47 0.92 C46 297.80 2.39 1 2 1 296.54 0.43 C47 428.68 34.31 11 5 2 424.97 0.87 C48 445.09 5.58 5 3 3 433.82 2.60 C49 449.10 24.35 0 1 1 446.28 0.63 C50 457.67 4.14 3 3 1 454.94 0.60 C51 305.26 54.97 9 7 2 300.49 1.59 C52 309.32 43.60 9 6 2 305.57 1.23 C53 362.31 54.52 6 13 2 357.49 1.35 C54 381.97 69.12 13 8 6 362.74 5.30 C55 355.51 63.93 5 13 5 349.65 1.67 C56 358.49 51.32 8 7 2 349.91 2.45 C57 385.72 70.04 9 7 1 380.12 1.47 C58 393.51 154.41 16 17 2 372.84 5.55 C59 378.97 61.02 6 6 0 371.73 1.95 C60 381.91 175.69 15 20 6 377.38 1.20 C61 458.56 300.00 16 11 8 447.09 2.57 C62 463.02 83.07 5 5 1 454.32 1.91 167 159 55 Anexo C. Resultados de las variantes propuestas 84 Tabla 48.Variante 7. Resultados de instancias de tipo R. Instancia Makespan (h) Ttb (s) Nº de Mejoras Flip Nº de Mejoras Swap Nº de Mejoras Job Alloc Makespan metaheurística ppal DEV (%) R01 388.77 388.77 12 11 8 379.42 2.47 R02 1021.48 102.21 24 33 6 1014.78 0.66 R03 509.78 264.49 9 24 14 487.42 4.59 R04 1928.35 326.21 14 25 6 1926.21 0.11 R05 871.62 600.00 8 15 7 870.52 0.13 R06 747.39 600.00 27 16 15 567.23 31.76 R07 4126.94 299.93 6 14 3 4126.57 0.01 R08 496.32 600.00 15 7 13 287.36 72.72 R09 789.35 600.00 21 17 13 548.84 43.82 R10 1018.24 600.00 7 9 12 979.81 3.92 R11 1490.42 600.00 34 37 11 1483.53 0.46 R12 405.17 600.00 13 15 5 257.01 57.65 R13 236.33 575.72 10 10 7 236.33 0.00 R14 799.90 600.00 10 6 14 687.23 16.40 R15 222.18 388.87 7 21 14 209.85 5.88 R16 2414.08 431.11 7 13 4 2408.60 0.23 R17 467.64 600.00 26 22 20 403.54 15.89 R18 452.30 499.47 18 30 20 447.33 1.11 R19 1210.79 322.68 11 22 2 1206.89 0.32 R20 677.25 112.10 14 20 10 669.15 1.21 R21 2420.86 600.00 20 26 12 2416.19 0.19 R22 359.04 436.94 19 28 8 352.57 1.84 R23 489.05 600.00 11 10 12 463.85 5.43 R24 623.20 600.00 11 6 14 561.43 11.00 R25 488.24 169.09 3 14 11 488.10 0.03 R26 517.41 204.59 11 17 7 512.39 0.98 R27 802.20 600.00 6 12 18 773.03 3.77 R28 350.48 114.10 6 11 11 350.49 0.00 R29 593.17 600.00 15 5 14 567.16 4.59 R30 899.39 600.00 7 16 8 763.00 17.87 R31 700.31 396.36 15 30 15 698.84 0.21 R32 388.27 139.69 14 5 12 380.25 2.11 R33 2572.57 139.64 6 12 13 2563.60 0.35 R34 481.35 341.98 7 9 6 478.50 0.59 R35 444.23 176.50 7 4 17 437.49 1.54 R36 2295.52 118.00 14 19 14 2278.04 0.77 R37 132.40 455.20 3 9 3 132.40 0.00 R38 2019.83 203.02 12 6 21 2003.44 0.82 R39 303.32 398.23 13 7 16 292.33 3.76 R40 841.03 532.27 9 8 12 797.44 5.47 502 621 448 85 Programación de Operaciones en Procesos de Fabricación Aditiva