Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos

Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 1 Equation Chapter 1 Section 1 Proyecto Fin de Carrera Ingeniería de Organización Industrial Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos Autor: María Caballero Saborido Tutor: Carla Talens Fayos Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Sevilla, 20 2 3 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 2 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 3 Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos Autor: María Caballero Saborido Tutor: Carla Talens Fayos Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2023 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 4 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 5 Proyecto Fin de Grado: Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos Autor: María Caballero Saborido Tutor: Carla Talens Fayos El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2023 El Secretario del Tribunal Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 6 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 7 A mi familia A mis maestros A mis amigas Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 8 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 9 Agradecimientos Me gustaría agradecer a todas las personas que me han apoyado a lo largo de esta aventura y me han servido de apoyo en los momentos duros. A mi tutora Carla Talens Fayos, por aceptar tutorizarme este trabajo fin de grado, así como por su tiempo y dedicación durante todo el proceso. A mis padres, por haberme ofrecido todo lo que estaba en sus manos para conseguir mi objetivo. A mis compañeras, ya amigas Lucía y Patri, sin vosotras nada hubiera sido lo mismo. A mis abuelos, Concha y Manuel, por ser el ejemplo en el que convertirme algún día. María Caballero Saborido Sevilla, 2023 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 16 ÍNDICE DE TABLAS Tabla 1. Ejemplo de matriz de tiempos de proceso 26 Tabla 2. Tiempos de proceso en la primera etapa para la instancia de ejemplo 13 Tabla 3. Tiempos de setup dependientes de la secuencia para la instancia de ejemplo 14 Tabla 4. ARPD por cada regla de despacho 27 Tabla 5. ARPD de las heurísticas constructivas y búsquedas locales 30 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 17 ÍNDICE DE ILUSTRACIONES Ilustración 1. Esquema Sistema Productivo (Fuente: Elaboración propia) 20 Ilustración 2. Proceso de tratamiento de un programa de Programación de la Producción (Fuente: Elaboración propia) 24 Ilustración 3. Esquema una máquina (Fuente: Libro de teoría de PCP) 25 Ilustración 4. Esquema máquinas paralelas (Fuente: Libro de teoría de PCP) 25 Ilustración 5. Esquema Flowshop (Fuente: Libro de teoría de PCP) 27 Ilustración 6. Esquema Jobshop (Fuente: Libro de teoría de PCP) 27 Ilustración 7. Esquema Openshop (Fuente: Libro de teoría de PCP) 28 Ilustración 8. Grafo de precedencia (Fuente: Libro de teoría de PCP) 29 Ilustración 9. Programa de instancia de ejemplo. (Fuente: Elaboración propia) 14 Ilustración 10. Programa segunda secuencia de ejemplo (Fuente: Elaboración propia) 16 Ilustración 11. Esquema Adjacent Swap (Fuente: Libro de PCP) 23 Ilustración 12. Esquema General Swap (Fuente:Libro de PCP) 23 Ilustración 13. Esquema Insertion (Fuente:Libro de PCP) 24 Ilustración 14. Pseudocódigo de la búsqueda local aplicada 24 Ilustración 15. Gráfico sobre la evolución del ARPD en función del número de trabajos 28 Ilustración 16. Gráfico sobre la evolución del ARPD en función del parámetro Alpha 29 Ilustración 17. Gráfico sobre la evolución del ARPD de las heurísticas en función del número de trabajos 31 Ilustración 18. Gráfico sobre la evolución del ARPD de las heurísticas junto con búsqueda local en función del número de trabajos 31 Ilustración 19. Gráfico sobre la evolución del ARPD de las heurísticas en función del parámetro alpha 32 Ilustración 20. Gráfico sobre la evolución del ARPD de las heurísticas junto con búsqueda local en función del parámetro alpha 32 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 18 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 19 1 INTRODUCCIÓN Sólo el conocimiento que llega desde dentro es el verdadero conocimiento. - Sócrates - La Organización de la Producción consiste en la toma de decisiones que afectan al sistema productivo y a la logística de aprovisionamiento y de distribución a distintos niveles: estratégico (largo plazo), táctico (medio plazo) y operativo (corto plazo). Las decisiones estratégicas que afectan al sistema productivo son la localización de la unidad productiva, la capacidad de fabricación, el proceso productivo y las infraestructuras de servicios, entre otros. A nivel táctico, se hacen previsiones de la demanda, se determina el nivel de stocks deseable y se planifica la producción (cuánto hay que producir y en qué momento). Por último, se encuentran las decisiones operativas. Estas decisiones son las que se toman diariamente en la empresa y la más importante es la programación de operaciones. La programación de operaciones consiste en llevar a cabo la planificación de la producción, que ha determinado cuántos productos y cuándo de manera desagregada, en las distintas operaciones de nuestro sistema productivo. Es importante contextualizar las características propias de un sistema productivo, que es aquel cuyo objetivo es transformar recursos en productos aplicándoles una transformación. Los recursos que se Planificación operativa Planificación táctica Planificación estratégica  Localización de la unidad productiva  Capacidad productiva  Selección del proceso productivo  Infraestructuras  Personal  Previsión de la demanda  Nivel se stocks (Política de inventario)  Planificación de la producción: qué producir, subcontratar, …  Mercados que van a ser atendidos  Programación de las órdenes  Lanzar órdenes de compras  Ajustar fechas de entrega, calidades del producto, …  Logística Ilustración 1. Estrategias de planificación Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 20 transforman pueden ser materias primas, con la mano de obra de los trabajadores ubicados en unas instalaciones utilizando energía y otros suministros. El producto final obtenido tras someter los recursos a una transformación (proceso productivo) debe cumplir con los requerimientos de calidad y cantidad, así como con los tiempos de entrega. El ajuste que aparece en el esquema hace referencia al conjunto de mecanismos que se llevan a cabo en la empresa con el fin de controlar que el producto cumple con las normas de calidad establecidas. En el presente Trabajo Fin de Grado, se va a tratar un problema sobre programación de la producción basado en un entorno híbrido que consiste en un taller formado por dos etapas en el que cada uno de ellos es un entorno primario. Para este entorno, se van a considerar restricciones como tiempos de preparación de las máquinas (setup) entre trabajos y la compra a un proveedor externo de uno de los componentes necesarios para obtener el producto final. Se van a aplicar diferentes métodos aproximados para resolver el problema estudiado haciendo uso de un número determinado de instancias del problema. Se compararán distintas reglas de despacho y se probarán distintas versiones de una heurística adaptada con el objetivo de encontrar una buena solución para el problema. Para ilustrar el problema de estudio, se puede tomar como ejemplo una célula de montaje de PCB (Printed Circuit Board o Placa de Circuito Impreso) en la que se fabrican en una primera etapa componentes que posteriormente son montados en la placa que es suministrada por un proveedor externo. Si se relacionan las condiciones particulares del problema con los aspectos estratégicos mencionados anteriormente, podríamos decir que se trata de un proceso en línea en el que cada trabajo pasa por las dos etapas y en cuanto a la estrategia de fabricación, podría tratarse de estrategia Make-To-Stock que justifica que cada trabajo realice el proceso completo para almacenarse en inventario y estar disponible para cuando lo solicite el cliente. Recursos •Materias Primas •Mano de Obra •Energía/Suministros •Instalaciones... Transformación Producto •Tiempos de entrega •Calidad Requerida •Cantidad Requerida •Calidad del servicio... Ilustración 1. Esquema Sistema Productivo (Fuente: Elaboración propia) Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 21 1.1 Estructura del trabajo Este Trabajo Fin de Grado se ha estructurado de la siguiente manera:  Capítulo 2. Marco Teórico. Se presentarán los elementos básicos que componen un modelo de programación de la producción, así como la codificación de las soluciones. Se explicará la notación para identificar al modelo completo y la clasificación de los tipos de métodos de resolución.  Capítulo 3. Descripción del problema. Se explicará el funcionamiento del problema a abordar, las restricciones del modelo y la función objetivo. Se presentarán unos datos de ejemplo para mostrar la configuración de los datos del problema y dos diagramas de Gantt para ilustrar el funcionamiento del modelo.  Capítulo 4. Metodología. Se hará una breve revisión de los artículos estudiados relacionados con el problema descrito y se explicarán los métodos a aplicar.  Capítulo 5. Análisis de resultados. Se analizarán los resultados obtenidos tras los experimentos en base a un indicador y se realizará una comparación entre métodos con la misma naturaleza.  Capítulo 6. Conclusiones. Se reflexionará a cerca del trabajo realizado y de los resultados obtenidos. Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 22 2 UN PROBLEMA DE PROGRAMACIÓN DE LA PRODUCCIÓN La programación de la producción no sólo tiene sentido en entornos de producción masivos o en los que el producto sea sólo tangible, lo tiene en cualquier sistema productivo en el que, como se ha explicado anteriormente, se transforman unos inputs para conseguir un producto. Este hecho, junto con la alta competitividad del mercado actual, acrecienta significativamente la importancia de esta disciplina. Es importante saber que un problema de programación de la producción es un problema de optimización y que, por tanto, está compuesto de unas restricciones y una función objetivo que marca la dirección de búsqueda de la solución. Para entender el modelo que se estudiará en este Trabajo Fin de Grado es preciso hacer un recorrido por la notación, las partes y la solución de un modelo de Programación de la Producción. 2.1 Elementos de un problema de programación de la producción A continuación, se muestran los conceptos básicos que conforman un problema de programación de la producción:  M, máquinas: Recurso productivo con capacidad para realizar operaciones sobre la materia prima. En cualquier problema que se modele, las máquinas pueden representar desde máquinas reales de fabricación como pueden ser hornos, máquinas de corte, etc. a células de fabricación compuestas por operarios con herramientas o simples operarios. Más adelante, se explicará que la disposición de las máquinas o características propias dan lugar a los distintos entornos posibles de un sistema productivo.  N, trabajos: Total de productos terminados que se necesitan procesar. Los trabajos pueden representar objetos tangibles, en el caso de industrias manufactureras, o intangibles como pedidos, referencias, gestiones, … Los trabajos son procesados en las máquinas y van transformándose a lo largo del sistema productivo.  𝑝𝑖𝑗, tiempo de proceso: Es el tiempo que el trabajo j necesita ser procesado en la máquina i. Si Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 23 el tiempo de proceso no depende de la máquina se expresa como 𝑝 Para el análisis de un modelo concreto, los tiempos de proceso se conocerán a través de la experiencia o a través de la experimentación.  r, fecha de llegada: Instante de tiempo en el que el trabajo j se puede comenzar a procesar. Las fechas de llegada cobran especial importancia en problemas reales. Los modelos no son cajas negras aisladas del mercado y es usual que materias primas o componentes se suministren por proveedores externos o se subcontraten servicios o procesos, por lo que nuestro proceso estará limitado por el tiempo que tarden estos componentes o servicios en ser suministrados a nuestro sistema productivo.  𝑑, fecha de entrega: Instante de tiempo en el que el trabajo j debe estar completado. Las fechas de entrega pueden indicarse por el cliente que reclame nuestro producto o directamente por la propia empresa siguiendo el Plan Maestro de Producción que impone la cantidad de producto (o servicio) que se necesita en cada horizonte temporal establecido.  𝑤, peso: Prioridad del trabajo j para ser procesado. El peso puede representar distintas circunstancias del problema. Puede representar la importancia del cliente que recibe el trabajo, preferencia para finalizar un trabajo, etc. Estos pesos aparecen en el modelo generalmente en la función objetivo marcando la dirección en la que debemos conducir la búsqueda de la solución.  𝑅, ruta: Vector, para cada trabajo, que indica las máquinas en el orden por las que el trabajo j va siendo procesado. 2.2 Soluciones de un Modelo de Programación de la Producción Como buena disciplina ingenieril, la programación de la producción pretende dar respuesta a un problema, que en este caso consiste básicamente en saber inicio y fin de cada operación sobre cada trabajo bajo ciertas restricciones impuestas por el mercado, la propia empresa, los recursos, … Como ante cualquier problema lo más importante es encontrar una solución y en este caso toma el nombre de “programa”. Un programa consiste en representar el tiempo que cada recurso opera sobre cada trabajo indicando principio y fin. Los programas, como cualquier otro tipo de solución, deben dar respuesta al modelo y, por tanto, cumplir con las restricciones de este. Al programa que cumple con las restricciones del Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 24 modelo se le llama “programa admisible”. Existen infinitos programas posibles (debido a que la escala temporal es infinita) por lo que para acotar el número de programas posibles se trabajará con programas semiactivos que son aquellos en los que el fin de una operación sobre un trabajo y el comienzo de la operación sobre otro se encuentran lo menos separado posible. Para poder plasmar en el programa en el orden correcto la transformación de cada trabajo es necesario seguir una “receta”: la secuencia. La secuencia es una lista para cada una de las máquinas con todos los trabajos que procesa en el orden en el que lo hace. Mientras que existen infinitos programas debido a que pueden iniciarse en cualquier instante de la escala temporal, las secuencias son finitas ya que establecen un orden entre los trabajos y, por tanto, existen tantas como combinaciones de trabajos sean posibles. En la resolución de un problema de programación de la producción entran en juego dos procesos muy importantes: la abstracción y la metodología de resolución. La primera de ellas consiste en el ejercicio de convertir las características del problema real y físico en la representación matemática cuyo procedimiento no se explicará en este trabajo, pero sí se tratarán los métodos de resolución más adelante. 2.3 Modelo 𝜶| 𝜷|𝜸 Cuando se presenta un caso de estudio y una vez presentados los elementos básicos que pueden participar en el problema de programación de la producción es necesario hacer un ejercicio de abstracción para convertir el problema en el modelo correspondiente. El modelo se construye siguiendo la notación establecida por Graham (1979). Siguiendo la notación del artículo mencionado, es posible conocer qué problema se está tratando, rellenando cada uno de los Problema de Programación de la Producción Abstracción Modelo de Programación de la Producción Métodos de resolución Solución del modelo Ilustración 2. Proceso de tratamiento de un programa de Programación de la Producción (Fuente: Elaboración propia) Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 25 campos del formato 𝛼|𝛽|𝛾. ¿Qué significan 𝛼,𝛽 𝑦 𝛾? Las letras griegas 𝛼,𝛽 𝑦 𝛾 hacen referencia al tipo de entorno, restricciones y función objetivo del modelo. A continuación, se explica detalladamente cada una de ellas.  𝛼, tipo de entorno: El tipo de entorno del modelo viene marcado por la cantidad de máquinas, la relación que guardan entre ellas y con los trabajos a procesar. En la literatura se encuentran estudios sobre entornos muy diversos, pero los más sencillos y sobre los que se construyen los más complejos son los siguientes: o 𝛼=1, una máquina: Es el caso más sencillo de todos. En este entorno sólo hay una máquina por lo que cada trabajo debe procesarse en ella. Para construir el programa solución de este entorno es necesario establecer una secuencia. En este entorno tan sencillo los trabajos pueden ordenarse de 𝑛! formas distintas por tanto existen 𝑛! secuencias distintas y, además en este caso, programas semiactivos. o Máquinas paralelas: Como su nombre indica, es una disposición en la que las máquinas realizan de manera paralela alguna de las operaciones a los trabajos. Existen distintos tipos atendiendo a la relación entre los tiempos de proceso entre ellas.  𝛼=𝑃, Máquinas paralelas idénticas: Máquinas paralelas en las que el tiempo de proceso no depende de la máquina, es decir, no importa qué máquina Ilustración 3. Esquema una máquina (Fuente: Libro de teoría de PCP) Ilustración 4. Esquema máquinas paralelas (Fuente: Libro de teoría de PCP) 11 3 DESCRIPCIÓN DEL PROBLEMA El problema de ensamblado planteado en este Trabajo Fin de Grado no se ha considerado hasta el momento, pero, en la literatura, se pueden encontrar otros problemas relacionados respondiendo a distintas restricciones. A continuación, se hará una breve revisión de los artículos en los que se consideran problemas relacionados y que han servido de guía para el desarrollo de este proyecto. En Talens et al. (2020) se hace una revisión del problema general sin ninguna restricción. Se analiza el problema consistente en dos etapas, la primera procesa componentes pertenecientes a un trabajo que posteriormente se ensamblan en la segunda etapa. En este artículo, se proponen dos heurísticas constructivas para encontrar una solución que atienda a la función objetivo planteada que en su caso es el total completion time. De las dos, se adaptará la heurística llamada Fast Constructive Heuristic al problema con las restricciones que se han planteado en este proyecto. Por otro lado, en Komaki & Kayvanfar (2015) se analiza el problema con tiempos de llegada para cada uno de los componentes en la primera etapa. En este artículo se proponen diferentes reglas de despacho y una metaheurística. De esta configuración del problema de ensamblado se ha considerado la idea para este proyecto de insertar tiempos de llegada, pero sólo para uno de los componentes de la primera etapa. En tercer lugar, en Al-Anzi & Allahverdi (2006) se estudia el problema general sin restricciones con una sola máquina en la segunda etapa. Por último, en SupSung & Juhn (2009) se procesa un componente y otro es suministrado por un proveedor externo, que posteriormente se ensamblarán en la segunda etapa en una máquina de ensamblado. El problema que se estudia en el presente documento se trata de un entorno híbrido compuesto por dos etapas (stages). La primera etapa, llamada A, estará compuesta por 𝑚 máquinas dispuestas paralelamente y cada una de ellas será la encargada de fabricar un componente diferente que formará parte de cada trabajo. El hecho de que cada máquina fabrique un componente distinto implica que pueden realizarse de manera simultánea componentes para el mismo trabajo en las distintas máquinas. Además, existe un último componente que es suministrado externamente por un proveedor. Tras procesarse cada uno de los componentes y recibirse el componente externo, todos ellos podrán ser ensamblados en la segunda etapa, llamada B. En la segunda etapa se tendrán 𝑚 máquinas paralelas que realizan la misma actividad con los mismos tiempos de ensamblado cada una de ellas. En el ensamblado de componentes para cada trabajo, por Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 12 tanto, un trabajo visitará sólo una de las máquinas de la segunda etapa. El objetivo establecido para la búsqueda de la solución es minimizar el makespan o tiempo máximo de finalización de todos los trabajos secuenciados. El caso de estudio presentado se trata de un entorno híbrido en el que para dar una solución al problema es necesario proporcionar una secuencia y una regla de asignación que afectará a cómo se procesarán los trabajos en la segunda etapa. Una regla de asignación es el criterio que se usa para determinar en qué máquina debe colocarse el trabajo que se esté asignando y en la realidad es un criterio que puede estar sujeto a características del sistema productivo, de la empresa u otras. Algunas de ellas son: o ECT, Earliest Completion Time: Implica asignar el trabajo a aquella máquina cuyo tiempo de terminación sea menor tras la asignación del trabajo. Es la regla que se usa por defecto. o FAM, First Available Machine: Consiste en asignar el trabajo a la primera máquina disponible. o Órdenes de etiqueta: Implica asignar el trabajo en la máquina 1, luego en la máquina 2, … hasta la m. Teniendo en cuenta la función objetivo se escoge la regla Earliest Completion Time, es decir, se irán procesando los trabajos en la segunda etapa según estén disponibles para ser ensamblados y su tiempo de finalización sea menor. Con la presentación del problema estudiado en este trabajo, se puede establecer la notación del problema 𝛼| 𝛽|𝛾 establecida por Graham et al. (1979) y explicada en el apartado 2.3, teniendo en cuenta también la aportación que se hace en Framinan et al. (2019) para los modelos de Assembly Scheduling Problems. En este artículo se amplía la notación de Graham et al. (1979) para los casos de ensamblado, quedando con el siguiente formato: 𝛼→𝛼| 𝛽|𝛾 A continuación, se amplía el campo 𝛼 para poder representar cada una de las etapas. Para el caso de estudio que se desarrolla en este trabajo, se tienen los siguientes campos:  Entorno de la primera etapa: 𝛼=𝐷𝑃 . Las siglas “DP” significan dedicated parallel machines y es la notación específica para el entorno descrito en la etapa A. El subíndice m hace Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 13 referencia al número de máquinas dedicadas que hay en la etapa.  Entorno de la segunda etapa: 𝛼=𝑃 . Con lo descrito anteriormente se deduce que se trata de un entorno de máquinas idénticas paralelas.  Restricciones: 𝛽=𝑟,𝑠, . En cuanto a las restricciones, el problema presenta tiempos de llegada para los componentes suministrados externamente y tiempos de setup anticipatorios dependientes de la secuencia para las máquinas de la segunda etapa.  Función objetivo: 𝛾=𝐶 . La función objetivo del problema consistirá en la minimización del tiempo máximo necesario para producir todos los trabajos. 𝐷𝑃→𝑃 𝑟,𝑠,𝐶 Para ilustrar la configuración de los datos del problema, se plantea un ejemplo sencillo con los siguientes datos: N= [1, 2, 3, 4, 5] 𝑚=2 𝑚=2 𝑟=[8,9,26,16,30] Los tiempos de proceso en la primera etapa, 𝑝,, se presentan en la Tabla 2, y los tiempos de ensamblado son 𝑎𝑡=[6 ,7,8 ,5 ,6]. Tabla 2. Tiempos de proceso en la primera etapa para la instancia de ejemplo 𝑛 𝑚  1 2 3 4 5 1 7 8 6 5 6 2 5 4 3 3 4 Los tiempos de preparación, 𝑠,, se presentan en la Tabla 3, en la que la primera línea de la matriz representa el tiempo de puesta en marcha necesario en cada máquina, en el caso de que el trabajo correspondiente sea el primero en cualquiera de las máquinas de la segunda etapa. Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 14 Tabla 3. Tiempos de setup dependientes de la secuencia para la instancia de ejemplo 𝑗 𝑘 1 2 3 4 5 ∅ 3 2 1 4 2 1 2 1 2 3 4 2 3 2 1 2 3 3 4 2 2 3 1 4 1 2 2 3 4 5 2 3 4 2 2 Con todos los datos anteriores se pueden representar algunas secuencias para mostrar su representación gráfica a través de un diagrama de Gantt. - Primera secuencia: 𝑠 = [4,1,3,2,5] Nota: En el diagrama de Gantt presentado en la Ilustración 10 los trabajos presentan una unidad menos que la numeración seguida en el análisis. Como se puede apreciar en el diagrama de Gantt, en la primera etapa se representan dos máquinas paralelas en la que se procesan en cada una de ellas uno de los componentes pertenecientes a cada Ilustración 9. Diagrama de Gantt de la instancia de ejemplo. (Fuente: Elaboración propia) Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 15 trabajo. Al ser componentes diferentes implica que se puedan procesar componentes pertenecientes al mismo trabajo de manera simultánea. En la primera etapa, también se representa la llegada del componente suministrado externamente mediante un pulso para visualizar el instante en el que todos los componentes de un trabajo están listos para ser ensamblados en la segunda etapa. A continuación, se representan las máquinas ensamblado, que como se ha indicado anteriormente son máquinas paralelas idénticas. La particularidad de la segunda etapa son los tiempos de preparación necesarios entre el ensamblado de un trabajo y otro representados por “ST”. Por último, es fácil identificar el instante de fin del último trabajo en ser ensamblado que se corresponde con el valor de la función objetivo. El proceso para la resolución del problema se detalla a continuación: 1. Se denota j como el trabajo procesado en la posición j en la secuencia. El tiempo máximo de finalización del trabajo j en la primera etapa se calcula como: 𝐶1= 𝑚𝑎𝑥 {𝑟,𝐶}= 𝑚𝑎𝑥 {𝑟, 𝑚𝑎𝑥 𝑝+𝐶,} ( 1 ) Donde 𝐶,=0. 2. Una vez calculados los tiempos de finalización de los trabajos en la primera etapa, se asignan los trabajos en las máquinas de ensamblado siguiendo la regla de asignación elegida, ECT, teniendo en cuenta el tiempo de finalización del trabajo pendiente de asignar en la segunda etapa. Se define 𝑖∗ 𝑐𝑜𝑚𝑜 𝑖∗=𝑎𝑟𝑔𝑚𝑖𝑛,…,𝐶2, siendo j el último trabajo procesado en la máquina 𝑖 y k el trabajo pendiente de asignar: 𝐶2,= 󰇱 C1+𝑎𝑡 𝑠𝑖 𝑪𝟏𝒌−𝒔𝒋,𝒌>𝑪𝟐𝒊∗,𝒋 𝑠𝑖 𝑖=𝑖∗ 𝐶2∗,+𝑠,+𝑎𝑡 𝑠𝑖 𝑪𝟏𝒌≤ 𝑪𝟐𝒊∗,𝒋 𝑠𝑖 𝑖=𝑖∗ 𝐶, 𝑒𝑛 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜 ∀ 𝑘=1,…,𝑛 ( 2 ) Donde 𝐶,= 0 ∀ 𝑖=1…𝑚 Por último, el tiempo de finalización asociado a cada trabajo será: 𝐶=𝐶∗, ∀ 𝑖=1,…,𝑚 ∀ 𝑘 ( 3 ) y la función objetivo queda: 𝐹𝑂=min𝑚𝑎𝑥,…, 𝐶 ( 4 ) Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 16 - Si se propone una segunda secuencia: 𝑠= [1, 4, 2, 3, 5], el diagrama de Gantt resultante es el siguiente: En comparación con la primera secuencia representada, se observa que los cambios más significativos se dan en la segunda etapa. En este caso, los trabajos comienzan a ensamblarse antes, lo que implica que un orden diferente en el procesamiento de trabajos da lugar a distintas configuraciones de la segunda etapa y, por tanto, distinto valor de la función objetivo. Por otro lado, también se observan intervalos mayores entre el ensamblado de un trabajo y del siguiente. Por último, se comprueba que el valor de la función objetivo en este caso es ligeramente menor que el proporcionado por la primera secuencia. Todas estas características serán de vital importancia para diseñar el método de resolución Ilustración 10. Diagrama de Gantt de la segunda secuencia de ejemplo (Fuente: Elaboración propia) Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 17 4 METODOLOGÍA Al evaluar una secuencia diferente en el anterior apartado, se ha obtenido un mejor resultado de la función objetivo. Un aspecto fundamental es escoger una metodología de resolución que nos proporcione secuencias con buenos resultados. El criterio para escoger aplicar una metodología de resolución u otra se basa en el tiempo disponible para obtener un resultado. Por su parte, el tiempo disponible para obtener un resultado se refleja en el tiempo computacional que necesita la metodología para proporcionar una solución que a su vez depende directamente de las características del problema. 4.1 Reglas de despacho Las reglas de despacho que aplicaremos serán las propuestas por Komaki & Kayvanfar (2015). Siguiendo la clasificación del artículo citado, se dividen las reglas de despacho en los siguientes grupos:  Grupo I: Reglas de despacho fundamentadas en ordenar los índices, calculados para cada trabajo, en orden creciente según los tiempos de llegada y tiempos de proceso en la primera etapa. Para el cálculo de los distintos índices se tienen en cuenta los tiempos de proceso (𝑝) y las fechas de llegada (𝑟). o 𝐼: En el artículo anteriormente mencionado, se distingue entre dos formas de ordenar los trabajos teniendo en cuenta los tiempos de llegada en cada una de las máquinas de la primera etapa. La primera de ellas consiste en calcular el índice de cada trabajo tomando el valor máximo de tiempo de llegada de entre todos los componentes pertenecientes a un mismo trabajo y la segunda tomando el valor mínimo. En el problema abordado, no hay fechas de llegada para todos los componentes, únicamente para el componente adquirido a un proveedor externo, por lo que sólo hay asociada una fecha de llegada a cada trabajo. Por tanto, se resume el primer y segundo índice en el siguiente: 𝐼(𝑗)=𝑟 ∀ 𝑗 ( 5 ) Una vez calculados los índices para cada trabajo, se ordenan en orden creciente según el valor de su índice. o 𝐼: Este indicador consiste en tomar para cada trabajo el máximo entre el tiempo de llegada del componente suministrado externamente y el mayor tiempo de proceso de Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 18 entre los componentes que se procesan. 𝐼(𝑗)=max󰇥𝑟,𝑚𝑎𝑥,…,𝑝󰇦 ∀ 𝑗 ( 6 ) o 𝐼: Usando las últimas ideas se calcula este índice como el máximo entre el tiempo de llegada del tercer componente y el tiempo de proceso medio de los componentes procesados. 𝐼(𝑗)=max󰇥𝑟,∑    󰇦 ∀ 𝑗 ( 7 ) o 𝐼: De la misma manera que el anterior, pero tomando el mínimo de entre la fecha de llegada del componente externo y el tiempo de proceso medio. 𝐼(𝑗)=min󰇥𝑟,∑    󰇦 ∀ 𝑗 ( 8 ) o 𝐼: El cálculo de este indicador es el antagónico al 𝐼, es decir, se toma el mínimo de entre las opciones. 𝐼(𝑗)=min󰇥𝑟,𝑚𝑎𝑥,…,𝑝󰇦 ∀ 𝑗 ( 9 ) o 𝐼: Para calcular este indicador se necesita tener en cuenta la carga de trabajo de cada una de las máquinas de la primera etapa y seleccionar, para cada trabajo, el tiempo de proceso que pertenezca a la máquina con mayor carga. 𝐼(𝑗)=max𝑟,𝑝∗ ∀ 𝑗 ( 10 ) Donde 𝑇=∑𝑝   ∀ 𝑖 tomando como 𝑖∗ aquella máquina con mayor 𝑇. Una vez calculados para cada uno de los casos los índices, correspondientes a cada trabajo, se ordenan los trabajos en la secuencia en orden creciente según el valor de sus índices.  Grupo II: Reglas de despacho fundamentadas en minimizar el tiempo ocioso (o idle time) de la segunda etapa, ordenando los trabajos en orden decreciente según el valor de los índices calculados. En este grupo, se tienen en cuenta los tiempos de proceso y de ensamblado. o 𝐼: Los indicadores se corresponden al tiempo de ensamblado de cada trabajo. 𝐼(𝑗)=𝑎𝑡 ∀ 𝑗 ( 11 ) o 𝐼: En este caso, se toma como valor del indicador el máximo de entre los tiempos de proceso en la primera etapa y se suma el tiempo de ensamblado. Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 19 𝐼(𝑗)=𝑚𝑎𝑥,…,𝑝+𝑎𝑡 ∀ 𝑗 ( 12 ) o 𝐼: Para calcular este índice se tiene en cuenta de nuevo el concepto de carga de trabajo en la primera etapa y se suma el tiempo de ensamblado. 𝐼(𝑗)=𝑎𝑡+∑    ∀ 𝑗 ( 13 ) o 𝐼: El último índice de este grupo se calcula como el mayor tiempo de proceso de entre los tiempos de proceso de la primera etapa más el tiempo de ensamblado. 𝐼(𝑗)=𝑝∗+𝑎𝑡 ∀ 𝑗 ( 14 ) Donde 𝑇=∑𝑝   ∀ 𝑖 tomando como 𝑖∗ aquella máquina de la primera etapa mayor 𝑇. De nuevo se genera la secuencia ordenando los trabajos según el valor de los índices proporcionados por cada regla, en este caso en orden decreciente.  Grupo III: En último lugar, las reglas de despacho propuestas en este tercer grupo consideran los tiempos de proceso de la primera etapa, fechas de llegada y tiempos de ensamblado en la segunda etapa. o 𝐼(𝑗): Se toma el máximo de entre los tiempos de proceso en la primera etapa y el tiempo de llegada del tercer componente, y se suma el tiempo de ensamblado. 𝐼(𝑗)=max󰇥𝑟,𝑚𝑎𝑥,…,𝑝󰇦+𝑎𝑡 ( 15 ) o 𝐼(𝑗): Para el cálculo de este indicador se toma el máximo de entre la carga de trabajo aportada por el trabajo en la primera etapa y el instante de llegada del componente suministrado externamente, y se suma el tiempo de ensamblado 𝐼(𝑗)=max󰇡𝑟,∑    󰇢+𝑎𝑡 ∀ 𝑗 ( 16 ) o 𝐼(𝑗): Por último, este indicador se calcula teniendo en cuenta los instantes de llegada del componente suministrado externamente y el tiempo de proceso del componente perteneciente a la máquina de la primera etapa con mayor suma de tiempos de proceso. 𝐼(𝑗)=max𝑟,𝑝∗+𝑎𝑡 ∀ 𝑗 ( 17 ) Donde 𝑇=∑𝑝   ∀ 𝑖 tomando como 𝑖∗ aquella máquina de la primera etapa con mayor 𝑇. Por último, se vuelven a secuenciar los trabajos considerando los índices en orden Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 20 creciente. Se puede resaltar la imposibilidad de considerar los tiempos de setup en las reglas de despacho adaptadas de Komaki & Kayvanfar (2015) ya que primero se calcula el indicador, luego se ordenan y, posteriormente, se determina el trabajo a asignar. Por tanto, no es posible conocer el tiempo de preparación de antemano. 4.2 Heurística Constructiva Tras aplicar las reglas de despacho, la siguiente metodología a aplicar es un procedimiento heurístico. Se elige la heurística constructiva CH propuesta en Talens et al. (2020) para ser adaptada y resolver el problema estudiado en este trabajo. La idea de la heurística CH, tal y como se explica en Talens et al. (2020), consiste en construir una secuencia de forma recurrente seleccionando trabajos que aún no hayan sido secuenciados e ir añadiéndolos a la secuencia parcial. Como también se indica en el artículo mencionado, la clave de estos procedimientos algorítmicos está en diseñar un indicador ψ que mida la idoneidad de un trabajo que no ha sido secuenciado para ser el próximo en ser añadido a la secuencia parcial. El indicador ψ consistirá en una función lineal dependiente del tiempo ocioso (o idle time) inducido y de otro indicador CT al añadir el trabajo que se esté considerando, definido como la contribución total que supone el trabajo. Además de todo esto, se añade un coeficiente a que aportará mayor o menor importancia al idle time que suponga el trabajo. Este coeficiente se obtiene experimentalmente y en Talens et al. (2020) se probaron distintos valores de a para un conjunto de 10 instancias resultando generar mejores soluciones a = 5. Por tanto, las pruebas del algoritmo se harán con el coeficiente igualado a este valor. Además, para adaptar la heurística a las restricciones delproblema considerado en este trabajo, deben introducirse las fechas de llegada y los tiempos de setup anticipatorios dependientes de la secuencia. En primer lugar, las fechas de llegada pasarán a formar parte del cálculo del tiempo de finalización en la primera etapa del trabajo que se esté evaluando (𝜔). Por tanto, 𝐶 se calcula de la siguiente manera: 𝐶𝜔≔max max 󰇥𝐶1+𝑝,󰇦,𝑟 ( 18 ) Tiene lógica tomar como instante final de proceso en la primera etapa para cada trabajo el valor que sea mayor entre el tiempo de finalización de los componentes que se procesan o de llegada del componente adquirido externamente. Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 27 Tabla 4. ARPD por cada regla de despacho Tras la presentación de estos resultados calculados sobre todas las instancias, se observa que, de forma general, las reglas de despacho pertenecientes al primer grupo (de 𝐼 𝑎 𝐼) proporcionan valores de la función objetivo (makespan) en torno al 4% de desviación con respecto al mínimo, las del segundo grupo (𝐼 𝑎 𝐼) valores con el 2,60% de desviación aproximadamente y, por último, las del último grupo que proporcionan valores alrededor del 2,50% de desviación. Analizados los valores por grupos de reglas de despacho establecidos en función de los datos considerados para formar el indicador, se observa que en general las del tercer grupo donde se consideran datos de las dos etapas proporcionan mejores resultados. Sin embargo, analizando por separado cada una de las reglas de despacho destaca significativamente la 𝐼 cuyo porcentaje de desviación relativa media es de 0,75% con respecto al mínimo proporcionado por las reglas de despacho. Este hecho tiene su explicación en la generación de los tiempos de ensamblado (𝑎𝑡 ∈ 𝑈[1,100·𝑚·2]) cuyo rango de datos es mucho mayor que los tiempos de proceso de la primera etapa, por lo que construir la solución teniendo en cuenta sólo los tiempos de ensamblado justifica la mejora en los resultados. Si se analiza la evolución del valor promedio de cada regla de despacho en función del número de trabajos se diferencian claramente dos comportamientos diferentes en la evolución del ARPD. RD ARPD RD ARPD RD ARPD 𝑰 𝟏 4.603 𝑰 𝟔 4.603 𝑰 𝟏𝟏 2.0107 𝑰 𝟐 4.603 𝑰 𝟕 0.7529 𝑰 𝟏𝟐 2.0107 𝑰 𝟑 4.603 𝑰 𝟖 3.871 𝑰 𝟏𝟑 3.6359 𝑰 𝟒 3.0426 𝑰 𝟗 2.7072 𝑰 𝟓 3.8649 𝑰 𝟏𝟎 2.9884 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 28 Mientras que en instancias de un determinado número de trabajos se produce un empeoramiento con respecto a la cantidad de trabajos anterior, en los resultados proporcionados por ciertas reglas de despacho ocurre lo contrario. Para ejemplificar esto que sucede, se observa que las reglas 𝐼,𝐼,𝐼,𝐼,𝐼,𝐼,𝐼,𝐼 𝑒 𝐼 (todas pertenecientes al primer y tercer grupo) proporcionan un valor promedio peor para instancias de 40 trabajos con respecto a las de 30 mientras que el resto de reglas se comportan de manera opuesta generando mejores resultados para las instancias de 40 trabajos. Este comportamiento opuesto también se observa en el cambio de 40 a 50 trabajos, pero de manera inversa, y, en este caso, las reglas del primer y tercer grupo mejoran con respecto a resultados para instancias de 40 trabajos. Por tanto, podemos concluir que las reglas del primer y tercer grupo generan peores resultados para instancias de 40 trabajos respecto a las de 30, mejoran para instancias de 50 respecto a las de 40 y se mantienen prácticamente constantes entre las instancias de 60 y 70 trabajos. Sin embargo, ocurre lo contrario con las reglas del segundo grupo. Otro parámetro que puede revelar resultados interesantes es el parámetro α, con el que se han generado los valores de las fechas de llegada para el componente suministrado externamente. En la gráfica que se muestra a continuación, se observan claramente dos tendencias: ascenso en el valor del ARPD y, por tanto, empeoramiento de las soluciones a medida que aumenta el valor de α o por el contrario descenso y por tanto mejora en los resultados según aumenta el valor de α. Por un lado, los ARPD de las reglas 𝐼,𝐼,𝐼,𝐼,𝐼,𝐼,𝐼 evolucionan de manera descendente a medida que 0 1 2 3 4 5 6 7 8 30 40 50 60 70 ARPD NÚMERO DE TRABAJOS EVOLUCIÓN DEL ARPD POR RD EN FUNCIÓN DE n ARPD_I1 ARPD_I2 ARPD_I3 ARPD_I4 ARPD_I5 ARPD_I6 ARPD_I7 ARPD_I8 ARPD_I9 ARPD_I10 ARPD_I11 Ilustración 15. Gráfico sobre la evolución del ARPD en función del número de trabajos Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 29 aumenta el valor de α, lo que indica que a medida que aumenta el valor de las fechas de llegada estas reglas generan mejores resultados. Esto se debe a que todas las reglas anteriormente mencionadas tienen en cuenta en el cálculo del indicador las fechas de llegada y que, al aumentar el valor de estas, tienen mayor peso en el modelo y, por tanto, más necesario se hace tenerlas en cuenta para construir la secuencia. Por otro lado, el ARPD de las reglas 𝐼,𝐼,𝐼,𝐼 𝑒 𝐼 empeora a medida que aumenta el valor de α. En el caso de la 𝐼, el cálculo del indicador tiene más probabilidad de que se construya teniendo en cuenta el tiempo de proceso del componente, según aumenta el rango en el que se generan las fechas de llegada. El resto de reglas no tienen en cuenta las fechas de llegada, por lo que lógicamente, al aumentar el rango de valores que pueden tomar, pasan a tener mayor importancia en el modelo y, al no tenerse en cuenta, aumentan los valores de ARPD. 5.2.2 Heurísticas Como se ha mencionado anteriormente, la complejidad y el diseño de los métodos aplicados a un problema determina la calidad de las soluciones proporcionadas. En el caso de los procedimientos heurísticos, se espera que proporcionen mejores resultados que las reglas de despacho propuestas. Los resultados obtenidos con respecto al mínimo proporcionado por los procedimientos heurísticos y los de las búsquedas locales son: 0 1 2 3 4 5 6 7 0.6 0.8 1 ARPD α EVOLUCIÓN DEL ARPD POR RD EN FUNCIÓN DE α ARPD_I1 ARPD_I2 ARPD_I3 ARPD_I4 ARPD_I5 ARPD_I6 ARPD_I7 ARPD_I8 ARPD_I9 ARPD_I10 ARPD_I11 Ilustración 16. Gráfico sobre la evolución del ARPD en función del parámetro α Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 30 Tabla 5. ARPD de las heurísticas constructivas y búsquedas locales CH ARPD ACPU CH+BL ARPD ACPU CH_V1 0.0157 0.0261 CH_V1_BI 0.0041 10.8506 CH_V2 0.0155 0.0268 CH_V2_BI 0.0042 10.8556 CH_V3 0.01532 0.043 CH_V3_BI 0.0039 10.8977 CH_V4 0.01526 0.0415 CH_B4_BI 0.004 10.8845 Repasando las distintas versiones, en la primera de ellas, se calcula el indicador de carga teniendo en cuenta solo los tiempos de ensamblado repercutido al producto de las máquinas de la primera etapa y la segunda como en Talens et al. (2020). En la segunda versión, se modifica el denominador del indicador haciendo que los tiempos de ensamblado sólo afecten a la segunda etapa. Entre la primera y la segunda versión, se observa una ligera mejoría, al considerar únicamente las máquinas de la segunda etapa en el cálculo de CT. Esto puede indicar que, en el cálculo del indicador, la primera etapa no tiene tanta influencia como la segunda. En la tercera y cuarta versión, se introducen los tiempos de preparación (setups), no tenidos en cuenta hasta ahora por ningún método, en el cálculo del indicador CT. De nuevo, en este caso es resulta más exitoso calcular el indicador de carga sólo en base a las máquinas de la segunda etapa. En cuanto a las distintas versiones de las heurísticas, se han obtenido los resultados esperados, ya que los valores de la función objetivo han ido mejorando a medida que se han ido introduciendo las restricciones del modelo en el algoritmo, obteniendo los mejores resultados en las versiones 3 y 4. Por otro lado, las soluciones obtenidas por cada una de las versiones de la heurística han sido alimentadas a un método de búsqueda local. Como es de esperar, la aplicación de búsquedas locales proporciona una mejora de los resultados en todas las versiones de la heurística, aunque, como se observa en la Tabla 5, la mejor combinación es la que resulta de aplicar la búsqueda local Best Improvement a la solución obtenida por la versión 3. Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 31 En el caso de los procedimientos heurísticos se observa una tendencia bastante uniforme en la evolución del ARPD de todos los procedimientos, lo que indica que el comportamiento de los algoritmos es independiente del tamaño del problema y que mejoran sus resultados a medida que aumenta el número de trabajos. Ilustración 18. Gráfico sobre la evolución del ARPD de las heurísticas junto con búsqueda local en función del número de trabajos 0 0.001 0.002 0.003 0.004 0.005 0.006 0.007 30 40 50 60 70 ARPD TRABAJOS EVOLUCIÓN DEL ARPD DE HEURÍSTICA+BL EN FUNCIÓN DE n ARPD CH_V1_BI ARPD CH_V2_BI ARPD CH_V3_BI ARPD CH_V4_BI Ilustración 17. Gráfico sobre la evolución del ARPD de las heurísticas en función del número de trabajos 0 0.005 0.01 0.015 0.02 0.025 0.03 30 40 50 60 70 ARPD TRABAJOS EVOLUCIÓN DEL ARPD DE LAS HEURÍRSTICAS EN FUNCIÓN DE N ARPD CH_V1 ARPD CH_V2 ARPD CH_V3 ARPD CH_V4 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 32 En el caso de los procedimientos heurísticos junto con la búsqueda local, generan resultados más dispares entre ellos, aunque tienden a la mejora de resultados según aumenta el número de trabajos de manera general. Sin embargo, aunque el ARPD promedio de la versión 3 más la búsqueda local es mejor en general que el resto, según se muestra en la Tabla 5, para las instancias de 40 produce mejores resultados la versión 2 y para las de 70 trabajos la versión 4. Ilustración 19. Gráfico sobre la evolución del ARPD de las heurísticas en función del parámetro α En cuanto a los resultados segmentados en función del valor de α se obtiene que los mejores resultados obtenidos por todas las versiones de la heurística se producen para α=0,8. 0.013 0.0135 0.014 0.0145 0.015 0.0155 0.016 0.0165 0.017 0.6 0.8 1 ARPD α EVOLUCIÓN DEL ARPD DE LAS HEURÍSTICAS EN FUNCIÓN DE α ARPD CH_V1 ARPD CH_V2 ARPD CH_V3 ARPD CH_V4 0 0.001 0.002 0.003 0.004 0.005 0.006 0.6 0.8 1 ARPD α EVOLUCIÓN DEL ARPD DE LAS HEURÍSTICAS+BL EN FUNCIÓN DE α ARPD CH_V1_BI ARPD CH_V2_BI ARPD CH_V3_BI ARPD CH_V4_BI Ilustración 20. Gráfico sobre la evolución del ARPD de las heurísticas junto con búsqueda local en función del parámetro α Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 33 Es preciso comentar que mientras que las versiones 1 y 3 con búsqueda local proporcionan mejores resultados para α=0’8, en el caso de las versiones 2 y 4 se generan mejores resultados con respecto al resto de versiones sin aplicar búsqueda local. En el caso de la evolución del ARPD de las heurísticas con búsqueda local en función del parámetro α, se observa que proporcionan de forma general mejores resultados para instancias con α=1. Esto implica que, aunque la solución de partida para la búsqueda de vecinos con α=1 es peor que para α=0’8, la solución se encuentra ubicada en una mejor zona del espacio de soluciones, por lo que la búsqueda local resulta más exitosa para α=1. Por último, en la Tabla 5, también se presentan los resultados obtenidos del tiempo promedio de cómputo (ACPU). Como era de esperar, el tiempo de cómputo aumenta en los procedimientos que incluyen búsqueda local debido a la cantidad de inserciones realizadas y, por tanto, secuencias evaluadas. Sin embargo, es importante considerar adecuadamente el contexto en el que se encuentre el modelo para saber si es interesante invertir más tiempo en encontrar una solución mejor. Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 34 6 CONCLUSIONES La educación es el vestido de gala para asistir a la fiesta de la vida - Miguel Rojas Sánchez- En este Trabajo Fin de Grado se ha tratado un modelo de programación de la producción basado en el ensamblado de componentes, siendo uno de ellos suministrado por un proveedor externo, con el objetivo de minimizar el makespan o tiempo necesario para completar todos los trabajos. En la literatura se han estudiado modelos similares, aunque con distintas restricciones. Se han presentado dos metodologías para la resolución del problema propuesto. En primer lugar, se han adaptado las reglas de despacho propuestas en Komaki & Kayvanfar (2015) a las restricciones presentadas. Las reglas de despacho consisten en el cálculo de un indicador para cada trabajo y la posterior ordenación de los mismos siguiendo un criterio ascendente o descendente de secuenciación respecto al indicador. Dichas reglas de despacho se han clasificado en tres grupos diferentes en función de los datos que tuviera en cuenta del problema, resultando las del segundo grupo las que mejores resultados han aportado. En segundo lugar, se ha adaptado la Fast Constructive Heuristic, propuesta en Talens et al. (2021) para el problema sin restricciones, al problema con fechas de llegada del componente suministrado externamente y con tiempos de setup dependientes de la secuencia para la segunda etapa, que se ha tratado a lo largo de este trabajo. Además de la versión propuesta en Talens et al. (2021), se han analizado tres versiones más afectando al cálculo del indicador de carga. Como ha podido verse en el análisis de las distintas versiones, la versión cuatro ha resultado mejor en promedio que el resto. En tercer lugar, se han mejorado las soluciones aportadas por las distintas versiones de la heurística mediante la aplicación de un método de búsqueda local de vecinos basado en inserción. La exploración de vecinos ha consistido en la evaluación de un número concreto de secuencias vecinas calculado en base al total de trabajos de cada instancia con el objetivo de no dilatar demasiado el tiempo de cómputo. La mejor combinación de heurística con la búsqueda local ha resultado ser la tercera. Como futuras líneas de trabajo, sería interesante adaptar otras heurísticas existentes en la literatura para problemas relacionados y llevar a cabo una evaluación computacional en la que se comparen con los métodos propuestos en este trabajo. Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 35 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 36 7 REFERENCIAS Al-Anzi, F., & Allahverdi, A. (2006). A Hybrid Tabu Search Heuristic for the Two-Stage Assembly. International Journal of Production Research. Framinan J. M., Perez-Gonzalez, P., & Fernandez-Viagas, V. ((2019)). Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures. European Journal of Operational Research. Graham, R., Lawler , E., Lenstra, J., & Kan , A. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. In Annals of Discrete Mathematics, 287- 326. Komaki, G., & Kayvanfar, V. (2015). Grey Wolf Optimizer algorithm for the two-stage assembly flow shop scheduling problem with release time. Journal of Computational Science. Sung, C., & Juhn, J. (2009). Makespan minimization for a 2-stage assembly scheduling problem subject to component available time constraint. Int. J. Production Economics. Talens, C., Fernandez-Viagas, V., Perez-Gonzalez, P., & Framinan, J. (2020). New efficient constructive heuristics for the two-stage multi-machine assembly scheduling problem. Computers & Industrial Engineering. Talens, C., Fernandez-Viagas, V., Perez-Gonzalez, P., & Framinan, J. (2021). New hard benchmark for the 2-stage multi-machine assembly scheduling. Computers & Industrial Engineering. Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 43 8.2 Archivo de Heurísticas Constructivas from scheptk.scheptk import * from scheptk.util import * import numpy as np import matplotlib.pyplot as plt from untitled0 import * import copy import time def CH_V1(instancia,arrival_times): C1_i=[0 for i in range(instancia.m1)] C2_i=[[0 for i in range(instancia.jobs)] for i in range(instancia.m2)] pi=[] U=[j for j in range (instancia.jobs)] psi_j=[] a=5 indice=[] inicio=time.time() for j in range(instancia.jobs): for wj in (U): C1_wj=max(max(C1_i[i]+instancia.pt[i][wj] for i in range(instancia.m1)),arrival_times[wj]) if len(pi)==0: IT_j=max(C1_wj-min([max(C2_i[i]) for i in range(instancia.m2)])-instancia.sjk[0][wj],0) else: IT_j=max(C1_wj-min([max(C2_i[i]) for i in range(instancia.m2)])- instancia.sjk[np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])+1][wj],0) CT_j=(instancia.ass_time[wj]/instancia.m1*instancia.m2) psi_j.append(a*IT_j+CT_j) indice.append(wj) C1_i=[C1_i[i]+instancia.pt[i][indice[np.argmin(psi_j)]] for i in range(instancia.m1)] Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 44 if len(pi)==0: b=instancia.sjk[0][indice[np.argmin(psi_j)]] else: b=instancia.sjk[np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])+1][indice[np.argmin(psi_j)]] if min([max(C2_i[i]) for i in range(instancia.m2)])<max(max(C1_i),arrival_times[indice[np.argmin(psi_j)]])-b: C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][indice[np.argmin(psi_j)]]=max(arrival_times[indice[np.argmin(psi_j)]],max( C1_i))+instancia.ass_time[indice[np.argmin(psi_j)]] else: C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][indice[np.argmin(psi_j)]]=C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])]+b+instancia.ass_time[indice[np.argmin(psi_j)]] #print(indice) pi.append(indice[np.argmin(psi_j)]) #print(pi) U.remove(indice[np.argmin(psi_j)]) psi_j.clear() indice.clear() t_computo=time.time()-inicio return pi, t_computo def CH_V3(instancia,arrival_times): C1_i=[0 for i in range(instancia.m1)] C2_i=[[0 for i in range(instancia.jobs)] for i in range(instancia.m2)] pi=[] U=[j for j in range (instancia.jobs)] psi_j=[] a=5 Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 45 indice=[] inicio=time.time() for j in range(instancia.jobs): for wj in (U): C1_wj=max(arrival_times[wj], max(C1_i[i]+instancia.pt[i][wj] for i in range(instancia.m1))) if len(pi)==0: IT_j=max(C1_wj-instancia.sjk[0][wj]-min([max(C2_i[i]) for i in range(instancia.m2)]),0) CT_j=(instancia.ass_time[wj]+instancia.sjk[0][wj])/instancia.m1*instancia.m2 else: IT_j=max(C1_wj-instancia.sjk[np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])+1][wj]-min([max(C2_i[i]) for i in range(instancia.m2)]),0) CT_j=(instancia.ass_time[wj]+instancia.sjk[np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])+1][wj])/instancia.m1*instancia.m2 psi_j.append(a*IT_j+CT_j) indice.append(wj) C1_i=[C1_i[i]+instancia.pt[i][indice[np.argmin(psi_j)]] for i in range(instancia.m1)] if len(pi)==0: b=instancia.sjk[0][indice[np.argmin(psi_j)]] else: b=instancia.sjk[np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])+1][indice[np.argmin(psi_j)]] if min([max(C2_i[i]) for i in range(instancia.m2)])<max(max(C1_i),arrival_times[indice[np.argmin(psi_j)]])-b: C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][indice[np.argmin(psi_j)]]=max(arrival_times[indice[np.argmin(psi_j)]],max( C1_i))+instancia.ass_time[indice[np.argmin(psi_j)]] else: C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][indice[np.argmin(psi_j)]]=C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])]+b+instancia.ass_time[indice[np.argmin(psi_j)]] Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 46 pi.append(indice[np.argmin(psi_j)]) U.remove(indice[np.argmin(psi_j)]) psi_j.clear() indice.clear() psi_j.clear() indice.clear() t_computo=time.time()-inicio return pi, t_computo def CH_V2(instancia,arrival_times): C1_i=[0 for i in range(instancia.m1)] C2_i=[[0 for i in range(instancia.jobs)] for i in range(instancia.m2)] pi=[] U=[j for j in range (instancia.jobs)] psi_j=[] a=5 indice=[] inicio=time.time() for j in range(instancia.jobs): for wj in (U): C1_wj=max(arrival_times[wj], max(C1_i[i]+instancia.pt[i][wj] for i in range(instancia.m1))) if len(pi)==0: IT_j=max(C1_wj-min([max(C2_i[i]) for i in range(instancia.m2)])-instancia.sjk[0][wj],0) else: IT_j=max(C1_wj-min([max(C2_i[i]) for i in range(instancia.m2)])- instancia.sjk[np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])+1][wj],0) CT_j=instancia.ass_time[wj]/instancia.m2 psi_j.append(a*IT_j+CT_j) indice.append(wj) Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 47 C1_i=[C1_i[i]+instancia.pt[i][indice[np.argmin(psi_j)]] for i in range(instancia.m1)] if len(pi)==0: b=instancia.sjk[0][indice[np.argmin(psi_j)]] else: b=instancia.sjk[np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])+1][indice[np.argmin(psi_j)]] if min([max(C2_i[i]) for i in range(instancia.m2)])<max(max(C1_i),arrival_times[indice[np.argmin(psi_j)]])-b: C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][indice[np.argmin(psi_j)]]=max(arrival_times[indice[np.argmin(psi_j)]],max( C1_i))+instancia.ass_time[indice[np.argmin(psi_j)]] else: C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][indice[np.argmin(psi_j)]]=C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])]+b+instancia.ass_time[indice[np.argmin(psi_j)]] pi.append(indice[np.argmin(psi_j)]) U.remove(indice[np.argmin(psi_j)]) psi_j.clear() indice.clear() psi_j.clear() indice.clear() t_computo=time.time()-inicio return pi, t_computo def CH_V4(instancia,arrival_times): C1_i=[0 for i in range(instancia.m1)] C2_i=[[0 for i in range(instancia.jobs)] for i in range(instancia.m2)] pi=[] U=[j for j in range (instancia.jobs)] psi_j=[] a=5 indice=[] inicio=time.time() Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 48 for j in range(instancia.jobs): for wj in (U): C1_wj=max(arrival_times[wj], max(C1_i[i]+instancia.pt[i][wj] for i in range(instancia.m1))) if len(pi)==0: IT_j=max(C1_wj-min([max(C2_i[i]) for i in range(instancia.m2)])-instancia.sjk[0][wj],0) CT_j=(instancia.ass_time[wj]+instancia.sjk[0][wj])/instancia.m2 else: IT_j=max(C1_wj-min([max(C2_i[i]) for i in range(instancia.m2)])- instancia.sjk[np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])+1][wj],0) CT_j=(instancia.ass_time[wj]+instancia.sjk[np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])+1][wj])/instancia.m2 psi_j.append(a*IT_j+CT_j) indice.append(wj) C1_i=[C1_i[i]+instancia.pt[i][indice[np.argmin(psi_j)]] for i in range(instancia.m1)] if len(pi)==0: b=instancia.sjk[0][indice[np.argmin(psi_j)]] else: b=instancia.sjk[pi[-1]+1][indice[np.argmin(psi_j)]] if min([max(C2_i[i]) for i in range(instancia.m2)])<max(max(C1_i),arrival_times[indice[np.argmin(psi_j)]])-b: C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][indice[np.argmin(psi_j)]]=max(arrival_times[indice[np.argmin(psi_j)]],max( C1_i))+instancia.ass_time[indice[np.argmin(psi_j)]] else: C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][indice[np.argmin(psi_j)]]=C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])][np.argmax(C2_i[np.argmin([max(C2_i[i]) for i in range(instancia.m2)])])]+b+instancia.ass_time[indice[np.argmin(psi_j)]] pi.append(indice[np.argmin(psi_j)]) U.remove(indice[np.argmin(psi_j)]) psi_j.clear() indice.clear() psi_j.clear() Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 49 indice.clear() t_computo=time.time()-inicio return pi, t_computo 8.3 Best Improvement con criterio de parada import copy import time from untitled0 import * # BEST IMPROVEMENT def BI_I(instancia, seq,fo,arrival_times): # best_seq=copy.deepcopy(seq) best_obj=copy.deepcopy(fo) parada=(instancia.jobs*instancia.jobs)/5 inicio=time.time() iteraciones=0 for j in range (instancia.jobs): for k in range(instancia.jobs): if iteraciones<parada: if k!=j and k!=(j-1): vecino=copy.deepcopy(seq) vecino.pop(j) vecino.insert(k,seq[j]) c1,c2,seq=instancia.ct(vecino,arrival_times) obj=instancia.funcion_objetivo(c2) iteraciones=iteraciones+1 if obj<best_obj: # best_seq=copy.deepcopy(vecino) best_obj=obj Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 50 if iteraciones>parada: k=instancia.jobs j=instancia.jobs tiempo_computo=time.time()-inicio return best_obj, tiempo_computo 8.4 Reglas de despacho from scheptk.scheptk import * from scheptk.util import * import numpy as np import pdb import sys #===============================REGLAS DE DESPACHO======================================== #EN ORDEN CRECIENTE - reglas basadas en los arrival time y/o processing times def I1(instancia,arrival_times): seq=sorted_index_asc(arrival_times) return seq def I2(instancia,arrival_times): #de menor a mayor teniendo en cuenta la suma del tiempo de llegada y la del tiempo de proceso de las DPM I2=[max(arrival_times[j],max(instancia.pt[i][j] for i in range(instancia.m1))) for j in range(instancia.jobs)] Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 51 seq=sorted_index_asc(I2) return seq def I3(instancia,arrival_times): I3=[max(arrival_times[j],sum(instancia.pt[i][j] for i in range(instancia.m1))/instancia.m1) for j in range(instancia.jobs)] seq=sorted_index_asc(I3) return seq def I4(instancia,arrival_times): I4=[min(arrival_times[j],sum(instancia.pt[i][j] for i in range(instancia.m1))) for j in range(instancia.jobs)] seq=sorted_index_asc(I4) return seq def I5(instancia,arrival_times): I5=[min(arrival_times[j], max(instancia.pt[i][j] for i in range(instancia.m1))) for j in range(instancia.jobs)] seq=sorted_index_asc(I5) return seq def I6(instancia,arrival_times): aux=[sum(instancia.pt[i][j] for j in range(instancia.jobs)) for i in range(instancia.m1)] Ti=np.argmax(aux) I6=[max(arrival_times[j],instancia.pt[Ti][j]) for j in range(instancia.jobs)] seq=sorted_index_asc(I6) return seq Resolución de un Modelo Híbrido de Programación de la Producción mediante Algoritmos Heurísticos 52 # EN ORDEN DESCENDENTE - se tienen en cuenta tiempos de proceso y/o assembly times def I7(instancia,arrival_times): seq=sorted_index_desc(instancia.ass_time) return seq def I8(instancia,arrival_times): I8=[max(instancia.pt[i][j] for i in range(instancia.m1))+instancia.ass_time[j] for j in range(instancia.jobs)] seq=sorted_index_desc(I8) return seq def I9(instancia,arrival_times): I9=[instancia.ass_time[j]+sum(instancia.pt[i][j] for i in range(instancia.m1))/(instancia.m1) for j in range(instancia.jobs)] seq=sorted_index_desc(I9) return seq def I10(instancia,arrival_times): aux=[sum(instancia.pt[i][j] for j in range(instancia.jobs)) for i in range(instancia.m1)] Ti=np.argmax(aux) I10=[instancia.pt[Ti][j]+instancia.ass_time[j] for j in range(instancia.jobs)] seq=sorted_index_desc(I10) return seq #ORDEN CRECIENTE - se tienen en cuenta todas las propiedades: arrival times, processing times y assembly times def I11(instancia,arrival_times): I11=[max(arrival_times[k],max(instancia.pt[i][k] for i in range(instancia.m1)))+instancia.ass_time[k] for k in range (instancia.jobs)] seq=sorted_index_asc(I11)