Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop

Equation Chapter 1 Section 1 Autor: Francisco Manuel Vallejo Gómez de Travecedo Tutor: Pedro Luis González Rodríguez Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Sevilla, 2024 Trabajo Fin de Máster Organización Industrial y Gestión de Empresas Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop iii Trabajo Fin de Máster Organización Industrial y Gestión de Empresas Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno jobshop Autor: Francisco Manuel Vallejo Gómez de Travecedo Tutor: Pedro Luis González Rodríguez Catedrático de Universidad Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2024 Trabajo Fin de Máster: Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop v Autor: Francisco Manuel Vallejo Gómez de Travecedo Tutor: Pedro Luis González Rodríguez El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2024 El Secretario del Tribunal vii ix Agradecimientos Quiero expresar mi más profundo agradecimiento a mis padres, quienes jamás se han rendido y siempre han dado lo mejor de sí para brindarnos, a mis hermanas y a mí, una excelente educación. Gracias a ellos, hemos podido estudiar lo que hemos deseado y en los lugares que hemos escogido. Nos han inculcado el valor del esfuerzo y el trabajo arduo, siempre recordándonos “Siembra hoy lo que recogerás mañana”. Hoy es ese mañana, y puedo decir con orgullo que sus enseñanzas han dado fruto. Me gustaría agradecer a Pedro por su amabilidad, simpatía, y constante disposición. Su motivación y apoyo han sido fundamentales para la elaboración de este Trabajo Fin de Máster. Su dedicación y buena voluntad han hecho de esta experiencia un camino más llevadero y enriquecedor. Francisco Manuel Vallejo Gómez de Travecedo Sevilla, 2024 2.4.1 Descripción del problema ................................................................................................................. 47 2.4.2 Clasificación de problemas según la subdivisión de lotes .............................................................. 49 2.4.3 Efectos de la subdivisión de lotes..................................................................................................... 50 2.4.4 Problemas revisados ......................................................................................................................... 52 2.4.5 Técnicas de optimización .................................................................................................................. 60 2.5 Conclusiones extraídas de la revisión de la literatura ............................................................................. 62 3 Modelado del problema ...................................................................................................................... 65 3.1 Descripción del problema ......................................................................................................................... 65 3.2 Hipótesis y función objetivo ...................................................................................................................... 66 3.3 Modelado ................................................................................................................................................... 67 3.3.1 Notación ............................................................................................................................................. 68 3.3.2 Modelo MILP ..................................................................................................................................... 69 3.4 Conclusiones del capítulo .......................................................................................................................... 71 4 Experimentación, validación y mejoras ................................................................................................ 73 4.1 Generación de instancias (datos del problema) ...................................................................................... 74 4.2 Caso genérico ............................................................................................................................................. 78 4.2.1 Instancia pequeña ............................................................................................................................. 78 4.2.2 Instancia mediana ............................................................................................................................. 80 4.2.3 Instancia grande ................................................................................................................................ 81 4.3 Heurística para mejora del programa de producción ............................................................................. 84 4.4 Tiempos de setup anticipatorios .............................................................................................................. 88 4.5 Limitaciones del MILP................................................................................................................................ 89 4.6 Conclusiones del capítulo .......................................................................................................................... 91 5 Conclusiones ........................................................................................................................................ 93 5.1 Conclusiones generales ............................................................................................................................. 93 5.2 Contribuciones del trabajo ........................................................................................................................ 94 5.3 Futuras líneas de investigación ................................................................................................................ 94 Referencias.................................................................................................................................................. 96 xvii ÍNDICE DE TABLAS Tabla 1. Notación αβγ básica para problemas JSP. 37 Tabla 2. Clasificación de problemas según las restricciones en el tamaño de los sublotes. 50 Tabla 3. Esquema de clasificación. 56 Tabla 4. Resumen bibliográfico del problema LSJSP. 59 Tabla 5. Parámetros de la instancia pequeña. 76 Tabla 6. Parámetros de la instancia mediana. 77 Tabla 7. Parámetros de la instancia grande. 78 xix ÍNDICE DE FIGURAS Figura 1. Load chart. Incluye medición de la productividad semanal y período de trabajo planeado. [Fuente: [8]]. 32 Figura 2. Progress chart. Incluye fechas de inicio, fechas de entrega y número de unidades producidas cada día. [Fuente: [10]] 32 Figura 3. Layout chart. Muestra la programación de las operaciones para trabajadores de forma individual o para máquinas. [Fuente: [10]]. 33 Figura 4. Evolución de la programación de operaciones en entornos de producción. [Fuente: [14]]. 35 Figura 5. Ejemplo esquemático de un job shop de 9 máquinas y 3 trabajos. [Fuente: elaboración propia]. 36 Figura 6. Ejemplo de diagrama de Gantt. Programación de operaciones en un job shop con 3 máquinas y 4 trabajos. [Fuente: [15]]. 36 Figura 7. Clasificación de tiempos de setup. [Fuente: elaboración propia]. 41 Figura 8. Número de artículos considerados en la revisión sistemática según el tipo de proceso productivo. [Fuente: [27]]. 47 Figura 9. Problema JSP: (a) sin subdivisión de lotes; y (b) con subdivisión de lotes. [Fuente: [20]]. 51 Figura 10. Comparación de sublotes con holguras y sin holguras y tamaños consistentes y variables en un job shop de 3 máquinas y 2 trabajos. [Fuente: [26]]. 52 Figura 11. Comparación de la programación de la producción en cada fase de la resolución. [Fuente: [33]]. 55 Figura 12. Variación del tamaño de sublotes para mejorar el makespan. [Fuente: [25] ] 55 Figura 13. Grafo disyuntivo aplicado a un job shop. [Fuente: [40]]. 67 Figura 14. Representación del makespan en un grafo disyuntivo. [Fuente: [40]]. 68 Figura 15. Programa de producción para instancia pequeña. Caso genérico. [Fuente: elaboración propia]. 79 Figura 16. Información detallada de un sublote. [Fuente: elaboración propia]. 79 Figura 17. Programa de producción para instancia mediana. Caso genérico. [Fuente: elaboración propia]. 80 Figura 18. Evolución del Makespan y MIP Gap para instancia mediana. Caso genérico. [Fuente: elaboración propia]. 81 xxi Figura 19. Programa de producción para instancia grande. Caso genérico. [Fuente: elaboración propia]. 82 Figura 20. Evolución del Makespan y MIP Gap para instancia grande. Caso genérico. [Fuente: elaboración propia]. 82 Figura 21. Programa de producción para instancia grande. Caso genérico. Reducción de número de lotes máximo. [Fuente: elaboración propia]. 83 Figura 22. Evolución del Makespan y MIP Gap para instancia grande. Caso genérico. Reducción de número de lotes máximo. [Fuente: elaboración propia]. 84 Figura 23. Diagrama de flujo de heurística para mejorar el programa de producción. [Fuente: elaboración propia]. 85 Figura 24. Programa de producción sin mejorar. Caso genérico. [Fuente: elaboración propia]. 86 Figura 25. Programa de producción con número de lotes minimizado. Caso genérico. [Fuente: elaboración propia]. 87 Figura 26. Programa de producción número de lotes minimizado y máximo adelanto. Caso genérico. [Fuente: elaboración propia]. 87 Figura 27. Programa de producción para instancia pequeña. Caso genérico. Demanda de 200 unidades. Setup no anticipatorio. [Fuente: elaboración propia]. 88 Figura 28. Programa de producción para instancia pequeña. Caso genérico. Demanda de 200 unidades. Setup anticipatorio. [Fuente: elaboración propia]. 89 23 1 INTRODUCCIÓN n este capítulo se expone el objetivo principal del proyecto, la forma en la que se aborda y las razones que justifican su elección. También se presenta un breve resumen de los capítulos en los que está estructurado el trabajo. 1.1 Contexto y justificación La programación de la producción está influenciada por las condiciones del mercado. En los últimos años la tendencia ha pasado de producción en masa de pocos tipos de productos a producción en masa de productos “customizados” y con un ciclo de vida más corto. Esto aplica a todas las industrias. Por ejemplo, en la industria química los productos se suelen adaptar a las condiciones que presentan los procesos de los clientes. En la industria de bienes de consumo, debido a la gran variedad de envases, la customización y etiquetado de estos y la gran variedad de sabores e ingredientes, la tendencia es más notable aún [1]. En la industria aeronáutica también se aprecia el cambio en la demanda de aviones. Sobre todo en la línea de negocio low-cost, las diferentes compañías piden la personalización del interior de la cabina, los asientos y su distribución, etc. Debido a la demanda de diversas customizaciones, la arquitectura de cada avión que se entrega al cliente es única, incluso si son aviones de la misma familia. Cualquier personalización en un único componente puede implicar modificaciones en los componentes conectados al primero. Además, clientes de todo el mundo establecen requisitos con relación al proceso productivo, como por ejemplo donde se fabrica el avión, donde se entrega y cuando se entrega [2]. Para satisfacer la demanda y los requisitos de los clientes, los sistemas de producción deben ser flexibles y eficientes. Hace algunos años, en el sector aeronáutico, las cadenas de suministro de los fabricantes estaban casi totalmente formadas e integradas por las propias multinacionales. La mayor parte de los componentes y piezas que conforman la aeronave eran fabricados por ellos mismos. Se tenían diferentes plantas, cada una E Introducción 24 24 especializada en una parte del avión y después se ensamblaban todas las partes en la línea final de montaje (Final Assembly Line o FAL). Esto último de momento no ha cambiado. En el caso de que no se pueda disponer de algún componente, este se pide a proveedores subcontratados. Con el cambio de paradigma del mercado, los grandes fabricantes han aumentado la subcontratación de proveedores ya que les permite más flexibilidad y enfocarse en otras actividades que aportan más valor y competitividad. En la actualidad las multinacionales del sector aeronáutico se dedican principalmente al diseño de piezas y diseño y ensamblaje de aeronaves, dejando la fabricación de componentes a empresas subcontratadas. Para facilitar la integración de la cadena de suministro, se crean grandes polígonos industriales situados cerca de las líneas de ensamblaje final. Así se disminuyen costes y tiempos de transporte y se aumentan los beneficios y la flexibilidad. En Sevilla, se encuentra la FAL del A400M, el avión de transporte más avanzado, probado, certificado y operativo, con las tecnologías más avanzadas del siglo XXI, indica Airbus [3]. Andalucía y más en concreto Sevilla está en la vanguardia de la industria aeronáutica. En el polígono Aerópolis, se encuentra el Parque Tecnológico Aeroespacial de Andalucía, donde hay instaladas más de 90 empresas aeroespaciales y tecnológicas [4]. Muchas de estas empresas presentan un entorno de fabricación tipo taller o job shop. En un job shop, cada trabajo pasa por una o más máquinas siguiendo una ruta única. Es decir, no todos los trabajos pasan en el mismo orden por las máquinas y no todos los trabajos pasan por todas las máquinas. En la revisión del estado del arte no se ha encontrado en la literatura científica ningún artículo que ofrezca y valide un modelo MILP sencillo y flexible para abordar el problema simultáneo de lotificación de trabajos (lot streaming) y programación de la producción en un job shop genérico con el objetivo de minimizar el intervalo de tiempo en el que se procesan la totalidad de los trabajos (makespan). En la mayoría de los artículos que tratan la lotificación y la programación de la producción, la lotificación está orientada a los costes y se consideran varias ventanas temporales. Estos artículos denotan el problema como Lot Sizing Problem. Son muy pocos los artículos que tratan el problema concreto de lotificación de trabajos en ventanas temporales continuas. Se denotan como lot sizing job shop scheduling problem y la mayoría abordan el problema en 2 25 25 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop fases (no integralmente). La minimización de costes de setup y costes de mantenimiento solo es apropiada cuando pueden ser determinados como costes out-of-pocket (que suponen un flujo de caja) directamente asignables a tipos de productos individuales. En la ausencia de costes reales, es más apropiado minimizar el makespan. Minimizando el makespan se liberan antes los recursos de producción (máquinas) de forma que se puede satisfacer más demanda [5]. Teniendo en cuenta el marco en el que se encuentra Sevilla en referencia a la industria aeronáutica, la cantidad de empresas subcontratadas por Airbus que fabrican piezas en entornos de tipo taller y la ausencia de literatura científica de este problema en concreto, se decide realizar este Trabajo de Fin de Máster. Se aborda el problema LSJSP (Lot Streaming Job Shop Scheduling Problem) para el entorno genérico job shop mediante el desarrollo de un modelo de Programación Lineal Entera Mixta y su posterior implementación en un solver, validación y análisis. 1.2 Objetivo El objetivo principal del presente trabajo es desarrollar un modelo de Programación Lineal Entera Mixta para resolver el problema integrado de lotificación de trabajos y programación de la producción en un entorno de fabricación tipo job shop genérico. El estudio de este problema se considera de gran utilidad por:  La aportación que supone al actual estado del arte y por su potencial posterior uso para desarrollar y validar métodos metaheurísticos que permitan la aplicabilidad del modelo en escenarios reales a gran escala.  Facilitar un modelo MILP flexible fácilmente adaptable a escenarios reales con restricciones específicas.  La validación y el análisis del rendimiento de un modelo MILP que trata este problema de forma íntegra, hallando la solución en una sola fase. Para alcanzar este objetivo general, se deben cumplir los siguientes objetivos específicos: 1. Revisión y análisis de la literatura científica para conocer el estado del arte de problemas de esta índole e identificar métodos, técnicas y enfoques que puedan ser útiles en la resolución de este problema mediante un modelo MILP. Estado del arte 32 32 Figura 1. Load chart. Incluye medición de la productividad semanal y período de trabajo planeado. [Fuente: [8]]. Para tener un mejor control del tiempo, Gantt elaboró una tabla similar (progress chart) en la que sí indicaba la fecha de inicio de cada actividad, las operaciones que se deben hacer para cada actividad y cuando se deben hacer y la fecha en la que las piezas producidas debían ser enviadas. Esta tabla es la que más se parece a los Gantt usados hoy en día, aunque a un nivel superior a la programación de talleres. Figura 2. Progress chart. Incluye fechas de inicio, fechas de entrega y número de unidades producidas cada día. [Fuente: [10]] Para el caso que se trata en este proyecto, la programación de entornos tipo taller (job shop), el gráfico más 33 33 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop relevante es el layout chart, tabla en la que se especifica cuando comienza un trabajo, quien lo realiza y cuánto tiempo tomará terminarlo. En el eje horizontal se representa cada recurso único (máquinas en el caso de un taller) y en el eje vertical el tiempo. Para cada trabajo, se representa con una línea horizontal fina la fecha de inicio y fin del trabajo, así como su duración. Con una línea horizontal gruesa se representa la cantidad de trabajo completado hasta la fecha. De esta manera se puede comparar la planificación (teórica) con la ejecución (real). Figura 3. Layout chart. Muestra la programación de las operaciones para trabajadores de forma individual o para máquinas. [Fuente: [10]]. Si se quiere profundizar más en el tema de las tablas de Gantt, Clark ofrece una revisión en profundidad de las tablas de Gantt en su libro “The Gantt Chart: A Working Tool of Management”. [11]. En general, muchas compañías implementaron en sus fábricas oficinas de planificación de la producción como sugería Taylor, en las que se desarrollaban programas de producción con los métodos que propuso Gantt. 2.1.2 Evolución, impacto y tendencia de la programación de la producción Las dos grandes revoluciones de la programación de la producción han sido 1. El desarrollo por parte de Henry L. Gantt de herramientas muy útiles para entender las complejas relaciones entre humanos, máquinas, pedidos, recursos y tiempo. 2. El desarrollo de la tecnología y más en concreto de la informática y la computación para recopilar, visualizar, procesar y compartir datos de forma rápida y sencilla, lo que ha mejorado todo tipo de procesos de toma de decisiones. El estudio, de forma científica, de la programación de operaciones comienza con un artículo de Johnson [12], que introduce un modelo de un flowshop de 2 máquinas. Este artículo es conocido como el inicio de la programación de operaciones como se conoce hoy en día y de la teoría clásica de la programación Estado del arte 34 34 (scheduling). Desde entonces, es un campo independiente de estudio dentro de la investigación operativa. Desde 1950 a 1970, la programación se modelaba como problemas de optimización combinatoria que se abordaban mediante algoritmos, incluyendo programación dinámica y programación entera. Más tarde estas técnicas se clasificaron como problemas NP-hard. Para encontrar soluciones cerca del óptimo de forma más eficiente, se cambió el foco a métodos aproximados, es decir, heurísticas iterativas y heurísticas constructivas. En 1977, ya se habían propuesto más de 100 heurísticas (Panwalkar and Iskander [13]). Desde la década de los 80, como resultado de la utilización de ordenadores de uso particular en fábricas, la programación se ha desarrollado a un ritmo vertiginoso. Se han desarrollado heurísticas, metaheurísticas, modelos de Inteligencia Artificial (IA), modelos matemáticos de programación y simulaciones. Los entornos de fabricación también han cambiado, ya no solo se habla de líneas (flowshop), líneas de máquinas paralelas (parallel-machines) o talleres (job shops). En la década de los 90 surgen nuevos entornos híbridos, células flexibles, sistemas flexibles, etc. En el año 2010 surgió el cloud manufacturing, que no es más que la fabricación de productos tal y como la conocemos pero haciendo uso de la nube para alojar toda la información y todo el software que forma parte del proceso de fabricación. De esta manera la cadena de suministro es mucho más flexible, ya que todos los nodos pueden acceder a la información. También hace más fácil la customización, ya que las órdenes que emiten los clientes se reciben instantáneamente, lo cual permite ahorrar tiempo y planificar mejor la producción. En los últimos 5 años, se empieza a hablar de edge-cloud collaboration manufacturing. El desarrollo del internet de las cosas (IoT), la descentralización de los recursos y el crecimiento exponencial del número de datos con el que se trabaja puede dar lugar a congestión en la red, problemas de latencia, baja calidad del servicio, problemas de ciberseguridad, etc. [14]. Para ello se propone este enfoque, en el que se aprovechan las ventajas de la supercomputación y la capacidad de optimización a escala global que permite la nube junto con la rápida velocidad de respuesta, la alta calidad de servicio y la seguridad de los datos, en local en la misma fábrica. 35 35 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop Figura 4. Evolución de la programación de operaciones en entornos de producción. [Fuente: [14]]. Como se puede observar, la programación de operaciones es una parte muy importante en la optimización de sistemas de producción que se ha ido desarrollando continuamente desde la mitad del siglo XX. Este desarrollo se ha visto siempre influenciado por los avances en tecnología y por las condiciones del mercado, que presentan cambios en la demanda y en los modelos de producción. Con el cambio de paradigma en la industria, de Industria 3.0 a Industria 4.0, se busca con la programación de la producción la capacidad de producir productos personalizados de forma eficiente, como si fuesen productos de una línea. 2.2 Job Shop Scheduling Problem (JSP) En el presente trabajo se va a explicar en qué consiste un entorno tipo taller y que características básicas presenta. Cabe decir que en la literatura también se le denota como JSSP pero aquí nos referiremos a este problema como JSP. 2.2.1 Problema genérico Un entorno de fabricación job shop genérico puede ser descrito de la siguiente manera: en un entorno con varias máquinas 𝑀 ={𝑀,𝑀,…,𝑀}, hay un número de trabajos 𝐽 = {𝐽,𝐽,…,𝐽,…,𝐽}. Cada trabajo 𝐽 contiene una serie de operaciones 𝑂 ={𝑂,𝑂,…,𝑂,…,𝑂} que deben ser ejecutadas siguiendo una secuencia determinada (𝑛 es el número de máquinas por las que pasa cada trabajo). A cada operación se le asigna una máquina 𝑀 y un tiempo de operación 𝑝. En la versión más clásica del problema de programación de operaciones en un job shop, el objetivo es secuenciar todas las operaciones de todos los trabajos en todas las máquinas para minimizar el tiempo para el que se completan todas las operaciones. Este tiempo se conoce como makespan., aunque otros objetivos son posibles, como la minización del tiempo de flujo o la minimización de los tiempos de retraso de los productos, Estado del arte 36 36 en el caso de existencia de fechas de entrega (ver el resumen de métricas de rendimiento en la Tabla 1). En la Figura 5 se muestra un esquema de un posible entorno job shop con 9 máquinas y 3 trabajos. Cada trabajo sigue una ruta diferente, es decir, pasa por máquinas diferentes en un orden diferente. El trabajo 1 pasa por las máquinas 1, 5, 4, 7 y 6. El trabajo 2 empieza en la máquina 3 y pasa a continuación por 1, 4, 5, 2, 6, y 9. El trabajo 3 pasa por las máquinas 8, 9, 6, 3, 2, y 1. Todos los trabajos pasan exactamente en ese orden, siguen esa ruta establecida. Figura 5. Ejemplo esquemático de un job shop de 9 máquinas y 3 trabajos. [Fuente: elaboración propia]. En la Figura 6 se puede ver un diagrama de Gantt en el que se representa la solución de un problema (no hace referencia al problema representado en el esquema anterior) de esta índole. Figura 6. Ejemplo de diagrama de Gantt. Programación de operaciones en un job shop con 3 máquinas y 4 trabajos. [Fuente: [15]]. El problema clásico, conocido en inglés como Job Shop Scheduling Problem comenzó a estudiarse a mediados del siglo XX. En 1956 se estudió este problema con 2 trabajos y 4 máquinas (2 x 4 JSP)[16]. En 1959 37 37 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop Bowman presentó un 3 x 4 JSP [17] y Sisson [18] le dio por primera vez el nombre de job shop a este entorno. Desde entonces en las últimas 6 décadas se ha publicado una gran cantidad de artículos relacionados con programación de operaciones en este tipo de entorno [19]. 2.2.2 Caracterización del entorno En la literatura se pueden clasificar los problemas JSP y sus derivados a partir de ciertas características. Una notación ampliamente aceptada para describir problemas de programación de la producción es α|β|γ donde: - 𝛂 describe características de las máquinas. - 𝛃 describe características de los trabajos y los tiempos y restricciones asociados. - 𝛄 indica el objetivo para evaluar la solución. Para el problema JSP y sus variantes, se resumen en la Tabla 1 algunas características y restricciones. Cabe decir que en la literatura se encuentran problemas complejos que incluyen muchas más características y restricciones. Estas que se exponen son las más básicas. Los términos y conceptos se explican más adelante en este capítulo. Tabla 1. Notación α|β|γ básica para problemas JSP. CARACTERÍSTICAS DE LAS MÁQUINAS [ 𝜶 ] J Job Shop FJ Flexible Jop Shop AJ Assembly Job Shop CARACTERÍSTICAS DE LOS TRABAJOS [ 𝜷 ] Tipos de interrupción No reanudable (Non-resumable) 𝑝𝑚𝑡𝑛 − 𝑛𝑜𝑛 − 𝑟𝑒𝑠𝑢𝑚𝑎𝑏𝑙𝑒 Semireanudable (Semi-resumable) 𝑝𝑚𝑡𝑛 − 𝑠𝑒𝑚𝑖 − 𝑟𝑒𝑠𝑢𝑚𝑎𝑏𝑙𝑒 Reanudable (Resumable) 𝑝𝑚𝑡𝑛 − 𝑟𝑒𝑠𝑢𝑚𝑎𝑏𝑙𝑒 Fechas de llegada/entrega Fecha de llegada (Release date) 𝑟  Fecha de entrega (Due date) 𝑑  Fecha de entrega común (Common due date) 𝑑  = 𝑑 Lotes (Batching) Procesar 𝑏 trabajos 𝑏𝑎𝑡𝑐 ℎ ( 𝑏 ) En paralelo (Parallel batching): el tiempo de proceso es el mayor de los trabajos de dicho lote 𝑝 − 𝑏𝑎𝑡𝑐 ℎ ( 𝑏 ) En serie (Serial batching): el tiempo de proceso es la suma de los tiempos de los trabajos de dicho lote 𝑠 − 𝑏𝑎𝑡𝑐 ℎ ( 𝑏 ) Tiempos de setup Estado del arte 38 38 Independientes de la secuencia (máquina i, trabajo j) 𝑠  Dependiente de la secuencia ( máquina i, trabajo j después de trabajo k) 𝑠  MÉTRICAS DE RENDIMIENTO (Referidas al trabajo j) Tiempo de terminación (Completion time) 𝐶  Tiempo de flujo (Flow time) 𝐹  = 𝐶  − 𝑟  Retraso (lateness) 𝐿  = 𝐶  − 𝑑  Tardana (Tardiness) 𝑇  = max ( 0 , 𝐿  ) Adelanto (Earliness) 𝐸  = max ( 0 , − 𝐿  ) Llegada tarde (Tardy job) 𝑈  = 1 𝑠𝑖 𝑇  > 0 𝑈  = 0 𝑒𝑛 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜 OBJETIVOS (BASADOS EN MÉTRICAS) [ 𝛾 ] 𝛾 = 𝑓 → 𝑀𝑖𝑛 𝑓 Tipo max form Makespan 𝐶  = 𝑚 á 𝑥 𝐶  Maximum flowtime 𝑚 á 𝑥 𝐹  En general cualquier maximización de una métrica Tipo sum form Total Completion Time  𝐶      Total Flowtime  𝐹      En general cualquier sumatorio de una métrica Con el fin de explicar y dar a comprender un poco mejor la caracterización de los problemas, se tratan con más detalle la caracterización de trabajos y máquinas y la clasificación de tiempos de setup, objetivos, lotificación y restricciones. 2.2.2.1 Trabajo Se consideran los atributos más significativos de un trabajo:  Fecha de llegada (Release time): tiempo más temprano en el que el trabajo puede comenzar.  Fecha de entrega (Due date): tiempo más tardío en el que el trabajo debe acabar.  Tipo de ruta: parcial si hay uno o más trabajos que no tienen que pasar por todas las máquinas.  Tiempo de proceso (Processing time): tiempo que tarda en procesarse un trabajo. Para el problema 39 39 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop JSP hay que especificar el tiempo de procesamiento de cada trabajo en cada máquina.  Tiempo de setup (Setup time): tiempo que tarda en hacerse el setup previo al comienzo del trabajo. Los tiempos de setup pueden estar asociados a los trabajos o no. La clasificación se presenta 23más adelante.  Tipos de interrupción (preempetion): indica si se puede interrumpir el procesamiento de un trabajo y en el caso de que esto suceda si se puede continuar más tarde la operación sin perder el trabajo hecho, si se pierde una parte o si se pierde todo. 2.2.2.2 Máquina En el problema clásico las máquinas no presentan ningún atributo, más allá de la disposición que presentan. Sin embargo, conforme el estado del arte se ha ido desarrollando han ido surgiendo atributos asociables a máquinas. Algunos son:  Funcionalidad de la máquina: unifuncional si solo puede procesar un tipo de operación o multifuncional si puede procesar más de un tipo de operación.  Disponibilidad: indica si la máquina siempre está disponible o puede presentar paradas por mantenimiento o fallos. También se consideran en algunos casos la congestión inicial de las máquinas.  Consumo de energía y emisiones de carbono. 2.2.2.3 Objetivos El fin último de la programación de la producción es optimizar un objetivo. Bien puede ser minimizándolo, como en el caso del makespan o maximizándolo, como en el caso de aumentar la productividad de las máquinas. Los objetivos se pueden clasificar en 5 tipos: 1. Basados en tiempo. Por ejemplo en el makespan, en la fecha de entrega, en los retrasos, etc. 2. Basados en el número de trabajos. Por ejemplo en el número de trabajos en proceso, en stock o retrasados (no cumplen la fecha de entrega). 3. Basados en el coste. Por ejemplo en el coste de producción o el coste logístico. 4. Basados en los beneficios. 5. Basados en el consumo de energía y el impacto medioambiental. Estos últimos solo son comunes en la literatura más reciente. 2.2.2.4 Tiempos de Setup En la literatura revisada, los tiempos de setup se clasifican principalmente según 3 cuestiones: Estado del arte 40 40 1. El elemento del entorno con el que se asocian. a. Asociados a trabajos. Cada trabajo tiene un tiempo de setup asignado para cada máquina. b. Asociados a máquinas. Cada máquina tiene un tiempo de setup determinado. c. Asociado a operaciones. El tiempo de setup depende de la operación que se realice (y en algunos casos en qué máquina se realice). En la literatura inglesa se conocen como fixture setup times. Se refieren a la duración necesaria para preparar o configurar accesorios utilizados para sostener, soportar, posicionar o elaborar piezas de trabajo durante procesos de fabricación, prueba o ensamblaje. 2. Si dependen o no de la secuencia de operaciones de cada trabajo. a. Independientes de la secuencia. Siempre que un trabajo comienza una operación se considera el tiempo de setup correspondiente. b. Dependientes de la secuencia. El tiempo de setup de cada trabajo en cada máquina dependerá del trabajo que lo precede o de la operación que se ha realizado justo antes de la que se va a realizar. 3. Si la operación de setup se puede ejecutar antes de que el trabajo o lote correspondiente esté disponible para ser procesado en la máquina. Será anticipatorio en el caso de que se pueda y no anticipatorio en caso contrario. Para el caso anticipatorio, Chan, Wong et al [20] exponen que este tipo de setups puede aumentar el tiempo total de la planificación. Por ejemplo, se hace un setup anticipatorio para un producto 1 en la máquina 1 pero este no llega a tiempo. Puede darse el caso de que tras programar de nuevo la producción se quiera procesar un producto 2, para lo que habría que hacer de nuevo un setup. 41 41 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop Figura 7. Clasificación de tiempos de setup. [Fuente: elaboración propia]. 2.2.2.5 Lotificación Considerando un trabajo como una cantidad de unidades a producir, lotificar consiste en separar esa cantidad en diferentes lotes. En cuanto a cómo se van a tratar los lotes en las máquinas, se puede distinguir entre:  Producción en paralelo: todos los lotes se procesan en paralelo (atendiendo a la capacidad de las máquinas). En el caso de que las máquinas en paralelo sean idénticas, el tiempo de proceso será el del lote más grande.  Producción en serie: los lotes se procesan en serie. El tiempo de proceso será la suma de los tiempos de proceso asignados a cada lote. Existen muchas políticas para hacer la lotificación y para dividir los lotes en lotes más pequeños. Como es una rama bastante amplia de la programación de la producción, se hace una revisión y clasificación más detallada en el apartado 2.3. 2.2.2.6 Restricciones Las restricciones se pueden considerar como una característica del entorno, las cuales pueden darse de manera simultánea y siendo su tipología muy diversa. En la literatura se estudian problemas que suelen incluir restricciones de capacidad o tiempo.  Restricciones de capacidad. Se refieren al número de elementos que se pueden procesar o transportar Estado del arte 48 48 El problema consiste en responder de forma conjunta a estas tres preguntas. Es decir, resolver la subdivisión de los lotes y la programación de la producción a la vez. Una solución óptima del problema consiste en determinar una programación factible de las operaciones a realizar teniendo en cuenta la subdivisión de lotes en el mínimo tiempo de finalización. Por lo tanto, junto con la programación de operaciones se determina:  El número de sublotes para cada trabajo j (considerando que todas las unidades a producir del trabajo j componen un lote).  El tamaño de cada sublote. En la literatura inglesa, los artículos referidos a este problema se denotan como lot streaming job shop scheduling problema o LSJSP. Buscando por los términos “lot size” y “lot sizing” seguido de “scheduling” y/o “job shop” no se han encontrado artículos que traten este problema. Se usan los términos “lot streaming” o “lot splitting” para referirse a la división de lotes en sublotes. Estos términos se refieren a dividir un lote cuyo tamaño conocemos en varios sublotes, mientras que los términos referidos al tamaño del lote, “lot size” y “lot sizing”, se refieren a determinar el tamaño del lote. Realmente, el concepto en sí es el mismo, ya que tanto un lote como un sublote son un grupo de productos. Por lo tanto hay que entender, que aunque todos estos términos significan lo mismo, existe una diferencia crucial cuando se emplean en la jerga de los procesos productivos:  “Lot sizing” se refiere a determinar el tamaño óptimo de un lote con el objetivo de equilbrar los costes de producción (inventario, configuración, etc).  “Lot streaming” se refiere a dividir un lote grande en lotes más pequeños para que puedan ser procesados en diferentes máquinas o estaciones en paralelo con el objetivo de minimizar tiempos (con tiempos nos referimos a tiempo de terminación, tiempos de espera, tardanzas, etc). Se asume que los sublotes siguen la misma secuencia que el lote padre. En la Figura 9 se puede ver a través de un ejemplo particular (de las muchas opciones existentes) la diferencia entre la programación de la producción en un job shop sin considerar sublotes y considerándolos. En la actualidad el tiempo juega un papel fundamental para las empresas. La sociedad actual quiere servicios y productos de forma inmediata. Ser el más rápido y reducir los tiempos de logística y producción es fundamental para quedarse con un trozo del pastel. Varias empresas de primer nivel más respetadas y 49 49 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop reconocidas han implementado esta política de producción para reducir el tiempo de espera (lead time) de los procesos y mejorar el servicio al cliente [28]. 2.4.2 Clasificación de problemas según la subdivisión de lotes En la literatura se proponen diferentes formas de clasificar los problemas según las restricciones que se apliquen a la subdivisión de lotes. Chan, Wong et al [20] proponen 4 tipos de enfoques: 1. Sublotes idénticos sin holguras: el lote se divide en sublotes de igual tamaño y estos deben procesarse en la misma máquina de forma continuada, sin procesar otras operaciones entre ellos. 2. Sublotes idénticos con holguras: el lote se divide en sublotes de igual tamaño y se permite realizar otras operaciones entre sublotes del mismo lote padre en la misma máquina. 3. Sublotes variables sin holguras: el lote se puede dividir en sublotes de diferente tamaño y estos deben procesarse en la misma máquina de forma continuada, sin procesar otras operaciones entre ellos. 4. Sublotes variables con holguras: el lote se puede dividir en sublotes de diferente tamaño y se permite realizar otras operaciones entre sublotes del mismo lote padre en la misma máquina. Las holguras, dicho de otro modo, significan permitir que la secuencia de sublotes del trabajo 𝑗 sea interrumpida por sublotes del trabajo 𝑘, siendo 𝑘 ≠𝑗. Por otro lado, Lei y Guo [29] proponen una clasificación que tiene en cuenta también la variación de tamaño de los lotes en las distintas estaciones o máquinas por las que pasan. Por lo tanto, se tienen 3 tipos de tamaños: a) Tamaños iguales cuando todos los sublotes de un producto tienen el mismo tamaño. b) Tamaños consistentes en el caso de que el tamaño de los sublotes de un producto sea diferente para cada sublote pero no se altera el tamaño de estos cuando se cambia de estación. c) Tamaño variable en el caso de que no haya ninguna restricción en el tamaño de los sublotes. Es decir, cada sublote puede tener un tamaño diferente y variar cuando cambia de estación. En la Tabla 2 se exponen los 6 tipos de problemas que se obtienen combinando ambas clasificaciones. TAMAÑO DE LOS LOTES HOLGURAS Tipo 1 Igual No permitidas Tipo 2 Igual Permitidas Tipo 3 Consistente No permitidas Tipo 4 Consistente Permitidas Tipo 5 Variable No permitidas Estado del arte 50 50 Tipo 6 Variable Permitidas Tabla 2. Clasificación de problemas según las restricciones en el tamaño de los sublotes. 2.4.3 Efectos de la subdivisión de lotes En un JSP clásico, el tiempo de procesado de un conjunto de trabajos idénticos es el resultado de la suma de tiempos individuales. Procesar todos los productos de manera continuada, en un único lote, supone perder la opción de 1. Intercalar la producción con otros conjuntos de productos. 2. Procesar en paralelo en distintas máquinas trabajos idénticos de un mismo conjunto. Si se pudieran implementar estas características en un JSP, se conseguiría reducir el tiempo en el que los primeros lotes de cada conjunto de trabajos idénticos acaban su procesado completo. El resultado sería una mayor disponibilidad para satisfacer la demanda. Como se ha explicado en el inicio del apartado 2.4, con la subdivisión de lotes se busca dividir un lote en varios sublotes de forma que dos sublotes de un mismo trabajo pueden ser procesados simultáneamente. Este solapamiento de operaciones de un mismo trabajo puede reducir el tiempo de terminación de los trabajos, la cantidad de trabajos que se están procesando (WIP o work in progress), el tiempo de flujo, etc. [30]. Cuando se subdividen los lotes, lo lógico es que, según aumente el número de sublotes, los costes de transporte entre estaciones y los costes de setup aumenten y que los costes de inventario disminuyan [30]. Si no se tienen tiempos de setup, siempre será óptimo considerar el número máximo de sublotes posible. El problema sería resolver la programación de la producción. Como cada sublote se trata como un trabajo independiente, el espacio de soluciones posibles crece significativamente. Lo mismo sucede evidentemente si crece el número de trabajos [31]. Si se tienen tiempos de setup (que es lo común), hay un compromiso entre el tiempo que se ahorra dividiendo los lotes y el tiempo extra que supone hacer más setups. [31]. La Figura 9 tomada de [20] muestra un ejemplo de la mejora que supone la subdivisión de lotes en el tiempo de terminación. 51 51 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop Figura 9. Problema JSP: (a) sin subdivisión de lotes; y (b) con subdivisión de lotes. [Fuente: [20]]. Considerar tamaños variables y permitir holguras en la programación del flujo de lotes puede aportar más beneficios prácticos a los entornos industriales reales, en particular cuando el sistema está dotado de una mayor flexibilidad de fabricación [26]. En la Figura 10 se compara el efecto que tiene permitir o no permitir holguras (intermingling) y considerar tamaños consistentes y variables en el makespan. El tiempo de terminación disminuye en los casos en los que se permiten holguras y en los casos en los que el tamaño es variable. Si se dan ambas condiciones, la mejora es aún mayor. Estado del arte 52 52 Figura 10. Comparación de sublotes con holguras y sin holguras y tamaños consistentes y variables en un job shop de 3 máquinas y 2 trabajos. [Fuente: [26]]. Sin embargo, en el caso de assembly job shops considerar tamaños iguales para todos los sublotes es más favorable que considerar tamaños consistentes o variables. Esto se debe a que la entrega del producto final depende de completar los lotes que componen la misma lista de materiales (BOM). Este efecto fue analizado por Chan, Wong et al [32]. 2.4.4 Problemas revisados En la literatura son escasos los artículos que tratan el problema LSJSP. Además, como se ha visto en la sección 2.2, existen multitud de parámetros que caracterizan el problema. Aun considerando muchos de ellos, en casos reales podemos encontrar muchos más. Esto genera un amplio abanico de problemas. Los entornos de producción son cada vez más complejos y flexibles. De igual manera aumenta la complejidad de los problemas y su resolución. Se han revisado 15 artículos que tratan exclusivamente un problema LSJSP, LSFJSP (flexible job shop) o LSAJSP (assembly job shop). Como hay muy pocos artículos publicados que tratan este tema, se ha hecho una revisión bibliográfica de los últimos 30 años. Aunque los artículos publicados en la década de los 90 presentan técnicas de optimización desactualizadas, ofrecen una base muy buena sobre la que se desarrollan algunos artículos más recientes. La subdivisión de lotes (lot streaming) es objeto de estudio desde hace más de 30 años, aunque su estudio sigue estando vigente debido a la complejidad que presenta el problema, tanto en el modelado como en la optimización. Normalmente se estudia de manera conjunta con entornos de producción flow shop y job shop. 53 53 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop En la mayoría de los casos se formula el problema con tamaño de sublotes igual o consistente. El problema más complejo en el que se considera el tamaño de los sublotes variables se estudian con menos frecuencia (ver [33] que aborda el FJS y [26] en el que se trata el JS. Debido a requisitos prácticos y pragmáticos, a la formulación del problema genérico se suelen añadir extensiones. Se tienen en cuenta más aspectos del proceso productivo. Low, Hsu et al [30] establecen como objetivo la minimización del makespan pero tienen en cuenta costes de producción, manipulación, inventario y setup. Liu [34] enfoca el modelo a órdenes de clientes, por lo que le da importancia al retraso de los trabajos y al tiempo de flujo de los productos terminados. Chan, Wong et al [20] incluyen un índice de congestión del sistema para aproximar la congestión inicial de las máquinas. Defersha y Chen [22] tienen en cuenta que algunas operaciones no se pueden comenzar hasta que no haya pasado un tiempo suficiente tras terminar la operación predecesora. Por ejemplo, el secado de una pieza después de una operación de pintura o esperar a que se enfríe si se ha sometido a un tratamiento térmico. Lei y Guo [29] tienen en cuenta el transporte entre estaciones y la transferencia de los sublotes entre diferentes máquinas. Bozèk y Werner [33] también tienen en cuenta tiempos de transporte. Estas extensiones no solo se limitan a tiempos, capacidad y costes. Novas [35] tiene en cuenta diferentes políticas operacionales para realizar la programación de la producción. Es común encontrar artículos en los que se resuelve el problema en dos fases. La mayoría resuelven primero el problema del lot streaming y después resuelven la programación de la producción. Solo hay un caso en el que se hace en orden inverso [33]. Primero se resuelve la programación considerando el menor tamaño posible para todos los sublotes, con el objetivo de minimizar el makespan. En una segunda fase se maximiza el tamaño de los lotes y se maximiza el número de operaciones indivisibles. En la Figura 11 se puede ver la evolución de la solución para una instancia siguiendo este enfoque. Cada rectángulo representa un sublote. S es la suma del tamaño de los sublotes y N es el número de sublotes. Dentro de cada rectángulo se denota entre paréntesis el trabajo y la operación. En las programaciones C y D, las operaciones indivisibles se indican con estrellas y para el resto se indica el ratio de maximización de los lotes, comparando con la programación B. Para este enfoque, los tiempos computacionales son extremadamente altos, llegando a superar las 5 horas para cada fase. Estado del arte 54 54 55 55 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop Figura 11. Comparación de la programación de la producción en cada fase de la resolución. [Fuente: [33]]. En problemas en los que se resuelve primero la lotificación y después la programación de la producción, es común que para la segunda fase se fije el tamaño del lote. De esta forma se simplifica la programación de la producción y a efectos prácticos es igual que programar un job shop genérico. Buscher y Shen [25] siguen esta estructura de resolución en su algoritmo de búsqueda tabú y añaden una fase más. En la tercera fase, con la programación de la producción ya hecha, varían el tamaño de los sublotes para mejorar la solución. Para ello, implementan un algoritmo al que llaman SVP. El efecto se puede ver en la Figura 12. En la figura en la parte superior se tiene la programación sin aplicar el SVP. En la figura inferior con la mejora tras aplicar el SVP. Figura 12. Variación del tamaño de sublotes para mejorar el makespan. [Fuente: [25] ] En el siguiente apartado se explica cuáles son las técnicas de optimización que se usan en la resolución de estos problemas. Con el fin de exponer toda la información recopilada de forma más clara y visual y clasificar los artículos revisados, se ha elaborado la Tabla 4 atendiendo a las características que se han considerado más relevantes para la caracterización del problema. Estado del arte 56 56 En primer lugar, es conveniente definir estas características:  Entorno. Se distingue entre job shop (JS), job shop flexible (FJS) y job shop de montaje (AJS). Han sido ya explicados en el apartado 2.2.3. Corresponde a la 𝛂 de la notación propuesta en 2.2.2.  Objetivo para evaluar la solución. Corresponde a la γ de la notación propuesta en 2.2.2.  Número de pasos de la resolución. En algunos casos se resuelve la subdivisión de lotes y la programación de la producción en 2 niveles diferentes.  Pasos de la resolución. Se indica que se resuelve en cada paso.  Número de lotes. Se indica si está fijado o es variable.  Tamaño de los sublotes. Indica si son fijos, iguales, consistentes o variables.  Método de resolución. Indica la técnica de optimización que se ha usado.  Capacidad.  Fechas de entrega.  Tiempo de setup. o Permitido con antelación. o Dependencia. o Elemento con el que se asocia. Tabla 3. Esquema de clasificación. Descripción Atributo Valor potencial Acrónimo α Entorno Job shop JS Job shop flexible FJS Job shop de montaje AJS γ Objetivo min {métrica} Makespan Cmax Retraso Tmax Tiempo de flujo de bienes acabados fgFc Coste total oc:[Ci] [Ci] Costes incluibles Coste de holding hc Coste de inventario ic Coste de setup sc Coste del backlog Bc Coste de producción pc max {métrica} Operaciones indivisibles nso Nps Número de pasos en Número entero 57 57 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop resolución Ps Pasos en la resolución Subdivisión de lotes ls Programación de operaciones sch Transporte de productos trs Otros o Ln Número de sublotes Fijo F Variable V Ls Tamaño de sublotes Igual Eq Consistente Ct Variable Vb To Técnica de optimización Heurística H Programación lineal LP Programación entera MIP Programación entera lineal mixta MILP Programación con restricciones CP Algoritmo genético GA Algoritmo genético híbrido HGA Algoritmo genético paralelo PGA Reglas de despacho simple SDR Búsqueda tabú TS Algoritmo colonia de abejas artificiales modificado MABC Algoritmo Jaya multiobjetivo MOJA Metaheurística híbrida HMH:{técnicas} Cp Capacidad Considerada Si No considerada No Dd Fecha de entrega Considerada Si No considerada No St Tiempos de setup {Ad}:{D}:{As} {Ad} Permitido con antelación Si Aad No NAad {D} Dependencia Independiente de la secuencia Si Dependiente de la secuencia Sd Dependiente de la configuración previa de la máquina Fd {As} Elemento con el que se asocia Trabajo Job Máquina m Operación o Estado del arte 64 64 65 3 MODELADO DEL PROBLEMA En el presente capítulo se explica en detalle el modelado del problema. En el apartado 3.1 se describe el problema haciendo referencia al marco teórico que se dio en el capítulo anterior y que es aplicable para el problema genérico. En el apartado 3.2 se detallan las hipótesis que se han hecho y complementan el apartado anterior. Con estas consideraciones se facilita información del entorno de producción y se desgranan las limitaciones con las que se modela el problema. Por último, en el apartado 3.3 se muestra el modelado del problema. Se indica la notación usada y se presenta el modelo base que se ha modificado para abordar el problema. El modelo base, conocido como disjunctive model o modelo disyuntivo es el modelo genérico para entornos job shop más eficiente en términos de computación. En el subapartado 3.3.2 se muestra el modelo y se explican en detalle todas las restricciones de este. 3.1 Descripción del problema En el subapartado 2.4.1 se describe el problema genérico de programación de la producción considerando la sublotificación de los trabajos. La descripción es válida y aplica al problema concreto tratado aquí. Se considera el escenario donde trabajos, que son entendidos como lotes, compuestos por varios ítems discretos e idénticos deben ser procesados en varias máquinas configuradas en un entorno tipo taller o job shop. En vez de transferir, de una máquina a otra, el lote completo después de que todos los ítems hayan sido procesados, se considera transferir los ítems del lote en lotes más pequeños (sublotes), de forma que se puedan procesar ítems pertenecientes al mismo lote el paralelo. Más en concreto, se trata el problema con lotes de tamaño consistente y permitiendo holguras. Es decir, se pueden procesar sublotes de un trabajo distinto entre 2 sublotes del mismo trabajo. Las rutas de los trabajos Modelado del problema 66 66 son parciales. Esto significa que un trabajo puede tener una ruta que no contiene todas las máquinas. Además, se consideran tiempos de setup independientes de la secuencia. 3.2 Hipótesis y función objetivo Se consideran las siguientes hipótesis en el modelado del problema:  Cada trabajo j con una ruta parcial asignada 𝑅 se considera un lote.  En cada ruta parcial 𝑅 cada máquina 𝑚 no puede repetirse. Es decir, un trabajo 𝑗 no puede pasar dos veces por la misma máquina 𝑚.  Todos los lotes están disponibles en el instante inicial.  Todas las máquinas están disponibles en el instante inicial.  Se permiten holguras entre sublotes de diferentes trabajos (intermingling).  No se permiten interrupciones (preemption) en el procesado de sublotes. Es decir, una vez que un lote ha empezado a procesarse debe terminarse sin interrupciones.  Los tiempos de transferencia de los sublotes entre máquinas se consideran despreciables e iguales a 0.  Los tiempos de setup considerados son independientes de la secuencia.  Las máquinas no pueden procesar más de un sublote a la vez.  El buffer para el trabajo en proceso es ilimitado. Es decir, se considera que el sistema de producción tiene capacidad infinita.  No se consideran inventarios iniciales, finales o entre estaciones.  No se consideran fallos en las máquinas ni paradas por mantenimiento.  Los tiempos de setup no son anticipatorios, a menos que se especifique. Esto significa que no se puede realizar el setup antes de que se libere el sublote correspondiente. Respecto a la métrica de rendimiento. La función objetivo considerada es minimizar el makespan, es decir, el tiempo comprendido entre el inicio de la primera operación y la finalización de la última operación. Según la notación propuesta en el subapartado 2.2.2, este problema se podría expresar de la siguiente manera. Jm | pmtn − non − resumable/𝑠 /consistent lot(j) − streaming | 𝐶 67 67 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop 3.3 Modelado La representación del problema en un Gantt ofrece una visualización muy cómoda y fácilmente comprensible de las soluciones, pero realmente no ayuda a entender la estructura del problema. El grafo disyuntivo ayuda a entender mejor dicha estructura. Figura 13. Grafo disyuntivo aplicado a un job shop. [Fuente: [40]]. En la Figura 13. Grafo disyuntivo aplicado a un job shop. se muestra un grafo disyuntivo que representa un entorno de producción job shop en el que se procesan 3 trabajos en 3 máquinas. El grafo disyuntivo se puede expresar como 𝐺 =(𝑉,𝐶∪𝐷) donde:  𝑉 es el conjunto de vértices correspondiente a las operaciones. 2 vértices ficticios 𝑠 y 𝑡 se añaden para representar los instantes de inicio y finalización.  𝐶 es un conjunto de arcos conjuntivos entre las operaciones 𝑖 y (𝑖+1) de un trabajo. También se añaden arcos conjuntivos desde 𝑠 a la primera operación de cada trabajo y desde la última operación de cada trabajo a 𝑡.  𝐷 es un conjunto de arcos disyuntivos entre operaciones que se procesan en la misma máquina. Son los arcos representados con líneas discontinuas de colores. Para determinar un programa hay que definir el orden de las tareas que se van a procesar en cada máquina. Esto se puede hacer orientando todas las líneas discontinuas (arcos disyuntivos) de manera que cada grupo correspondiente a una máquina sea acíclico. También se deben evitar los ciclos entre arcos disyuntivos y conjuntivos porque generan programas no factibles. El makespan en el grafo viene dado por el camino más largo entre 𝑠 y 𝑡. Modelado del problema 68 68 Figura 14. Representación del makespan en un grafo disyuntivo. [Fuente: [40]]. Se puede definir el problema de la programación de un job shop como un problema de grafos: encontrar una orientación de las aristas de un grafo disyuntivo tal que el grafo dirigido resultante sea acíclico y el camino ponderado más largo de 𝑠 a 𝑡 sea mínimo. El modelado del problema se basa en el modelo propuesto por Manne [41]. Es conocido como modelo disyuntivo, ya que se basa en el grafo disyuntivo. Se ha probado que es el modelo más eficiente (mejora más rápido) para instancias pequeñas [42]. 3.3.1 Notación Naturaleza Notación Definición Constantes y Parámetros 𝐽 Número de trabajos o productos. 𝑀 Número de máquinas 𝑈 Número de sublotes máximo. 𝑑  Demanda de cada trabajo 𝑗 𝑝  Tiempo de procesado de cada unidad del trabajo 𝑗 en la máquina 𝑚 𝑅  Ruta del trabajo 𝑗 Variables continuas 𝐶 Makespan 𝑥  Instante en el que el lote 𝑢 del trabajo 𝑗 empieza a procesarse en la máquina 𝑚 𝑦  Instante en el que el setup asociado al lote 𝑢 del trabajo 𝑗 empieza a procesarse en la máquina 𝑚 𝑝  Tiempo de procesado del lote 𝑢 del trabajo 𝑗 empieza a procesarse en la máquina 𝑚 Variables enteras 𝑞  Tamaño del sublote 𝑢 del trabajo 𝑗 binaria 𝑧  Variable binaria que vale 1 si el lote 𝑙 del trabajo 𝑘 precede al lote 𝑢 del trabajo 𝑗 en la máquina 𝑚 𝑄  Variable binaria que vale 1 si el tamaño del lote 𝑞  es mayor que 0 69 69 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop 3.3.2 Modelo MILP A continuación se presenta el modelo de programación lineal entera mixta. Consta de 15 expresiones: 1 función objetivo y 14 restricciones, incluyendo las restricciones que determinan la naturaleza de las variables. Objetivo min 𝐶  (1) Restricciones 𝑦    ≥ 𝑥      ,  ,  + 𝑝      ,  ,  ∀ ℎ ∈ ( 2 , . . . , 𝑀 ) 𝑖𝑛 𝑅  ; ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ∈ 𝑈 (2) 𝑦  ≥ 𝑥  ,    + 𝑝  ,    ∀ 𝑚 ∈ ( 𝑀 ∧ 𝑅  ) ; ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ≠ 1 ∈ 𝑈 (3) 𝑧  + 𝑧  = 1 ∀ 𝑚 ∈  𝑀 ∧ 𝑅  ∧ 𝑅   ; ∀ 𝑗 , 𝑘 ∈ 𝐽 ; ∀ 𝑢 , 𝑙 ∈ 𝑈 𝑗 ≠ 𝑘 ∨ 𝑢 ≠ 𝑙 (4) 𝑦  + 𝑉 ·  1 − 𝑧   ≥ ( 𝑥  + 𝑝  ) ∀ 𝑚 ∈  𝑀 ∧ 𝑅  ∧ 𝑅   ; ∀ 𝑗 , 𝑘 ∈ 𝐽 ; ∀ 𝑢 , 𝑙 ∈ 𝑈 𝑗 ≠ 𝑘 ∨ 𝑢 ≠ 𝑙 (5) 𝑥  ≥ 𝑦  + 𝑠  · 𝑄  ∀ 𝑚 ∈ ( 𝑀 ∧ 𝑅  ) ; ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ∈ 𝑈 (6) 𝐶  ≥ 𝑥  + 𝑝  ∀ 𝑚 ∈ 𝑀 ; ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ∈ 𝑈 (7)  𝑞    = 𝑑  ∀ 𝑗 ∈ 𝐽 (8) 𝑞  ≤ 𝑉 · 𝑄  ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ∈ 𝑈 (9) 𝑄  ≤ 𝑞  ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ∈ 𝑈 (10) 𝑝  = 𝑝  · 𝑞  ∀ 𝑚 ∈ 𝑀 ; ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ∈ 𝑈 (11) 𝑥  ≥ 0 ∀ 𝑚 ∈ 𝑀 ; ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ∈ 𝑈 (12) 𝑦  ≥ 0 ∀ 𝑚 ∈ 𝑀 ; ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ∈ 𝑈 (13) 𝑧  ∈ { 0 , 1 } ∀ 𝑚 ∈ 𝑀 ; ∀ 𝑘 , 𝑗 ∈ 𝐽 , 𝑘 ≠ 𝑗 (14) 𝑄  ∈ { 0 , 1 } ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ∈ 𝑈 (15) El objetivo (1) es el makespan, el tiempo en el que se completa el procesado del último lote del programa. La restricción (2) describe la ruta de trabajo de cada producto 𝑗. Se impone que el setup asociado a un sublote no puede comenzar en la siguiente máquina hasta que no haya terminado de procesarse en la máquina anterior. Modelado del problema 70 70 Esta restricción se puede modificar para considerar el caso de setups anticipatorios. Basta con imponer que, en vez de que no pueda comenzar el setup, que no pueda comenzar el procesamiento del sublote como tal. La restricción modificada sería: 𝑥    ≥ 𝑥      ,  ,  + 𝑝      ,  ,  ∀ ℎ ∈ ( 2 , . . . , 𝑀 ) 𝑖𝑛 𝑅  ; ∀ 𝑗 ∈ 𝐽 ; ∀ 𝑢 ∈ 𝑈 (2*) La restricción (3) indica que, en cada máquina, los sublotes de cada producto 𝑗 deben procesarse en orden. El sublote número 𝑥−1 debe preceder al lote número 𝑥. Las restricciones (4) y (5) describen la precedencia entre sublotes en cada máquina. En (4) se indica que un sublote siempre precede a otro sublote en la misma máquina, siempre que sean sublotes con igual número, pero asociados a distintos trabajos o sublotes con distinto número, pero asociados al mismo trabajo. En ningún caso ambos sublotes pueden estar asociados al mismo trabajo y tener el mismo índice, pues se estaría imponiendo que el propio sublote se precede a sí mismo, lo cual lógicamente no es posible. En (5) se especifica que, en cada máquina, el setup del sublote sucesor tiene que empezar después de que acabe de procesarse el sublote predecesor. La restricción (6) describe la ejecución del setup para el procesado de cada sublote. Si el tamaño del sublote no es 0, entonces se ejecuta el setup y el procesado comenzará cuando este termine. En otras palabras, todos los sublotes tienen que empezar a procesarse cuando haya acabado su setup siempre y cuando el tamaño del lote no sea 0. La restricción (7) describe el makespan. Simplemente sirve para calcular el valor de la función objetivo y por ende establecer la dirección de mejora. La restricción (8) indica que todas las unidades de un lote o producto han de ser repartidas en sublotes. Por lo tanto, la suma del tamaño de los sublotes ha de ser el número total de unidades que componen la orden de trabajo del producto. Las restricciones (9) y (10) son fundamentales para la ejecución de los setup. Son complementarias a la restricción (6). Mediante la variable aleatoria 𝑄 se indica si el sublote 𝑢 asociado al producto 𝑗 va a contener alguna unidad. Al modelo se le indica el número máximo de sublotes que se quieren considerar, sin embargo 71 71 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop puede que lo óptimo no sea considerar ese número de sublotes sino un número menor. Por ejemplo, se podría considerar una división máxima en 10 sublotes pero que para un producto lo óptimo fuese dividir el lote en 3 sublotes y para otro producto dividirlo en 5 sublotes. La restricción (11) describe el tiempo de proceso de cada sublote en cada máquina, teniendo en cuenta el tamaño de este y el tiempo de proceso unitario del producto en la correspondiente máquina. En el momento en el que el tamaño de los sublotes es consistente, esta restricción es necesaria, pues cada sublote tendrá un tiempo de procesamiento diferente, dependiendo del tamaño del sublote, la máquina y el producto. Las restricciones (12) a (15) describen la naturaleza de las variables. Las restricciones (12) y (13) indican que los instantes temporales iniciales de la ejecución de los setups y del procesado de los sublotes tienen que ser positivos. Por ende, el makespan será siempre positivo, por cómo está definido en (7). Las restricciones (14) y (15) indican la naturaleza binaria de las variables 𝑧 y 𝑄. 3.4 Conclusiones del capítulo En este capítulo se ha especificado el problema que se aborda mediante una serie de hipótesis y la definición de la función objetivo (makespan). Se ha explicado que el modelo está basado en el modelo disyuntivo propuesto por Manne en la década de los 60. Se elige este modelo como base por ser, de entre los modelos más genéricos de la programación de job shops, el más eficiente en términos de computación. Este modelo está basado en el grafo disyuntivo. Para formular el modelo que aborda el problema de lot streaming se ha elaborado una notificación específica. Se indica como se han formulado las constantes y parámetros (número de máquinas, trabajos, etc) y las variables, diferenciando entre variables continuas y variables enteras y binarias. Por último, se ofrece el modelo de programación lineal entera mixta (MILP). El modelo está compuesto por la función objetivo y 13 restricciones. A diferencia de otros modelos vistos en la literatura, este es muy sencillo. En general, en los artículos científicos se ofrecen modelos con más de 20 restricciones. En algunos casos ni siquiera se ofrecen resultados ni pruebas computacionales. Además, el modelo propuesto tiene la bondad de ser genérico. Es decir, añadiendo más restricciones o modificando levemente las ya existentes se pueden abordar otros problemas similares. Siempre en el marco de Modelado del problema 72 72 la programación de la producción en entornos job shop con lot streaming. 73 4 EXPERIMENTACIÓN, VALIDACIÓN Y MEJORAS En el presente capítulo se va a discutir un escenario genérico de validación del modelo presentado en el capítulo 3, así como una mejora en el programa de producción mediante una heurística, el efecto y las implicaciones de la consideración de setups anticipados y las limitaciones que presenta el modelo MILP. En el apartado 4.1 se explica cómo se han generado las instancias del problema y por qué se ha optado por generar instancias y no por tomar instancias ampliamente reconocidas en la literatura científica. Se ofrecen los datos de las instancias con las cuales se prueba y valida el modelo. En el apartado 4.2 se muestran los resultados para el escenario genérico, que es aquel en el que se considera el tamaño de los sublotes consistente y los tiempos de setup no son anticipatorios. Es el escenario para el que se ha modelado el problema originalmente. A raíz de los resultados obtenidos en este apartado, se implementa una heurística que mejora el programa de producción obtenido mediante el modelo MILP. La heurística y los resultados obtenidos con ella se muestran en el apartado 4.3. En el apartado 4.4 se muestran los resultados que se obtienen cuando se modifica la restricción número 2 para considerar tiempos de setup anticipatorios. Por último, en el apartado 4.5 se exponen las limitaciones del modelo MILP y en el apartado 4.6 las conclusiones del capítulo. Es importante aclarar que no se hace una experimentación en la que se compite con otros modelos para ver cuál es más eficiente computacionalmente. Con esta experimentación el objetivo es validar el modelo, ver Experimentación, validación y mejoras 80 80 en la máquina 0 en el instante 1641. Esta holgura no es relevante para la función objetivo, por lo tanto no se elimina. Se puede decir entonces que, aunque el modelo respeta y cumple las hipótesis de partida, en algunos casos el modelo tiende a subdividir trabajos en varios lotes cuando en realidad no es necesario. En otros casos, se programan operaciones lo más tarde posible, dando lugar a holguras también innecesarias. Ambos comportamientos vienen dados por la naturaleza de la función objetivo. 4.2.2 Instancia mediana Para la segunda instancia se obtiene el programa mostrado en la Figura 17. En este caso el número máximo de sublotes permitido es 3. Sin embargo, se aprecia que no para todos los trabajos se opta por dividir el lote en 3 sublotes, como es el caso del producto 3. Figura 17. Programa de producción para instancia mediana. Caso genérico. [Fuente: elaboración propia]. Lo más interesante de esta instancia es la evolución del valor de la función objetivo y del MIP Gap. En la Figura 18 se muestra en el eje X el coste de computación, en el eje Y en el lado izquierdo el valor del makespan y en el eje Y en el lado derecho el valor del MIP Gap. La primera solución admisible se encuentra tras 1 segundo de computación, con un makespan igual a 15491. Se observa que, en menos de 1 minuto, se consigue un valor cuyo gap es inferior al 30% y una reducción del makespan del 30,1% respecto a la primera solución admisible encontrada. Desde el minuto 1 hasta que se alcanza el óptimo, el gap disminuye bastante aunque la mejora en la función objetivo no es tan significativa. 81 81 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop La diferencia en el makespan entre la primera solución admisible encontrada y la solución óptima es de 4808 unidades (el valor final obtenido es 10683). Resulta interesante y positivo que el 97,9% del rango de mejora se ha logrado en menos de 1 minuto. Es decir, se ha reducido en 4709 unidades el makespan en menos de 1 minuto. Este comportamiento no se puede extrapolar a todas las instancias. Dependiendo de la instancia, la mejora puede ser más o menos rápida y más o menos significativa. Figura 18. Evolución del Makespan y MIP Gap para instancia mediana. Caso genérico. [Fuente: elaboración propia]. 4.2.3 Instancia grande Por último, se corre el modelo para la instancia grande. El programa obtenido se muestra en la Figura 19. En este caso se desconoce el tiempo necesario para alcanzar la optimalidad. Se establece como mecanismo de parada un coste computacional máximo de 7200 segundos o lo que es igual, 2 horas. Experimentación, validación y mejoras 82 82 Figura 19. Programa de producción para instancia grande. Caso genérico. [Fuente: elaboración propia]. Se observa que estableciendo un máximo de 5 sublotes por trabajo, solo para el trabajo P4 se han hecho 5 subdivisiones. Para algunos trabajos, como el P2, solo se consideran 2 sublotes. El makespan toma un valor de 74.375 y viene dado por el lote P4-L4 en la máquina M2. La evolución de la función objetivo y el MIP Gap se muestra en la Figura 20. Figura 20. Evolución del Makespan y MIP Gap para instancia grande. Caso genérico. [Fuente: elaboración propia]. La primera solución factible se obtiene tras 25 minutos de computación. En la primera hora, solo se consigue reducir la función objetivo aproximadamente un 1%. En la siguiente hora, la mejora respecto a la solución 83 83 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop inicial encontrada es de un poco más del 3%. En términos absolutos, se consigue reducir el makespan en 2400 unidades temporales, aproximadamente. Se observa que, para instancias de este tamaño o superior, el coste computacional es muy elevado en comparación con la mejora que se obtiene. Si las unidades temporales fuesen minutos, 74.375 minutos (makespan) equivalen a 77 días en el caso de que la fábrica cuente con 2 turnos de producción de 8 horas o 52 días en el caso de que la fábrica tenga producción ininterrumpida. En cualquier caso, son horizontes temporales en los que es muy probable que sea necesario reprogramar la producción en varias ocasiones, debido a factores que no se pueden controlar y en el mejor caso se pueden predecir. Volviendo a la cuestión de la relación entre el coste computacional y la mejora de la solución, surge la pregunta ¿Sería mejor resolver la instancia considerando un número máximo de lotes menor? ¿Se obtendría un makespan inferior? En la Figura 21 se muestra el programa obtenido tras 3600 segundos de computación estableciendo un número máximo de sublotes igual a 2. Se observa que se obtiene una mejora en la solución, respecto a la solución anterior, aunque poco significativa. Esta vez se obtiene un makespan de 73.412 unidades. En términos relativos, se ha mejorado un 1,29 %. Para todos los trabajos se obtiene un solo lote, es decir, se resuelve como si se tratara de un job shop sin lot streaming. Figura 21. Programa de producción para instancia grande. Caso genérico. Reducción de número de lotes máximo. [Fuente: elaboración propia]. La evolución de la solución se muestra en la Figura 22. Se observa que se encuentra el mejor valor de la función objetivo en menos de 1 minuto de computación. El resto del tiempo, el solver “afina” la estimación que hace del MIP Gap, que se reduce de un 68.4 % a un 27.3 %. Experimentación, validación y mejoras 84 84 Figura 22. Evolución del Makespan y MIP Gap para instancia grande. Caso genérico. Reducción de número de lotes máximo. [Fuente: elaboración propia]. Se pueden obtener dos conclusiones de la experimentación con esta instancia: 1. Para instancias grandes, con un coste computacional de optimalidad superior a 1 hora puede darse el caso de que se obtengan mejores resultados y mucho más rápido sin considerar la subdivisión de lotes. Este valor podría servir de cota superior para continuar la optimización en busca de un mejor makespan en menor tiempo, disminuyendo el número de lotes para ver si se reduce el makespan. Al renunciar a valores de números lotes máximo, perdemos la garantía de optimalidad según las hipótesis iniciales, pero tendremos más posibilidades de encontrar una buena solución, posiblemente como subóptimo al limitar el espacio de búsqueda. 2. El modelo no es adecuado para resolver instancias grandes en poco tiempo. Sería conveniente desarrollar una heurística, metaheurística o mate-heurística para tratar estas instancias considerando lot streaming. 4.3 Heurística para mejora del programa de producción En el apartado anterior se han visto varios aspectos del modelo y del problema que se podrían mejorar. Se ha decidido mejorar 2 de ellos: 1. Eliminar holguras innecesarias, adelantando todo lo posible la producción de todos los sublotes que pueden comenzar antes, siempre respetando las precedencias según la secuencia establecida. 2. Eliminar setups innecesarios, combinando sublotes. 85 85 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop Para abordar estos aspectos se ha implementado la heurística que se muestra en la Figura 23. Figura 23. Diagrama de flujo de heurística para mejorar el programa de producción. [Fuente: elaboración propia]. Ambos aspectos se abordan imponiendo la imposibilidad de aumentar el makespan. La heurística puede ser explicada paso a paso de la siguiente manera: 1. Se genera la instancia correspondiente. 2. Se resuelve la instancia con el modelo expuesto en el subapartado 3.3.2. Si no se encuentra una solución factible en el tiempo límite establecido, se reduce el número máximo de lotes permitido y se vuelve a resolver la instancia. En caso contrario, si se encuentra una solución factible, se continúa con el paso 3. 3. Se toma la solución obtenida y se resuelve con el mismo modelo, cambiando la función objetivo a: 𝐹.𝑂.= 𝑚𝑖𝑛𝑄     Y estableciendo un límite superior para la variable 𝐶 (makespan) igual al valor obtenido en el paso 2. Experimentación, validación y mejoras 86 86 Con esto se minimiza el número de sublotes, con lo que se eliminan tiempos de setup innecesarios. 4. Se fijan las variables p,𝑧,𝑞 𝑦 𝑄, de forma que no se puede modificar el tamaño de los lotes ni la secuencia de estos. Es decir, solo se pueden mover en el tiempo, si presentan holguras. Para fijarlas se impone que el límite superior e inferior de cada variable que se quiere fijar sea el valor obtenido en el paso 2. A continuación, se cambia de nuevo la función objetivo: F.O.=min𝑥       Con ello se consigue adelantar lo máximo posible la producción de todos los lotes, sin aumentar el makespan. Se usan los datos de la instancia pequeña, detallados en el apartado 4.1. Solo cambia el valor de la demanda que aumenta a 300 unidades. La evolución del programa de producción se muestra a continuación. En la Figura 24 se muestra el programa de producción sin mejorar, obtenido en el paso 2. Se observa que el trabajo P2, representado en verde, se ha dividido en 3 sublotes innecesariamente. Figura 24. Programa de producción sin mejorar. Caso genérico. [Fuente: elaboración propia]. En la Figura 25 se muestra el programa obtenido en el paso 3. Se muestra la unión de los sublotes del trabajo P2 en un único lote, eliminando los tiempos de setup innecesarios. 87 87 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop Figura 25. Programa de producción con número de lotes minimizado. Caso genérico. [Fuente: elaboración propia]. En la Figura 26 se muestra el programa obtenido en el paso 4. El lote P0-L0, que presentaba holgura, se adelanta lo máximo posible. Figura 26. Programa de producción número de lotes minimizado y máximo adelanto. Caso genérico. [Fuente: elaboración propia]. Como se puede observar, el makespan no se reduce, pero se obtienen 2 beneficios: 1. Reduciendo lo máximo posible el número de lotes se realizan menos setups. Esto implica que las máquinas aumentan su tiempo productivo y se disminuyen costes, ya sea en energía, en horas de operario o en otros aspectos derivados. Experimentación, validación y mejoras 88 88 2. Reduciendo lo máximo posible el inicio de la producción de los lotes, las máquinas que no son cuello de botella se liberan antes. Esto es una ventaja cuando se debe atender demanda inesperada o se debe hacer un reproceso de alguna unidad producida. Se aumenta el “oxígeno para respirar” en caso de situaciones extraordinarias, que implican aumentar el tiempo de uso de una máquina. 4.4 Tiempos de setup anticipatorios En el subapartado 3.3.2 se ofrece una modificación de la restricción número 2 del modelo para considerar tiempos de setup anticipatorios. Esta situación puede ser útil en algunos entornos de fabricación en los que las máquinas o equipos pueden ser preparados con antelación para el procesado de trabajos. Puede ser el caso de hornos que tienen que calentarse, cambios de utillaje en máquinas de CNC, cambio de pintura y limpieza en estaciones de pintura, limpieza de columnas de destilación, etc. Se muestra en este apartado una prueba de ello y se comparan los resultados obtenidos en la función objetivo. En la Figura 27 se muestra el programa con tiempos de setup no anticipatorios y en la Figura 28 se muestra el programa considerando setups anticipatorios. Figura 27. Programa de producción para instancia pequeña. Caso genérico. Demanda de 200 unidades. Setup no anticipatorio. [Fuente: elaboración propia]. 89 89 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop Figura 28. Programa de producción para instancia pequeña. Caso genérico. Demanda de 200 unidades. Setup anticipatorio. [Fuente: elaboración propia]. El programa en ambos casos es similar, casi idéntico. Sin embargo, hay diferencias cruciales. En el caso en el que no se considera la anticipación, el makespan obtenido es de 5380 unidades mientras que en el caso considerando anticipación se obtiene un makespan de 5309 unidades. Es claro que, considerando la anticipación, se disminuye el makespan. Además se observa que el tamaño de los lotes cambia ligeramente entre un programa y otro. Se podría pensar que para obtener el programa óptimo considerando la anticipación, basta con reprogramar el programa original, modificando solo los instantes de inicio de cada lote. Con esta prueba queda demostrado que esto no es así. Si se quiere obtener el programa óptimo para cada caso, se debe resolver el modelo correspondiente. Chan, Wong et al [20] indican que la anticipación de los tiempos de preparación puede dar lugar a un aumento del tiempo total de la planificación debido a retrasos inesperados que impliquen reprogramar la producción. Supongamos se realiza un setup para un determinado trabajo pero este no llega por causas inesperadas. A continuación, se realiza una reprogramación y se decide procesar otro producto diferente. Habría que hacer de nuevo un setup diferente. 4.5 Limitaciones del MILP Una vez hecho los experimentos, se puede afirmar que el modelo cumple satisfactoriamente, quedando validado el mismo, bajo el objetivo de minimización del makespan. Sin embargo, existen limitaciones que se deben tener en cuenta. Referencias 96 96 REFERENCIAS [1] H. O. Günther, “The block planning approach for continuous time-based dynamic lot sizing and scheduling,” Business Research, vol. 7, no. 1, 2014, doi: 10.1007/s40685-014-0003-y. [2] J. Buergin et al., “A modular-based approach for Just-In-Time Specification of customer orders in the aircraft manufacturing industry,” CIRP J Manuf Sci Technol, vol. 21, 2018, doi: 10.1016/j.cirpj.2018.01.003. [3] “Avión A400M.” Accessed: Mar. 28, 2024. [Online]. Available: https://www.airbus.com/en/productsservices/defence/military-aircraft/a400m [4] “Página oficial del Parque Tecnológico Aeroespacial de Andalucía.” Accessed: Mar. 28, 2024. [Online]. Available: https://www.aeropolis.es/ [5] S. I. Chen and D. Su, “A multi-stage stochastic programming model of lot-sizing and scheduling problems with machine eligibilities and sequence-dependent setups,” Ann Oper Res, vol. 311, no. 1, 2022, doi: 10.1007/s10479-019-03462-1. [6] O. W. Wight, Manufacturing Resource Planning: MRP II : Unlocking America’s Productivity Potential. Oliver Wight, 1984. [Online]. Available: https://books.google.es/books?id=96W5AAAAIAAJ [7] J. W. Herrmann, “A history of production scheduling,” in International Series in Operations Research and Management Science, vol. 89, 2006. doi: 10.1007/0-387-33117-4_1. [8] Patrick Weaver, “Henry L Gantt, 1861 - 1919 A retrospective view of his work,” PM World Journal, 2012. [9] H. L. Gantt and D. Forrer, Organizing for Work by Henry Laurence Gantt. Forrer & Associates, 1919. [Online]. Available: https://books.google.es/books?id=zc6YPAAACAAJ [10] Nathan Black, “A Brief History of Time(lines): Henry Gantt and his Revolutionary Chart.” Accessed: Mar. 28, 2024. [Online]. Available: https://www.onepager.com/community/blog/a-brief-history-of-the- gantt-chart/ [11] W. Clark, The Gantt Chart: A Working Tool of Management. Sir I. Pitman & sons, Limited, 1942. [Online]. Available: https://books.google.es/books?id=Cd8gAAAAMAAJ [12] S. M. Johnson, “Optimal two‐ and three‐stage production schedules with setup times included,” Naval Research Logistics Quarterly, vol. 1, no. 1, 1954, doi: 10.1002/nav.3800010110. [13] S. S. Panwalkar and W. Iskander, “A Survey of Scheduling Rules,” Oper Res, vol. 25, no. 1, 1977, doi: 97 97 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop 10.1287/opre.25.1.45. [14] Z. Jiang, S. Yuan, J. Ma, and Q. Wang, “The evolution of production scheduling from Industry 3.0 through Industry 4.0,” Int J Prod Res, vol. 60, no. 11, 2022, doi: 10.1080/00207543.2021.1925772. [15] Bruno Scalia, “The Job-Shop Scheduling Problem: Mixed-Integer Programming Models.” Accessed: Mar. 28, 2024. [Online]. Available: https://towardsdatascience.com/the-job-shop-scheduling-problem- mixed-integer-programming-models-4bbee83d16ab [16] S. B. Akers, “Letter to the Editor—A Graphical Approach to Production Scheduling Problems,” Oper Res, vol. 4, no. 2, pp. 244–245, Apr. 1956, doi: 10.1287/opre.4.2.244. [17] E. H. Bowman, “The Schedule-Sequencing Problem,” Oper Res, vol. 7, no. 5, pp. 621–624, Oct. 1959, doi: 10.1287/opre.7.5.621. [18] R. L. Sisson, “Methods of Sequencing in Job Shops—A Review,” Oper Res, vol. 7, no. 1, pp. 10–29, Feb. 1959, doi: 10.1287/opre.7.1.10. [19] H. Xiong, S. Shi, D. Ren, and J. Hu, “A survey of job shop scheduling problem: The types and models,” 2022. doi: 10.1016/j.cor.2022.105731. [20] F. T. S. Chan, T. C. Wong, and L. Y. Chan, “The application of genetic algorithms to lot streaming in a job-shop scheduling problem,” Int J Prod Res, vol. 47, no. 12, 2009, doi: 10.1080/00207540701577369. [21] T. C. Wong and S. C. Ngan, “A comparison of hybrid genetic algorithm and hybrid particle swarm optimization to minimize makespan for assembly job shop,” Applied Soft Computing Journal, vol. 13, no. 3, 2013, doi: 10.1016/j.asoc.2012.04.007. [22] F. M. Defersha and M. Chen, “Jobshop lot streaming with routing flexibility, sequence-dependent setups, machine release dates and lag time,” Int J Prod Res, vol. 50, no. 8, 2012, doi: 10.1080/00207543.2011.574952. [23] H. Wang, B. R. Sarker, J. Li, and J. Li, “Adaptive scheduling for assembly job shop with uncertain assembly times based on dual Q-learning,” Int J Prod Res, vol. 59, no. 19, 2021, doi: 10.1080/00207543.2020.1794075. [24] K. Copil, M. Wörbelauer, H. Meyr, and H. Tempelmeier, “Simultaneous lotsizing and scheduling problems: a classification and review of models,” OR Spectrum, vol. 39, no. 1, 2017, doi: 10.1007/s00291-015-0429-4. [25] U. Buscher and L. Shen, “An integrated tabu search algorithm for the lot streaming problem in job shops,” Eur J Oper Res, vol. 199, no. 2, 2009, doi: 10.1016/j.ejor.2008.11.046. [26] F. Xie, L. Li, L. Li, Y. Huang, and Z. He, “A decomposition-based multi-objective Jaya algorithm for lot-streaming job shop scheduling with variable sublots and intermingling setting,” Expert Syst Appl, Referencias 98 98 vol. 228, 2023, doi: 10.1016/j.eswa.2023.120402. [27] A. Salazar-Moya and M. V. Garcia, “Lot streaming in different types of production processes: A prisma systematic review,” Designs (Basel), vol. 5, no. 4, 2021, doi: 10.3390/designs5040067. [28] F. M. Defersha and S. Bayat Movahed, “Linear programming assisted (not embedded) genetic algorithm for flexible jobshop scheduling with lot streaming,” Comput Ind Eng, vol. 117, 2018, doi: 10.1016/j.cie.2018.02.010. [29] D. Lei and X. Guo, “Scheduling job shop with lot streaming and transportation through a modified artificial bee colony,” Int J Prod Res, vol. 51, no. 16, 2013, doi: 10.1080/00207543.2013.784404. [30] C. Low, C. M. Hsu, and K. I. Huang, “Benefits of lot splitting in job-shop scheduling,” International Journal of Advanced Manufacturing Technology, vol. 24, no. 9–10, 2004, doi: 10.1007/s00170-003- 1785-9. [31] S. Dauzère-Pérès and J. B. Lasserre, “Lot Streaming in job-shop scheduling,” Oper Res, vol. 45, no. 4, 1997, doi: 10.1287/opre.45.4.584. [32] F. T. S. Chan, T. C. Wong, and L. Y. Chan, “Lot streaming for product assembly in job shop environment,” Robot Comput Integr Manuf, vol. 24, no. 3, 2008, doi: 10.1016/j.rcim.2007.01.001. [33] A. Bożek and F. Werner, “Flexible job shop scheduling with lot streaming and sublot size optimisation,” Int J Prod Res, vol. 56, no. 19, 2018, doi: 10.1080/00207543.2017.1346322. [34] C. H. Liu, “Lot streaming for customer order scheduling problem in job shop environments,” Int J Comput Integr Manuf, vol. 22, no. 9, 2009, doi: 10.1080/09511920902866104. [35] J. M. Novas, “Production scheduling and lot streaming at flexible job-shops environments using constraint programming,” Comput Ind Eng, vol. 136, 2019, doi: 10.1016/j.cie.2019.07.011. [36] S. Dauzere-Peres and J. B. Lasserre, “An iterative procedure for lot streaming in job-shop scheduling,” Comput Ind Eng, vol. 25, no. 1–4, 1993, doi: 10.1016/0360-8352(93)90263-W. [37] S. Dauzère-Péres and J. B. Lasserre, “Integration of lotsizing and scheduling decisions in a job-shop,” Eur J Oper Res, vol. 75, no. 2, 1994, doi: 10.1016/0377-2217(94)90085-X. [38] S. Birogul, C. Elmas, and T. Yigit, “Lot streaming based job-shop scheduling problem using hybrid genetic algorithm,” Scientific Research and Essays, vol. 6, no. 14, 2011. [39] IBM, “Mathematical programming versus constraint programming.” Accessed: Apr. 29, 2024. [Online]. Available: http://ibmdecisionoptimization.github.io/docplex-doc/mp_vs_cp.html [40] “job shop disjunctive model.” Accessed: May 16, 2024. [Online]. Available: https://acrogenesis.com/ortools/documentation/user_manual/manual/ls/jobshop_def_data.html#disjunctive-graph1 99 99 Modelado MILP para la determinación conjunta del scheduling y lot-streaming en un entorno job-shop [41] A. S. Manne, “On the Job-Shop Scheduling Problem,” Oper Res, vol. 8, no. 2, 1960, doi: 10.1287/opre.8.2.219. [42] W. Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis,” Comput Oper Res, vol. 73, 2016, doi: 10.1016/j.cor.2016.04.006.