Análisis del problema Distributed Permutation Flowshop con tiempos de transporte post-procesado

i Equation Chapter 1 Section 1 Proyecto Fin de Carrera Grado en Ingeniería de Organización Industrial Análisis del problema Distributed Permutation Flowshop con tiempos de transporte post-procesado Autor: David Bellido Rodríguez Tutor: Paz Pérez González Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2024 ii Proyecto Fin de Carrera Ingeniería de Organización Industrial Análisis del problema Distributed Permutation Flowshop con tiempos de transporte post-procesado Autor: David Bellido Rodríguez Tutor: Paz Pérez González Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2024 iv Proyecto Fin de Carrera: Análisis del problema Distributed Permutation Flowshop con tiempos de transporte post-procesado Autor: David Bellido Rodríguez Tutor: Paz Pérez González 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 vi A mi familia A mis maestros viii Resumen El presente Trabajo de Fin de Grado tiene como objetivo principal identificar el mejor método para generar soluciones a un problema Distributed Flowshop con permutación y tiempos de transporte post-procesado. Este entorno está compuesto por varias fábricas idénticas, en las que todos los trabajos que se procesan deben pasar por todas las máquinas siguiendo la misma ruta. Este problema ha ganado relevancia en la actualidad debido a la evolución de las necesidades industriales y los avances tecnológicos que han provocado una globalización y descentralización de la producción donde las empresas han distribuido sus operaciones en diferentes ubicaciones geográficas para aprovechar ventajas como menores costes laborales y proximidad con proveedores, entre muchas otras. La metodología implementada en este estudio incluye la aplicación de 22 heurísticas basadas en la heurística NEH, adaptadas específicamente para abordar este problema. El rendimiento de estos algoritmos se evaluó mediante el ARPD (Average Relative Percentage Deviation), que mide la desviación respecto a la mejor solución obtenida, y el ACT (Average CPU Time), que mide los tiempos de cómputo. Para llevar a cabo estas evaluaciones, se han desarrollado e implementado los algoritmos en lenguaje de programación Python. 1 1 INTRODUCCIÓN l presente proyecto se enfoca en determinar el método que aporte la mejor solución a un problema de Programación de la Producción en un entorno de Distributed Flowshop con restricción de permutación, tiempos de transporte post-procesado y con objetivo de minimizar el Total Delivery Time (TDT). En un entorno de Distributed Flowshop, se cuenta con un conjunto de fábricas idénticas, donde las máquinas y, por consiguiente, los tiempos de proceso de los trabajos en cada una de ellas son iguales también. El layout de las fábricas está basado en entornos Flowshop, es decir, talleres en los que cada trabajo debe pasar por una serie de estaciones de trabajo en un orden fijo y predefinido. Además, para la programación de la producción de este problema, es necesario tomar dos decisiones: la asignación de trabajos a las fábricas y la secuenciación de los trabajos dentro de cada una de las fábricas. Este estudio se centra en un problema particular, ya que considera los tiempos de transporte necesarios después de que cada trabajo se ha fabricado en una fábrica determinada. Así, se introduce el concepto de Delivery Time, que es el tiempo total en el que un trabajo se entrega al cliente, sumando su tiempo de finalización y el tiempo de transporte desde la fábrica hasta el cliente. El objetivo del estudio es el Total Delivery Time (TDT). Minimizar la suma de los tiempos de entrega de todos los trabajos es beneficioso para este tipo de problemas, ya que optimiza la eficiencia general y minimiza los tiempos de entrega acumulativos. Esto no solo mejora el cómputo global de los tiempos de entrega, sino que también organiza los trabajos de tal manera que la entrega individual de cada uno sea más rápida. Los trabajos se transportan de manera individual una vez completados, asegurando que cada producto llegue a su destino final en el menor tiempo posible. Esta metodología mejora la eficiencia del proceso de manufactura y logística, y, además, responde a las necesidades de un mercado cada vez más demandante y personalizado. Este trabajo se alinea con la filosofía de Toyota y su sistema de producción Just-in-time (JIT), analizado y comprendido a través del libro de (Ohno, 1988). Este sistema ha sido estudiado e introducido en muchas organizaciones, independientemente del tipo de industria, escala o fronteras nacionales. El Just-in-time significa que, en un proceso de flujo, las piezas necesarias para el ensamblaje llegan a la línea de ensamblaje en el momento exacto que se necesitan y solo en la cantidad necesaria. Una empresa capaz de establecer este sistema se acercará a un inventario de almacenamiento nulo. Aunque este sistema originó en la industria automotriz, es aplicable a cualquier otro tipo de organización. Como decía Taiichi Ohno, “Lo único que hacemos es mirar la línea de tiempo desde el momento en el que un cliente nos hace un pedido hasta el momento en el que recibimos el dinero. Y estamos reduciendo esa línea de tiempo eliminando los desperdicios que no agregan valor”. Este enfoque resalta de manera sencilla pero brillante la importancia de la mejora continua, aplicable a cualquier industria que implemente este método. Entre las diferentes empresas que implementan en la actualidad ese método se encuentra Apple, McDonald’s, Dell, entre muchas otras. El documento está estructurado de la siguiente forma: • Capítulo 2, Fundamentos teóricos. Se introduce el concepto de Programación de la Producción, se presenta la notación empleada, se exploran los diferentes entornos existentes, así como las restricciones y funciones objetivo más comunes. • Capítulo 3, Descripción del problema. Se describe de forma detallada el problema estudiado en este proyecto. Además, se explican las nuevas incorporaciones que se hacen al problema, tanto en términos de restricciones como de función objetivo, destacando su relevancia para el estudio. • Capítulo 4, Metodología. Se presentan un total de 22 heurísticas basadas en artículos relevantes que abordan el problema global estudiado. Además, se describen una serie de métodos de aceleración cuyo objetivo es reducir los tiempos de cómputo de las heurísticas. • Capítulo 5, Análisis de resultados. Se lleva a cabo la aplicación de las 22 heurísticas descritas en el capítulo anterior y se analizan exhaustivamente los resultados en base a dos índices de rendimiento, el ARPD (Average Relative Percentage Deviations), que mide la distancia respecto al mejor resultado E 2 obtenido, y el ACT (Average CPU Time) que mide el tiempo promedio de cómputo de cada una de las heurísticas. • Capítulo 6, Conclusiones. Finalmente, se presentan las conclusiones derivadas del estudio realizado, basadas en los resultados obtenidos en el capítulo anterior. Se discute el impacto de los hallazgos en el campo de la Programación de la Producción y se señalan posibles direcciones futuras para la investigación. 4 2 FUNDAMENTOS TEÓRICOS ara la correcta comprensión del estudio llevado a cabo en este documento, es primordial entender los fundamentos teóricos en los que está basado. El libro de (Framinan et al., 2014) proporciona la mayor parte de la información utilizada en este capítulo. Comenzando con la Programación de la Producción, esta se basa en asignar los diversos recursos de una empresa a la fabricación de una gama de productos solicitados por los clientes. Por otro lado, se encuentra la gestión de la producción, que es un proceso de gestión en el que se toman una gran cantidad de decisiones a lo largo del tiempo para garantizar la entrega de productos con la máxima calidad, el mínimo coste y tiempo de entrega. Estas decisiones van desde decisiones estratégicas, de alto impacto y a largo plazo, como decidir si una determinada planta fabricará o no un nuevo producto, hasta decisiones operativas, de corto plazo, de bajo nivel y de pequeño impacto, como qué producto será el próximo en fabricarse en cierta máquina del taller. Dada la diferente naturaleza y el momento de estas decisiones, y los diferentes responsables de la toma de decisiones involucrados, la gestión de la producción ha adoptado una estructura jerárquica en la que se resuelven sucesivamente los diferentes problemas de decisión. En la parte superior de esta estructura se encuentran las decisiones estratégicas, seguidas por las decisiones tácticas (a medio plazo) y finalmente por las decisiones operativas. Sin embargo, estas decisiones no son usualmente sencillas, y requieren de datos históricos o casuales para estimar cómo usar los recursos de manera óptima. Por lo tanto, se crea previamente un plan agregado de producción, en el que se estiman las familias o grupos de productos con uso similar de recursos y/o comportamiento respecto a la demanda que se pretende vender durante un periodo de tiempo determinado. Este plan agregado de producción no da ninguna indicación detallada de las ordenes de producción que deben enviarse al taller, ahí es donde entra la Programación de la Producción. En la programación de la producción se toman una serie de decisiones, generalmente a corto plazo, las cuales tratan de hacer coincidir los trabajos (tareas) que se van a ejecutar con los recursos disponibles de la empresa. A continuación, definimos la notación de algunos datos básicos presentes en la programación de la producción:  N={1,..,n} es el conjunto de trabajos o tareas a procesar. Se utilizan los índices j, k ∈ N para referenciar a los trabajos.  M={1,..,m} es el conjunto de máquinas que procesan los trabajos o tareas. Se utiliza el índice i ∈ M para referenciar a las máquinas.  𝑅𝑗 es el vector en el que se indica el orden (Ruta) en el que el trabajo j va a ser procesado.  𝑝𝑖𝑗 es el tiempo en el que la máquina i ∈ M está ocupada procesando el trabajo j ∈ N. Si es independiente de la máquina se denota como 𝑝𝑗. Además de esta notación básica, es fundamental contar con un sistema de clasificación estandarizado que permita describir y analizar de manera precisa los distintos problemas que pueden surgir. Un marco ampliamente reconocido y utilizado para este propósito es la clasificación de tres campos 𝛼|𝛽|𝛾 , desarrollada por (Graham et al., 1979). Este sistema proporciona una forma estructurada y concisa de representar la complejidad de los problemas de programación de tareas, facilitando la comunicación entre investigadores y la aplicación de soluciones específicas. Lo podemos ver en la Ilustración 1. Clasificación de los modelos de programación de la producción. P Ilustración 1. Clasificación de los modelos de programación de la producción (Framinan et al., 2014). La notación viene dada por tres componentes esenciales: ▪ 𝛼: se utiliza para describir la configuración de las máquinas en el entorno de producción. Dos de las configuraciones más comunes son el entorno de máquina única y el entorno de máquinas paralelas. El caso más sencillo es el de una única máquina, se denota como 𝛼 =1. En esta, cada trabajo debe pasar por la máquina realizando una única operación. Cuando tenemos m máquinas funcionando en paralelo se vuelve un entorno más complejo que el anterior, debido a la necesidad de asignar trabajos a múltiples máquinas y secuenciar dichos trabajos en cada una de ellas. Diferenciamos tres tipos: ▪ Idénticas: se denotan como 𝛼 =𝑃𝑚. Son máquinas paralelas idénticas entre sí, lo que quiere decir que sus tiempos de proceso 𝑝𝑗 no dependen de la máquina. ▪ Uniformes: se denotan como 𝛼 =𝑄𝑚. Son máquinas paralelas que funcionan a diferentes velocidades 𝑣𝑖 de tal manera que el tiempo de proceso de cada trabajo en cada máquina viene dado por 𝑝𝑖𝑗 =𝑝𝑗 𝑣𝑖 . ▪ No relacionadas: se denotan como 𝛼 =𝑅𝑚. Son máquinas paralelas todas diferentes entre sí, este es el caso más general de máquinas paralelas, cuyo tiempo de proceso de cada trabajo depende de la máquina a la que se haya asignado 𝑝𝑖𝑗. Por otro lado, tenemos el caso en el que cada máquina tiene un propósito diferente y en el que cada trabajo visita todas las máquinas ya que debe realizar una operación en cada una. Este es el entorno de los talleres. Dependiendo de la ruta de los trabajos 𝑅𝑗 diferenciamos diferentes talleres: ▪ Taller de flujo regular (Flowshop): se denota como 𝛼 =𝐹𝑚. En este caso, todos los trabajos tienen la misma ruta 𝑅𝑗=(1,2,..,𝑚),∀𝑗 ∈ 𝑁. ▪ Taller de trabajo (Job shop): se denota como 𝛼 =𝐽𝑚. En este caso, cada trabajo tiene una ruta diferente, por tanto 𝑅𝑗, ∀𝑗∈𝑁 son un dato necesario. ▪ Taller abierto (Open shop): se denota como 𝛼 = 𝑂𝑚. Este es el caso más general y complejo de los talleres, en él no hay ruta determinada para ninguno de los trabajos. ▪ Taller de flujo distribuido (Distributed Flowshop): se denota como 𝛼 =𝐷𝐹. En este caso, se dispone de un conjunto de fábricas idénticas donde cada una de ellas opera como un taller de flujo (Flowshop). Es decir, todos los trabajos tienen la misma ruta. ▪ 𝛽: incluye las características y restricciones específicas de los trabajos. Esto abarca tiempos de procesamiento, tiempos de llegada, fechas de vencimiento, restricciones de precedencia, y otros muchos aspectos que influencian el orden y la forma en que los trabajos deben ser programados. Adicionalmente, cuando el campo está vacío 𝛽 =∅, se asumen unas suposiciones generales: los trabajos están disponibles al principio del horizonte de programación, los trabajos no se pueden interrumpir, las máquinas están siempre disponibles, cada máquina puede hacer un trabajo a la vez y un trabajo puede ser realizado solo en una máquina, el buffer entre máquinas se supone infinito y el 6 tiempo de transporte es despreciable (Perez-Gonzalez et al., 2023) Dentro de este campo encontramos muchas restricciones diferentes, las más comunes son las siguientes: ▪ 𝛽 =𝑟𝑗: release dates. Son las fechas de llegada (disponibilidad) de los trabajos o tareas a la planta. ▪ 𝛽 =𝑑𝑗 : deadlines. Son fechas de entrega de los trabajos de obligado cumplimiento. Cuando no son de obligado cumplimiento no aparecen en el campo 𝛽 y se denota como 𝑑𝑗 (common due date). ▪ 𝛽 =𝑠𝑖𝑗: setup times. Son tiempos de preparación de la máquina i antes de procesar el trabajo j. Cuando dependen de la secuencia se denota como 𝛽 =𝑠𝑖𝑗𝑘 y cuando es independiente de la máquina se elimina el subíndice i. En los entornos taller encontramos otras restricciones como pueden ser: ▪ 𝛽 =𝑝𝑟𝑚𝑢. Es una restricción muy común en los talleres de flujo o flowshop, esta implica que la secuencia de trabajos es la misma para todas las máquinas. ▪ 𝛽 =𝑛𝑜−𝑖𝑑𝑙𝑒. Esta restricción no permite tiempos ociosos de las máquinas entre trabajos. Una vez que la máquina empieza a procesar el primer trabajo de su programa, no puede parar. ▪ 𝛽 =𝑛𝑜−𝑤𝑎𝑖𝑡. Esta restricción no permite que los trabajos puedan esperar entre máquinas o etapas. ▪ 𝛽 =𝑡𝑎𝑝. Esta restricción, aplicada en entornos de talleres distribuidos, implica que se deben considerar los tiempos de transporte post-procesado desde cada una de las fábricas para cada uno de los trabajos. Esta se explica más en detalle en el Capítulo 3. ▪ 𝛾: Indica el criterio de optimización, es decir, la métrica que se busca minimizar o maximizar. En programación de la producción, las funciones objetivo se clasifican en las categorías de coste, tiempo, calidad y flexibilidad, como se puede ver en la Ilustración 2.Ilustración 2. Categorías de los objetivos Ilustración 2. Categorías de los objetivos (Framinan et al., 2014). Dentro de este campo existen algunas medidas de rendimiento, entre las cuales encontramos: ▪ 𝐶𝑗: Tiempo de finalización del trabajo j (completion time). ▪ 𝐹𝑗: Tiempo de flujo del trabajo j (flowtime). Es el tiempo que el trabajo está dentro del entorno. Viene dado por 𝐹𝑗=𝐶𝑗−𝑟𝑗 ▪ 𝐿𝑗: Retraso del trabajo j (lateness). Mide lo tarde que se termina un trabajo con respecto a su fecha de entrega, tal que 𝐿𝑗= 𝐶𝑗−𝑑𝑗 ▪ 𝑇𝑗: Tardanza del trabajo j (tardiness). Si el trabajo se termina antes de su fecha de entrega, no pasa nada. 𝑇𝑗=max⁡{0,𝐿𝑗} ▪ 𝐸𝑗: Adelanto del trabajo j (earliness). Si el trabajo termina después de su fecha de entrega, no pasa nada. 𝐸𝑗=max⁡{0,−𝐿𝑗} ▪ 𝑈𝑗: Trabajo tarde (tardy job). 𝑈𝑗={1 0⁡ 𝑠𝑖⁡𝑇𝑗>0(𝐶𝑗>𝑑𝑗) 𝑒𝑛⁡𝑐𝑎𝑠𝑜⁡𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜 ▪ 𝐷𝑇𝑗: Delivery Time (Tiempo de entrega). Está directamente relacionado con la restricción tap, ya que representa el tiempo en el que el trabajo llega a su destino final, incluyendo el tiempo de transporte al tiempo de finalización. Este término y sus funciones objetivo asociadas serán exploradas en detalle en el Descripción del problema. Mediante estas medidas de rendimiento, obtenemos las posibles funciones objetivo usando dos formatos: el formato de maximización y el formato de sumatoria. ▪ No relacionados con fechas de entrega: o Max-form: 𝑓 = 𝑚𝑎𝑥 1≤𝑗≤𝑛⁡𝑔(𝐶𝑗) ➢ Makespan (Maximum Completion Time): 𝐶𝑚𝑎𝑥 = 𝑚𝑎𝑥 1≤𝑗≤𝑛⁡𝐶𝑗 ➢ Maximum Flowtime: max𝐹𝑗= 𝑚𝑎𝑥 1≤𝑗≤𝑛⁡𝐹𝑗 ➢ Maximum Delivery Time: max𝐷𝑇𝑗= 𝑚𝑎𝑥 1≤𝑗≤𝑛⁡𝐷𝑇𝑗 o Sum-form: 𝑓 =∑ 𝑔(𝐶𝑗) 𝑛 𝑗=1 ➢ Total Completion Time: ∑𝐶𝑗=∑ 𝐶𝑗 𝑛 𝑗=1 ➢ Total Flow time: ∑𝐹𝑗=∑ 𝐹𝑗 𝑛 𝑗=1 ➢ Total Delivery Time: ∑𝐷𝑇𝑗=∑𝐷𝑇𝑗 𝑛 𝑗=1 ▪ Relacionados con fechas de entrega: o Max-form: ➢ Maximum Lateness: max𝐿𝑗= 𝑚𝑎𝑥 1≤𝑗≤𝑛⁡𝐿𝑗 ➢ Maximum Tardiness: max𝑇𝑗= 𝑚𝑎𝑥 1≤𝑗≤𝑛⁡𝑇𝑗 ➢ Maximum Earliness: max𝐸𝑗= 𝑚𝑎𝑥 1≤𝑗≤𝑛⁡𝐸𝑗 o Sum-form: ➢ Total Lateness: ∑𝐿𝑗=∑ 𝐿𝑗 𝑛 𝑗=1 ➢ Total Tardiness: ∑𝑇𝑗= ∑ 𝑇𝑗 𝑛 𝑗=1 ➢ Total Earliness: ∑𝐸𝑗=∑ 𝐸𝑗 𝑛 𝑗=1 ➢ Number of tardy jobs: ∑𝑈𝑗=∑ 𝑈𝑗 𝑛 𝑗=1 8 El resultado final de este proceso es, idealmente, un programa o schedule el cual indica las fechas de comienzo y fin de cada trabajo en cada una de las máquinas. Es muy importante no confundir con el termino secuencia, esta indica el orden en el que cada trabajo comienza a procesarse en cada máquina. En general, a cada secuencia le corresponden infinitos programas, depende de la regla de asignación que se esté utilizando y de la codificación de la secuencia. Un programa que cumple con todas las restricciones y características del proceso productivo se conoce como programa admisible o feasible schedule. Además, cuando no es posible adelantar ninguna operación sin cambiar el orden en que alguna máquina procesa los trabajos y localmente (en cada máquina) cada trabajo está lo más a la izquierda posible para un orden dado, se conoce como un programa semiactivo o semi-active schedule (Perez-Gonzalez et al., 2023). 16 Ilustración 5. Representación R2 con regla de asignación Ai Como se muestra en la Ilustración 3 e Ilustración 4, cuando se trata con R1, dependiendo de la regla de asignación se obtendrá un Diagrama de Gantt o Schedule diferente. Sin embargo, para R2 independientemente de la regla de asignación, dada una secuencia con este formato, la asignación la da la propia secuencia. Es importante no confundir esto con la obtención de dicha secuencia, para la cual sí será necesario aplicar las reglas de asignación, como se explicará en la sección posterior. 4.4. NEH con formato R1Ai En el caso de las heurísticas NEH con la codificación de R1, las reglas de asignación influyen en la obtención de la función objetivo. Ya que, como se vio anteriormente, dependiendo de la regla de asignación empleada, se obtiene un Schedule diferente. En la Ilustración 6 podemos ver el pseudocódigo de esta heurística. Ilustración 6. NEH(R1,Ai) adaptada de (Fernandez-Viagas et al., 2018) Inicialmente se parte de una secuencia de trabajos ordenada de manera descendiente según la suma de sus tiempos de proceso. Posteriormente, se asigna a la secuencia parcial Π (con formato R1), el primer trabajo de esa secuencia ordenada. A continuación, se asigna el siguiente trabajo de la secuencia ordenada a la secuencia Π. Para ello, se construyen secuencias parciales en las que se asigna el trabajo en cada una de las posibles posiciones. La regla de asignación determinará en que fábrica y en que posición va cada trabajo de esas secuencia parciales, lo que permite evaluarlas y ver cuál de todas las l posiciones dentro de la secuencia Π obtiene los mejores resultados. M0 j0 j1 M1 j1 M2 M3 M4 j2 M5 R2Ai Secuencia ((j0,j1),(j3),(j2)) F0 j3 j2 F1 F2 j0 j3 Este proceso se repite hasta asignar todos y cada uno de los trabajos de la secuencia de partida. 4.5. NEH con formato R2Ai Al contrario que las heurísticas NEH con la codificación R1, cuando empleamos la codificación R2, las reglas de asignación influyen en la manera de obtener la secuencia, ya que, una vez obtenida esa secuencia en forma matricial, la obtención de la función objetivo es común para todas ellas. En la Ilustración 7 podemos ver el pseudocódigo de esta heurística. Ilustración 7. NEH(R2,Ai) adaptada de (Fernandez-Viagas et al., 2018) En este caso, también se parte de la misma secuencia ordenada de mayor a menor suma de tiempos de proceso. Sin embargo, no se asigna directamente el primer trabajo de esta a la secuencia parcial Π, ya que ahora está en formato R2. Es decir, se debe aplicar una regla de asignación para determinar en qué fábrica y en qué posición se colocará el trabajo. Así, Π=(Π1,…,Π𝑓), donde Π𝑓 representa las secuencias parciales de cada una de las fábricas. Asignamos el primer trabajo de la secuencia inicial. Para ello, se crean secuencias parciales Π𝑓 donde se inserta el trabajo en todas las posibles posiciones, o únicamente en la última posición de cada fabrica. Esto lo determinará la regla de asignación que se esté aplicando, la cual finalmente decidirá cuál de todas las secuencias parciales Π𝑓 es la mejor, y, por tanto, cuál es la mejor fábrica f y la mejor posición l para asignar ese trabajo. Este proceso se repite hasta asignar todos y cada uno de los trabajos de la secuencia de partida. 4.6. Métodos de aceleración Uno de los problemas principales de estas heurísticas es el tiempo de cómputo de estas, ya que requieren insertar los trabajos en cada una de las posiciones posibles en busca del mejor resultado. Esto puede implicar un tiempo de cómputo excesivo en muchas ocasiones. Para mitigar este problema, se han empleado algunos métodos de aceleración. Es importante destacar que estos métodos se han utilizado únicamente en la codificación R1, ya que la R2 es lo suficientemente rápida como para no requerir dichas modificaciones. El primer método se aplica a R1A1 y R1A2, que necesitan calcular el makespan insertando cada trabajo en la última posición de la fábrica seleccionada. Para evitar el cálculo de todos los Completion Times, 𝐶𝑗, se calcula únicamente el makespan del último trabajo colocado. De esta manera, se evita el tiempo de cómputo adicional que implicaría recalcular la secuencia al completo repetidamente. El segundo método consiste en utilizar la memoización, una técnica de optimización que se usa principalmente para acelerar tiempos de cómputo. Esta técnica, descrita por (Norvig, 1991), se basa en crear una función que permite recordar automáticamente los resultados de cálculos previos. 18 En este contexto, la memoización almacena en memoria los valores del objetivo calculado según la regla de asignación de una secuencia dada. Así, cuando la heurística NEH realiza los cálculos de la función objetivo con las diferentes permutaciones de la secuencia, evita recalcular lo que ya ha sido calculado anteriormente. Finalmente, para las reglas en las que no se especifica buscar la mejor posición del trabajo en la fábrica, se asigna siempre al final de la secuencia ya existente en esa fábrica. De tal manera que si tenemos una secuencia como ((j3,j1,j5), (j2)) si la regla de asignación determina que el trabajo j6 se asigna a la última fábrica, se inserta de la siguiente forma ((j3,j1,j5), (j2,j6)). Por el contrario, cuando se especifica insertar en la mejor posición, se prueba en cada una de las posibles posiciones dentro de cada fábrica, de tal manera que nos quedamos con la fábrica y la posición dentro de la fábrica que mejor resultados da. Este último enfoque, aplicado tanto para R1 como para R2, nos permite reducir tiempos de cómputo en las reglas de asignación que no especifiquen buscar la mejor posición posible. 20 5 ANÁLISIS DE RESULTADOS n este capítulo se examinan los resultados obtenidos al aplicar las 22 heurísticas descritas en el capítulo anterior al problema planteado en este estudio. Las pruebas pertinentes se llevaron a cabo utilizando Python como lenguaje de programación, junto con la librería schedule (Librería SCHEDULE – Grupo de Investigación Organización Industrial, n.d.). Todo el código utilizado está disponible en el Anexo A: Código de programación. 5.1. Instancias e índices de rendimiento Antes de comenzar con el análisis de los resultados obtenidos en este estudio, debemos definir las instancias utilizadas. Se han distinguido dos grupos de instancias: un grupo de instancias pequeñas formado por 34 combinaciones diferentes de los parámetros 𝑛 ∈{4,6,8,10,12,14,16}⁡,𝑚 ∈ {2,3,4,5},𝐹 ∈ {2,3,4}, y un grupo de instancias más grandes basadas en las instancias de (Taillard, 1993). En todas ellas, los tiempos de proceso, 𝑝𝑗, y los tiempos de transporte post-procesado, 𝑇𝐴𝑃𝑓𝑗, están generados utilizando una distribución uniforme en el rango [1,99]. Para el análisis de ambos tamaños se define el índice RPD (Relative Percentage Deviations) en Ecuación 4, siendo 𝑇𝐷𝑇𝑖ℎ el Total Delivery Time de la instancia i, con 𝑖 ∈[1,𝐼], para la heurística h, con ℎ ∈𝐻, siendo H el conjunto de heurísticas. Por otro lado, 𝐵𝑒𝑠𝑡𝑖𝐻 representa el mejor Total Delivery Time entre todas las heurísticas del conjunto H para esa instancia i. Adicionalmente, se define el 𝐶𝑇𝑖ℎ (CPU Time) cómo el tiempo de cómputo, medido en segundos, de la heurística h en la instancia i. Este nos permite evaluar la escalabilidad y la eficiencia computacional del algoritmo, especialmente en problemas reales donde el tiempo de ejecución pueda ser un limitador importante. 𝑅𝑃𝐷𝑖ℎ=𝑇𝐷𝑇𝑖ℎ−𝐵𝑒𝑠𝑡𝑖𝐻 𝐵𝑒𝑠𝑡𝑖𝐻×100 Ecuación 4. Indice RPD 5.2. Análisis instancias pequeñas Estas instancias se consideran como pruebas preliminares, que nos proporcionan una visión general del rendimiento y comportamiento de las heurísticas. Por tanto, se ha decidido no examinar todas las posibles combinaciones de los parámetros n, m y F. Esta información es útil para prever cómo funcionarán en instancias más grandes, que son las que se encuentran con mayor frecuencia en situaciones reales. Por ende, en vez de mostrar los RPD individuales de cada método en cada instancia, se muestran los ARPD (Average Relative Percentage Deviations), definido en Ecuación 5. Por otro lado, en lugar de los tiempos de cómputo individuales (CT), se utilizará el promedio de estos (ACT: Average CPU Time). 𝐴𝑅𝑃𝐷 =1 𝐼×∑𝑇𝐷𝑇𝑖−𝐵𝑒𝑠𝑡𝑖 𝐵𝑒𝑠𝑡𝑖 𝐼 𝑖=1 Ecuación 5. Índice ARPD Tras haber definido los parámetros de análisis, procedemos a presentar y analizar de manera detallada los resultados obtenidos, los cuales se muestran en la Tabla 1. E Tabla 1. ARPD y ACT para instancias pequeñas Los tiempos de cómputo promedio de cada heurística son notablemente reducidos, casi insignificantes. Esta característica hace que estas instancias de prueba sean ideales para obtener esos resultados preliminares de los que se hablaban en la introducción de esta sección. Se observa que la regla de asignación A9 muestra los mejores resultados para ambas representaciones de las soluciones, R1 y R2, siendo esta última ligeramente inferior a la primera. Además, se evidencia que, para la codificación R2, con excepción de las reglas A8, A9, A10 y A11, los demás resultados tienden a ser considerablemente peores, llegando hasta un 34.9% de diferencia con respecto al mejor de los resultados. En adición a esto último, las heurísticas R1A4 y R1A5 muestran resultados comparables a las mencionadas anteriormente, en contraste con las demás. A fin de complementar el análisis presentado en la Tabla 1, se incluye a continuación un diagrama de caja y bigotes que ofrece una representación visual de los índices RPD de cada heurística evaluada. Este diagrama ofrece una perspectiva más clara y visual de las disparidades en el rendimiento entre las distintas heurísticas, lo cual no solo revela las divergencias más marcadas, sino también las semejanzas en el rendimiento entre ellas. Ilustración 8. Diagrama de caja y bigote para instancias pequeñas (RPD) 5.3. Análisis instancias grandes En esta sección estudiaremos el conjunto de instancias de mayor tamaño, lo cual nos permite explorar cómo las heurísticas propuestas responden y se adaptan a problemas con una mayor complejidad estructural y de datos. Este análisis es crucial para evaluar la viabilidad y efectividad de las heurísticas en escenarios prácticos y realistas. 22 En este contexto, el objetivo es analizar cómo las diferentes heurísticas gestionan la optimización en instancias grandes, comparando tanto la calidad de las soluciones como los tiempos de cómputo. Comenzaremos analizando las primeras 70 instancias, que abarcan combinaciones entre n, m y F tal que: 𝑛 ∈ {20,50,100},𝑚∈{5,10,20} y 𝐹 ∈{2,3,4,5,6,7}. Esto resulta en 70 instancias para cada tamaño de fábrica, sumando un total de 420 instancias. A continuación, se muestran los resultados del índice ARPD para cada uno de los métodos en función de los parámetros n y m (ver Tabla 2 y Tabla 3) y en función del parámetro F (ver Tabla 4 y Tabla 5). De igual forma, se muestran los tiempos de cómputo (ACT) en la Tabla 6, Tabla 7, Tabla 8 y Tabla 9. Tabla 2. ARPD de las NEH(R1,Ai) agrupada por n y m Tabla 3. ARPD de las NEH(R2,Ai) agrupada por n y m Tabla 4. ARPD de las NEH(R1,Ai) agrupada por F Tabla 5. ARPD de las NEH(R2,Ai) agrupada por F Tabla 6. ACT de las NEH(R1,Ai) agrupada por n y m Tabla 7. ACT de las NEH(R2,Ai) agrupada por n y m Tabla 8. ACT de las NEH(R1,Ai) agrupada por F 24 Tabla 9. ACT de las NEH(R2,Ai) agrupada por F Se observa que las heurísticas que obtienen valores más pequeños del índice ARPD coinciden con los resultados obtenidos en la sección anterior, donde se analizaban las instancias más pequeñas. Es decir, las reglas A8, A9, A10 y A11 para ambas codificaciones, R1 y R2, siguen siendo las mejores para instancias más grandes, manteniéndose siempre por debajo del 10% del ARPD. Además, la R1A4 y R1A5 son las que más se acercan a estas cuatro últimas reglas, al igual que en las instancias pequeñas. Para complementar el análisis, a continuación, se incluye un diagrama de caja y bigotes que ofrece una representación visual de los índices RPD de cada heurística evaluada, tal como se realizó en la sección anterior. Ilustración 9. Diagrama de caja y bigote para instancias grandes (RPD) La heurística R1A9 es la que ofrece mejores resultados en cuanto a ARPD. La regla de asignación utilizada, A9, coincide con la ganadora, A4, de (Fernandez-Viagas et al., 2018), pero adaptada al problema estudiado. Sin embargo, esta heurística presenta unos tiempos de cómputo elevados para instancias más grandes. Los tiempos promedio de cómputo (ACT) superan los 500 segundos para 𝑚 = 5 y 𝑛 =100. Aunque este tiempo puede parecer razonable, es importante compararlo con los tiempos de cómputo para el tamaño previo (𝑚 = 20 y 𝑛 =50), donde los ACT eran alrededor de 60 y 70 segundos. Esta escalada significativa en los tiempo de cómputo provoca que, para el resto de instancias de (Taillard, 1993) que quedan por analizar, estas heurísticas se vuelvan muy ineficientes en términos de tiempos de cómputo. Para visualizar esto de manera más clara y concisa, se presenta la Tabla 10 en una gráfica, donde se muestra el ARPD frente al ACT para cada una de las heurísticas aplicadas. Tabla 10. ARPD y ACT para instancias grandes Ilustración 10. ARPD frente ACT para instancias grandes La Ilustración 10 confirma la información previamente discutida. Dado que los tiempos de cómputo escalan considerablemente para la codificación R1 en las instancias restantes, se analizarán estas instancias exclusivamente en la codificación R2. Este análisis servirá principalmente para ver los tiempos de cómputo de estas heurísticas en instancias muy grandes, ya que, al no analizar las heurísticas con la codificación R1, los índices ARPD nos servirán únicamente para confirmar que las reglas A8, A9, A10 y A11 siguen siendo las mejores con respecto al resto en las instancias más grandes de (Taillard, 1993). Los resultados del análisis de las ultimas 50 instancias se ven reflejados de igual forma que se representaron las primeras 70, según el índice ARPD agrupadas por los parámetros m y n, en la Tabla 11 y agrupadas por el parámetro F en la Tabla 12. Los tiempos de cómputo, que realmente es lo que más interesa de este análisis vienen reflejados en la Tabla 13 y Tabla 14. 32 ANEXO A: CÓDIGO DE PROGRAMACIÓN En el presente Anexo se muestra el código completo utilizado para la ejecución de las diferentes heurísticas explicadas en este documento. - Archivo ClaseModel.py. from memo import check_memo_dt, update_memo_dt, check_memo_ct, update_memo_ct from scheptk.scheptk import FlowShop from scheptk.scheptk import Model from scheptk.util import read_tag, print_tag, sorted_index_desc import sys # to stop the execution (function exit()) class DistributedFlowShop(Model): def __init__(self, filename): # Leemos la instancia FlowShop self.flowshopinst=FlowShop(filename) # initializing additional data (not basic) self.machines = 0 # starting reading print("----- Reading Distributed FlowShop instance data from file " + filename + " -------") # jobs (mandatory data) self.jobs = read_tag(filename, "JOBS") # if jobs = -1 the program cannot continue if (self.jobs==-1): print("No jobs specified. The program cannot continue.") sys.exit() else: print_tag("JOBS", self.jobs) # machines (another mandatory data) self.machines = read_tag(filename, "MACHINES") # if machines = -1 the program cannot continue if(self.machines ==-1): print("No machines specified. The program cannot continue.") sys.exit() else: print_tag("MACHINES", self.machines) # factories (another mandatory data) self.factories = read_tag(filename, "FACTORIES") if (self.factories==-1): print("No factories specified. The program cannot continue.") sys.exit() else: print_tag("FACTORIES", self.factories) # processing times (mandatory data, machines in rows, jobs in cols) self.pt = read_tag(filename, "PT") if(self.pt==-1): print("No processing times specified. The program cannot continue.") sys.exit() else: if(len(self.pt) != self.machines ): print("Number of processing times does not match the number of machines (MACHINES={}, length of PT={}). The program cannot continue".format(self.machines, len(self.pt))) sys.exit() else: for i in range(self.machines): if(len(self.pt[i]) != self.jobs): print("Number of processing times does not match the number of jobs for machine {} (JOBS={}, length of col={}). The program cannot continue".format(i, self.jobs, len(self.pt[i]))) sys.exit() print_tag("PT", self.pt) # tap times (mandatory data) self.tap = read_tag(filename,"TAP") if (self.tap==-1): 34 print("No tap times specified. The program cannot continue.") sys.exit() else: if(len(self.tap) != self.factories): print("Number of tap times does not match the number of factories. The program cannot continue.") sys.exit() else: for i in range(self.factories): if(len(self.tap[i]) != self.jobs): print("Number of tap times does not match the number of jobs for machine {} (JOBS={}, length of col={}). The program cannot continue.".format(i, self.jobs, len(self.tap[i]))) sys.exit() print_tag("TAP", self.tap) print("----- end of Distributed FlowShop instance data from file " + filename + " -------") def ct(self,solution): # Obtenemos una lista completa de los trabajos en orden de secuencia seq_compl= [trabajo for maquina in solution for trabajo in maquina] # Breve comprobación de la secuencia if(len(set(seq_compl))!=len(seq_compl)): print("Trabajos repetidos en la secuencia") sys.exit() # Inicializamos los completion times a 0 completion_time = [[0 for j in range(len(seq_compl))] for i in range(self.machines*self.factories)] # Calculamos los índices de los trabajos en seq_compl trabajo_indices = {trabajo: index for index, trabajo in enumerate(seq_compl)} factory=1 maq_inicial=0 factory_order=[] # Recorremos la secuencia con sublistas for maquina in solution: # Comprobamos si fabrica trabaja if(len(maquina)!=0): for trabajo in maquina: trabajo_index = trabajo_indices[trabajo] factory_order.append(factory-1) # Colocamos el primer trabajo de la fábrica en la primera máquina if trabajo==maquina[0]: completion_time[maq_inicial][trabajo_index] = self.pt[0][trabajo] # Colocamos el trabajo en el resto de máquinas for i in range(maq_inicial+1,self.machines*factory): completion_time[i][trabajo_index] = completion_time[i-1][trabajo_index] + self.pt[imaq_inicial][trabajo] # Colocamos el resto de trabajos else: completion_time[maq_inicial][trabajo_index] = completion_time[maq_inicial][trabajo_index-1] + self.pt[0][trabajo] for i in range(maq_inicial+1,self.machines*factory): completion_time[i][trabajo_index] = max(completion_time[i][trabajo_index- 1],completion_time[i-1][trabajo_index]) + self.pt[i-maq_inicial][trabajo] maq_inicial=self.machines*factory factory+=1 return completion_time, seq_compl, factory_order def ctR1A1(self,solution): # Breve comprobación de la secuencia if(len(set(solution))!=len(solution)): print("Trabajos repetidos en la secuencia") sys.exit() secuencia=[[] for i in range(self.factories)] ct_f=[[0 for j in range(self.machines)] for i in range(self.factories)] for i in range(len(solution)): job=solution[i] makespan=[] # Creamos secuencias parciales en cada una de las posiciones ct_f_parciales=[] for f in range(self.factories): # Calculamos el completion time del último trabajo colocado 36 ct_f_aux=[list(fila) for fila in ct_f] ct_f_aux[f][0]=ct_f_aux[f][0]+self.pt[0][job] for m in range(1,self.machines): ct_f_aux[f][m]=max(ct_f_aux[f][m-1],ct_f_aux[f][m])+self.pt[m][job] ct_f_parciales.append(ct_f_aux) makespan.append(max([ct_f_parciales[-1][f][self.machines-1] for f in range(self.factories)])) minimo=min(makespan) f_seleccionada=makespan.index(minimo) secuencia[f_seleccionada].append(job) ct_f=ct_f_parciales[f_seleccionada] completion_time, solution, factory_order = self.ct(secuencia) return completion_time, solution, factory_order def ctR1A2(self,solution): # Breve comprobación de la secuencia if(len(set(solution))!=len(solution)): print("Trabajos repetidos en la secuencia") sys.exit() secuencia=[[] for i in range(self.factories)] ct_f=[[0 for j in range(self.machines)] for i in range(self.factories)] for i in range(len(solution)): job=solution[i] makespan=[] # Creamos secuencias parciales en cada una de las posiciones ct_f_parciales=[] for f in range(self.factories): # Calculamos el completion time del último trabajo colocado ct_f_aux=[list(fila) for fila in ct_f] ct_f_aux[f][0]=ct_f_aux[f][0]+self.pt[0][job] for m in range(1,self.machines): ct_f_aux[f][m]=max(ct_f_aux[f][m-1],ct_f_aux[f][m])+self.pt[m][job] ct_f_parciales.append(ct_f_aux) makespan.append(ct_f_parciales[-1][f][self.machines-1]) f_seleccionada=makespan.index(min(makespan)) secuencia[f_seleccionada].append(job) ct_f=ct_f_parciales[f_seleccionada] completion_time, solution, factory_order = self.ct(secuencia) return completion_time, solution, factory_order def ctR1A3(self,solution): # Breve comprobación de la secuencia if(len(set(solution))!=len(solution)): print("Trabajos repetidos en la secuencia") sys.exit() secuencia=[[] for i in range(self.factories)] for i in range(len(solution)): job=solution[i] # Comprobamos si está calculado valor=check_memo_ct(secuencia) if(valor==-1): ct_global, ct_local = self.Cmax(secuencia, "ct") A3=ct_local update_memo_ct(secuencia, ct_global, ct_local) else: A3=valor[:-1] minimo=min(A3) f_seleccionada=A3.index(minimo) secuencia[f_seleccionada].append(job) completion_time, solution, factory_order = self.ct(secuencia) return completion_time, solution, factory_order def ctR1A4(self,solution): # Breve comprobación de la secuencia if(len(set(solution))!=len(solution)): print("Trabajos repetidos en la secuencia") sys.exit() secuencia=[[] for i in range(self.factories)] for i in range(len(solution)): job=solution[i] A4=[] # Creamos secuencias parciales en cada una de las posiciones 38 for f in range(self.factories): secuencia[f].append(job) # Obtengo la posición del trabajo en orden de secuencia aplanada = [trabajo for sublista in secuencia for trabajo in sublista] posicion=aplanada.index(job) DT=self.DTj(secuencia, "ct")[0][posicion] A4.append(DT) secuencia[f].pop(-1) f_seleccionada=A4.index(min(A4)) secuencia[f_seleccionada].append(job) completion_time, solution, factory_order = self.ct(secuencia) return completion_time, solution, factory_order def ctR1A5(self, solution): # Breve comprobación de la secuencia if(len(set(solution))!=len(solution)): print("Trabajos repetidos en la secuencia") sys.exit() secuencia=[[] for i in range(self.factories)] for i in range(len(solution)): job=solution[i] A5=[] # Creamos secuencias parciales en cada una de las posiciones sec_parciales=[] for fabrica,sec in enumerate(secuencia): permutacion=sec[:] permutacion.append(job) sec_aux=secuencia[:] sec_aux[fabrica]=permutacion[:] sec_parciales.append(sec_aux) # Comprobamos si está calculado valor=check_memo_dt(sec_parciales[-1]) if(valor==-1): dt_global, dt_f = self.sumDTj(sec_parciales[-1], "ct") A5.append(dt_global) update_memo_dt(sec_parciales[-1], dt_global, dt_f) else: A5.append(valor[-1]) f_seleccionada=A5.index(min(A5)) secuencia[f_seleccionada].append(job) completion_time, solution, factory_order = self.ct(secuencia) return completion_time, solution, factory_order def ctR1A6(self, solution): # Breve comprobación de la secuencia if(len(set(solution))!=len(solution)): print("Trabajos repetidos en la secuencia") sys.exit() secuencia=[[] for i in range(self.factories)] for i in range(len(solution)): job=solution[i] A6=self.DTjmax(secuencia, "ct")[1] minimo=min(A6) f_seleccionada=A6.index(minimo) secuencia[f_seleccionada].append(job) completion_time, solution, factory_order = self.ct(secuencia) return completion_time, solution, factory_order def ctR1A7(self, solution): # Breve comprobación de la secuencia if(len(set(solution))!=len(solution)): print("Trabajos repetidos en la secuencia") sys.exit() secuencia=[[] for i in range(self.factories)] for i in range(len(solution)): job=solution[i] valor=check_memo_dt(secuencia) if(valor==-1): dt_global, dt_f = self.sumDTj(secuencia, "ct") A7=dt_f update_memo_dt(secuencia, dt_global, dt_f) 40 else: A7=valor[:-1] minimo=min(A7) f_seleccionada=A7.index(minimo) secuencia[f_seleccionada].append(job) completion_time, solution, factory_order = self.ct(secuencia) return completion_time, solution, factory_order def ctR1A8(self, solution): # Breve comprobación de la secuencia if(len(set(solution))!=len(solution)): print("Trabajos repetidos en la secuencia") sys.exit() secuencia=[[] for i in range(self.factories)] for i in range(len(solution)): job=solution[i] sec_parciales=[] A8=[] # Creamos secuencias parciales en cada una de las posiciones for fabrica,sec in enumerate(secuencia): for j in range(len(sec)+1): if len(sec)==0: permutacion=[] else: permutacion=sec[:] permutacion.insert(j,job) sec_aux=secuencia[:] sec_aux[fabrica]=permutacion[:] sec_parciales.append(sec_aux) valor=check_memo_dt(sec_parciales[-1]) if(valor==-1): dt_global, dt_f = self.sumDTj(sec_parciales[-1], "ct") A8.append(dt_f[fabrica]) update_memo_dt(sec_parciales[-1], dt_global, dt_f) else: A8.append(valor[fabrica]) minimo=min(A8) secuencia=sec_parciales[A8.index(minimo)] completion_time, solution, factory_order = self.ct(secuencia) return completion_time, solution, factory_order def ctR1A9(self, solution): # Breve comprobación de la secuencia if(len(set(solution))!=len(solution)): print("Trabajos repetidos en la secuencia") sys.exit() secuencia=[[] for i in range(self.factories)] for i in range(len(solution)): job=solution[i] sec_parciales=[] A9=[] # Creamos secuencias parciales en cada una de las posiciones for fabrica,sec in enumerate(secuencia): for j in range(len(sec)+1): if len(sec)==0: permutacion=[] else: permutacion=sec[:] permutacion.insert(j,job) sec_aux=secuencia[:] sec_aux[fabrica]=permutacion[:] sec_parciales.append(sec_aux) valor=check_memo_dt(sec_parciales[-1]) if(valor==-1): dt_global, dt_f = self.sumDTj(sec_parciales[-1], "ct") A9.append(dt_global) update_memo_dt(sec_parciales[-1], dt_global, dt_f) else: A9.append(valor[-1]) minimo=min(A9) secuencia=sec_parciales[A9.index(minimo)] completion_time, solution, factory_order = self.ct(secuencia) return completion_time, solution, factory_order def ctR1A10(self, solution): 48 secuencia=[[] for i in range(instancia.factories)] for i in range(len(orden)): job=orden[i] # Criterio de asignación a la fábrica objetivo=instancia.Cmax(secuencia, ct_func)[1] minimo=min(objetivo) f_seleccionada=objetivo.index(minimo) secuencia[f_seleccionada].append(job) return secuencia def NEHR2A4(instancia, ct_func): # Ordenamos de mayor a menor pt pt_total=[] for i in range(instancia.jobs): suma=sum(sublista[i] for sublista in instancia.pt) pt_total.append(suma) orden=sorted_index_desc(pt_total) secuencia=[[] for i in range(instancia.factories)] for i in range(len(orden)): job=orden[i] sec_parciales=[] objetivo=[] # Creamos secuencias parciales en todas las posiciones for fabrica,sec in enumerate(secuencia): permutacion=sec[:] permutacion.append(job) sec_aux=secuencia[:] sec_aux[fabrica]=permutacion[:] sec_parciales.append(sec_aux) aplanada = [trabajo for sublista in sec_parciales[-1] for trabajo in sublista] posicion=aplanada.index(job) # Criterio de asignación objetivo.append(instancia.DTj(sec_parciales[-1], ct_func)[0][posicion]) minimo=min(objetivo) secuencia=sec_parciales[objetivo.index(minimo)] return secuencia def NEHR2A5(instancia, ct_func): # Ordenamos de mayor a menor pt pt_total=[] for i in range(instancia.jobs): suma=sum(sublista[i] for sublista in instancia.pt) pt_total.append(suma) orden=sorted_index_desc(pt_total) secuencia=[[] for i in range(instancia.factories)] for i in range(len(orden)): job=orden[i] sec_parciales=[] objetivo=[] # Creamos secuencias parciales en todas las posiciones for fabrica,sec in enumerate(secuencia): permutacion=sec[:] permutacion.append(job) sec_aux=secuencia[:] sec_aux[fabrica]=permutacion[:] sec_parciales.append(sec_aux) # Criterio de asignación objetivo.append(instancia.sumDTj(sec_parciales[-1],ct_func)[0]) minimo=min(objetivo) secuencia=sec_parciales[objetivo.index(minimo)] return secuencia def NEHR2A6(instancia, ct_func): # Ordenamos de mayor a menor pt pt_total=[] for i in range(instancia.jobs): suma=sum(sublista[i] for sublista in instancia.pt) pt_total.append(suma) orden=sorted_index_desc(pt_total) secuencia=[[] for i in range(instancia.factories)] for i in range(len(orden)): job=orden[i] A6=instancia.DTjmax(secuencia, "ct")[1] minimo=min(A6) 50 f_seleccionada=A6.index(minimo) secuencia[f_seleccionada].append(job) return secuencia def NEHR2A7(instancia, ct_func): # Ordenamos de mayor a menor pt pt_total=[] for i in range(instancia.jobs): suma=sum(sublista[i] for sublista in instancia.pt) pt_total.append(suma) orden=sorted_index_desc(pt_total) secuencia=[[] for i in range(instancia.factories)] for i in range(len(orden)): job=orden[i] A7=instancia.sumDTj(secuencia, "ct")[1] minimo=min(A7) f_seleccionada=A7.index(minimo) secuencia[f_seleccionada].append(job) return secuencia def NEHR2A8(instancia, ct_func): # Ordenamos de mayor a menor pt pt_total=[] for i in range(instancia.jobs): suma=sum(sublista[i] for sublista in instancia.pt) pt_total.append(suma) orden=sorted_index_desc(pt_total) secuencia=[[] for i in range(instancia.factories)] for i in range(len(orden)): job=orden[i] sec_parciales=[] A8=[] # Creamos secuencias parciales en todas las posiciones for fabrica,sec in enumerate(secuencia): for j in range(len(sec)+1): if len(sec)==0: permutacion=[] else: permutacion=sec[:] permutacion.insert(j,job) sec_aux=secuencia[:] sec_aux[fabrica]=permutacion[:] sec_parciales.append(sec_aux) # Criterio de asignación A8.append(instancia.sumDTj(sec_parciales[-1], "ct")[1][fabrica]) minimo=min(A8) secuencia=sec_parciales[A8.index(minimo)] return secuencia def NEHR2A9(instancia, ct_func): # Ordenamos de mayor a menor pt pt_total=[] for i in range(instancia.jobs): suma=sum(sublista[i] for sublista in instancia.pt) pt_total.append(suma) orden=sorted_index_desc(pt_total) secuencia=[[] for i in range(instancia.factories)] for i in range(len(orden)): job=orden[i] sec_parciales=[] A9=[] # Creamos secuencias parciales en todas las posiciones for fabrica,sec in enumerate(secuencia): for j in range(len(sec)+1): if len(sec)==0: permutacion=[] else: permutacion=sec[:] permutacion.insert(j,job) sec_aux=secuencia[:] sec_aux[fabrica]=permutacion[:] sec_parciales.append(sec_aux) # Criterio de asignación A9.append(instancia.sumDTj(sec_parciales[-1], "ct")[0]) 52 minimo=min(A9) secuencia=sec_parciales[A9.index(minimo)] return secuencia def NEHR2A10(instancia, ct_func): # Ordenamos de mayor a menor pt pt_total=[] for i in range(instancia.jobs): suma=sum(sublista[i] for sublista in instancia.pt) pt_total.append(suma) orden=sorted_index_desc(pt_total) secuencia=[[] for i in range(instancia.factories)] for i in range(len(orden)): # Determinamos la fábrica con peor sumDTj para descartarla criterioDescarte=instancia.sumDTj(secuencia, "ct")[1] f_descartada=criterioDescarte.index(max(criterioDescarte)) job=orden[i] sec_parciales=[] A10=[] # Creamos secuencias parciales en todas las posiciones for fabrica,sec in enumerate(secuencia): if fabrica==f_descartada: continue # Paso a la siguiente fábrica for j in range(len(sec)+1): if len(sec)==0: permutacion=[] else: permutacion=sec[:] permutacion.insert(j,job) sec_aux=secuencia[:] sec_aux[fabrica]=permutacion[:] sec_parciales.append(sec_aux) # Criterio de asignación A10.append(instancia.sumDTj(sec_parciales[-1], "ct")[0]) minimo=min(A10) secuencia=sec_parciales[A10.index(minimo)] return secuencia def NEHR2A11(instancia, ct_func): # Ordenamos de mayor a menor pt pt_total=[] for i in range(instancia.jobs): suma=sum(sublista[i] for sublista in instancia.pt) pt_total.append(suma) orden=sorted_index_desc(pt_total) n_descartadas=instancia.factories-int(instancia.factories/2) # cantidad de f descartadas secuencia=[[] for i in range(instancia.factories)] for i in range(len(orden)): # Determinamos la fábrica con peor sumDTj para descartarla criterioDescarte=instancia.sumDTj(secuencia, "ct")[1] f_orden=sorted_index_desc(criterioDescarte) # f ordenadas de mayor a menor sumDTj f_descartadas=[f_orden[i] for i in range(n_descartadas)] job=orden[i] sec_parciales=[] A11=[] # Creamos secuencias parciales en todas las posiciones for fabrica,sec in enumerate(secuencia): if(any(f==fabrica for f in f_descartadas)): continue # Paso a la siguiente fábrica for j in range(len(sec)+1): if len(sec)==0: permutacion=[] else: permutacion=sec[:] permutacion.insert(j,job) sec_aux=secuencia[:] sec_aux[fabrica]=permutacion[:] sec_parciales.append(sec_aux) # Criterio de asignación A11.append(instancia.sumDTj(sec_parciales[-1], "ct")[0]) 54 minimo=min(A11) secuencia=sec_parciales[A11.index(minimo)] return secuencia - Archivo memo.py memo = {} memo_ct ={} def check_memo_dt(secuencia): clave=str(secuencia) # Devuelve el valor cuando ya fue calculada y -1 en cc if clave in memo: return memo[clave] else: return -1 def update_memo_dt(secuencia, valorglobal, valorlocal): clave=str(secuencia) valorlocal.append(valorglobal) memo[clave]=valorlocal def check_memo_ct(secuencia): clave=str(secuencia) # Devuelve el valor cuando ya fue calculada y -1 en cc if clave in memo_ct: return memo_ct[clave] else: return -1 def update_memo_ct(secuencia, valorglobal, valorlocal): clave=str(secuencia) valorlocal.append(valorglobal) memo_ct[clave]=valorlocal def resetmemo(): global memo global memo_ct memo={} memo_ct={}