Resolución de problemas de planificación de la producción en fabricación aditiva considerando 2D Nesting y múltiples orientaciones

Equation Chapter 1 Section 1 Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Resolución de problemas de planificación de la producción en fabricación aditiva considerando 2D Nesting y múltiples orientaciones Autor: Alejandro Rodríguez Carrero Tutores: Ignacio Eguía Salinas José Carlos Molina Gómez Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2024 iii Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Resolución de problemas de planificación de la producción en fabricación aditiva considerando 2D Nesting y múltiples orientaciones Autor: Alejandro Rodríguez Carrero Tutores: Ignacio Eguía Salinas (Catedrático) José Carlos Molina Gómez (Titular de Universidad) Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2024 v Trabajo Fin de Grado: Resolución de problemas de planificación de la producción en fabricación aditiva considerando 2D Nesting y múltiples orientaciones Autor: Alejandro Rodríguez Carrero Tutores: Ignacio Eguía Salinas José Carlos Molina Gómez El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: El Secretario del Tribunal Sevilla, 2024 vii A mi familia y amigos, por apoyarme en todo momento y confiar en mí. A mis maestros, por ayudarme y enseñarme de la mejor manera sus conocimientos. ix Agradecimientos En primer lugar, quiero expresar mi más sincero agradecimiento a mis tutores de este trabajo mencionados anteriormente, por su invaluable guía y apoyo a lo largo de todo el proceso de elaboración de este trabajo. Sus conocimientos y consejos han sido fundamentales para la realización de esta investigación. Agradecer también a las personas que han estado a mi lado durante este importante capítulo de mi vida: mi familia y amigos. Sin su apoyo incondicional, este trabajo fin de carrera no habría sido posible. A mi familia, gracias por su amor, paciencia y por creer siempre en mí. Su dedicación y esfuerzo han sido la base sobre la cual he construido mis logros académicos. Gracias por brindarme las oportunidades necesarias para alcanzar mis sueños. A mis amigos, gracias por estar siempre ahí para ofrecerme su apoyo y comprensión. Sus palabras de aliento y su amistad han sido fundamentales para mantenerme motivado y enfocado. Gracias por las risas, las conversaciones y por compartir conmigo este camino. ÍNDICE DE FIGURAS Ilustración 1. Comparación entre tecnologías convencionales (a) y las aditivas (b) (Muguruza, 2019). 14 Ilustración 2. Procesos de la Fabricación Aditiva (Gibson et al., 2021) 15 Ilustración 3. Categorías AM (Joshi & Sheikh, 2015) 16 Ilustración 4. Técnica SLM (from http://www.custompartnet.com/wu/direct-metal-laser-sintering) 17 Ilustración 5. Ejemplo de trabajo o “build volume” (Fera, et al., 2018) 21 Ilustración 6. Skyline nesting (Chergui, Hadj-Hamou, & Vignat, 2018) 21 Ilustración 7. Nesting and Scheduling sub-problems. (Oh, et al., 2020) 22 Ilustración 8. Clasificación problemas “Nesting and Sheduling”. (Oh, et al., 2020) 23 Ilustración 9. Nesting types (Oh, Witherell, Lu, & Sprock, 2020) 24 Ilustración 10. Orientaciones de una pieza en los ejes X, Y, Z (Framinan, et al., 2023). 26 Ilustración 11. Algoritmos de nivel (Lodi, Martello, & Vigo, 2002) 29 Ilustración 12. Posibles orientaciones de una parte (Lodi, Martello, & Vigo, 2002) 32 Ilustración 13. Ejemplo de una pieza y un job 46 Ilustración 14. Giro de una pieza 47 Ilustración 15. Corte Guillotina horizontal del algoritmo 2D Nesting 47 Ilustración 16. Ejemplo final job 48 Ilustración 17. Diagrama de Flujo del Algoritmo 2D Nesting 48 Ilustración 18. Primera parte fichero datos de entrada (Sección inicial) 51 Ilustración 19. Segunda parte fichero datos de entrada (Volumen y fechas piezas) 51 Ilustración 20. Tercera parte fichero entrada de datos (Características piezas) 52 Ilustración 21. Cuarta parte fichero entrada de datos (Características máquinas) 52 xvii Notación FA AM 1O 2O 3O SLM 2D 3D TFG ABOs OBO Fabricación Aditiva Additive Manufacturing Una orientación Dos orientaciones Tres orientaciones Selective Laser Melting Dos dimensiones Tres dimensiones Trabajo fin de grado Orientaciones de construcción alternativas Optimal build orientation 1 OBJETO DEL TRABAJO FIN DE GRADO 1.1. Objetivos del trabajo El principal objetivo de este trabajo es introducir y resolver el problema de planificación de la producción en Fabricación Aditiva (FA) en entornos de máquinas heterogéneas en paralelo con orientaciones alternativas en las piezas y considerando el 2D Nesting. El problema consiste en asignar y localizar piezas en agrupaciones o estructuras (jobs) para ser fabricadas haciendo uso de máquinas de FA dispuestas en paralelo. El problema incorpora atributos presentes en entornos industriales reales como son la consideración de máquinas heterogéneas, la posibilidad de disponer las piezas en diferentes orientaciones alternativas a la hora de ser fabricadas en el job o la consideración de fechas de disponibilidad y entrega de las piezas, que añaden una componente de dificultad al problema. El problema se presenta mediante un modelo de programación lineal y es resuelto mediante un algoritmo heurístico de construcción semiparalela, adaptación al algoritmo presentado por Paraskevopoulos et al. (2008), para problemas de diseño de rutas de vehículos (Vehicle Routing Problem,VRP). Esta adaptación está diseñada específicamente para abordar las particularidades de la planificación en AM, mejorando la agrupación de piezas y la asignación de trabajos a las máquinas. Para llevar a cabo este objetivo, se ha realizado el estudio de múltiples artículos científicos que analizan el problema de planificación de la producción en FA partiendo de problemas básicos hasta los más complejos. Dichos artículos han servido de base para plantear el problema mediante un modelo matemático formulado con técnicas de programación lineal. Por otra parte, debido a la novedad del problema presentado, se ha realizado una recopilación de instancias existentes que resuelven variantes del problema en la literatura científica, con el fin de elaborar una nueva batería de problemas. Con el fin de validar el comportamiento y rendimiento del algoritmo implementado, se han comparado las soluciones obtenidas por el algoritmo con soluciones óptimas o aproximadas de la literatura científica y entre ellas mismas al no encontrar nada parecido. El motivo por el que se ha elegido este problema es por la necesidad de avanzar en el estudio de problemas de FA identificado en múltiples artículos de la literatura. El campo de estudio está sufriendo un fuerte desarrollo en los últimos años, pero no ha culminado de aprovechar todo su potencial. La componente de multiorientación estudiada supone un aporte distintivo en la consecución de los objetivos analizados. Los objetivos del Trabajo Fin de Grado (TFG) son los siguientes: 1. Analizar el problema que se aborda y problemas relacionados en la literatura. 2. Adecuación y generación de instancias a resolver en el estudio mediante Excel, Visual Basic para Aplicaciones (VBA) y Python. 3. Diseño y desarrollo de un algoritmo en Visual Studio mediante lenguaje C++ que resuelva el problema. 4. Análisis de datos obtenidos de la resolución de las instancias. 5. Comparación de resultados y extracción de conclusiones. La contribución principal de este TFG es la consideración de la multiorientación de las piezas para su agrupación en jobs o estructuras y la elaboración de un algoritmo heurístico que resuelva el problema de planificación de la producción en Fabricación Aditiva de forma eficiente. Objeto del Trabajo Fin de Grado 12 12 1.2. Estructura del trabajo La estructura del Trabajo Fin de Grado está divido en 5 grandes capítulos, las referencias y un anexo, descritos a continuación: • Capítulo 1: La fabricación aditiva. Programación de la producción. El primer apartado es un capítulo introductorio de descripción de la FA, programación de la producción en FA y el problema Nesting en FA. Se comenta brevemente el propósito del TFG y su interés de estudio, su aplicabilidad, objetivos, ámbito, origen tecnológico y clasificación de la tecnología. También incluye una revisión de la literatura relacionada y que se ha tomado como base del trabajo. • Capítulo 2: Definición de la problemática. Este capítulo describe en profundidad el problema a resolver. Se exponen sus características principales en cuanto al entorno, restricciones y objetivos, además de comentar cualquier aspecto que ayude a comprender el problema en cuestión. Incluye el modelo de programación lineal sobre el que se ha basado el algoritmo del estudio. • Capítulo 3: Método de resolución. El tercer capítulo describe con detalle las componentes del algoritmo heurístico desarrollado en el TFG para la resolución del problema. • Capítulo 4: Experimentación. Este apartado recoge una descripción detallada de los resultados computacionales obtenidos tras la ejecución del algoritmo en los casos de estudio. Se muestra el conjunto de pruebas realizadas, y se realiza la comparativa de los resultados obtenidos. • Capítulo 5: Conclusiones. Para finalizar, este último capítulo recoge las conclusiones extraídas tras el estudio, así como las posibles futuras líneas de investigación que se podrían plantear. Al final del documento se encuentran las referencias bibliográficas, además de un Anexo que contiene las instancias utilizadas como referencia. 13 2 LA FABRICACIÓN ADITIVA. PROGRAMACIÓN DE LA PRODUCCIÓN a fabricación aditiva, o impresión 3D, ha causado un gran revuelo en la industria actual, irrumpiendo con muchísima fuerza en el mercado gracias a la eficiencia y precisión que ofrecen sus técnicas de fabricación. En este capítulo, se introduce la fabricación aditiva a través de descripciones e ilustraciones, y la relevancia que ha cobrado en los últimos años. Analizaremos sus ventajas y desventajas respecto a los métodos de fabricación actuales. Se explican también los problemas que se han estudiado en la literatura y los procesos de fabricación abordados. Finalmente, se exponen los diferentes tipos de problemas que se modelarán y resolverán centrándonos sobre todo en los problemas de Nesting. 2.1 Introducción a la fabricación aditiva La fabricación aditiva (Additive Manufacturing, AM), también conocida como fabricación por adición o comúnmente llamada impresión en tres dimensiones ha surgido como una tecnología revolucionaria en el ámbito de la ingeniería y la producción industrial, irrumpiendo con muchísima fuerza en el mercado gracias a la eficiencia y precisión que ofrecen sus técnicas de fabricación, convirtiéndose así en uno de los pilares de la revolución industrial, que forma parte de la Industria 4.0. Esta tecnología ha experimentado un crecimiento exponencial en los últimos años, siendo aplicada en una amplia gama de sectores industriales, desde la medicina hasta la industria aeroespacial. La versatilidad y las ventajas ofrecidas por la fabricación aditiva, como la reducción de costos, tiempos de producción más rápidos y la capacidad de crear geometrías que de otro modo serían imposibles de fabricar, la han convertido en una herramienta fundamental en el arsenal de los ingenieros y diseñadores (Tofail, et al., 2018). A diferencia de los métodos tradicionales de fabricación sustractiva, donde se eliminan materiales de un bloque sólido para obtener la forma deseada, la fabricación aditiva construye objetos capa por capa a partir de datos digitales, permitiendo la creación de componentes altamente complejos con una precisión sin precedentes (Thompson, et al., 2016). Como podemos apreciar en la ilustración 1, hay una gran diferencia en el desperdicio que se obtiene en cada proceso productivo. L La Fabricación Aditiva. Programación de la producción 14 14 Ilustración 1. Comparación entre tecnologías convencionales (a) y las aditivas (b) (Muguruza, 2019). 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 (Hernández-Castellano, et al., 2019). 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. 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 2 el proceso genérico que se lleva a cabo desde principio a fin a la hora de fabricar una pieza en una impresora 3D. 15 Ilustración 2. Procesos de la Fabricación Aditiva (Gibson et al., 2021) Debido a la gran evolución que ha experimentado la FA desde sus inicios y a la diversidad de usos que puede tener, es necesario estandarizar y definir una clasificación clara que facilite la caracterización de esta tecnología y la comunicación entre los profesionales que hagan uso de ellas a nivel mundial. Analizando la terminología estándar desarrollada en la Norma Española UNE-EN ISO/ASTM 52900:2015, aprobada en España a noviembre de 2017, podemos encontrar las siguientes siete categorías de FA (Zhang & Liou, 2021): 1. Proyección de aglutinante (BJ) - “proceso en el que un agente líquido aglutinante se deposita selectivamente para unir materiales en polvo”. 2. Deposición de energía focalizada (DED) - “proceso en el cual se utiliza energía térmica focalizada para unir materiales mediante fusión, a medida que se depositan. La energía térmica focalizada significa que una fuente de energía (por ejemplo, láser, haz de electrones o arco de plasma) se enfoca o concentra para fundir los materiales que se están depositando.” 3. Extrusión de material (ME, FDM) - “proceso en el cual el material se dispensa selectivamente a través de una boquilla o un orificio.” 4. Proyección de material (DOD) - “proceso en el cual se depositan selectivamente gotas del material de fabricación. Como ejemplo de estos materiales se incluyen los fotopolímeros y las ceras.” 5. Fusión de lecho de polvo (PBF, SLS, DMLS, SLM, EBM) - “proceso en el cual la energía térmica funde selectivamente ciertas zonas de un lecho de polvo.” 6. Laminado de hojas - “proceso en el cual el material en forma de láminas u hojas se une para formar un objeto.” 7. Fotopolimerización en tanque o cuba (VP, SLA, DLP) - “proceso en el que el fotopolímero líquido se cura selectivamente en una cuba mediante polimerización activada por luz.” En la siguiente Ilustración podemos observar de forma esquemática la clasificación comentada: La Fabricación Aditiva. Programación de la producción 16 16 Ilustración 3. Categorías AM (Joshi & Sheikh, 2015) De todas las técnicas mostradas en la ilustración 3, profundizaremos en Selective Laser Melting (SLM) perteneciente a la categoría fusión de lecho de polvo, puesto que es una de las técnicas más usadas en la industria y con la que trabajaremos en este proyecto. SLM se utiliza para fundir y fusionar polvos metálicos mediante un láser de densidad de alta potencia. El polvo es muy fino y se deposita sobre un sustrato utilizando un rodillo con un espesor normalmente entre 20 µm y 100 µm. El rayo láser de densidad de alta potencia funde la sección transversal 2D de la primera capa para así fusionar esas áreas. Luego, se deposita una nueva capa de polvo sobre el sustrato y las áreas correspondientes se funden y fusionan mediante láser. Este proceso capa por capa se repite hasta lograr un producto final. Los campos de aplicación de dicha técnica, especialmente para aleaciones de titanio, se están ampliando aún más recientemente. SLM se ha convertido en una técnica de fabricación aditiva ampliamente utilizada para fabricar piezas críticas (como turbobombas) utilizadas en la industria aeroespacial. La NASA ha decidido fabricar de forma aditiva una bomba de combustible para un motor de cohete en una sola pieza en lugar de montar cientos de componentes (incluida una turbina que gira a más de 90.000 rpm). De modo que la bomba fabricada aditivamente tiene un 45% menos de piezas en comparación con las bombas fabricadas tradicionalmente (Kucukkoc, et al., 2021). En la Ilustración 4 podemos observar de manera visual la técnica. 17 Ilustración 4. Técnica SLM (from http://www.custompartnet.com/wu/direct-metal-laser-sintering) En distintos ámbitos, como la navegación espacial, la industria aérea o la medicina, la fabricación aditiva ha supuesto una revolución. Varias de las características de este tipo de fabricación han supuesto un avance respecto a las tecnologías de fabricación convencionales. En primer lugar, la concentración de todas las operaciones en una sola máquina supone un ahorro importante de espacio ya que no es necesario disponer de una amplia cadena de montaje. Adicionalmente, supone un ahorro en costes, ya que no son necesarias todas las máquinas, robots y herramientas que sí serían imprescindibles en una cadena de producción. A parte del ahorro anteriormente mencionado, hay que añadir el ahorro en componentes de la pieza que, en lugar de fabricarse en distintas máquinas, se construiría en su totalidad en la máquina de fabricación aditiva. Este último, además de un ahorro en costes, supone un ahorro en tiempo ya que, a parte de los tiempos de fabricación individuales de cada componente, con los necesarios tiempos de espera si existe un orden de fabricación, se puede añadir que, si un componente debe realizarse externamente, serían necesarios unos tiempos de transporte. En segundo lugar, el espacio necesario para el almacenaje del material para la fabricación será menor, ya que se almacenará el material en polvo y no en fracciones. A consecuencia de este ahorro de espacio en general, ha sido posible, por ejemplo, incorporar una máquina de fabricación aditiva en la Estación Espacial Internacional, donde el peso y el espacio ocupado son factores claves (Oh, Witherell, Lu, & Sprock, 2020). Asimismo, con vistas a factores medioambientales y al uso responsable de los materiales, esta tecnología permite la reutilización del material. Por supuesto, una gran diferenciación de la fabricación aditiva respecto a tecnologías convencionales es la posibilidad de una personalización total del producto, alcanzando prácticamente cualquier posibilidad de diseño. Esto es debido a la fabricación capa a capa, permitiendo llegar a geometrías que mediante otras técnicas sería inviable o incluso imposible. Por el contrario, la fabricación aditiva presenta varios puntos en los que se puede mejorar. El primer punto de mejora son los tiempos de fabricación, siendo estos todavía elevados. La tardanza se debe al método de fabricación capa a capa, que requiere pasar por todas las posiciones de la pieza. El segundo aspecto por mejorar es el coste de las máquinas, que es bastante alto. Sin embargo, este aspecto es solucionable si se incrementa la demanda de estas máquinas, haciendo posible alcanzar costes de fabricación más reducidos. Por último, diversos estudios han concluido que la huella carbónica de ciertos polvos de metal es elevada, como el titanio, siendo necesario el estudio de vías de mejora en este punto . Adicionalmente, surgen otras problemáticas que no están tan relacionadas con la tecnología en sí, sino en la organización de la producción en este tipo de máquinas. De esta manera, surge el conocido como problemas “nesting”, que hace referencia a los problemas de anidado de piezas. El anidado de piezas se refiere a la manera La Fabricación Aditiva. Programación de la producción 24 24 Ilustración 9. Nesting types (Oh, Witherell, Lu, & Sprock, 2020) Finalmente, las funciones objetivos son muy diversas y dependen de los criterios seleccionados por los autores. En los casos de “Nesting” son objetivos relacionados con la maximización del “nesting rate” o la minimización del “maximum build height”. En los casos de Scheduling, los objetivos se centran principalmente en la minimización de los retrasos/adelantos o de los costes o del makespan. 25 2.3 El problema Nesting en Fabricación Aditiva El problema “nesting” en el contexto de AM se puede definir de la siguiente manera: dado un conjunto de piezas para procesar en un conjunto de recursos de AM, determine cómo agrupar y colocar mejor las piezas en los “build volumes” (Framinan, Perez-Gonzalez, & Fernandez-Viagas, 2023). Este problema también se denomina en la literatura “optimal packing” (ver, por ejemplo, Canellidis et al., (2016)). Los problemas “nesting” pueden considerarse un tipo de “cutting and packing problema” y se han tratado intensamente en la literatura. Sin embargo, cabe mencionar que el problema “nesting” de AM representa el caso más extremo de empaquetamiento 3D, ya que las piezas generalmente tienen tamaños arbitrarios y no hay límites en la orientación de la pieza o la posición en el volumen (Dickinson y Knopf, 2002). La primera aplicación de técnicas OR para el problema “nesting” AM es Wodziak et al. (1994), quienes utilizan algoritmos genéticos para resolver la versión 2D del problema con el objetivo de minimizar la entrada, mientras que Ikonen et al. (1997) abordan por primera vez la versión 3D. Las mejoras posteriores a su método en términos de tiempos de cálculo son proporcionadas por Dickinson y Knopf (1998), Hur et al. (2001) y Dickinson y Knopf (2002). Si bien se han considerado otros objetivos, el primer intento de integrar diferentes objetivos (incluido el “build time”, las estructuras de soporte o la calidad de las piezas) lo llevan a cabo Gogate y Pande (2008). La mayoría de los investigadores que abordan la versión 3D del problema utilizan variaciones de la llamada heurística “Deepest Bottom-Left-Fill” (DBLF), que considera la posición más profunda en el “build volume”, empaquetando las piezas lo más cerca posible de la parte inferior e izquierda (en ese orden) en el nivel más profundo posible. Este enfoque generalmente se ha combinado con metaheurísticas, siendo el principal desafío lograr un equilibrio adecuado entre la calidad de la solución (es decir, la minimización de las brechas en el “build volume”) y el esfuerzo computacional (que aumenta a medida que se codifica el volumen de la pieza de forma más precisa y con la estrategia elegida para colocar las piezas). Un estudio reciente sobre esta compensación es el de Araújo et al. (2020b). En cuanto a las metaheurísticas empleadas, cabe destacar que la inmensa mayoría de las contribuciones utilizan Algoritmos Genéticos. Dentro de este problema podemos encontrar otro subproblema llamado: “Optimal build orientation”. Este problema (también denominado “optimal part orientation”) se puede definir de la siguiente manera: dada una pieza que se va a procesar en un recurso de fabricación aditiva, se determina la mejor orientación de la construcción de acuerdo con una serie de objetivos de producción. Dado que en FA la pieza se construye capa por capa, el objeto crece a lo largo de la llamada dirección de construcción (“build direction”), y esto afecta a una serie de propiedades (incluidos el coste, el tiempo y la calidad) de la pieza fabricada. En términos generales, las capas son paralelas a la plataforma de construcción, por lo que la pieza se construye a lo largo del eje Z de la máquina AM, consulte la Ilustración 10. Por lo tanto, dada una pieza a construir (generalmente representada por un modelo 3D de la pieza), el modelo se puede colocar en la plataforma de construcción (y entonces, la dirección de construcción y el eje Z del modelo coinciden), o se puede girar a lo largo de los ejes X e Y como en la figura de la derecha de la Ilustración 10. Por lo tanto, la tupla (α, β) representa una orientación de construcción y determina cómo se construirá la pieza capa por capa. A su vez, esto determina una serie de propiedades de la pieza, incluidas las características mecánicas (es decir, el límite elástico y de tracción a lo largo de la capa son generalmente mayores que entre las capas), características de calidad (es decir, los errores dimensionales y la rugosidad de la superficie aparecen más comúnmente entre las capas), el tiempo de construcción (por ejemplo, la altura del edificio se ve claramente afectada por la orientación de la pieza) y los costes de construcción (como, por ejemplo, los costes de energía o los costes de posprocesamiento, claramente afectados por el tiempo y la calidad de construcción antes mencionados), entre otros Framinan, Perez-Gonzalez, & Fernandez-Viagas (2023). La Fabricación Aditiva. Programación de la producción 26 26 Ilustración 10. Orientaciones de una pieza en los ejes X, Y, Z (Framinan, et al., 2023). Este problema ha sido tratado intensamente en la literatura y los métodos para abordarlo pueden clasificarse como métodos de un solo paso o métodos de dos pasos. Los métodos de un solo paso desarrollan un algoritmo de búsqueda exhaustivo o utilizan una técnica de optimización para obtener una solución del espacio de soluciones. Básicamente, dado un modelo 3D de la pieza y un conjunto de objetivos de producción, estos métodos mejoran iterativamente la mejor solución hasta ahora generando primero una nueva orientación de construcción (generalmente girando la pieza paso a paso a lo largo de uno de los ejes), y luego obtener estimaciones de los valores de los objetivos de producción si la pieza se produce de acuerdo con esta orientación de construcción. En los métodos de dos pasos, el primer paso consiste en pasar de un espacio de búsqueda infinito (todas las orientaciones de construcción posibles) a un espacio de búsqueda finito compuesto por un conjunto de orientaciones de construcción alternativas (ABOs). Este conjunto se obtiene mediante varias técnicas (incluido “feature recognition”, “convex hull generation”, o “facet clustering”). El segundo paso consiste en utilizar algún método de optimización, generalmente multicriterio, para seleccionar una orientación de construcción del conjunto (la llamada “OBO” o “Optimal Build Orientation”). En estos métodos, se ahorra el esfuerzo computacional requerido para evaluar muchas orientaciones de construcción que no difieren esencialmente de otras ya exploradas. En cambio, se derivan reglas basadas en las preferencias de los usuarios o en los patrones deseados para la orientación de la pieza, de modo que se obtiene un conjunto finito de orientaciones de construcción. El principal problema de estos métodos es que, no importa qué técnica se utilice para seleccionar el conjunto de orientaciones de construcción alternativas, no hay garantía de que se incluya la óptima en el conjunto. Además, algunas de las técnicas de selección tienen limitaciones y no pueden abordar piezas de forma libre. El primer trabajo que aborda el problema es el de Frank y Fadel (1995), quienes presentan un sistema experto basado en entrevistas a usuarios para ayudar a seleccionar la mejor orientación de construcción. Lan et al. (1997) encuentran que existe una relación entre el tiempo de construcción y la altura de construcción (ya que está relacionado con el número de capas) y utilizan este hecho para proponer un algoritmo geométrico específico para el problema. El modelo que describe la relación entre el tiempo de construcción y la altura es posteriormente refinado por varias contribuciones, como Xu et al. (1997), Thrimurthulu et al. (2004), Khodaygan y Golmohammadi (2018), Griffiths et al. (2019), o Di Angelo et al. (2020), para tener en cuenta otros aspectos que influyen en el tiempo de construcción, como el espesor de la capa, la generación de estructuras de soporte o el volumen. Dada la naturaleza multiobjetivo inherente del problema, muchos enfoques ponderan los objetivos de producción o abordan el problema de optimización multiobjetivo, ya sea utilizando “Pareto-fronts” o técnicas de toma de decisiones multicriterio como DEA (Ransikarbum & Kim, 2017), AHP (Ransikarbum et al., 2021), TOPSIS (Di Angelo et al., 2020) o “fuzzy decision making” de múltiples atributos (Qin et al., 2019). En sistemas donde las piezas llegan una por una y no se puede predecir el tamaño y la forma de las siguientes piezas, esto provoca (en algunos casos prohibitivamente) una pérdida de tiempo optimizar la orientación de construcción de cada pieza. En estos casos, se puede aplicar un método de decisión de orientación de construcción o build orientation policy. De manera similar a por ejemplo, reglas de asignación, estas políticas se basan en una característica del trabajo que puede identificarse fácilmente. Algunas políticas a destacar son 27 Laying Policy (LP) donde la pieza se coloca de manera que tenga su altura más baja, o Standing Policy (SP) donde la pieza se coloca de manera que tenga su altura más alta. Un conjunto de estas políticas se investiga en Oh et al. (2020b). Finalmente, vale la pena mencionar que la mayoría de los artículos se centran en encontrar la orientación de construcción óptima para una sola pieza. Sin embargo, dado que una construcción normalmente consta de un grupo de piezas, se debe encontrar una orientación de construcción óptima (común). Este problema es abordado por Zhang et al. (2017) utilizando un procedimiento de dos pasos (Framinan, et al., 2023). Definición de la problemática 28 28 3 DEFINICIÓN DE LA PROBLEMÁTICA n este capítulo se definirá de manera descriptiva y matemática el problema específico de este proyecto, definiendo además los parámetros de entrada que se necesitan. Se empieza definiendo los problemas “2D Bin Packing para el Nesting”, ya que contemplan un cierto parecido con el problema en estudio. Los siguientes apartados ya se centrarán de una manera más profunda y específica en nuestro problema, describiendo problemas con múltiples orientaciones, con fechas de disponibilidad y entrega, y definiendo las 3 funciones objetivas que se estudian (Min. “Makespan”, “Total Costs” y “Total Tardiness”, centrándonos en este último). En los últimos dos apartados nos apoyaremos en los artículos de Oh et al., (2020) y Chergui, HadjHamou, & Vignat (2018). 3.1 Problemas 2D Bin Packing para el Nesting Este apartado se basará mayormente en el artículo de Lodi, Martello, & Vigo (2002). En el problema 2D Bin Packing (2BP), se nos da un conjunto de n elementos rectangulares j ∈J = {1, …, n}, cada uno con ancho 𝑤𝑗 y alto ℎ𝑗, y un número ilimitado de contenedores rectangulares idénticos finitos, que tienen ancho W y alto H. El problema es asignar, sin superponer, todos los artículos al número mínimo de contenedores, con sus bordes paralelos a los de los contenedores. Se supone que los elementos tienen orientación fija, es decir, no se pueden girar. El problema 2BP tiene muchas aplicaciones industriales, especialmente en el corte (industrias de la madera y el vidrio) y el embalaje (transporte y almacenamiento). Ciertas aplicaciones pueden requerir restricciones y/o suposiciones adicionales. El caso especial donde 𝑤𝑗= W (j = 1, …, n) es el famoso problema de 1D Bin Packing (1BP): dividir n elementos, cada uno con un tamaño asociado ℎ𝑗, en el número mínimo de subconjuntos para que la suma de los tamaños en cada subconjunto no excede una capacidad determinada H. Dado que se sabe que 1BP es fuertemente NP-hard, lo mismo se aplica a 2BP. En este artículo examinamos los avances recientes obtenidos para el problema del 2D Bin Packing, con especial énfasis en algoritmos exactos y enfoques heurísticos y metaheurísticos efectivos. En cuanto a la heurística, sólo consideraremos algoritmos off-line, para los cuales se supone que el algoritmo tiene pleno conocimiento de toda la entrada. E 29 Sin pérdida de generalidad, asumiremos a lo largo del artículo que todos los datos de entrada son números enteros positivos y que 𝑤𝑗 ≤ W y ℎ𝑗 ≤ H (j = 1, … , n). Existen 4 tipos de algoritmos para resolver estos problemas y sus respectivas variantes: • Upper Bounds (Límite superior) Aquí podemos encontrar los algoritmos más básicos y dónde podremos ver de forma sencilla la idea del problema 2D Bin Packing. La mayoría de los algoritmos off-line de la literatura son de tipo greedy y se pueden clasificar en dos familias: - Algoritmos de una fase, directamente empaquetan los artículos en contenedores finitos. - Algoritmos de 2 fases, comienza empacando los artículos en una sola tira, es decir, un contenedor que tiene un ancho W y una altura infinita. En la segunda fase, la solución de tira se utiliza para construir un empaque en contenedores finitos. Además, la mayoría de los enfoques son algoritmos de nivel, es decir, el embalaje en contenedor/tira se obtiene colocando los artículos, de izquierda a derecha, en filas formando niveles. El primer nivel es la parte inferior del contenedor/tira, y los niveles posteriores se producen mediante la línea horizontal que coincide con la parte superior del artículo más alto empaquetado en el nivel inferior. Se han derivado tres estrategias clásicas para el empaquetado de niveles a partir de algoritmos famosos para el caso unidimensional. En cada caso, los artículos se clasifican inicialmente por altura no decreciente y se empaquetan en la secuencia correspondiente. Sea “j” el elemento actual y “s” el último nivel creado, distinguimos 3 principales estrategias: - Next-Fit Decreasing Height (NFDH): el elemento j se empaqueta justificado a la izquierda en el nivel s, si encaja. De lo contrario, se crea un nuevo nivel (s: = s + 1) y se empaqueta j justificado a la izquierda en él. - First-Fit Decreasing Height (FFDH): El artículo j se empaqueta justificado a la izquierda en el primer nivel donde encaja, si corresponde. Si ningún nivel puede acomodar j, se inicializa un nuevo nivel como en NFDH. Esta estrategia, con algunas variantes, es la que utilizaremos en este trabajo y se encuentra definido en el apartado 4.2. - Best-Fit Decreasing Height (BFDH): El artículo j se empaqueta justificado a la izquierda en ese nivel, entre aquellos en los que cabe, para los cuales el espacio horizontal no utilizado es mínimo. Si ningún nivel puede acomodar j, se inicializa un nuevo nivel como en NFDH. Ilustración 11. Algoritmos de nivel (Lodi, Martello, & Vigo, 2002) Con estas 3 estrategias, diferentes investigadores las han combinado para encontrar la mejor solución minimizando los espacios vacíos en cada contenedor. Definición de la problemática 30 30 • Lower Bounds (Límite inferior) Tiene como objetivo encontrar una cota inferior del número mínimo de contenedores (“bins”) necesarios para empaquetar un conjunto de objetos rectangulares en un espacio dado. Buenos límites inferiores del valor de la solución óptima son importantes tanto en la implementación de enfoques enumerativos exactos como en la evaluación empírica de soluciones aproximadas. El límite más simple para 2BP es el límite inferior continuo computable en tiempo lineal: 𝐿0=[∑𝑤𝑗ℎ𝑗 𝑛 𝑗=1 𝑊𝐻 ] Existen límites más complejos que se pueden consultar en (Lodi, Martello, & Vigo, 2002). • Algoritmos exactos Martello & Vigo (1998) presentaron un enfoque enumerativo para la solución exacta de 2BP. Los elementos se clasifican inicialmente en orden no creciente de su área. Un procedimiento de reducción intenta determinar el embalaje óptimo de algunos contenedores, reduciendo así el tamaño de la instancia. Luego se obtiene heurísticamente una primera solución vigente, de valor 𝑧∗. El algoritmo se basa en un esquema de ramificación de dos niveles: - Árbol de decisión de rama exterior: en cada nodo de decisión, se asigna un artículo a un contenedor sin especificar su posición real. - Árbol de decisión de rama interna: se determina un embalaje factible (si lo hay) para los artículos actualmente asignados a un contenedor, posiblemente mediante la enumeración de todos los patrones posibles. La búsqueda en el árbol de decisión de la rama exterior se realiza primero en profundidad, utilizando los límites inferiores descritos en la sección anterior. Siempre que sea posible establecer que no se pueden asignar más elementos no asignados a un contenedor inicializado determinado, dicho contenedor se cierra: un contenedor inicializado y no cerrado se considera activo. En el nivel k (k = 1, …, n), el elemento k se asigna, a su vez, a todos los contenedores activos y, posiblemente, a uno nuevo (si el número total de contenedores activos y cerrados es inferior a 𝑧∗ − 1). Primero se comprueba heurísticamente la viabilidad de la asignación de un artículo a un contenedor. Se calcula un límite inferior L (I) para la instancia I definida por los elementos actualmente asignados al contenedor: si L (I) > 1, se realiza un retroceso. De lo contrario, se aplican algoritmos heurísticos a I: si se encuentra un empaquetado de un solo contenedor factible, se reanuda la enumeración externa. De lo contrario, el esquema de ramificación interno enumera todas las formas posibles de empaquetar I en un contenedor a través de la estrategia descendente más a la izquierda: en cada nivel, el siguiente artículo se coloca, a su vez, en todas las posiciones donde tiene su borde izquierdo adyacente al borde derecho de otro artículo o al borde izquierdo del contenedor, y su borde inferior adyacente al borde superior de otro artículo o al borde inferior del contenedor. Tan pronto como se encuentre un embalaje viable para todos los elementos de I, se reanuda la enumeración externa. Si no existe tal embalaje, se realiza un retroceso externo. Siempre que la asignación actual sea factible, la posibilidad de cerrar el contenedor se verifica mediante cálculos de límite inferior. • Metaheurísticas En los últimos años, las técnicas metaheurísticas se han convertido en una herramienta popular para la solución aproximada de problemas difíciles de optimización combinatoria. Lodi, Martello, & Vigo (1999) desarrollaron algoritmos de búsqueda tabú efectivos para 2BP y para algunas de las variantes analizadas en la siguiente sección. Describimos aquí brevemente el marco unificado de búsqueda tabú dado en el artículo citado, cuya característica principal es la adopción de un esquema de búsqueda y una vecindad que son independientes del 31 problema de empaque específico a resolver. Por tanto, el marco se puede utilizar para prácticamente cualquier variante de 2BP, simplemente cambiando el algoritmo determinista específico utilizado para evaluar los movimientos dentro de la búsqueda de vecindad. Dada una solución actual, los movimientos la modifican cambiando el embalaje de un subconjunto S de artículos, intentando vaciar un contenedor objetivo específico. Sea 𝑆𝑖 el conjunto de artículos actualmente empacados en el contenedor i: el contenedor objetivo t es el que minimiza, sobre todos los contenedores i, la función 𝜑(𝑆𝑖)= 𝛼 ∑𝑤𝑗ℎ𝑗𝑗∈𝑆𝑖 𝑊𝐻 −|𝑆𝑖| 𝑛 (𝛼 es un peso positivo preespecificado), que da una medida de la facilidad de vaciar el contenedor. De hecho, favorece los contenedores objetivo que contienen un área pequeña y una cantidad relativamente grande de artículos. Una vez que se ha seleccionado el contenedor de destino, el subconjunto S se define para incluir un artículo, j, del contenedor de destino y el contenido actual de otros k contenedores. El nuevo empaquetado para S se obtiene ejecutando un algoritmo heurístico apropiado A en S. El valor del parámetro k, que define el tamaño y la estructura de la vecindad actual, se actualiza automáticamente durante la búsqueda. Si el movimiento empaqueta los artículos de S en k (o menos) contenedores, es decir, el artículo j se ha eliminado del contenedor de destino, se selecciona un nuevo artículo, se define un nuevo conjunto S en consecuencia y se realiza un nuevo movimiento. De lo contrario, S se cambia seleccionando un conjunto diferente de k contenedores, o un elemento j diferente del contenedor de destino (si se han intentado todas las configuraciones posibles de k contenedores para el j actual). Si el algoritmo se atasca, es decir, el contenedor de destino no se vacía, la vecindad se amplía aumentando el valor de k, hasta un límite superior prefijado. Hay una lista y una tenencia tabúes para cada valor de k. Se obtiene una solución inicial ejecutando el algoritmo A en la instancia completa, mientras que la solución de búsqueda tabú inicial consiste en empaquetar un artículo por contenedor. En situaciones especiales, a un movimiento le sigue una acción de diversificación. La ejecución se detiene tan pronto como se encuentra una solución óptima comprobada o se alcanza un límite de tiempo. • Variantes Los problemas de embalaje en contenedores bidimensionales ocurren en varios contextos del mundo real, especialmente en las industrias de corte y embalaje. Como consecuencia de ello, surgen una serie de variantes, según aplicaciones específicas. En la mayoría de los casos, los requisitos adicionales se refieren a la orientación y/o al corte con guillotina. En los problemas de embalaje en contenedores y en tiras considerados hasta ahora hemos supuesto que los artículos tienen una orientación fija (es decir, no pueden rotarse) y que no se impone ninguna restricción a los patrones de corte. En ciertos contextos del mundo real, se puede permitir la rotación de artículos (generalmente 90°) para producir mejores empaques. Esta variante de las orientaciones de las piezas la desarrollamos en el siguiente apartado. Definición de la problemática 32 32 3.2 Problemas con múltiples orientaciones En la fabricación aditiva, dado que una capa se construye sobre otra, para construir una pieza donde su capa superior sea mayor que las inferiores, pueden ser necesarias estructuras de soporte para evitar la deformación de la pieza cuando se construye la capa más grande. Por lo tanto, algunas capas pueden tener áreas (normalmente con menor densidad y/o material más barato/rápido) cuya única función es servir de soporte para las capas más grandes. Obviamente, esto aumenta el tiempo y los costos (material, energía) necesarios para construir la pieza, y está claro que usar una orientación de construcción diferente del modelo CAD (es decir, simplemente darle la vuelta al modelo) puede resultar en construcciones más rápidas y económicas. Además, como se analiza más adelante, las propiedades físicas de la pieza son diferentes según la orientación, por lo que encontrar la orientación de construcción óptima para una pieza es una decisión importante en FA (Framinan, Perez-Gonzalez, & Fernandez-Viagas, 2023). En la siguiente ilustración se muestra un ejemplo de 6 posibles orientaciones de una misma parte: Ilustración 12. Posibles orientaciones de una parte (Lodi, Martello, & Vigo, 2002) Aunque pueden existir infinitas orientaciones, en la realidad sólo unos subconjuntos de orientaciones prácticas son seleccionables. La definición de este conjunto de orientaciones alternativas de cada parte es una primera tarea que se basa en calidad, costes o tiempos y que para nuestro problema será información de partida. Es decir, para nuestro estudio, existirá un conjunto de “ng” partes a fabricar con el mismo material. Cada una de las partes “i” tendrá un conjunto de “K(i)” orientaciones alternativas prácticas. Cada orientación alternativa “k” de una misma parte “i” se conoce: - La superficie o área que ocupa proyectada sobre la bandeja de la estructura “Aik” (cm2) - La altura que ocupa desde la bandeja de la estructura “Hik” (cm) - El volumen que ocupa en la estructura, que no depende de la orientación “Vi” (cm3) Para la fabricación de todas las partes existirán “nm” máquinas de fabricación aditiva por capas, cada una de ellas con características propias (área de la bandeja, altura máxima, tiempos de preparación o velocidades de producción). Podría ocurrir que alguna parte no se puede fabricar en algunas de las máquinas. Las principales características de las máquinas son: - El tiempo que se emplea por unidad de volumen del material “VTm” (h/cm3) - El tiempo que se emplea para cada capa de polvo por unidad de altura y que se repite hasta alcanzar la altura máxima “HTm” (h/cm) - El tiempo de preparación de la máquina cada vez que se haga un trabajo “SETm” (h) - La superficie de la bandeja que sirve de base “MAm” (cm2) - La altura máxima de procesado “MHm” (cm) 33 El problema a estudiar consistirá en repartir todas las “ng” partes a fabricar entre diferentes estructuras, de forma que en cada estructura pueden ir una o varias partes y cada parte se fabricará con una de sus orientaciones prácticas. Cada estructura se considera un trabajo a realizar en una de las máquinas disponibles, de forma que los tamaños de las bandejas y las alturas máximas en cada máquina pueden ser diferentes. 3.3 Problemas con fechas de disponibilidad y entrega. Objetivos Además de agrupar las partes en trabajos, decidir la orientación de cada parte entre las alternativas y decidir en qué máquina va cada trabajo, hay que decidir el orden de fabricación de cada trabajo en la máquina asignada. Para seleccionar la mejor solución entre todas las posibles, se van a plantear diversos modelos de programación matemática: - Modelo “AM-Cost”: modelo de programación lineal entera (ILP) de planificación de la producción que minimiza los costes totales. El coste de producción de cada trabajo “j” en cada máquina “m” será la suma del coste de preparación de la máquina en cada cambio de trabajo (cost of setting up), más el coste asociadas a las capas de polvo (cost of powder layering) más el coste de material empleado y el de operación (cost of material melting). Para calcular los costes de producción, hay que definir los costes unitarios de producción: o El coste por unidad de volumen del material “MC” ($/cm3) o El coste de operación por unidad de tiempo empleado en cada máquina “TCm” ($/h) o El coste de mano de obra por unidad de tiempo para preparar la máquina “HC” ($/h) También haría falta añadir la siguiente variable auxiliar: o JPCjm: Coste de producción de la estructura j-ésima en la máquina m - Modelo “AM-Makespan”: modelo de programación lineal mixta-entera (MILP) de planificación y programación de la producción que minimiza el tiempo de finalización del último trabajo (makespan). Haría falta añadir la siguiente variable auxiliar: o Cmax: Tiempo de finalización del último trabajo (makespan) - Modelo “AM-Tardiness”: modelo de programación lineal mixta-entera (MILP) de planificación y programación de la producción que minimizan los retrasos (tardiness) de forma ponderada asociados a las partes o a los pedidos de un conjunto de partes. Haría falta añadir la siguiente variable auxiliar: o CCi: Tiempo de finalización de la parte i Todos ellos comparten las siguientes variables: Variables de decisión - Xijmk: = 1, si la parte i se fabrica con orientación k en el trabajo j-ésimo de la máquina m Variables auxiliares - Zjm: = 1, si alguna parte es asignada al trabajo j-ésimo de la máquina m (si ∑Xij i≥1) - Hmaxj: Máxima altura de cualquier parte del trabajo j Método de Resolución 40 40 𝐶𝑖𝑘𝑚 1=𝐴𝑖𝑘 𝑀𝐴𝑚 (2) Similarmente, la métrica (3) da prioridad a la inserción de piezas de mayores volúmenes. 𝑉𝑚𝑎𝑥𝑚 representa el volumen máximo de material que puede procesar la máquina m. Se calcula como el producto de 𝑀𝐴𝑚 por 𝐻𝑚𝑎𝑥𝑚. 𝑉𝑗𝑚 indica el volumen total de material asignado del trabajo parcialmente construido y 𝑉𝑖 es el volumen de material de la pieza a insertar. 𝐶𝑖𝑗𝑚 2=𝑉𝑚𝑎𝑥𝑚−𝑉𝑗𝑚−𝑉𝑖 𝑉𝑚𝑎𝑥𝑚 (3) Por otro lado, la métrica (4) da prioridad a la inserción de piezas en orientaciones que no aumenten la altura máxima del trabajo parcialmente construido. Tenga en cuenta que el valor de esta métrica solo se considerará cuando la altura de la pieza a insertar en una orientación específica (Hik) sea mayor que la altura máxima actual del trabajo (𝐻𝑚𝑎𝑥𝑗𝑚= max {i,k}∈J(j)𝐻𝑖𝑘). Se calcula un valor adimensional dividiendo por la altura de la plataforma de construcción de su máquina relacionada (Hmaxm). 𝐶𝑖𝑘𝑗𝑚 3=𝑚𝑎𝑥{0; 𝐻𝑖𝑘−𝐻𝑚𝑎𝑥𝑗𝑚} 𝐻𝑚𝑎𝑥𝑚 (4) Finalmente, la última métrica 𝐶𝑖𝑘𝑗𝑚 4 mide el impacto relativo obtenido con respecto a la función objetivo del problema después de la inserción de la pieza i en una orientación específica k en el trabajo j de la máquina m. Dependiendo de la función objetivo a utilizar, esta métrica se expresa de diferente forma: A) Función objetivo: minimizar el coste total de producción de los trabajos (JPC) El coste de producción de un trabajo j en una máquina m (JPCjm) se calcula a través de la Ecuación (5). 𝐽𝑃𝐶𝑗𝑚=𝑆𝐸𝑇𝑚·𝐻𝐶 + ( 𝑉𝑇𝑚 · 𝑇𝐶𝑚 +MC)· ∑𝑉𝑖 ⬚ 𝑖∈𝐽(𝑗) + 𝐻𝑇𝑚 · 𝑇𝐶𝑚 · 𝑚𝑎𝑥 {𝑖,𝑘}∈𝐽(𝑗)𝐻𝑖𝑘 (5) Así, la métrica (6) mide la diferencia relativa obtenida con respecto al coste de producción del trabajo antes (JPCjm) y después (JPCjm(+ik)) de la inserción de la pieza i con una orientación específica k en el trabajo j de la máquina m. 𝐶𝑖𝑘𝑗𝑚 4=𝐽𝑃𝐶𝑗𝑚(+𝑖𝑘)−𝐽𝑃𝐶𝑗𝑚 𝐽𝑃𝐶𝑗𝑚 (6) Así, la función “greedy” para la función objetivo de minimizar el coste total de producción de los trabajos viene expresada en la Ecuación (7). ф𝑖𝑘𝑗𝑚 (𝐴)=𝛼1∗𝐴𝑖𝑘 𝑀𝐴𝑚+𝛼2∗𝑉𝑚𝑎𝑥𝑚−𝑉𝑗𝑚−𝑉𝑖 𝑉𝑚𝑎𝑥𝑚+𝛼3∗𝑚𝑎𝑥 ⬚{0; 𝐻𝑖𝑘−𝐻𝑚𝑎𝑥𝑗𝑚} 𝐻𝑚𝑎𝑥𝑚+ (7) 41 𝛼4∗𝐽𝑃𝐶𝑗𝑚(+𝑖𝑘)−𝐽𝑃𝐶𝑗𝑚 𝐽𝑃𝐶𝑗𝑚 B) Función objetivo: minimizar el tiempo total de finalización (Makespan) El makespan es la cantidad de tiempo requerido para procesar todos los trabajos en las máquinas asignadas. Por tanto, en esta fase de construcción de trabajos, la métrica 𝐶𝑖𝑘𝑗𝑚 4 mide el impacto relativo en el Tiempo de Procesamiento de un trabajo j en una máquina m antes (PTjm) y después (PTjm(+ik)) de la inserción de la pieza i con una orientación específica k. El tiempo de procesamiento PTjm de un trabajo j en una máquina m se calcula mediante la ecuación (8). 𝑃𝑇𝑗𝑚=𝑆𝐸𝑇𝑚 + 𝑉𝑇𝑚·∑𝑉𝑖 ⬚ 𝑖∈𝐽(𝑗) + 𝐻𝑇𝑚·𝑚𝑎𝑥 {𝑖,𝑘}∈𝐽(𝑗)𝐻𝑖𝑘 (8) La métrica (9) es la que se usa para esta función objetivo. 𝐶𝑖𝑘𝑗𝑚 4=𝑃𝑇𝑗𝑚(+𝑖𝑘)−𝑃𝑇𝑗𝑚 𝑃𝑇𝑗𝑚 (9) Así, la función “greedy” para la función objetivo de minimizar el tiempo total de finalización (Makespan) viene expresada en la Ecuación (10). ф𝑖𝑘𝑗𝑚 (𝐵)=𝛼1∗𝐴𝑖𝑘 𝑀𝐴𝑚+𝛼2∗𝑉𝑚𝑎𝑥𝑚−𝑉𝑗𝑚−𝑉𝑖 𝑉𝑚𝑎𝑥𝑚+𝛼3∗𝑚𝑎𝑥 ⬚{0; 𝐻𝑖𝑘−𝐻𝑚𝑎𝑥𝑗𝑚} 𝐻𝑚𝑎𝑥𝑚+ 𝛼4∗𝑃𝑇𝑗𝑚(+𝑖𝑘)−𝑃𝑇𝑗𝑚 𝑃𝑇𝑗𝑚 (10) C) Función objetivo: minimizar el retraso total El retraso total es la cantidad de tiempo acumulado de retraso al terminar cada pieza después de su fecha de vencimiento considerando la fecha de finalización del trabajo asignada a cada pieza. Luego, en esta fase de construcción de trabajos, la métrica debe medir el impacto relacionado con el retraso total de las piezas de un trabajo j en una máquina m antes (JTjm) y después (JTjm(+ik)) de la inserción de la pieza i en una orientación específica k. También deben ser consideradas la fecha de vencimiento de la pieza i (DDi) y la fecha de disponibilidad de la pieza i (RDi). El retraso total JTjm de las piezas de un trabajo j en una máquina m se calcula mediante la ecuación (11), donde DDi es la fecha de vencimiento de la pieza i, y CTjm se expresa en la Ecuación (12) como el tiempo de finalización del trabajo j en la máquina m, es decir, la suma del tiempo de inicio del trabajo j en la máquina m (STjm) y del procesamiento del trabajo j en la máquina m (PTjm). El tiempo de inicio de un trabajo j en la máquina m (STjm) se expresa en la Ecuación (13) como el máximo entre el tiempo de finalización del trabajo precedente en la máquina m y la mayor fecha de disponibilidad de las piezas del trabajo j. 𝐽𝑇𝑗𝑚= ∑𝑚𝑎𝑥 ⬚{0; 𝐶𝑇𝑗𝑚−𝐷𝐷𝑖} 𝑖∈𝐽(𝑗) (11) Método de Resolución 42 42 𝐶𝑇𝑗𝑚=𝑆𝑇𝑗𝑚+𝑃𝑇𝑗𝑚 (12) 𝑆𝑇𝑗𝑚=𝑚𝑎𝑥 ⬚{𝐶𝑇𝑗−1,𝑚; 𝑚𝑎𝑥 𝑖∈𝐽(𝑗){𝑅𝐷𝑖}} (13) Es importante destacar que la estrategia de construir cada trabajo con la máxima cantidad de piezas es eficiente para los objetivos de minimizar los costes totales y de minimizar el makespan, pero no necesariamente es eficiente para la función objetivo de minimizar el retraso total. Una pieza que es urgente es posible que sea interesante fabricarla sola en un trabajo para que se pueda cumplir la fecha de vencimiento si el objetivo es reducir retrasos. Por ello, se va a definir una estrategia diferente para construir los trabajos y con distintas métricas para la función “greedy” cuando se considere la función objetivo de minimizar el retraso total. Se va a considerar que se finaliza la construcción de un trabajo j en la máquina m cuando asignar una nueva pieza i suponga un retraso mayor que el retraso antes de asignar dicha pieza al trabajo, es decir, si JTjm(+ik) (después) es mayor que JTjm (antes). Esta comprobación no se aplica al inicializar el trabajo j con la primera pieza i (seed). Con esta estrategia, ya se consideran los retrasos y las métricas se van a basar fundamentalmente en tiempos. Así, la función “greedy” que se va a aplicar para la función objetivo de minimizar el retraso total viene expresada en la Ecuación (14). ф𝑖𝑘𝑗𝑚 (𝐶)=𝛼1∗𝐴𝑖𝑘 𝑀𝐴𝑚+𝛼2∗𝑆𝑇𝑗𝑚−𝑅𝐷𝑖 1+𝑆𝑇𝑗𝑚 +𝛼3∗𝐷𝐷𝑖 1+𝑆𝑇𝑗𝑚+ 𝛼4∗𝑃𝑇𝑗𝑚(+𝑖𝑘)−𝑃𝑇𝑗𝑚 𝑃𝑇𝑗𝑚 (14) Es importante comentar que, tanto en este paso de construcción como en el siguiente paso de inicialización de los trabajos, hay que comprobar que la pieza a insertar cumple con las restricciones del proceso (Función de Admisibilidad): - La pieza no supere la altura de la plataforma de construcción de la máquina - El instante de inicio del trabajo sea mayor o igual a la fecha de disponibilidad de la pieza, y - La superficie de la pieza entre en el espacio disponible de la plataforma de construcción de la máquina. Esta última restricción se puede comprobar de 2 formas: • Considerando que el área de la pieza (largo x ancho) sea menor que el área disponible de la plataforma o bien, • Considerando que la superficie de cada pieza es un elemento rectangular con ancho y largo, y que la plataforma es un contenedor rectangular, que tienen un ancho y largo conocido, de forma que todas las piezas se asignen al contenedor sin superponerse, con sus bordes paralelos al contenedor. Este problema se corresponde con el 2D Bin Packing,descrito de forma más extensa en el anterior apartado. 43 4.1.3 Inicialización de trabajos Siguiendo el esquema de inserción genérico de Paraskevopoulos et al. (2008), inicialmente se debe determinar una pieza “semilla” (seed) para empezar a construir cada posible trabajo en cada máquina. El trabajo que se construya para una máquina de fabricación aditiva depende en gran medida de esta decisión. A) Función objetivo: minimizar el coste total de producción de los trabajos (JPC) Basada en la experiencia al minimizar costes, la pieza factible con mayor volumen es el criterio con mejor rendimiento para ser asignada como primera pieza a un trabajo en una máquina. Nótese que la dificultad de agrupar piezas en un mismo trabajo aumenta a medida que las piezas presentan mayores volúmenes. Este criterio es eficiente para minimizar costes y cuando no se consideran fechas de disponibilidad ni fechas de entregas de las piezas a fabricar. La orientación finalmente seleccionada de la pieza “seed” dependerá del valor obtenido por la función “greedy” mostrada en la ecuación (1) en función de los coeficientes de ponderación considerados en el problema. B) Función objetivo: minimizar el tiempo total de finalización (Makespan) Si el problema considera fechas de disponibilidad en las piezas (RDi) y el criterio se basa en minimizar la fecha de finalización de elaboración de la última pieza (makespan), entonces es interesante adelantar en el tiempo la construcción de los trabajos. . Por ello, al igual que en el anterior caso, la pieza “seed” y su orientación vendrá determinada por el valor de la función “greedy” de las piezas que estén disponibles en el momento de elaborar un job. (aquellas piezas que cumplen que su RDi es inferior al instante de comienzo del trabajo j en la máquina m (STjm). En el caso de que ninguna pieza estuviera disponible en ese momento, se elegirá la pieza con menor RDi entre las piezas factibles no asignadas con la orientación que determine la función “greedy”, retrasando el valor del STjm al instante RDseed. C) Función objetivo: minimizar el retraso total Finalmente, si el problema considera fechas de entrega en las piezas (DDi) con el objetivo de minimizar el retraso total cometido en la planificación, entonces la pieza “seed” de cada trabajo dependerá de factores como las fechas de disponibilidad y entrega de las piezas (RDi , DDi), el instante de comienzo del trabajo j en la máquina m (STjm) o el tiempo de procesamiento de la pieza i con orientación k en la máquina m (TPikm). El objetivo es priorizar, por una parte, la inserción de piezas con un DDi menor (independiente del tiempo de procesado de la pieza) y por otra, priorizar inserciones de piezas que acerquen el tiempo de producción de la máquina al DDi, provocando el menor retraso posible. Por ello, se utilizará la expresión de la ecuación 14, que dará prioridad según los coeficientes de ponderación del problema a resolver: ф𝑖𝑘𝑗𝑚 (𝑖𝑛𝑖𝑐)=+𝛼3∗𝐷𝐷𝑖 1+𝑆𝑇𝑗𝑚+𝛼4∗{|𝐷𝐷𝑖−𝑇𝑃𝑖𝑘𝑚−𝑆𝑇𝑗𝑚|+max ⬚{0,𝑅𝐷𝑖−𝑆𝑇𝑗𝑚 }} (14) Método de Resolución 44 44 4.1.4 Selección del trabajo En la fase de Construcción de Trabajos se prepara un trabajo por cada máquina AM con las piezas no programadas y seleccionando la orientación más adecuada de dichas piezas. En esta fase de Selección del Trabajo, se elegirá de entre todos los trabajos construidos, el trabajo j a fabricar en la máquina m más efectivo con menor valor de la Función Objetivo Actual (Current Objective Function, COFjm). Dicho valor se calculará dependiendo de la función objetivo a analizar. A) Función objetivo: minimizar el coste total de producción de los trabajos (JPC) La planificación de la producción de varias piezas en AM supone que cada pieza se produce exactamente una vez por una máquina AM en un trabajo. Basándonos en este supuesto, un criterio de coste efectivo para seleccionar el mejor trabajo j producido en cada iteración en la máquina asignada m (COFjm) se basa en minimizar el Costo Promedio Actual por unidad de volumen de material (CACjm), ya que se alcanza una utilización más eficiente de la capacidad de la máquina AM. Este enfoque se presenta en la ecuación (15) y también ha sido adoptado en la heurística propuesta por Li et al. (2017). Además, también se han utilizado variantes de este criterio en otras áreas de investigación (ver, por ejemplo, Paraskevopoulos et al. 2008). 𝐶𝐴𝐶𝑗𝑚=𝐽𝑃𝐶𝑗𝑚 ∑𝑉𝑖𝑖∈𝐽(𝑗) (15) B) Función objetivo: minimizar el tiempo total de finalización (Makespan) Un criterio eficiente basado en tiempos para seleccionar en cada iteración el mejor trabajo j fabricado en la máquina asignada m (COFjm) se basa en minimizar el Tiempo de finalización (CTjm) presentado en la ecuación (12). C) Función objetivo: minimizar el retraso total Un criterio eficiente basado en retrasos para seleccionar en cada iteración el mejor trabajo j fabricado en la máquina asignada m (COFjm) se basa en minimizar los Retrasos totales de cada trabajo (JTjm) presentado en la ecuación (11). 45 Pseudocódigo del algoritmo Heurística de construcción semi-paralela (α1_rango, α2_rango, α3_rango, α4_rango) Data: Initialize available AM machine lists Mm, m=1,2,…, Mmax. Result: S 1 MS ← Mejor_Solucion(); 2 FOR α1 ϵ α1_rango DO: 3 FOR α2 ϵ α2_rango DO: 4 FOR α3 ϵ α3_rango DO: 5 α4=1α3α2α1; 6 IF (α4 ≥ 0) THEN: 7 S ← SolucionInicial(), PLi ← ListaPiezas(); 8 WHILE (PLi ≠ 0) DO: 9 FOR todas las máquinas m de Mm DO: 10 jm ← InicializaTrabajo(m); seed ← BuscaPiezaSemilla(PLi); 11 IF (seed ≠ 0) THEN: 12 FOR todas las orientaciones k de seed DO: 13 ɸ (seed,k,j,m) ← FuncionGreedy(seed, k, j, m, α1, α2, α3, α4); 14 Ф ← AlmacenarMejorPieza(ɸ(seed,k,j,m)); 15 ENDFOR 16 jm ← Insertar(seed, k, Ф); done ←TRUE; 17 WHILE (done = TRUE) DO: 18 done ←FALSE 19 FOR todas las piezas i de PLi -{seed} DO: 20 FOR todas las orientaciones k de i DO: 21 ɸ(i,k,j,m) ← FuncionGreedy(i, k, j, m, α1, α2, α3, α4); 22 IF ((ɸ≥ 0) AND FunciónAdmisibilidad()) THEN: 23 Ф ← AlmacenarMejorPieza(ɸ(i,k,j,m)); done ←TRUE; 24 ENDIF 25 ENDFOR 26 ENDFOR 27 IF (done) THEN: 28 jm ← InsertarPieza(i, k, Ф); 29 ENDIF 30 ENDWHILE 31 ENDIF 32 ENDFOR 33 FOR todos los trabajos jm DO: Método de Resolución 46 46 34 COFjm ← FunciónObjetivoActual(jm); jx ← AlmacenarMejorTrabajo(COFjm); 35 ENDFOR 36 S ← InsertarTrabajo(jx); LPi ← EliminarPiezas(jx); 37 ENDWHILE 38 IF f (S) < f (MS) THEN: 39 MS ← S; 40 ENDIF 41 ENDIF 42 ENDFOR 43 ENDFOR 44 ENDFOR 4.2 Algoritmo 2D Nesting El algoritmo implementado en este trabajo tiene como objetivo resolver el problema bidimensional del “Nesting”, es decir, comprobar si un conjunto de piezas caracterizadas por las dimensiones (ancho y largo) de su área proyectada pueden ser asignadas a un job de una máquina. El problema determinará la ubicación y posición de cada una de las piezas dentro del job que se caracteriza igualmente por las dimensiones de ancho y largo. En la siguiente ilustración se muestra un ejemplo de una pieza y de un job, mostrando sus dimensiones (ancho y largo): Ilustración 13. Ejemplo de una pieza y un job Este algoritmo puede clasificarse como un algoritmo de "Strip Packing" con heurística de "First-Fit Decreasing Height" (FFDH). Da prioridad a la inserción de las piezas con mayores áreas proyectadas por lo que en cada iteración, ordenará tanto las partes, como los espacios resultantes de mayor a menor. Se va a definir el algoritmo dividiéndolo en dos grandes pasos: 47 Paso 1: Inicialización y elección de la pieza semilla El algoritmo se inicializa ordenando las piezas y los huecos (inicialmente sólo hay un hueco coincidente con las dimensiones del job) de mayor a menor área proyectada, la cual se calcula multiplicando el ancho por el largo (á𝑟𝑒𝑎=𝑎∗𝑙). Una vez estén las piezas ordenadas, se elige la pieza con mayor área, esta pieza será nuestra pieza semilla o “seed”, ya que a partir de ella empezamos a construir la solución. A continuación, se prueba a introducir la pieza en el job (ubicándola en la parte inferior izquierda, que sería la posición (0,0), como se muestra en la figura de la izquierda en la ilustración 14), si la pieza cabe, se elimina del listado de piezas disponibles y pasamos al segundo paso. Con el propósito de mejorar el empaquetamiento, si la pieza tal y como está definida no cabe en el job, se procede a girar la pieza intercambiando los valores de ancho y largo (la orientación no cambia, es la misma) y se vuelve a comprobar la admisibilidad. Se muestra un ejemplo de la importancia de girar la pieza en la siguiente imagen: Ilustración 14. Giro de una pieza Si como ha sucedido en la imagen, al girar la pieza ésta es ubicada en el job, se elimina del listado y se pasa al siguiente paso, si por el contrario sigue sin caber, el algoritmo termina aquí y no habría solución. Paso 2: Desarrollo del algoritmo Una vez introducida la pieza en el Job en la esquina inferior izquierda, se realiza un “Corte Guillotina horizontal” trazando una línea horizontal desde la esquina superior de la pieza hasta el borde derecho del job. Después de hacer esto, tendremos el espacio no ocupado del job dividido en 2 huecos (los llamaremos E1 Y E2): Ilustración 15. Corte Guillotina horizontal del algoritmo 2D Nesting Ahora lo que hará el algoritmo será incluir estos dos nuevos espacios que han surgido al introducir la pieza al listado de espacios y reordenarlos como anteriormente mayor a menor área. Seguidamente, el algoritmo repetirá los pasos 1 y 2 continuando con la siguiente pieza de mayor área proyectada y comprobando la inserción en todos los huecos disponibles. El algoritmo finalizará cuando alguna pieza no puede ser ubicada en ningún hueco disponible (devolviendo false) o cuando todas las piezas pueden ser ubicadas en el job (devolviendo true). Por último, se muestra un ejemplo de cómo podría quedar cerrado un job: Método de Resolución 48 48 Ilustración 16. Ejemplo final job Con el objetivo de obtener una visualización conceptual del algoritmo, se adjunta el siguiente diagrama de flujo: Ilustración 17. Diagrama de Flujo del Algoritmo 2D Nesting 49 5 EXPERIMENTACIÓN En este apartado se describe la experimentación, se muestran los resultados de todos los experimentos (un total de 360) y se comparan los resultados obtenidos. Se van a usar como punto de partida las 20 instancias de (Kucukkoc, 2021), que se ampliarán con información adicional de costes, y con nuevas instancias para 2 y 3 orientaciones. La heurística de construcción semiparalela definida en el anterior apartado de forma extensa se ha desarrollado en C++, donde se integrará el algoritmo de 2D Bin Packing también explicado en el apartado anterior. Se resolverán las instancias con tres funciones objetivos (minimizar Makespan, minimizar Total Tardiness y minimizar Total Costs), en todos los casos considerando y sin considerar el algoritmo 2D Bin Packing, es decir, aceptando válido si el área ocupada no supere el área máxima de cada máquina. 5.1 Generación de instancias La generación de nuevas instancias para la experimentación del problema abordado tiene su origen en las 20 instancias presentadas en Kucukkoc, Li, & Tang (2021), que tienen como información: las fechas de entrega y fechas de disponibilidad de cada pieza, la geometría de cada pieza (alto, ancho y largo) de una única orientación, su volumen, y la información de cada máquina relacionada con tiempos. Cada instancia está compuesta por entre 12 y 40 piezas, utilizando 2 tipos de máquinas y un número fijo máximo de trabajos y máquinas por instancia. Como podemos observar en la tabla 5, el número de piezas y máquinas va aumentando a la vez que aumentan las instancias, incrementando así su complejidad para ser ejecutadas y resueltas. Experimentación 56 56 Como se puede apreciar, a medida que aumentan el número de orientaciones alternativas, el cote total disminuye en casi todas las instancias del estudio. Considerando 2O reducimos el valor de la función objetivo respecto a 1O un total de 9.928,05 unidades monetarias, considerando 3O respecto a 2O reducimos 5.856,00 unidades monetarias y respecto a 1O, un total de 15.784,05. Como ocurría al minimizar Total Tardiness, en un único experimento se empeora respecto del problema con menos orientaciones. 5.2.3 Experimentación por el uso del 2D Bin Packing En este apartado nos centraremos en la comparación de usar la técnica 2D Bin Packing (descrita de forma más extensa en apartados anteriores) frente a no usarla para resolver el problema descrito en este trabajo. Al no usar esta técnica, el algoritmo lo único que realizará para comprobar que un grupo de piezas caben en un job de una máquina será sumar el área de cada pieza y comprobar que esta suma sea menor que el área de la máquina dónde van a ser fabricados. De esta manera se intuyen unos resultados mejores que en el apartado anterior pero muchas de las soluciones probablemente no sean admisibles en la realidad. Para llevar a cabo esta comparación, ejecutaremos las 20 instancias comentadas, descritas y utilizadas en el apartado anterior para las tres funciones objetivo (Minimizar Makespan, Minimizar Total Tardiness, y Minimizar Total Costs), para las 3 orientaciones posibles de las piezas y para todos los valores de los parámetros alfa, quedándose con el mejor resultado de cada experimento, esta vez sin considerar 2D Bin Packing. Así, se ejecutarán un total de 180 experimentos. • Minimizar Total Tardiness En la siguiente tabla 11 se compara el uso del 2D Bin Packing minimizando el Total Tardiness. Para ello, comparamos el valor de la función objetivo y el número de partes que se entregan con retraso. Además, se añade una columna donde se muestra la diferencia entre el valor de la función objetivo para cada instancia. Tabla 11. Comparación uso 2D Bin Packing Min Total Tardiness Como se puede apreciar, al no considerar la técnica 2D Bin Packing, el retraso total disminuye o se igualan en 57 todas las instancias del estudio y también disminuye el número de piezas entregadas con retraso. Considerando solo una orientación, el valor de la función objetivo disminuye un total de 153,10 unidades de tiempo, considerando 2O se reduce un total de 163,81 unidades de tiempo y 4 piezas entregadas con retraso, y considerando 3O un total de 136,57 y 2 piezas entregadas con retraso. • Minimizar Makespan En este apartado se compara el uso del 2D Bin Packing, esta vez minimizando el Makespan. Para ello, comparamos el valor de la función objetivo de cada instancia a través de la columna “Diferencia”, donde se refleja la diferencia entre el uso de dicha técnica. Tabla 12. Comparación uso 2D Bin Packing Min Makespan En este caso, como podemos apreciar en la tabla 12, al no considerar la técnica 2D Bin Packing, el valor del makespan disminuye considerando 2 y 3 orientaciones en un total de 70,72 y 325,04 unidades de tiempo respectivamente, pero aumenta considerando una única orientación en un total de 4,11 unidades de tiempo. De nuevo nos encontramos en algunos experimentos que el relajar el uso del 2D Bin Packing se empeora respecto del mismo problema cuando se usa 2D Bin Packing. Esta anomalía se debe al estar usando una heurística. • Minimizar Total Costs Por último, se compara el uso del 2D Bin Packing, minimizando el Total Costs. Para ello, comparamos el valor Experimentación 58 58 de la función objetivo de cada instancia a través de la columna “Diferencia”, donde se refleja la diferencia entre el uso de dicha técnica. Tabla 13. Comparación uso 2D Bin Packing Min Total Costs Como se puede apreciar en la tabla 13, al no considerar la técnica 2D Bin Packing, el cote total disminuye en todas las instancias del estudio. Considerando solo una orientación, el valor de la función objetivo disminuye un total de 29.258,27 unidades monetarias, considerando 2O se reduce un total de 27.626,19 unidades monetarias y considerando 3O un total de 22.772,15. 59 6 CONCLUSIONES Y FUTURAS LÍNEAS 6.1 Conclusiones del estudio En este trabajo final de grado se ha abordado el problema de la planificación de la producción en fabricación aditiva mediante la implementación de técnicas avanzadas como el 2D Nesting y la consideración de múltiples orientaciones para las piezas. La investigación se ha centrado en cómo la adición de diversas orientaciones a las piezas puede mejorar la eficiencia y optimización del proceso de producción. Para ello, hemos desarrollado una heurística de construcción semiparalela muy eficiente, que es una adaptación de la heurística de Paraskevopoulos et al. (2008) para problemas de rutas de vehículos (VRP). La heurística desarrollada se ha adaptado al problema en estudio para tres posibles funciones objetivos: minimizar el tiempo de finalización de los trabajos (makespan), minimizar los costes totales de producción (total costs) y minimizar los tiempos de retrasos en las entregas (total tardiness). A lo largo del estudio, se ha demostrado que la consideración de múltiples orientaciones permite una mejor utilización del espacio disponible, lo que se traduce en una reducción significativa de material desperdiciado y un aumento de la capacidad de producción. Este enfoque no solo optimiza el uso del material, sino que también reduce los tiempos de producción y los costos asociados. Comparando los resultados obtenidos con y sin la aplicación de la técnica 2D Bin Packing, se ha evidenciado que la integración de esta técnica junto con la consideración de múltiples orientaciones proporciona soluciones más realistas, pero inferiores que sin considerarla en la mayoría de los casos. La técnica 2D Bin Packing, por sí sola, ofrece mejoras en la disposición de las piezas; sin embargo, al complementarla con la capacidad de orientar las piezas de diversas maneras, se alcanzan niveles óptimos de eficiencia que no se podrían lograr de otra forma. En resumen, la combinación de técnicas de 2D Nesting y la consideración de múltiples orientaciones de las piezas en fabricación aditiva se presenta como una estrategia altamente efectiva para la planificación de la producción. Esta combinación no solo mejora la utilización del espacio y los recursos, sino que también ofrece un enfoque más flexible y adaptable a diferentes tipos de producción. Por tanto, la implementación de estas técnicas puede considerarse un avance significativo en el campo de la fabricación aditiva, aportando beneficios tangibles tanto en términos de eficiencia como de sostenibilidad. 6.2 Líneas futuras de investigación Como se ha demostrado minimizando el valor de la función objetivo para el makespan considerando 2 y 3 orientaciones para cada pieza, la heurística desarrollada no tiene la capacidad de llegar a la solución óptima debido al gran tamaño del problema, por lo que una futura mejora a este trabajo sería emplear un algoritmo de resolución más complejo como puede ser la implementación de una metaheurística. Referencias 60 60 REFERENCIAS 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. Aloui, A., & Hadj-Hamou, K. (2021). A heuristic approach for a scheduling problem in additive manufacturing under technological constraints. Computers & Industrial Engineering, 154, 107115. Araújo, L. J. P., Panesar, A., Özcan, E., Atkin, J., Baumers, M., & Ashcroft, I. (2020). An experimental analysis of deepest bottom-left-fill packing methods for additive manufacturing. International Journal of Production Research, 58(22), 6917–6933. Canellidis, V., Giannatsis, J., & Dedoussis, V. (2016). Evolutionary computing and genetic algorithms: Paradigm applications in 3D printing process optimization. In Studies in Computational Intelligence (Vol. 627, pp. 271–298). Springer Verlag. Che, Y., Hu, K., Zhang, Z., & Lim, A. (2021). Machine scheduling with orientation selection and twodimensional packing for additive manufacturing. Computers & Operations Research, 130, 105245. Chergui, A., Hadj-Hamou, K., & Vignat, F. (2018). Production scheduling and nesting in additive manufacturing. Computers & Industrial Engineering, 126, 292-301. Di Angelo, L., Di Stefano, P., Dolatnezhadsomarin, A., Guardiani, E., & Khorram, E. (2020a). A reliable build orientation optimization method in additive manufacturing: The application to FDM technology. International Journal of Advanced Manufacturing Technology, 108(1–2), 263–276. Dickinson, J. K., & Knopf, G. K. (1998). Serial packing of arbitrary 3D objects for optimizing layered manufacturing. In Casasent, D. P. (Ed.), Intelligent robots and computer vision XVII: Algorithms, techniques, and active vision, society of photo-optical instrumentation engineers (SPIE) conference series (Vol. 3522, pp. 130–138). Dickinson, J. K., & Knopf, G. K. (2002). Packing subsets of 3D parts for layered manufacturing. International Journal of Smart Engineering System Design, 4(3), 147–161. Fera, M., Macchiaroli, R., Fruggiero, F., & Lambiase, A. (2018). A new perspective for production process analysis using additive manufacturing—complexity vs production volume. The International Journal of Advanced Manufacturing Technology, 95, 673-685. Fera, M., Macchiaroli, R., Fruggiero, F., & Lambiase, A. (2020). A modified tabu search algorithm for the single-machine scheduling problem using additive manufacturing technology. International Journal of Industrial Engineering Computations, 11(3), 401-4. Framinan, J. M., Perez-Gonzalez, P., & Fernandez-Viagas, V. (2023). An overview on the use of operations research in additive manufacturing. Annals of Operations Research, 322(1), 5-40. Frank, D., & Fadel, G. (1995). Expert system-based selection of the preferred direction of build for rapid prototyping processes. Journal of Intelligent Manufacturing, 6(5), 339–345. Gibson, I., Rosen, D. W., Stucker, B., Khorasani, M., Rosen, D., Stucker, B., & Khorasani, M. (2021). Additive manufacturing technologies (Vol. 17, pp. 160-186). Cham, Switzerland: Springer. Gogate, A. S., & Pande, S. S. (2008). Intelligent layout planning for rapid prototyping. International Journal of Production Research, 46(20), 5607–5631. Griffiths, V., Scanlan, J. P., Eres, M. H., Martinez-Sykora, A., & Chinchapatnam, P. (2019). Cost-driven build orientation and bin packing of parts in Selective LaserMelting (SLM). European Journal of Operational 61 Research, 273(1), 334–352. Hernández-Castellano, P. M., Martínez-Rivero, M., ., Gutiérrez-Barcenilla, A., Suárez-García, L., & MarreroAlemán, M. (2019). Fabricación Aditiva: material didáctico interactivo. (No. COMPON-2019CINAIC-0057). Hur, S.-M., Choi, K.-H., Lee, S.-H., & Chang, P.-K. (2001). Determination of fabricating orientation and packing in SLS process. Journal of Materials Processing Technology, 112(2–3), 236–243. Ikonen, I., Biles,W., Kumar, A., Ragade, R. K., &Wissel, J. C. (1997). A genetic algorithm for packing threedimensional non-convex objects having cavities and holes. Proceedings of 7th International Conference on Genetic Algorithms (pp. 591–598). Joshi, S. C., & Sheikh, A. A. (2015). 3D printing in aerospace and its long-term sustainability. Virtual and physical prototyping, 10(4), 175-185. Khodaygan, S.,&Golmohammadi,A.H. (2018).Multi-criteria optimization of the part build orientation (PBO) through a combined meta-modeling/NSGAII/TOPSIS method for additive manufacturing processes. International Journal on Interactive Design and Manufacturing, 12, 1071–1085. Kucukkoc, I. (2019). MILP models to minimise makespan in additive manufacturing machine scheduling. Computers and Operations Research, 105. Kucukkoc, I., Li, Z., & Tang, Q. (2021). 2D Nesting and Scheduling in Metal Additive Manufacturing In Optimization and Data Science: Trends and Applications: 5th AIROYoung Workshop and AIRO PhD School 2021 Joint Event (pp. 169-180). Springer International Publishing.. Lan, P.-T., Chou, S.-Y., Chent, L.-L., & Gemmill, D. (1997). Determining fabrication orientations for rapid prototyping with stereolithography apparatus. Computer-Aided Design, 29, 62. Li, Q., Kucukkoc, I., & Zhang, D. Z. (2017). Production planning in additive manufacturing and 3D printing. Computers & Operations Research, 83, 157-172. Lodi, A., Martello, S., & Vigo, D. (1999). Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS J. Comput. 11 345–357. Lodi, A., Martello, S., & Vigo, D. (2002). Recent advances on two-dimensional bin packing problems. Discrete Applied Mathematics, 123(1-3), 379-396. Martello, S., & Vigo, D. (1998). Exact solution of the two-dimensional finite bin packing problem, Manage. Sci. 44 388-399. Muguruza, A. (2019). Contribución a las tecnologías de fabricación aditiva para la obtención de piezas multimaterial, combinando la impresión 3D por máscara con la impresión funcional mediante sistemas InkJet. Tesis Doctoral. UPC. Oh, Y., Witherell, P., Lu, Y., & Sprock, T. (2020). Nesting and scheduling problems for additive manufacturing: A taxonomy and review. Additive Manufacturing, 36, 101492. Oh, Y., Zhou, C., & Behdad, S. (2020b). The impact of build orientation policies on the completion time in wodimensional irregular packing for additive manufacturing. International Journal of Production Research, 58(21), 6601–6615. Paraskevopoulos, D. C., Repoussis, P. P., Tarantilis, C. D., Ioannou, G., & Prastacos, G. P. (2008). A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows. Journal of Heuristics, 14(5), 425-455. Qin, Y., Qi, Q., Scott, P. J., & Jiang, X. (2019). Determination of optimal build orientation for additive manufacturing using Muirhead mean and prioritised average operators. Journal of Intelligent Manufacturing, 30(8), 3015–3034. Ransikarbum, K., Ha, S., Ma, J., & Kim, N. (2017). Multi-objective optimization analysis for part-to-Printer assignment in a network of 3D fused deposition modeling. Journal of Manufacturing Systems, 43, 3546. Ransikarbum, K., Pitakaso, R., Kim, N., & Ma, J. (2021). Multicriteria decision analysis framework for part Referencias 62 62 orientation analysis in additive manufacturing. Journal of Computational Design and Engineering, 8(4), 1141–1157. Thompson, M. K., Moroni, G., Vaneker, T., Fadel, G., Campbell, R. I., Gibson, I., & ... & Martina, F. (2016). Design for Additive Manufacturing: Trends, opportunities, considerations, and constraints. CIRP annals, 65(2), 737-760. Thrimurthulu, K., Pandey, P. M., & Reddy, N. V. (2004). Optimum part deposition orientation in fused eposition modeling. International Journal of Machine Tools and Manufacture, 44, 585–594. 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. Wodziak, J. R., Fadel, G. M., & Kirschman, C. (1994). A genetic algorithm for optimizing multiple part placement to reduce build time. In Proceedings of the 5th international conference on rapid prototyping. Xu, F., Wong, Y. S., Loh, H. T., Fuh, J. Y. H., & The, T. M. (1997). Optimal orientation with variable slicing in stereolithography. Rapid Prototyping Journal, 3, 76–88. Zhang, Y., Gupta, R. K., & Bernard, A. (2016). Two-dimensional placement optimization for multi-parts production in additive manufacturing. Robotics and Computer-Integrated Manufacturing, 38, 102-117. Zhang, Y., Bernard, A., Harik, R., & Karunakaran, K. P. (2017). Build orientation optimization for multi-part production in additive manufacturing. Journal of Intelligent Manufacturing, 28(6), 1393–1407. Zhang, J., Yao, X., & Li, Y. (2020). Improved evolutionary algorithm for parallel batch processing machine scheduling in additive manufacturing. International Journal of Production Research, 58(8), 2263-2282. Zhang, X., & Liou, F. (2021). Introduction to additive manufacturing. In Additive manufacturing (pp. 1-31). Elsevier. 63 Anexos 64 64 ANEXOS Anexo 1. Ficheros AMO de las 20 instancias con 1 orientación El formato de los ficheros de datos “AMO” han sido detallado en el apartado 5.1 “Generación de instancias”. Tal como se explica en dicho apartado 5.1, los ficheros de 2 y 3 orientaciones se generan a partir de estos ficheros de 1 orientación, rotando los valores de la “Altura” el “Ancho” y el “Largo” de cada pieza. Por ello, solo se anexan los 20 ficheros de 1 orientación. INSTANCIA I1_1O Número parts: 12 Número jobs máximo: 5 Número máquinas: 2 ***************************************************************************** Part # orient volumen FDisp FEntrega Nombre 1 1 1573.80 6.25 305.90 P1 2 1 421.30 7.35 282.18 P2 3 1 147.80 9.83 378.25 P3 4 1 285.20 20.95 214.67 P4 5 1 583.30 36.58 148.98 P5 6 1 3282.50 51.50 576.18 P6 7 1 1265.50 56.35 240.42 P7 8 1 723.30 69.90 211.63 P8 9 1 278.50 75.07 330.87 P9 10 1 1051.80 86.00 387.98 P10 11 1 201.90 93.03 447.13 P11 12 1 866.10 93.10 445.10 P12 ************************************************************************ part. orient Altura Sup Ancho Largo 1 1 16.70 300.80 18.80 16.00 2 1 8.80 152.80 6.70 22.80 3 1 20.30 19.50 9.30 2.10 4 1 7.40 84.20 21.60 3.90 5 1 27.30 61.10 14.90 4.10 6 1 25.80 299.30 23.20 12.90 7 1 14.50 148.70 22.20 6.70 8 1 3.50 376.40 24.60 15.30 9 1 20.40 20.50 20.50 1.00 10 1 23.30 91.10 6.80 13.40 11 1 26.30 20.00 4.00 5.00 65 12 1 12.80 123.90 5.90 21.00 ********************************************************************************** mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 Anexos 72 72 mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 73 INSTANCIA I8_1O Número parts: 18 Número jobs máximo: 7 Número máquinas: 2 ***************************************************************************** Part # orient volumen FDisp FEntrega Nombre 1 1 201.90 93.03 447.13 P11 2 1 866.10 93.10 445.10 P12 3 1 7347.60 97.15 634.57 P13 4 1 333.60 97.25 177.55 P14 5 1 2956.00 101.75 355.30 P15 6 1 32.50 106.95 258.75 P16 7 1 265.60 107.58 295.55 P17 8 1 1387.40 115.55 509.62 P18 9 1 1086.00 128.37 294.25 P19 10 1 3559.20 132.32 575.72 P20 11 1 2902.90 134.15 569.97 P21 12 1 854.60 136.65 353.23 P22 13 1 1986.00 138.30 326.28 P23 14 1 2974.30 149.48 515.72 P24 15 1 408.20 164.08 525.87 P25 16 1 1271.40 167.45 362.63 P26 17 1 252.40 177.23 358.03 P27 18 1 3740.90 206.40 589.43 P28 ************************************************************************ part. orient Altura Sup Ancho Largo 1 1 26.30 20.00 4.00 5.00 2 1 12.80 123.90 5.90 21.00 3 1 28.40 333.50 21.80 15.30 4 1 10.90 74.20 23.20 3.20 5 1 14.10 268.50 19.60 13.70 6 1 3.90 11.20 3.60 3.10 7 1 3.20 138.90 10.60 13.10 8 1 24.60 92.00 7.30 12.60 9 1 7.10 424.00 21.20 20.00 10 1 25.20 181.40 8.40 21.60 11 1 29.60 173.80 16.40 10.60 12 1 21.10 86.40 10.80 8.00 13 1 25.20 107.80 22.00 4.90 14 1 28.20 141.60 9.50 14.90 15 1 22.90 29.00 6.30 4.60 16 1 24.20 166.40 17.70 9.40 17 1 19.00 20.90 1.00 20.90 18 1 26.60 220.60 11.20 19.70 ********************************************************************************** Anexos 74 74 mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 75 INSTANCIA I9_1O Número parts: 18 Número jobs máximo: 8 Número máquinas: 2 ***************************************************************************** Part # orient volumen FDisp FEntrega Nombre 1 1 2956.00 101.75 355.30 P15 2 1 32.50 106.95 258.75 P16 3 1 265.60 107.58 295.55 P17 4 1 1387.40 115.55 509.62 P18 5 1 1086.00 128.37 294.25 P19 6 1 3559.20 132.32 575.72 P20 7 1 2902.90 134.15 569.97 P21 8 1 854.60 136.65 353.23 P22 9 1 1986.00 138.30 326.28 P23 10 1 2974.30 149.48 515.72 P24 11 1 408.20 164.08 525.87 P25 12 1 1271.40 167.45 362.63 P26 13 1 252.40 177.23 358.03 P27 14 1 3740.90 206.40 589.43 P28 15 1 991.90 219.62 560.93 P29 16 1 1377.60 228.55 653.97 P30 17 1 11122.90 242.90 1177.72 P31 18 1 5234.10 244.87 739.32 P32 ************************************************************************ part. orient Altura Sup Ancho Largo 1 1 14.10 268.50 19.60 13.70 2 1 3.90 11.20 3.60 3.10 3 1 3.20 138.90 10.60 13.10 4 1 24.60 92.00 7.30 12.60 5 1 7.10 424.00 21.20 20.00 6 1 25.20 181.40 8.40 21.60 7 1 29.60 173.80 16.40 10.60 8 1 21.10 86.40 10.80 8.00 9 1 25.20 107.80 22.00 4.90 10 1 28.20 141.60 9.50 14.90 11 1 22.90 29.00 6.30 4.60 12 1 24.20 166.40 17.70 9.40 13 1 19.00 20.90 1.00 20.90 14 1 26.60 220.60 11.20 19.70 15 1 18.50 102.50 12.50 8.20 16 1 10.10 183.30 15.40 11.90 17 1 24.50 592.90 24.50 24.20 18 1 30.60 273.70 23.00 11.90 ********************************************************************************** Anexos 76 76 mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 77 INSTANCIA I10_1O Número parts: 18 Número jobs máximo: 9 Número máquinas: 3 ***************************************************************************** Part # orient volumen FDisp FEntrega Nombre 1 1 1086.00 128.37 294.25 P19 2 1 3559.20 132.32 575.72 P20 3 1 2902.90 134.15 569.97 P21 4 1 854.60 136.65 353.23 P22 5 1 1986.00 138.30 326.28 P23 6 1 2974.30 149.48 515.72 P24 7 1 408.20 164.08 525.87 P25 8 1 1271.40 167.45 362.63 P26 9 1 252.40 177.23 358.03 P27 10 1 3740.90 206.40 589.43 P28 11 1 991.90 219.62 560.93 P29 12 1 1377.60 228.55 653.97 P30 13 1 11122.90 242.90 1177.72 P31 14 1 5234.10 244.87 739.32 P32 15 1 274.60 245.08 553.43 P33 16 1 2628.40 248.18 536.87 P34 17 1 206.90 258.98 524.58 P35 18 1 639.50 268.42 646.72 P36 ************************************************************************ part. orient Altura Sup Ancho Largo 1 1 7.10 424.00 21.20 20.00 2 1 25.20 181.40 8.40 21.60 3 1 29.60 173.80 16.40 10.60 4 1 21.10 86.40 10.80 8.00 5 1 25.20 107.80 22.00 4.90 6 1 28.20 141.60 9.50 14.90 7 1 22.90 29.00 6.30 4.60 8 1 24.20 166.40 17.70 9.40 9 1 19.00 20.90 1.00 20.90 10 1 26.60 220.60 11.20 19.70 11 1 18.50 102.50 12.50 8.20 12 1 10.10 183.30 15.40 11.90 13 1 24.50 592.90 24.50 24.20 14 1 30.60 273.70 23.00 11.90 15 1 3.10 145.50 14.70 9.90 16 1 18.90 257.50 17.40 14.80 17 1 11.20 40.60 1.70 23.90 18 1 4.60 202.80 19.50 10.40 ********************************************************************************** Anexos 78 78 mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 3 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 79 INSTANCIA I11_1O Número parts: 24 Número jobs máximo: 9 Número máquinas: 3 ***************************************************************************** Part # orient volumen FDisp FEntrega Nombre 1 1 1573.80 6.25 305.90 P1 2 1 421.30 7.35 282.18 P2 3 1 147.80 9.83 378.25 P3 4 1 285.20 20.95 214.67 P4 5 1 583.30 36.58 148.98 P5 6 1 3282.50 51.50 576.18 P6 7 1 1265.50 56.35 240.42 P7 8 1 723.30 69.90 211.63 P8 9 1 278.50 75.07 330.87 P9 10 1 1051.80 86.00 387.98 P10 11 1 201.90 93.03 447.13 P11 12 1 866.10 93.10 445.10 P12 13 1 7347.60 97.15 634.57 P13 14 1 333.60 97.25 177.55 P14 15 1 2956.00 101.75 355.30 P15 16 1 32.50 106.95 258.75 P16 17 1 265.60 107.58 295.55 P17 18 1 1387.40 115.55 509.62 P18 19 1 1086.00 128.37 294.25 P19 20 1 3559.20 132.32 575.72 P20 21 1 2902.90 134.15 569.97 P21 22 1 854.60 136.65 353.23 P22 23 1 1986.00 138.30 326.28 P23 24 1 2974.30 149.48 515.72 P24 ************************************************************************ part. orient Altura Sup Ancho Largo 1 1 16.70 300.80 18.80 16.00 2 1 8.80 152.80 6.70 22.80 3 1 20.30 19.50 9.30 2.10 4 1 7.40 84.20 21.60 3.90 5 1 27.30 61.10 14.90 4.10 6 1 25.80 299.30 23.20 12.90 7 1 14.50 148.70 22.20 6.70 8 1 3.50 376.40 24.60 15.30 9 1 20.40 20.50 20.50 1.00 10 1 23.30 91.10 6.80 13.40 11 1 26.30 20.00 4.00 5.00 12 1 12.80 123.90 5.90 21.00 13 1 28.40 333.50 21.80 15.30 Anexos 80 80 14 1 10.90 74.20 23.20 3.20 15 1 14.10 268.50 19.60 13.70 16 1 3.90 11.20 3.60 3.10 17 1 3.20 138.90 10.60 13.10 18 1 24.60 92.00 7.30 12.60 19 1 7.10 424.00 21.20 20.00 20 1 25.20 181.40 8.40 21.60 21 1 29.60 173.80 16.40 10.60 22 1 21.10 86.40 10.80 8.00 23 1 25.20 107.80 22.00 4.90 24 1 28.20 141.60 9.50 14.90 ********************************************************************************** mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 3 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 81 INSTANCIA I12_1O Número parts: 24 Número jobs máximo: 9 Número máquinas: 3 ***************************************************************************** Part # orient volumen FDisp FEntrega Nombre 1 1 1573.80 6.25 305.90 P1 2 1 421.30 7.35 282.18 P2 3 1 147.80 9.83 378.25 P3 4 1 285.20 20.95 214.67 P4 5 1 583.30 36.58 148.98 P5 6 1 3282.50 51.50 576.18 P6 7 1 1265.50 56.35 240.42 P7 8 1 723.30 69.90 211.63 P8 9 1 278.50 75.07 330.87 P9 10 1 1051.80 86.00 387.98 P10 11 1 201.90 93.03 447.13 P11 12 1 866.10 93.10 445.10 P12 13 1 7347.60 97.15 634.57 P13 14 1 333.60 97.25 177.55 P14 15 1 2956.00 101.75 355.30 P15 16 1 32.50 106.95 258.75 P16 17 1 265.60 107.58 295.55 P17 18 1 1387.40 115.55 509.62 P18 19 1 1086.00 128.37 294.25 P19 20 1 3559.20 132.32 575.72 P20 21 1 2902.90 134.15 569.97 P21 22 1 854.60 136.65 353.23 P22 23 1 1986.00 138.30 326.28 P23 24 1 2974.30 149.48 515.72 P24 ************************************************************************ part. orient Altura Sup Ancho Largo 1 1 16.70 300.80 18.80 16.00 2 1 8.80 152.80 6.70 22.80 3 1 20.30 19.50 9.30 2.10 4 1 7.40 84.20 21.60 3.90 5 1 27.30 61.10 14.90 4.10 6 1 25.80 299.30 23.20 12.90 7 1 14.50 148.70 22.20 6.70 8 1 3.50 376.40 24.60 15.30 9 1 20.40 20.50 20.50 1.00 10 1 23.30 91.10 6.80 13.40 11 1 26.30 20.00 4.00 5.00 12 1 12.80 123.90 5.90 21.00 13 1 28.40 333.50 21.80 15.30 Anexos 88 88 8 1 3.50 376.40 24.60 15.30 9 1 20.40 20.50 20.50 1.00 10 1 23.30 91.10 6.80 13.40 11 1 26.30 20.00 4.00 5.00 12 1 12.80 123.90 5.90 21.00 13 1 28.40 333.50 21.80 15.30 14 1 10.90 74.20 23.20 3.20 15 1 14.10 268.50 19.60 13.70 16 1 3.90 11.20 3.60 3.10 17 1 3.20 138.90 10.60 13.10 18 1 24.60 92.00 7.30 12.60 19 1 7.10 424.00 21.20 20.00 20 1 25.20 181.40 8.40 21.60 21 1 29.60 173.80 16.40 10.60 22 1 21.10 86.40 10.80 8.00 23 1 25.20 107.80 22.00 4.90 24 1 28.20 141.60 9.50 14.90 25 1 22.90 29.00 6.30 4.60 26 1 24.20 166.40 17.70 9.40 27 1 19.00 20.90 1.00 20.90 28 1 26.60 220.60 11.20 19.70 29 1 18.50 102.50 12.50 8.20 30 1 10.10 183.30 15.40 11.90 ********************************************************************************** mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 3 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 4 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 5 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 89 INSTANCIA I16_1O Número parts: 30 Número jobs máximo: 11 Número máquinas: 6 ***************************************************************************** Part # orient volumen FDisp FEntrega Nombre 1 1 1573.80 6.25 305.90 P1 2 1 421.30 7.35 282.18 P2 3 1 147.80 9.83 378.25 P3 4 1 285.20 20.95 214.67 P4 5 1 583.30 36.58 148.98 P5 6 1 3282.50 51.50 576.18 P6 7 1 1265.50 56.35 240.42 P7 8 1 723.30 69.90 211.63 P8 9 1 278.50 75.07 330.87 P9 10 1 1051.80 86.00 387.98 P10 11 1 201.90 93.03 447.13 P11 12 1 866.10 93.10 445.10 P12 13 1 7347.60 97.15 634.57 P13 14 1 333.60 97.25 177.55 P14 15 1 2956.00 101.75 355.30 P15 16 1 32.50 106.95 258.75 P16 17 1 265.60 107.58 295.55 P17 18 1 1387.40 115.55 509.62 P18 19 1 1086.00 128.37 294.25 P19 20 1 3559.20 132.32 575.72 P20 21 1 2902.90 134.15 569.97 P21 22 1 854.60 136.65 353.23 P22 23 1 1986.00 138.30 326.28 P23 24 1 2974.30 149.48 515.72 P24 25 1 408.20 164.08 525.87 P25 26 1 1271.40 167.45 362.63 P26 27 1 252.40 177.23 358.03 P27 28 1 3740.90 206.40 589.43 P28 29 1 991.90 219.62 560.93 P29 30 1 1377.60 228.55 653.97 P30 ************************************************************************ part. orient Altura Sup Ancho Largo 1 1 16.70 300.80 18.80 16.00 2 1 8.80 152.80 6.70 22.80 3 1 20.30 19.50 9.30 2.10 4 1 7.40 84.20 21.60 3.90 5 1 27.30 61.10 14.90 4.10 6 1 25.80 299.30 23.20 12.90 7 1 14.50 148.70 22.20 6.70 Anexos 90 90 8 1 3.50 376.40 24.60 15.30 9 1 20.40 20.50 20.50 1.00 10 1 23.30 91.10 6.80 13.40 11 1 26.30 20.00 4.00 5.00 12 1 12.80 123.90 5.90 21.00 13 1 28.40 333.50 21.80 15.30 14 1 10.90 74.20 23.20 3.20 15 1 14.10 268.50 19.60 13.70 16 1 3.90 11.20 3.60 3.10 17 1 3.20 138.90 10.60 13.10 18 1 24.60 92.00 7.30 12.60 19 1 7.10 424.00 21.20 20.00 20 1 25.20 181.40 8.40 21.60 21 1 29.60 173.80 16.40 10.60 22 1 21.10 86.40 10.80 8.00 23 1 25.20 107.80 22.00 4.90 24 1 28.20 141.60 9.50 14.90 25 1 22.90 29.00 6.30 4.60 26 1 24.20 166.40 17.70 9.40 27 1 19.00 20.90 1.00 20.90 28 1 26.60 220.60 11.20 19.70 29 1 18.50 102.50 12.50 8.20 30 1 10.10 183.30 15.40 11.90 ********************************************************************************** mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 3 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 4 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 5 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 6 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 91 INSTANCIA I17_1O Número parts: 30 Número jobs máximo: 13 Número máquinas: 7 ***************************************************************************** Part # orient volumen FDisp FEntrega Nombre 1 1 201.90 93.03 447.13 P11 2 1 866.10 93.10 445.10 P12 3 1 7347.60 97.15 634.57 P13 4 1 333.60 97.25 177.55 P14 5 1 2956.00 101.75 355.30 P15 6 1 32.50 106.95 258.75 P16 7 1 265.60 107.58 295.55 P17 8 1 1387.40 115.55 509.62 P18 9 1 1086.00 128.37 294.25 P19 10 1 3559.20 132.32 575.72 P20 11 1 2902.90 134.15 569.97 P21 12 1 854.60 136.65 353.23 P22 13 1 1986.00 138.30 326.28 P23 14 1 2974.30 149.48 515.72 P24 15 1 408.20 164.08 525.87 P25 16 1 1271.40 167.45 362.63 P26 17 1 252.40 177.23 358.03 P27 18 1 3740.90 206.40 589.43 P28 19 1 991.90 219.62 560.93 P29 20 1 1377.60 228.55 653.97 P30 21 1 11122.90 242.90 1177.72 P31 22 1 5234.10 244.87 739.32 P32 23 1 274.60 245.08 553.43 P33 24 1 2628.40 248.18 536.87 P34 25 1 206.90 258.98 524.58 P35 26 1 639.50 268.42 646.72 P36 27 1 431.50 279.77 691.40 P37 28 1 968.20 286.25 566.03 P38 29 1 95.00 290.73 335.78 P39 30 1 2306.20 294.53 473.53 P40 ************************************************************************ part. orient Altura Sup Ancho Largo 1 1 26.30 20.00 4.00 5.00 2 1 12.80 123.90 5.90 21.00 3 1 28.40 333.50 21.80 15.30 4 1 10.90 74.20 23.20 3.20 5 1 14.10 268.50 19.60 13.70 6 1 3.90 11.20 3.60 3.10 7 1 3.20 138.90 10.60 13.10 Anexos 92 92 8 1 24.60 92.00 7.30 12.60 9 1 7.10 424.00 21.20 20.00 10 1 25.20 181.40 8.40 21.60 11 1 29.60 173.80 16.40 10.60 12 1 21.10 86.40 10.80 8.00 13 1 25.20 107.80 22.00 4.90 14 1 28.20 141.60 9.50 14.90 15 1 22.90 29.00 6.30 4.60 16 1 24.20 166.40 17.70 9.40 17 1 19.00 20.90 1.00 20.90 18 1 26.60 220.60 11.20 19.70 19 1 18.50 102.50 12.50 8.20 20 1 10.10 183.30 15.40 11.90 21 1 24.50 592.90 24.50 24.20 22 1 30.60 273.70 23.00 11.90 23 1 3.10 145.50 14.70 9.90 24 1 18.90 257.50 17.40 14.80 25 1 11.20 40.60 1.70 23.90 26 1 4.60 202.80 19.50 10.40 27 1 23.40 41.30 2.60 15.90 28 1 7.50 253.50 13.70 18.50 29 1 12.70 11.50 8.20 1.40 30 1 22.70 178.80 14.30 12.50 ********************************************************************************** mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 3 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 4 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 5 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 6 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 7 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 93 INSTANCIA I18_1O Número parts: 30 Número jobs máximo: 12 Número máquinas: 8 ***************************************************************************** Part # orient volumen FDisp FEntrega Nombre 1 1 201.90 93.03 447.13 P11 2 1 866.10 93.10 445.10 P12 3 1 7347.60 97.15 634.57 P13 4 1 333.60 97.25 177.55 P14 5 1 2956.00 101.75 355.30 P15 6 1 32.50 106.95 258.75 P16 7 1 265.60 107.58 295.55 P17 8 1 1387.40 115.55 509.62 P18 9 1 1086.00 128.37 294.25 P19 10 1 3559.20 132.32 575.72 P20 11 1 2902.90 134.15 569.97 P21 12 1 854.60 136.65 353.23 P22 13 1 1986.00 138.30 326.28 P23 14 1 2974.30 149.48 515.72 P24 15 1 408.20 164.08 525.87 P25 16 1 1271.40 167.45 362.63 P26 17 1 252.40 177.23 358.03 P27 18 1 3740.90 206.40 589.43 P28 19 1 991.90 219.62 560.93 P29 20 1 1377.60 228.55 653.97 P30 21 1 11122.90 242.90 1177.72 P31 22 1 5234.10 244.87 739.32 P32 23 1 274.60 245.08 553.43 P33 24 1 2628.40 248.18 536.87 P34 25 1 206.90 258.98 524.58 P35 26 1 639.50 268.42 646.72 P36 27 1 431.50 279.77 691.40 P37 28 1 968.20 286.25 566.03 P38 29 1 95.00 290.73 335.78 P39 30 1 2306.20 294.53 473.53 P40 ************************************************************************ part. orient Altura Sup Ancho Largo 1 1 26.30 20.00 4.00 5.00 2 1 12.80 123.90 5.90 21.00 3 1 28.40 333.50 21.80 15.30 4 1 10.90 74.20 23.20 3.20 5 1 14.10 268.50 19.60 13.70 6 1 3.90 11.20 3.60 3.10 7 1 3.20 138.90 10.60 13.10 Anexos 94 94 8 1 24.60 92.00 7.30 12.60 9 1 7.10 424.00 21.20 20.00 10 1 25.20 181.40 8.40 21.60 11 1 29.60 173.80 16.40 10.60 12 1 21.10 86.40 10.80 8.00 13 1 25.20 107.80 22.00 4.90 14 1 28.20 141.60 9.50 14.90 15 1 22.90 29.00 6.30 4.60 16 1 24.20 166.40 17.70 9.40 17 1 19.00 20.90 1.00 20.90 18 1 26.60 220.60 11.20 19.70 19 1 18.50 102.50 12.50 8.20 20 1 10.10 183.30 15.40 11.90 21 1 24.50 592.90 24.50 24.20 22 1 30.60 273.70 23.00 11.90 23 1 3.10 145.50 14.70 9.90 24 1 18.90 257.50 17.40 14.80 25 1 11.20 40.60 1.70 23.90 26 1 4.60 202.80 19.50 10.40 27 1 23.40 41.30 2.60 15.90 28 1 7.50 253.50 13.70 18.50 29 1 12.70 11.50 8.20 1.40 30 1 22.70 178.80 14.30 12.50 ********************************************************************************** mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 3 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 4 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 5 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 6 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 7 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 8 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 95 INSTANCIA I19_1O Número parts: 40 Número jobs máximo: 15 Número máquinas: 11 ***************************************************************************** Part # orient volumen FDisp FEntrega Nombre 1 1 1573.80 6.25 305.90 P1 2 1 421.30 7.35 282.18 P2 3 1 147.80 9.83 378.25 P3 4 1 285.20 20.95 214.67 P4 5 1 583.30 36.58 148.98 P5 6 1 3282.50 51.50 576.18 P6 7 1 1265.50 56.35 240.42 P7 8 1 723.30 69.90 211.63 P8 9 1 278.50 75.07 330.87 P9 10 1 1051.80 86.00 387.98 P10 11 1 201.90 93.03 447.13 P11 12 1 866.10 93.10 445.10 P12 13 1 7347.60 97.15 634.57 P13 14 1 333.60 97.25 177.55 P14 15 1 2956.00 101.75 355.30 P15 16 1 32.50 106.95 258.75 P16 17 1 265.60 107.58 295.55 P17 18 1 1387.40 115.55 509.62 P18 19 1 1086.00 128.37 294.25 P19 20 1 3559.20 132.32 575.72 P20 21 1 2902.90 134.15 569.97 P21 22 1 854.60 136.65 353.23 P22 23 1 1986.00 138.30 326.28 P23 24 1 2974.30 149.48 515.72 P24 25 1 408.20 164.08 525.87 P25 26 1 1271.40 167.45 362.63 P26 27 1 252.40 177.23 358.03 P27 28 1 3740.90 206.40 589.43 P28 29 1 991.90 219.62 560.93 P29 30 1 1377.60 228.55 653.97 P30 31 1 11122.90 242.90 1177.72 P31 32 1 5234.10 244.87 739.32 P32 33 1 274.60 245.08 553.43 P33 34 1 2628.40 248.18 536.87 P34 35 1 206.90 258.98 524.58 P35 36 1 639.50 268.42 646.72 P36 37 1 431.50 279.77 691.40 P37 38 1 968.20 286.25 566.03 P38 39 1 95.00 290.73 335.78 P39 Anexos 96 96 40 1 2306.20 294.53 473.53 P40 ************************************************************************ part. orient Altura Sup Ancho Largo 1 1 16.70 300.80 18.80 16.00 2 1 8.80 152.80 6.70 22.80 3 1 20.30 19.50 9.30 2.10 4 1 7.40 84.20 21.60 3.90 5 1 27.30 61.10 14.90 4.10 6 1 25.80 299.30 23.20 12.90 7 1 14.50 148.70 22.20 6.70 8 1 3.50 376.40 24.60 15.30 9 1 20.40 20.50 20.50 1.00 10 1 23.30 91.10 6.80 13.40 11 1 26.30 20.00 4.00 5.00 12 1 12.80 123.90 5.90 21.00 13 1 28.40 333.50 21.80 15.30 14 1 10.90 74.20 23.20 3.20 15 1 14.10 268.50 19.60 13.70 16 1 3.90 11.20 3.60 3.10 17 1 3.20 138.90 10.60 13.10 18 1 24.60 92.00 7.30 12.60 19 1 7.10 424.00 21.20 20.00 20 1 25.20 181.40 8.40 21.60 21 1 29.60 173.80 16.40 10.60 22 1 21.10 86.40 10.80 8.00 23 1 25.20 107.80 22.00 4.90 24 1 28.20 141.60 9.50 14.90 25 1 22.90 29.00 6.30 4.60 26 1 24.20 166.40 17.70 9.40 27 1 19.00 20.90 1.00 20.90 28 1 26.60 220.60 11.20 19.70 29 1 18.50 102.50 12.50 8.20 30 1 10.10 183.30 15.40 11.90 31 1 24.50 592.90 24.50 24.20 32 1 30.60 273.70 23.00 11.90 33 1 3.10 145.50 14.70 9.90 34 1 18.90 257.50 17.40 14.80 35 1 11.20 40.60 1.70 23.90 36 1 4.60 202.80 19.50 10.40 37 1 23.40 41.30 2.60 15.90 38 1 7.50 253.50 13.70 18.50 39 1 12.70 11.50 8.20 1.40 40 1 22.70 178.80 14.30 12.50 ********************************************************************************** mach. TC (1/VT) MC HT SET HC MA MH ancho largo 1 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 2 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 3 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 97 4 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 5 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 6 60 32.40 2 1 2 2 625 32.50 25.00 25.00 M1 7 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 8 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 9 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 10 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2 11 60 32.40 2 1 1 2 625 32.50 25.00 25.00 M2