Análisis de la aplicación de heurísticas y meta Formato de Publicación de la Escuela Técnica Superior de Ingeniería heurísticas aplicadas al problema Distributed Flowshop para minimizar el total tardiness

28 Proyecto Fin de Carrera Ingeniería de Telecomunicación Formato de Publicación de la Escuela Técnica Superior de Ingeniería Autor: F. Javier Payán Somet Tutor: Juan José Murillo Fuentes Dep. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2013 Trabajo Fin de Grado Grado en Ingeniería de Tecnologías Industriales Análisis de la aplicación de heurísticas y metaheurísticas aplicadas al problema Distributed Flowshop para minimizar el total tardiness Autor: Alejandro Silva Cavero Tutor: Paz Pérez González Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2025 Trabajo Fin de Grado Grado en Ingeniería de Tecnologías Industriales Análisis de la aplicación de heurísticas y metaheurísticas aplicadas al problema Distributed Flowshop para minimizar el total tardiness Autor: Alejandro Silva Cavero Tutor: Paz Pérez González Catedrático de Universidad Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2025 Trabajo Fin de Grado: Análisis de la aplicación de heurísticas y metaheurísticas aplicadas al problema Distributed Flowshop para minimizar el total tardiness Autor: Alejandro Silva Cavero Tutor: Paz Pérez González El tribunal nombrado para juzgar el trabajo arriba indicado, compuesto por los siguientes profesores: Presidente: Vocal/es: Secretario: acuerdan otorgarle la calificación de: El Secretario del Tribunal Fecha: Agradecimientos A mis padres, Antonio y Maribel, por apoyarme en todas mis decisiones. A mis hermanos, Alberto, Antonio y Gema, por la unión que tenemos. A mi pareja, Ana, por estar siempre a mi lado. I Resumen El entorno se caracteriza por involucrar dos decisiones: la asignación de los trabajos a las fábricas, y la secuenciación de los mismos en cada una de ellas. Este trabajo aborda la optimización de un problema de programación de la producción en un entorno de Distributed Flowshop, que se caracteriza por involucrar dos decisiones: la asignación de los trabajos a las fábricas existentes, y la secuenciación de los mismos en cada una de ellas. El objetivo principal es minimizar la tardanza total de los trabajos asignados a cada fábrica, es decir, la suma de la desviación de los tiempos de terminación con respecto a las fechas de entrega, cuando los trabajos van tarde. En primer lugar se han introducido los conceptos fundamentales de la programación de operaciones, los cuales permiten caracterizar adecuadamente el problema y sus restricciones. Se han implementado diversos métodos de resolución, entre ellos reglas de despacho tradicionales, algoritmos heurísticos y metaheurísticos, los cuales fueron explicados en detalle para una mejor comprensión de su funcionamiento y aplicabilidad. El trabajo realiza un análisis comparativo del desempeño de cada algoritmo, evaluando su eficacia en términos de reducción de tardanza y eficiencia computacional. La experimentación incluye un estudio exhaustivo de los parámetros que definen el problema, como el número de fábricas, la cantidad de trabajos y el número de máquinas involucradas en cada fábrica. Adicionalmente, se ha llevado a cabo un seguimiento del tiempo de computación para cada algoritmo, lo que permite una evaluación precisa de su viabilidad en escenarios de producción real. Este proyecto concluye con una evaluación de los resultados obtenidos, analizando la efectividad de los algoritmos aplicados para minimizar el tiempo de tardanza total en entornos de producción distribuidos. III 1 Introducción E lDistributed Permutation Flowshop Scheduling Problem (DPFSP) es una variante avanzada del problema clásico de programación de producción conocido como Flowshop. En un entorno DPFSP, existe un número determinado de fábricas totalmente idénticas. En cada una de ellas, hay un conjunto de máquinas por las que deben ser procesados los trabajos asignados. Además, debido a la restricción de permutación, dentro de cada fábrica, la secuencia de trabajos en cada máquina será la misma. Este modelo refleja la creciente complejidad de los sistemas de producción modernos, donde las máquinas y recursos no están centralizados en una única fábrica, sino distribuidos geográficamente, lo que añade una capa adicional de planificación y coordinación (Olhager & Feldmann, 2018). En el DPFSP, la principal tarea es asignar y secuenciar los trabajos en el conjunto de fábricas de manera que se optimice un objetivo específico, como pueden ser la minimización del tiempo total de finalización de los trabajos (makespan), la reducción de los retrasos (tardiness), o la maximización de la utilización de los recursos. Este problema es de gran relevancia en la industria manufacturera y de servicios, ya que una programación eficiente puede resultar en una reducción de costes y tiempos significativa, mejorando la competitividad (Fernandez-Viagas & Framinan, 2015). 1.1 Objetivo El objetivo en este documento es resolver y analizar el problema de DPFS, mediante la aplicación de diversas reglas de despacho, heurísticas y metaheurísticas. La restricción propuesta es la de permutación y el objetivo a optimizar es el total tardiness, ambos conceptos se definen en el capítulo 2. Para ello, una vez obtenidos los resultados de cada uno de los métodos, se realiza una comparativa para evaluarlos, con el fin de establecer una conclusión sobre el desempeño que ofrece cada algoritmo. 1.2 Herramientas empleadas En este proyecto, se ha empleado Python como herramienta principal para el desarrollo e implementación de los métodos para resolver el DPFSP. Python es un lenguaje de programación ampliamente utilizado en el ámbito académico e industrial debido a su simplicidad, versatilidad y la extensa disponibilidad de bibliotecas especializadas (Oliphant, 2007). Para abordar la complejidad del DPFSP y aplicar las heurísticas y metaheurísticas, se ha utilizado la librería scheptk (Framinan, 2023), diseñada específicamente para problemas de programación de la producción. Adicionalmente, para el análisis de los resultados se han elaborado tablas y gráficas empleando el programa Microsoft Excel, por su gran utilidad en este aspecto. 1.3 Estructura En esta primera sección se introduce de forma breve el problema con el que se trabaja a lo largo del documento, así como el objetivo del trabajo, las herramientas utilizadas y el contenido de cada uno de los apartados. La sección dos trata sobre conceptos básicos de programación de operaciones, necesarios para entender cualquier problema desde la base, la variedad de problemas posibles y la caracterización del problema a resolver. 1 2Capítulo 1. Introducción En la tercera sección se presentan los métodos de resolución empleados, detallando el funcionamiento de cada una de las reglas de despacho, heurísticas y metaheurísticas. Luego, en la cuarta sección, se presentan las instancias que se han utilizado para resolver el problema y se realiza una comparativa y análisis de los resultados obtenidos. Por último, en la sección número cinco, se establecen las conclusiones a las que se han llegado tras el análisis. 2 Descripción del problema E n este apartado se va a tratar de introducir los conceptos básicos relacionados con la programación de operaciones, con el objetivo de caracterizar el problema planteado en este documento. 2.1 Conceptos básicos La definición de dichos conceptos así como la notación usada son los siguientes (Perez-Gonzalez et al., 2022): • Máquina: Recurso productivo con capacidad para realizar operaciones de transformación o transporte de material. El conjunto de máquinas viene definido por M=1,...,m, siendo el índice empleado i ∈ M. • Trabajo: Producto que es objeto de una operación en alguna de las máquinas de la fábrica. El conjunto de trabajos viene definido por N=1,...,n, siendo el índice empleado j∈N. • Tiempo de proceso: Es el tiempo en el que la máquina i ∈ Mestá ocupada en procesar el trabajo j ∈ N. Se denota como pi j. • Fecha de entrega: Instante de tiempo en el que el trabajo j ∈ Ndebe de estar terminado, se denota como dj. La última operación de cada trabajo debe completarse antes de dj. • Ruta de proceso: Vector en el que se indica el orden en el que el trabajo jva a ser procesado. Se denota como Rj. Otro concepto importante es el de programa o schedule, que consiste en la asignación en la escala temporal concreta de las máquinas de una empresa para la fabricación de un conjunto de trabajos. Un programa determina el comienzo y el final de cada operación a realizar en cada recurso productivo. Para que un programa sea admisible debe cumplir con todas las restricciones y características del proceso productivo, el objetivo de la programación de la producción es encontrar dicho programa admisible, en la Figura 2.1 se muestra un ejemplo. Sin embargo para que un programa sea semi-activo se tiene que cumplir que no pueda adelantarse ninguna operación sin cambiar el orden en que alguna máquina procesa los trabajos, localmente, en cada máquina, cada trabajo se encuentra lo más a la izquierda posible para un orden dado, como se observa en la Figura 2.2. Figura 2.1 Ejemplo de programa admisible [Fuente: Perez-Gonzalez et al., 2022]. 3 4Capítulo 2. Descripción del problema Figura 2.2 Ejemplo de programa semi-activo [Fuente: Perez-Gonzalez et al., 2022]. Por último, se define secuencia como el orden en que cada trabajo comienza a procesarse en cada máquina. Esta se puede representar como un vector para cada máquina o en caso de que la asignación sea la misma para todas las máquinas, como un vector único. 2.2 Modelos de programación de la producción La importancia de este punto recae en la necesidad de clasificar el problema para así llevar a cabo su resolución. Por ello Graham et al. (1979) propusieron una notación en base a tres áreas: entorno, restricciones y objetivos. Representado como α|β|γ, se presenta en la Figura 2.3. Figura 2.3 Clasificación de los modelos de programación de la producción [Fuente: Framinan et al., 2014]. • Entorno ( α ): Este primer campo consiste en especificar el entorno de las máquinas, es decir, el número de máquinas en la fábrica y la disposición de cada una de ellas. Los layouts existentes se pueden simplificar en los siguientes seis tipos, máquina individual, máquinas paralelas, taller de flujo regular o flowshop, taller de trabajos o jobshop, taller abierto o openshop e híbridos. No obstante, existen más entornos, como el Distributed Flowshop que se presenta en este documento. • Restricciones ( β ): Aquí se definen las características de los trabajos, son restricciones que se deben cumplir para que el programa sea admisible. Algunas de las restricciones principales son las siguientes (Perez-Gonzalez et al., 2022): ◦ Interrupción o preemption: Los trabajos pueden interrumpirse una vez que han empezado a procesarse. ◦Fecha de llegada: Instante de tiempo en el que el trabajo está disponible. ◦ Fecha de entrega: Únicamente cuando es obligatoria (deadline). Es el instante de tiempo límite en el que un trabajo debe ser entregado. ◦ Tiempos de setup: Es el tiempo de preparación de la máquina para procesar el trabajo correspondiente. ◦Lotes: Se puede procesar a la vez una cantidad determinada de trabajos en una única máquina. 2.3 Caracterización del problema 5 ◦ Precedencia: Un trabajo no puede empezar a procesarse hasta que no acaben los trabajos que lo preceden. Como restricciones de los entornos tipo taller podemos encontrar (Perez-Gonzalez et al., 2022): ◦Permutación: Misma secuencia para todas las máquinas. ◦ Tiempos ociosos no permitidos o no-idle: Una vez la máquina empieza a procesar el primer trabajo de su programa, no puede parar. ◦ Los trabajos no pueden esperar entre máquinas: Una vez comienza a procesarse el trabajo en la primera máquina, las acciones realizadas sobre este no pueden detenerse hasta que haya pasado por todas las máquinas, no-wait. ◦ Almacén de una máquina o buffer: Es el espacio donde esperan los trabajos para ser procesados en la siguiente máquina, se limita la cantidad de trabajos en dicha zona de espera. Cuando las restricciones no están presentes, es necesario tener en cuenta las siguientes suposiciones generales (Perez-Gonzalez et al., 2022): ◦Los trabajos se encuentran 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, y un trabajo puede ser realizado solo en una máquina. ◦El buffer entre máquinas se supone infinito. ◦El tiempo de transporte es despreciable. • Objetivos ( γ ): En este tercer y último campo se escoge un criterio de optimización, la función objetivo (FO) del problema. A continuación, se presentan algunos de los objetivos que se pueden elegir (PerezGonzalez et al., 2022). ◦ Tiempo de terminación del trabajo jocompletion time ( Cj ): Es el instante en el que el trabajo acaba, no tiene relación con la fecha de entrega. Hay dos FO posibles, la primera es el makespan ( Cmax ), es el mayor tiempo de terminación de los trabajos; la segunda, el total completion time (∑Cj), para el que se suma el tiempo de finalización de cada trabajo. ◦ Tardanza del trabajo j o tardiness ( Tj ): Si el trabajo termina antes de su fecha de entrega no pasa nada, solo mide los trabajos que terminan después del due date. Al igual que en el caso anterior hay dos tipos de FO, maximum tardiness ( Tmax ), es el trabajo con mayor tardanza; y total tardiness (∑Tj), se obtiene sumando la tardanza de todos los trabajos. ◦ Retraso del trabajo jolateness ( Lj ): Este objetivo al igual que el anterior depende de la fecha de entrega, pero en caso de que se procese el trabajo antes de cumplir dicha fecha, el resultado, tomaría un valor negativo. Del mismo modo existen dos FO posibles, maximum lateness ( Lmax ) y total lateness (∑Lj). ◦ Adelanto del trabajo joearliness ( Ej ): Es el caso opuesto al tardiness, si el trabajo termina después de su fecha de entrega, no pasa nada. Puede ser maximum earliness ( Emax ) o total earliness ( ∑Ej ). ◦ Tiempo de flujo del trabajo joflowtime ( Fj ): Es el tiempo que el trabajo está en el entorno mientras se procesa o espera para ser procesado. No tiene relación con la fecha de entrega, igual que el completion time. La FO puede ser maximum flowtime (Fmax) o total flowtime (∑Fj). ◦ Número de trabajos tarde ( Uj ): Si un trabajo llega tarde tomará el valor 1 y en caso contrario cero, obteniendo así el número de trabajos tarde (∑Uj). Como resumen, definiendo cada uno de los tres campos explicados, se puede caracterizar cualquier tipo de problema, este será el objetivo del siguiente subapartado. 2.3 Caracterización del problema En primer lugar, aplicando la notación presentada en la sección 2.2, el problema a resolver en este documento es el siguiente, DF|prmu| ∑Tj . A continuación, se detalla la opción seleccionada en cada uno de los tres campos. 6Capítulo 2. Descripción del problema • Entorno: Se ha seleccionado un Distributed Flowshop ( α =DF), variante del problema de flowshop, una particularidad de este es que la ruta de proceso es la misma para todos los trabajos, que empiezan a procesarse en la máquina 1 y acaban en la máquina m, sin alterar el orden. En el flowshop todos los procesos de fabricación ocurren en una única fábrica, algo cada vez menos común en la economía global de hoy en día, por ello surge el modelo de Distributed Flowshop, que consiste en un número F de fábricas idénticas y cada una con mmáquinas disponibles. Así, en el proceso de programación será clave la asignación de los distintos trabajos a cada fábrica y la secuenciación de dichos trabajos dentro de cada una de estas (Naderi & Ruiz, 2010). Además, algunas de las suposiciones necesarias son las siguientes, el número de fábricas idénticas debe ser superior a uno y deben procesar los ntrabajos existentes, todas las fábricas disponen del mismo conjunto de mmáquinas, todas las máquinas y trabajos están disponibles en el instante temporal cero, y por último, cada máquina puede procesar un único trabajo a la vez y cada trabajo se puede procesar en una máquina a la vez y el tiempo de proceso de un trabajo en una máquina específica es el mismo en cada una de las fábricas. En la Figura 2.4, mediante un diagrama de Gantt, se puede observar un ejemplo de programa para un Distributed Flowshop, en el que se considera que hay dos fábricas con dos máquinas en cada una de ellas (m=2) y cinco trabajos (n=5) que deben ser programados. Figura 2.4 Ejemplo de Distributed Flowshop [Fuente: Khare y Agrawal, 2021]. • Restricciones: La única restricción presente en este campo es la de permutación ( β =prmu), como se vió en la sección 2.2, implica que, dentro de cada una de las fábricas, la secuencia es idéntica para todas las máquinas. De ese modo se reduce el número de posibles programas semiactivos dentro de cada fábrica, pasando de (n!)man! programas. • Objetivo: Se ha propuesto minimizar el total tardiness ( ∑Tj ), por lo cual, todos aquellos trabajos cuyo instante temporal de salida en la última máquina sea superior a la fecha de entrega, repercutirán negativamente a la función objetivo, aumentando el valor total. A modo de ejemplo se puede apreciar en la Figura 2.4 la fecha de entrega de cada uno de los trabajos ( dj ) y el valor del tardiness ( Tj ) de cada uno, a excepción del trabajo 3 ya que su due date es superior a su tiempo de terminación. El resultado del objetivo consistiría en sumar cada uno de los tiempos de tardanza, los cuales son T1 =16, T2 =17, T3=0, T4=5 y T5=9, siendo el valor de la FO de 47 unidades. 3 Métodos de resolución P ara resolver el problema presentado en la sección 2.3, es necesario tener en cuenta los aspectos que se exponen a continuación: • La primera parte del proceso de programación de un Distributed Flowshop consiste en la asignación de trabajos a las diferentes fábricas. Se ha escogido como regla de asignación únicamente la regla ECT (earliest completion time), que consiste en asignar cada trabajo a la fábrica en la que tendría un menor tiempo de terminación. La decisión se debe a que Naderi y Ruiz (2010) demostraron que la regla ECT da un mejor resultado con un coste computacional muy pequeño, de ahí la elección de dicha regla. • La segunda parte se basa en secuenciar los trabajos en cada una de las fábricas. Para ello se aplicarán diversos métodos propuestos por Khare y Agrawal (2021), en su estudio tratan de minimizar la tardanza total para el problema de DPFS, con la restricción de permutación, quedando caracterizado el problema como el que se ha planteado en este estudio: DF|prmu| ∑Tj . Así surge el interés de probar los mismos métodos, concretamente, tres reglas de despacho, dos heurísticas y dos metaheurísticas, que se desarrollarán en los siguientes subapartados. El problema es conocido por ser NP-hard, por lo que se proponen métodos aproximados de resolución, al no poder garantizar la optimalidad. 3.1 Reglas de despacho Las reglas de despacho o dispatching rules son métodos clásicos y por tanto no pueden atribuirse a un único autor. Estas consisten en llevar a cabo un cálculo simple para luego secuenciar las tareas (trabajos en este caso) con un orden de prioridad (Framinan et al., 2014). Las tres reglas de despacho empleadas son: earliest due date (EDD), smallest overall slack time (OSL) y smallest slack time on the last machine (LSL). 3.1.1 EDD Esta regla tiene en cuenta únicamente la fecha de entrega ( dj ) de los trabajos, que son ordenados de menor a mayor valor. Generando así una secuencia de ntrabajos del tipo π = π1 , π2 , π3 ,..., πn , con dπ(j)≤dπ(j+1) para j= 1, 2,..., n−1. En caso de empate se escoge el trabajo con menor índice. 3.1.2 OSL Consiste en clasificar los trabajos en orden no decreciente del overall slack time, es decir, para cada trabajo, la diferencia de tiempo entre la fecha de entrega ( dj ) y la suma de los tiempos de proceso de dicho trabajo en todas las máquinas. El cálculo es el siguiente: dπ(j)−∑m i=1pi,π(j)≤dπ(j+1)−∑m i=1pi,π(j+1) . Igual que en el EDD, el desempate se realiza escogiendo el trabajo con el índice más pequeño. 3.1.3 LSL La última regla de despacho es smallest slack time on the last machine, parecida a la regla OSL pero en este caso no se tiene en cuenta el slack time general sino el de la última máquina (m). De esa forma, el cálculo que se aplica sería: dπ(j)−pm,π(j)≤dπ(j+1)−pm,π(j+1). Mismo desempate que las reglas EDD y OSL. 7 8Capítulo 3. Métodos de resolución 3.2 Heurísticas Las heurísticas, al igual que las metaheurísticas (sección 3.3), son algoritmos de resolución aproximados. La necesidad de aplicar estos métodos radica en la complejidad computacional inherente a los métodos exactos, donde la mayoría de los modelos de programación requieren un tiempo de computación excesivamente elevado (Framinan et al., 2014). Como característica general, las heurísticas son específicamente diseñadas para un modelo en particular, por lo que dependen en gran medida del problema (Framinan et al., 2014). Se tratan de procedimientos sencillos, basados en el sentido común y en el conocimiento del problema, que ofrecen buenas soluciones de forma rápida. Las heurísticas empleadas en esta sección son dos, la primera se llama NEHD edd , la cual es una extensión de la heurística NEH edd (Kim, 1993) considerando la existencia de varias fábricas, esta heurística es una de las más conocidas y citadas para los problemas de flowshop, siendo reconocida por su buen desempeño y eficiencia; la segunda se llama smallest slack time on every machine (ESL). 3.2.1 NEHDedd En esta heurística, lo primero es clasificar los trabajos en orden no decreciente según las fechas de entrega. Luego, se selecciona cada trabajo en el orden establecido y se asigna a la fábrica con el menor valor de tardiness, tras haber comprobado todas las posiciones posibles en todas las fábricas. El pseudocódigo del algoritmo se presenta en la Figura 3.1. Figura 3.1 Pseudocódigo del algoritmo NEHDedd [Fuente: Khare y Agrawal, 2021]. 3.2.2 ESL Esta segunda heurística se inspira en la regla de despacho LSL, en este caso, en lugar de tener en cuenta únicamente el slack time de la última máquina, se contemplan todas las máquinas. De esta forma, para cada máquina se disponen los trabajos en orden no decreciente según el slack time, obteniendo en total m secuencias. La secuencia escogida será la que ofrezca el menor valor de la función objetivo, es decir, el mínimo total tardiness. En la Figura 3.2 se observa el pseudocódigo para esta heurística. 3.3 Metaheurísticas 9 Figura 3.2 Pseudocódigo del algoritmo ESL [Fuente: Khare y Agrawal, 2021]. 3.3 Metaheurísticas Lo primero es comentar las características principales de las metaheurísticas, para luego detallar aquellas que se han empleado en este documento. Las metaheurísticas se definen como algoritmos generales que pueden aplicarse a diversos problemas mediante pequeñas modificaciones para adaptarlos. Suelen ser más robustas y flexibles que las propias heurísticas y capaces de encontrar soluciones mucho más refinadas. Sin embargo, conllevan un coste computacional superior (Framinan et al., 2014). En las secciones 3.3.1 y 3.3.2 se detalla cada uno de los algoritmos, primero el Hybrid Discrete Harris Hawks Optimisation (HDHHO) y en segundo lugar el Iterated Greedy (IG). 3.3.1 Hybrid Discrete Harris Hawks Optimisation El algoritmo HDHHO (Khare & Agrawal, 2021) es una versión mejorada del HHO (Heidari et al., 2019), que consiste en una metaheurística basada en la población e inspirada en la naturaleza según el comportamiento de caza de las águilas de Harris. El patrón de caza de las águilas se divide en tres fases: exploración, transición de exploración a explotación y explotación. Fase de exploración Se trata de detectar la posición de la presa (mejor solución), las águilas (soluciones candidatas) esperan y observan según dos estrategias. En la primera, cada águila decide su posición en función de la ubicación de la presa y de otras águilas; en la segunda, se ubican en posiciones aleatorias. La formulación de dichas estrategias es la siguiente: X(t+1) =    Xrand (t)−r1×|Xrand(t)−2r2X(t)|si q ≥0.5 (Xprey(t)−Xm(t))−r3×(LB +r4×(UB −LB)) si q <0.5 El vector de posición de cada águila en la siguiente iteración es X(t+1) , el vector de posición Xrand (t) se escoge aleatoriamente entre las águilas de la población actual, X(t) es el vector de posición de la iteración tactual, el vector de posición Xprey representa la mejor solución obtenida hasta el momento y Xm(t) es la posición media entre todas las águilas, se obtiene aplicando el siguiente cálculo: Xm(t) = ∑N i=1Xi(t) N 16 Capítulo 3. Métodos de resolución Algoritmo Finalmente, aplicando cada uno de los pasos anteriores, se elabora el pseudocódigo para el algoritmo Iterated Greedy, como se observa en la Figura 3.9. Figura 3.9 Pseudocódigo del algoritmo Iterated Greedy [Fuente: Khare y Agrawal, 2021]. 4 Resultados y análisis E l objetivo de esta sección es resolver el problema planteado con cada uno de los algoritmos propuestos, para establecer una comparativa entre dichos algoritmos y así determinar cual se adapta mejor al problema. Lo primero de todo será detallar las diversas instancias usadas en el problema, sección 4.1. Así, posteriormente en la sección 4.2, se realiza la obtención y comparativa de resultados. 4.1 Instancias Esta sección se divide en dos subsecciones. En la primera, se definen las instancias empleadas para el calibrado de las metaheurísticas HDHHO e Iterated Greedy; mientras que en la segunda, se especifican las instancias seleccionadas para evaluar los algoritmos definitivos. 4.1.1 Instancias de calibrado Se utilizan únicamente para las metaheurísticas, dado que estas cuentan con una serie de parámetros variables que hay que fijar. Para ello, Khare y Agrawal (2021) proponen un conjunto de 54 instancias únicas con las que realizar el calibrado. Las características son las siguientes: •Número de trabajos: n=20, 50, 100 •Número de máquina: m=5, 10, 20 •Número de fábricas: f=2, 3, 4, 5, 6, 7 • El tiempo de proceso de cada trabajo en cada máquina se genera aleatoriamente, valor entre 1 y 99, ambos incluidos. • Las fechas de entrega se calculan con el método de Hasija y Rajendran (2004). Primero se calcula el tiempo de proceso total de cada trabajo en todas las máquinas, Pj=∑m i=1pi j con j=1,2,...,n , y luego se obtiene el valor de la fecha de entrega con la ecuación dj=Pj×(1+rand ×(1/f)×α) , siendo el valor de rand un número aleatorio entre 0 y 1, ambos incluidos, y α=0.5 (Khare & Agrawal, 2021). 4.1.2 Instancias para comparar los algoritmos Una vez calibrados los parámetros de las metaheurísticas, se emplean nuevas instancias para comparar todos los algoritmos. Se va a usar el banco de pruebas de Naderi y Ruiz (2010), el cual se compone de dos conjuntos de instancias. El primer conjunto es de instancias pequeñas, donde el número de trabajos n ∈ 4, 6, 8, 10, 12, 14, 16, de máquinas m ∈ 2, 3, 4, 5 y de fábricas f ∈ 2, 3, 4, además para cada combinación se generan cinco instancias diferentes, así, hay un total de 420 instancias. El segundo conjunto está formado por instancias grandes, basado en las instancias de Taillard (1993), donde, n × m ∈ 20 × 5, 20 × 10, 20 × 20, 50 × 5, 50 × 10, 50 × 20, 100 × 5, 100 × 10, 100 × 20, 200 × 10, 200 × 20, 500 × 20 son las combinaciones posibles, con diez instancias diferentes para cada opción y para cada f∈2, 3, 4, 5, 6, 7, formando un total de 720 instancias. 17 18 Capítulo 4. Resultados y análisis 4.2 Experimentación En este apartado se detalla como se han obtenido los resultados para cada uno de los métodos propuestos, los criterios empleados para la comparativa y un análisis del desempeño de los algoritmos. El indicador empleado para determinar la elección de los parámetros en el calibrado y realizar la comparativa entre todos los algoritmos es el ARPD (Average Relative Percentage Deviation). El ARPD es la media de los resultados del RPD, que se obtiene con la siguiente fórmula: RPD =Algsol −Bestsol Bestsol ×100 Donde Algsol es el tiempo de tardanza total para una configuración/algoritmo concreto y Bestsol es el menor tiempo de tardanza en la instancia. Por tanto, muestra la variación del total tardiness entre cada configuración/algoritmo y la mejor solución, para cada instancia. El ARPD se calcula aplicando la siguiente expresión: ARPD =∑q i=1RPDi q 4.2.1 Resultados del calibrado Como se ha comentado en la sección 4.1.1, este calibrado se realiza únicamente para las metaheurísticas. Por ello, las configuraciones analizadas y los resultados obtenidos para cada algoritmo se detallan a continuación. Hybrid Discrete Harris Hawks Optimisation Para el HDHHO los parámetros de entrada necesarios son el tamaño de la población y el número máximo de iteraciones a realizar. Para el primero, se propone tres niveles posibles: 10, 20 y 30 águilas. De igual forma, el segundo parámetro cuenta con la misma cantidad de niveles, pero con los siguientes valores: 50, 100 y 200 iteraciones como máximo. Existen 9 configuraciones en total, que son evaluadas en cada una de las 54 instancias, obteniéndose un valor RPD para cada configuración en cada instancia. La cantidad de iteraciones máximas es el criterio de parada establecido. Por último, se aplica el ARPD, cuya solución aparece en la Tabla 4.1, además, se marca en negrita el mejor resultado para cada parámetro, estos son los elegidos para la comparación final. Tabla 4.1 Valores ARPD para parámetros de entrada en HDHHO. Valores ARPD parámetros de entrada HDHHO 10 1,4623 Tamaño de la población 20 1,5215 30 1,3170 50 1,5431 Iteraciones máximas (N) 100 1,5427 200 1,2149 De forma gráfica, en la Figura 4.1, se muestra la respuesta del ARPD para cada variable. Aquellos parámetros con el valor más cercano a cero son los que proporcionan un mejor desempeño, y por tanto, los ganadores en el proceso de calibrado. La configuración por la que se ha optado para el HDHHO es: población de 30 águilas y 200 iteraciones como máximo. 4.2 Experimentación 19 Figura 4.1 Resultado ARPD de cada parámetro del HDHHO [Fuente: Elaboración propia]. Iterated Greedy Los parámetros a calibrar y los valores que se han considerado son los siguientes: • Porcentaje de trabajos a eliminar, d = 0.2, 0.3, 0.5. Cuanto más elevado sea el porcentaje mayor será la diversificación. • Temperatura de referencia, T0= 0.1, 0.4, 1, 10. Cuanto mayor sea el valor de la temperatura, la aceptación de peores soluciones será menor. •Método de inicialización, heurística NEHDedd o ESL. •Búsqueda local, RSLS o RPLS. Estableciendo todas las combinaciones posibles el número total de configuraciones es de 48 ( 3×4×2×2 ). Se aplica el algoritmo para cada configuración en cada una de las 54 instancias. El criterio de terminación escogido es por tiempo (segundos), siendo el cálculo n×m×0.025 . Aplicando el indicador propuesto, se obtienen los resultados de todos los parámetros, como se muestra en la Tabla 4.2, en negrita aparecen los mejores resultados de cada parámetro, son los escogidos para la comparación final. Tabla 4.2 Valores ARPD para parámetros de entrada en IG. Valores ARPD parámetros de entrada IG 0.2 1,8676 %de trabajos a eliminar (d) 0.3 2,3578 0.5 3,3201 0.1 2,2624 Temperatura referencia (T0) 0.4 2,2559 12,1867 10 3,3557 Método de inicialización ESL 2,5499 NEHDedd 2,4804 Búsqueda local RSLS 2,4768 RPLS 2,5536 20 Capítulo 4. Resultados y análisis Figura 4.2 Resultado ARPD de cada parámetro del IG [Fuente: Elaboración propia]. En la Figura 4.2 se presentan los mismos resultados pero gráficamente, facilitando su comprensión. La configuración escogida para el Iterated Greedy es: d = 20 % , T0= 1, inicialización con heurística NEHDedd y búsqueda local con RSLS. 4.2.2 Resultados de los algoritmos empleando instancias pequeñas Una vez calibradas ambas metaheurísticas se procede a evaluar cada uno de los algoritmos planteados usando las instancias pequeñas introducidas en la sección 4.1.2. Con el objetivo de establecer una comparativa general y una valoración del desempeño. Las metaheurísticas son los únicos algoritmos que requieren un criterio de terminación. Para llevar a cabo una comparativa exhaustiva se ha decidido que el tiempo de ejecución en cada instancia sea igual para ambos métodos. Se mantiene el criterio de terminación en el HDHHO, que consiste en realizar iteraciones hasta llegar al número de iteraciones máximas. De ese modo, el criterio de terminación escogido para el Iterated Greedy en cada instancia es el tiempo de ejecución empleado en el HDHHO para esa misma instancia. A continuación, se muestra en la Tabla 4.3 los resultados obtenidos al aplicar el ARPD para cada uno de los algoritmos. Se puede observar como el Iterated Greedy es el que ofrece el mejor desempeño con diferencia, marcado en negrita, casi en la totalidad de las instancias es la mejor solución o coincide con esta. Por otro lado, la desviación del HDHHO respecto a la mejor solución se encuentra cercana al 4 % de media. Además, la mejora de las metaheurísticas respecto de las heurísticas y de las reglas de despacho es clara, como se muestra en la Tabla 4.3 y se aprecia con mayor facilidad en la Figura 4.3. Es interesante analizar más a fondo el comportamiento de los algoritmos una vez aplicados al problema. Los parámetros que definen dicho problema son las fábricas, los trabajos y las máquinas, como ya se explicó en la sección 2. Por ello, se analiza como afecta sobre los algoritmos la variación de cada uno de los parámetros. Se evalúan únicamente las metaheurísticas y las heurísticas, al ser los que presentaban mejores resultados en la comparativa general. En primer lugar, como se muestra en la Tabla 4.4, se ha calculado el ARPD de cada algoritmo para 2, 3 y 4 fábricas. Con esos resultados, representados en la Figura 4.4, se deduce que la metaheurística HDHHO empeora cuantas más fábricas entran en juego, mientras que el IG presenta un gran rendimiento sin importar la cantidad de fábricas, tiene los mejores resultados, marcados en negrita. La heurística ESL tiene un comportamiento prácticamente constante, a diferencia de la NEHDedd la cual es muy irregular. 4.2 Experimentación 21 Tabla 4.3 Valores ARPD por algoritmos para instancias pequeñas. Valores ARPD EDD 30,1573 LSL 15,3584 OSL 80,9338 Algoritmos ESL 12,0856 NEHDedd 20,5280 IG 0,0072 HDHHO 4,1458 Figura 4.3 Resultado ARPD de cada algoritmo para instancias pequeñas [Fuente: Elaboración propia]. Tabla 4.4 Valores ARPD por fábricas para las heurísticas y metaheurísticas en instancias pequeñas. ARPD Fábricas ARPD 2 3 4 Medio ESL 13,3896 11,3939 11,4733 12,0856 Algoritmos NEHDedd 9,5986 33,4609 18,5243 20,5280 IG 0,0215 0 0 0,0072 HDHHO 3,2494 4,5240 4,6640 4,1458 Luego, se ha llevado a cabo la evaluación según el número de trabajos, siendo las opciones las siguientes: n={4,6,8,10,12,14,16} , Tabla 4.5. Al igual que antes, el IG presenta los mejores resultados para todas las opciones posibles, salvo para la configuración con cuatro trabajos y el HDHHO vuelve a empeorar, en este caso, conforme aumenta el número de trabajos, Figura 4.5. La heurística NEHD edd sí muestra un comportamiento de mejora con el aumento de los trabajos, y la ESL funciona peor con este aumento. En negrita se muestran los mejores resultados. 22 Capítulo 4. Resultados y análisis Figura 4.4 Resultado ARPD por fábricas para instancias pequeñas [Fuente: Elaboración propia]. Tabla 4.5 Valores ARPD por trabajos para las heurísticas y metaheurísticas en instancias pequeñas. ARPD Trabajos ARPD 4 6 8 10 12 14 16 Medio ESL 3,377 6,205 13,827 14,931 13,535 15,490 17,234 12,086 Algoritmos NEHDedd 51,036 19,546 16,239 17,851 13,384 13,410 12,230 20,528 IG 0,050 0 0 0 0 0 0 0,007 HDHHO 00,829 1,932 4,382 6,381 7,505 7,992 4,146 Figura 4.5 Resultado ARPD por trabajos para instancias pequeñas [Fuente: Elaboración propia]. Por último, se calcula el ARPD según el número de máquinas, m={2,3,4,5} . Una vez más, los resultados para la metaheurística HDHHO se alejan de la mejor solución en relación al incremento de máquinas. El Iterated Greedy continúa ofreciendo el mejor rendimiento para todas las configuraciones, resultados en negrita. Con este parámetro la heurística ESL se comporta mejor que la NEHD edd en todas las opciones. Este análisis se puede extraer de la Tabla 4.6, y de la Figura 4.6. Un aspecto clave a la hora de comparar algoritmos es tener en cuenta el tiempo de cómputo. Por ello, en la 4.2 Experimentación 23 Tabla 4.6 Valores ARPD por máquinas para las heurísticas y metaheurísticas en instancias pequeñas. ARPD Máquinas ARPD 2 3 4 5 Medio ESL 8,7269 13,5922 12,9154 13,1079 12,0856 Algoritmos NEHDedd 10,4172 15,8606 38,4292 17,4049 20,5280 IG 0,0286 0 0 0 0,0072 HDHHO 2,2121 3,8160 5,1526 5,4024 4,1458 Figura 4.6 Resultado ARPD por máquinas para instancias pequeñas [Fuente: Elaboración propia]. Tabla 4.7, se ha calculado el tiempo medio empleado para todas las instancias por cada uno de los métodos. Se puede observar como los tiempos para las reglas de despacho y las heurísticas son despreciables, mientras que para las metaheurísticas requieren de media poco más de un minuto. Esa diferencia de tiempo entre unos métodos y otros puede justificarse al lograr mejores resultados de la función objetivo. Tabla 4.7 Tiempo medio de computación por algoritmo para instancias pequeñas. Tiempo medio por instancia (s) EDD 0,001 LSL 0,001 OSL 0,001 Algoritmos ESL 0,004 NEHDedd 0,003 IG 73,353 HDHHO 73,349 Adicionalmente, en la Figura 4.7 y en la Figura 4.8, se puede observar un ejemplo de como evoluciona el valor de la FO en cada una de las metaheurísticas respecto del número de iteraciones. 4.2.3 Resultados de los algoritmos empleando instancias grandes Inicialmente, como en el apartado anterior, se realiza una comparativa general entre los algoritmos, pero en este caso usando las instancias grandes del banco de pruebas. Los criterios de terminación para las 24 Capítulo 4. Resultados y análisis Figura 4.7 Evolución de la FO en el IG para instancias pequeñas [Fuente: Elaboración propia]. Figura 4.8 Evolución de la FO en el HDHHO para instancias pequeñas [Fuente: Elaboración propia]. metaheurísticas son los mismos que los de la sección 4.2.2. En la Tabla 4.8 se refleja la media del RPD para cada uno de los métodos empleados en este trabajo. Los resultados obtenidos se proyectan también en la Figura 4.9. Al igual que para las instancias pequeñas, el Iterated Greedy, ofrece un desempeño sobresaliente, llegando siempre a la mejor solución o coincidiendo con esta, marcado en negrita. En cuanto al HDHHO, se produce un incremento del ARPD en relación a las instancias pequeñas, superando el 20 % de desviación respecto a la mejor solución. Las heurísticas y reglas de despacho también se ven perjudicadas, siendo la ESL la que empeora de forma más notable. 4.2 Experimentación 25 Tabla 4.8 Valores ARPD por algoritmos para instancias grandes. Valores ARPD EDD 67,8893 LSL 66,9362 OSL 109,4472 Algoritmos ESL 56,0614 NEHDedd 26,9495 IG 0 HDHHO 24,2003 Figura 4.9 Resultado ARPD de cada algoritmo para instancias grandes [Fuente: Elaboración propia]. A continuación, se repite el análisis por parámetros del problema, empezando por el número de fábricas, donde f={2,3,4,5,6,7} , Tabla 4.9. El ARPD para el HDHHO incrementa con el aumento de fábricas y es levemente inferior al NEHDedd, que presenta un funcionamiento muy superior al ESL, como se aprecia en la Figura 4.10. Tabla 4.9 Valores ARPD por fábricas para las heurísticas y metaheurísticas en instancias grandes. ARPD Fábricas ARPD 2 3 4 5 6 7 Medio ESL 63,1011 59,5642 56,8367 57,9869 49,4813 49,3981 56,0614 Algoritmos NEHDedd 20,4043 23,3693 28,1868 32,2264 26,8433 30,6669 26,9495 IG 0000000 HDHHO 19,2898 22,0515 24,9495 28,1252 23,5781 27,2079 24,2003 32 Capítulo 4. Resultados y análisis Figura 4.18 Comparativa ARPD por fábricas para el NEHD edd en instancias pequeñas [Fuente: Elaboración propia]. Figura 4.19 Comparativa ARPD por trabajos para el NEHD edd en instancias pequeñas [Fuente: Elaboración propia]. Tabla 4.17 Comparativa ARPD por fábricas para el IG en instancias pequeñas, según parámetros Tabla 4.13. Comparativa ARPD Fábricas ARPD 2 3 4 Medio Algoritmos IG Khare y Agrawal 0,055 0,091 0,100 0,082 IG del estudio 0,022 0 0 0,007 4.3 Análisis y comparación de resultados 33 Tabla 4.18 Comparativa ARPD por trabajos para el IG en instancias pequeñas, según parámetros Tabla 4.13. Comparativa ARPD Trabajos ARPD 4 6 8 10 12 14 16 Medio Algoritmos IG Khare y Agrawal 0 0 0,007 0,019 0,060 0,144 0,344 0,082 IG del estudio 0,050 0 0 0 0 0 0 0,007 Figura 4.20 Comparativa ARPD por fábricas para el HDHHO en instancias pequeñas, según parámetros Tabla 4.13 [Fuente: Elaboración propia]. Figura 4.21 Comparativa ARPD por trabajos para el HDHHO en instancias pequeñas, según parámetros Tabla 4.13 [Fuente: Elaboración propia]. 34 Capítulo 4. Resultados y análisis 4.3.3 Instancias grandes Al emplear las instancias grandes Khare y Agrawal (2021) introducen otras siete metaheurísticas contrastadas, para así evaluar la efectividad del IG y del HDHHO. En este caso se comparan únicamente las metaheurísticas, en la Tabla 4.19 aparece el resultado del ARPD para cada algoritmo en cada estudio, tras evaluar las 720 instancias. Para Khare y Agrawal aumenta considerablemente el ARPD del IG respecto a las instancias pequeñas, debido a la existencia de nuevas metaheurísticas, mientras que el IG de este estudio mantiene el desempeño mostrado. Por otro lado, el HDHHO sufre un empeoramiento menos acentuado con las instancias grandes para Khare y Agrawal, en el caso de este trabajo el comportamiento del HDHHO se ve muy afectado al emplear instancias grandes, como se explicó en el subapartado 4.2.3. Tabla 4.19 Comparativa ARPD de cada metaheurística con Khare y Agrawal (2021) en instancias grandes, según parámetros Tabla 4.13. Comparativa ARPD Resultado del estudio Khare y Agrawal Algoritmos IG 01,76 HDHHO 24,20 5,27 5 Conclusiones F inalmente en este apartado se presentan las conclusiones del estudio realizado. El problema que se ha analizado ha sido el Distributed Flowshop con restricción de permutación y con el objetivo de minimizar el tiempo total de tardanza de los trabajos. Para ello se han aplicado diversas heurísticas y metaheurísticas planteadas por Khare y Agrawal (2021), desarrolladas en la sección 3. Posteriormente, en la sección 4, se ha realizado la experimentación, llegando a las siguientes conclusiones: • Entre las dos metaheurísticas estudiadas, Iterated Greedy y HDHHO, ha sido el IG, en todas las situaciones analizadas, la que ha mostrado los mejores resultados y un mejor rendimiento para el problema definido, tanto en este estudio como en el de Khare y Agrawal (2021). • Una posible causa de la peor adaptación del algoritmo HDHHO al problema, respecto al IG, puede ser que este se propuso originalmente por Heidari et al. (2019) para resolver problemas en un entorno Flowshop. Cabe destacar que en el estudio de Khare y Agrawal (2021) este método logra un mejor resultado respecto al de este trabajo, uno de los motivos principales es la diferencia entre el parámetro de iteraciones elegido. • El IG, en las instancias grandes, realiza un número reducido de iteraciones respecto a las instancias pequeñas. La causa principal es el tiempo que emplea en realizar la búsqueda local cuando opera con un gran número de trabajos, una posible solución sería limitar la cantidad de vecinos que se analizan en dicha búsqueda local. • Entre los parámetros candidatos, se han seleccionado aquellos que pueden ofrecer un mayor desempeño en las metaheurísticas. •La regla de despacho LSL presenta mejores resultados que la EDD y la OSL. • En cuanto a las heurísticas, el algoritmo ESL funciona mejor en instancias pequeñas y el NEHDedd en instancias grandes. 35 Bibliografía Fernandez-Viagas, V., & Framinan, J. (2015). A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem. International Journal of Production Research,53, 1111-1123. https://doi.org/10.1080/00207543.2014.948578 Framinan, J. (2023). scheptk (SCHEduling Python ToolKit) [Version 0.1.3]. https://github.com/framinan/ scheptk Framinan, J., Leisten, R., & García, R. (2014). Manufacturing scheduling systems: An integrated view on models, methods and tools (Vol. 9781447162). https://doi.org/10.1007/978-1-4471-6272-8 Graham, R., Lawler, E., Lenstra, J., & Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey (Vol. 5). https://doi.org/10.1016/S0167-5060(08)70356-X Hasija, S., & Rajendran, C. (2004). Scheduling in flowshops to minimize total tardiness of jobs. International Journal of Production Research,42, 2289 - 2301. https://doi.org/10.1080/00207540310001657595 Heidari, A., Mirjalili, S., Faris, H., Aljarah, I., Mafarja, M., & Chen, H. (2019). Harris hawks optimization: Algorithm and applications. Future Generation Computer Systems,97, 849 - 872. https://doi.org/10. 1016/j.future.2019.02.028 Khare, A., & Agrawal, S. (2021). Effective heuristics and metaheuristics to minimise total tardiness for the distributed permutation flowshop scheduling problem. International Journal of Production Research,59, 7266-7282. https://doi.org/10.1080/00207543.2020.1837982 Kim, Y. - D. (1993). Heuristics for flowshop scheduling problems minimizing mean tardiness. Journal of the Operational Research Society,44, 19-28. https://doi.org/10.1057/jors.1993.3 Naderi, B., & Ruiz, R. (2010). The distributed permutation flowshop scheduling problem. Computers and Operations Research,37. https://doi.org/10.1016/j.cor.2009.06.019 Olhager, J., & Feldmann, A. (2018). Distribution of manufacturing strategy decision-making in multi-plant networks. International Journal of Production Research,56, 692 - 708. https://doi.org/10.1080/ 00207543.2017.1401749 Oliphant, T. (2007). Python for scientific computing. Computing in Science and Engineering,9, 10 - 20. https://doi.org/10.1109/MCSE.2007.58 Perez-Gonzalez, P., Framinan, J., & Navarro-Garcia, B. (2022). Programación de Operaciones. Escuela Técnica Superior de Ingeniería, Universidad de Sevilla, Identificador: 1043. Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research,177, 2033 - 2049. https://doi.org/ 10.1016/j.ejor.2005.12.009 Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278-285. https://doi.org/10.1016/0377-2217(93)90182-M Tasgetiren, M., Liang, Y. - C., Sevkli, M., & Gencyilmaz, G. (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research,177, 1930 - 1947. https://doi.org/10.1016/j.ejor.2005.12. 024 Yang, X. - S. (2010, julio). Nature-Inspired Metaheuristic Algorithms. Luniver Press. https://www.researchgate. net/publication/235979455_Nature-Inspired_Metaheuristic_Algorithms 37 Anexo: Código de programación en Python """""""""""""""""""""""" ##### heuristicas_v8 ##### """""""""""""""""""""""" import copy, random, math from scheptk.util import sorted_index_asc, read_tag from scheptk.scheptk import FlowShop from time import time from sympy import * from sympy.abc import x import matplotlib.pyplot as plt import numpy as np """ FUNCIÓN OBJETIVO """ def objective_function(instancia,secuencia,archivo): total_tardiness = 0 for f in range(read_tag(archivo, "FACTORIES")): if secuencia[f] != []: total_tardiness += instancia.SumTj(secuencia[f]) return total_tardiness """""" """""" ### FUNCIÓN PARA ASIGNAR CADA TRABAJO EVALUADO A LA FÁBRICA EN LA QUE TENDRÍA MENOR COMPLETION TIME (ECT) ### ### Lo uso en las funciones EDD, OSL, LSL y ESL. (Regla de asignacion ECT) def FACTORY_LEAST_CT(instancia,sec,archivo): #EN PRINCIPIO SEC_ACTUAL ELIMINAR Y DEJAR SEC Y YA, NO LA TOCO NUNCA, SOLO LA RECORRO. factories=read_tag(archivo, "FACTORIES") sec_factories=[[] for f in range(factories)] #Vector para guardar la secuencia escogida en cada fábrica. sec_actual=copy.deepcopy(sec) #Orden de los trabajos que hay que asignar a las fábricas. 39 40 Anexo: Código de programación en Python for j in range(instancia.jobs): CT_aux=[] #Vector auxiliar para guardar el cálculo del CT que tendría un mismo trabajo en cada una de las fábricas. for f in range(factories): sec_factories[f].append(sec_actual[j]) #Asigno el trabajo j a la fá brica f. compl_time=max(instancia.Cj(sec_factories[f])) #Calculo el CT de dicho trabajo en la fábrica asignada en la línea anterior. CT_aux.append(compl_time) sec_factories[f].pop() #Elimino el trabajo asignado inicialmente a la fábrica f. factory_CT_min=CT_aux.index(min(CT_aux)) #Guardo el número de la fá brica en la que se ha obtenido el menor CT del trabajo evaluado. sec_factories[factory_CT_min].append(sec_actual[j]) #Asigno el trabajo evaluado a la fáb con el CT más pequeño para ese trabajo. return sec_factories """""" """""""""""""""""""""""" ##### REGLAS DE DESPACHO ##### """""""""""""""""""""""" """ EDD """ def EDD (instancia,archivo): sec_edd=sorted_index_asc(instancia.dd) #Ordeno la secuencia según los duedates de menor a mayor. #Aplico regla de asignación ECT. sec=copy.deepcopy(FACTORY_LEAST_CT(instancia, sec_edd,archivo)) return sec """""" """ OSL """ def OSL (instancia, archivo): suma_pt=[0 for j in range (instancia.jobs)] #Vector para guardar el PT total de cada trabajo (suma pt de un mismo trabajo en cada máquina). osl=[0 for j in range (instancia.jobs)] #Vector para guardar el Overall Slack Time de cada trabajo. for j in range (instancia.jobs): for i in range (instancia.machines): suma_pt[j]=suma_pt[j] + instancia.pt[i][j] #Proceso para obtener el PT total de cada trabajo. osl[j]=instancia.dd[j] - suma_pt[j] #Proceso para obtener el OSL de cada trabajo. sec_osl=sorted_index_asc(osl) #Ordeno la secuencia según el OSL de menor a mayor. Anexo: Código de programación en Python 41 #Aplico regla de asignación ECT. sec=copy.deepcopy(FACTORY_LEAST_CT(instancia, sec_osl, archivo)) return sec """""" """ LSL """ def LSL (instancia, archivo): lsl=[0 for j in range (instancia.jobs)] #Vector para guardar el Last Slack Time de cada trabajo. for j in range(instancia.jobs): lsl[j]=instancia.dd[j] - instancia.pt[instancia.machines-1][j] #Proceso para obtener el LSL de cada trabajo. sec_lsl=sorted_index_asc(lsl) #Ordeno la secuencia según el LSL de menor a mayor. #Aplico regla de asignación ECT. sec=copy.deepcopy(FACTORY_LEAST_CT(instancia, sec_lsl, archivo)) return sec """""" """""""""""""""""""""""" ##### HEURÍSTICAS ##### """""""""""""""""""""""" """ ESL """ def ESL (instancia, archivo): slack=[[0 for j in range(instancia.jobs)] for j in range(instancia.machines )] #Vector para guardar el Slack Time de cada trabajo en cada máquina. sec_esl=[0 for i in range(instancia.machines)] #Vector para guardar la secuencia resultante en cada máquina. (m secuencias) for i in range(instancia.machines): for j in range(instancia.jobs): slack[i][j]=instancia.dd[j] - instancia.pt[i][j] #Proceso de cálculo del slack time de cada trabajo en cada máquina. TT=[] #Vector para guardar el TT obtenido para cada una de las m secuencias a analizar. for i in range(instancia.machines): sec_esl[i]=sorted_index_asc(slack[i]) #Ordeno la secuencia según el ESL de menor a mayor. (en cada máquina) sec=copy.deepcopy(FACTORY_LEAST_CT(instancia,sec_esl[i],archivo)) # Obtengo la secuencia de cada fábrica. TT_aux=[] #Vector auxiliar para guardar el cálculo del TT en cada fá brica. for f in range(read_tag(archivo, "FACTORIES")): TT_aux.append(sum(instancia.Tj(sec[f]))) #Añado en el vector auxiliar el valor del TT en cada fábrica. 48 Anexo: Código de programación en Python sec_aux[f].pop(0) break return secuencia_desagregada def crear_vector_posicion_por_solucion(secuencia_desagregada): posiciones_aleatorias = [random.uniform(0, 1) for i in range(len(secuencia_ desagregada))] posiciones_aleatorias.sort() return posiciones_aleatorias def generar_solucion_aleatoria(instancia, archivo): solucion_aleatoria = [j for j in range(instancia.jobs)] random.shuffle(solucion_aleatoria) sol_aleatoria_asignada = copy.deepcopy(FACTORY_LEAST_CT(instancia, solucion _aleatoria, archivo)) return sol_aleatoria_asignada """""" """ FUNCIÓN EXPLORATION PHASE """ def exploration_phase(secuencias_valores_continuos, fitness_todas_soluciones, indice_solucion_actual): # Definición parámetros r1=random.random() r2=random.random() r3=random.random() r4=random.random() q=random.random() UB=max(r1, r2, r3, r4, q) LB=min(r1, r2, r3, r4, q) Xrand=random.choice(secuencias_valores_continuos) #Vector posición de una solución (águila) escogida aletoriamente Xactual=secuencias_valores_continuos[indice_solucion_actual] #Vector posici ón de la solución (águila) de la iteración actual pos_Xprey=secuencias_valores_continuos[fitness_todas_soluciones.index(min( fitness_todas_soluciones))] #Vector pos. Xprey # Cálculo de Xm suma=[0 for k in range(len(secuencias_valores_continuos[0]))] for i in range(len(secuencias_valores_continuos)): for j in range(len(secuencias_valores_continuos[i])): suma[j]=suma[j]+secuencias_valores_continuos[i][j] Xm=[x / len(secuencias_valores_continuos) for x in suma] # Ecuación según valor de q if q>=0.5: # x1 para primera multiplicacion, x2 para la segunda. e1,e2,e3,e4 para restar listas. vector_pos_next_it = [e1-e2 for e1,e2 in zip(Xrand,[x1 * r1 for x1 in [ abs(ele) for ele in [e3-e4 for e3,e4 in zip(Xrand,[x2 * (2*r2) for x 2 in Xactual])]]])] secuencias_valores_continuos[indice_solucion_actual]=copy.deepcopy( vector_pos_next_it) Anexo: Código de programación en Python 49 elif q<0.5: parte_aleatoria=r3*(LB+r4*(UB-LB)) # Para Xprey tengo que usar su vector posición, la posición del vector_ pos_aguilas con el min fitness. vector_pos_next_it =[x - parte_aleatoria for x in [e1-e2 for e1,e2 in zip(secuencias_valores_continuos[fitness_todas_soluciones.index(min( fitness_todas_soluciones))],Xm)]] secuencias_valores_continuos[indice_solucion_actual]=copy.deepcopy( vector_pos_next_it) return secuencias_valores_continuos """""" """ GRÁFICA HDHHO Y EVOLUCIÓN PARÁMETRO E """ def grafica_HDHHO(valores_fo, ff, jj, ii, kk): fig, ax = plt.subplots() instantes_tiempo = [j for j in range(len(valores_fo))] # Representación de la solución con una línea ax.plot(instantes_tiempo, valores_fo, linestyle=’-’, linewidth=2, marker=’x ’, markersize=0, color=’b’, alpha=0.7) # Representación de la solución óptima ax.plot(instantes_tiempo[valores_fo.index(min(valores_fo))], valores_fo[ valores_fo.index(min(valores_fo))], linestyle=’ ’, linewidth=0, marker=’ o’, markersize=10, color=’r’, alpha=1, label=’Optimo Local’) ax.set_ylabel(’Valor de la F.O.’) ax.set_xlabel(’Iteraciones’) ax.legend() # Guardar la gráfica plt.savefig("RESULTADOS/small_instances/graficas_HDHHO/HDHHO_I_" + str(ff) + "_" + str(jj) + "_" + str(ii) + "_" + str(kk) + ".png") # Mostrar la gráfica plt.show() def grafica_HDHHO_inst_large(valores_fo, ff, jj, ii, kk): fig, ax = plt.subplots() instantes_tiempo = [j for j in range(len(valores_fo))] # Representación de la solución con una línea ax.plot(instantes_tiempo, valores_fo, linestyle=’-’, linewidth=2, marker=’x ’, markersize=0, color=’b’, alpha=0.7) # Representación de la solución óptima ax.plot(instantes_tiempo[valores_fo.index(min(valores_fo))], valores_fo[ valores_fo.index(min(valores_fo))], linestyle=’ ’, linewidth=0, marker=’ o’, markersize=10, color=’r’, alpha=1, label=’Optimo Local’) ax.set_ylabel(’Valor de la F.O.’) ax.set_xlabel(’Iteraciones’) ax.legend() # Guardar la gráfica plt.savefig("RESULTADOS/large_instances/graficas_HDHHO/HDHHO_Ta" + str(ff) + str(jj) + str(ii) + "_" + str(kk) + ".png") 50 Anexo: Código de programación en Python # Mostrar la gráfica plt.show() def grafica_plot_E(valores_fo): fig, ax = plt.subplots() instantes_tiempo = [j for j in range(len(valores_fo))] # Representación de la solución con una línea ax.plot(instantes_tiempo, valores_fo, linestyle=’-’, linewidth=2, marker=’x ’, markersize=0, color=’b’, alpha=0.7) """""" """ HDHHO """ def HDHHO(instancia, T, tam_pob, archivo): # Inicializar soluciones (águilas) EDD, LSL, OSL, ESL, NEHDedd y el resto hasta N aleatorias. population = [EDD(instancia, archivo), LSL(instancia, archivo), OSL( instancia, archivo), ESL(instancia, archivo), NEHDedd(instancia, archivo)] # Vector para guardar cada una de las soluciones existentes en la población. for i in range(tam_pob-5): population.append(generar_solucion_aleatoria(instancia, archivo)) sec_desag = [] # Vector para guardar cada secuencia desagregada (como vector único, sin asignar a fábricas) sec_val_cont = [] # Vector para guardar los valores de posición de cada secuencia. for i in range(len(population)): sec_desag.append(desagregar_asignacion_por_fabrica(population[i], instancia)) sec_val_cont.append(crear_vector_posicion_por_solucion(sec_desag[i])) spv = copy.deepcopy(sec_desag) soluciones_con_asignacion_tras_spv = [0 for j in range(len(population))] fitness_soluciones = [objective_function(instancia, population[j], archivo) for j in range(len(population))] best_Xprey = copy.deepcopy(population[fitness_soluciones.index(min(fitness_ soluciones))]) best_fitness = min(fitness_soluciones) # Para plotear gráfica valores_fo_grafica = [] plot_E = [] # Duración de cada instancia t1 = time() t2 = time() # Con criterio de terminación por iteraciones. t=0 while t < T: # Emplear SPV para convertir valores continuos en permutación de trabajos. Anexo: Código de programación en Python 51 for i in range(len(population)): spv[i] = SPV(sec_val_cont[i],spv[i]) # Calcular fitness de cada solución (águila), como tengo un vector desagregado, 1o ¯asigno a fábricas, 2o ¯calculo fitness. for i in range(len(spv)): soluciones_con_asignacion_tras_spv[i] = FACTORY_LEAST_CT(instancia, spv[i], archivo) fitness_soluciones[i] = objective_function(instancia, soluciones_con _asignacion_tras_spv[i], archivo) # Escoger Xprey y Xworst como las soluciones con menor y mayor fitness respectivamente. Xprey = copy.deepcopy(soluciones_con_asignacion_tras_spv[fitness_ soluciones.index(min(fitness_soluciones))]) Xworst = copy.deepcopy(soluciones_con_asignacion_tras_spv[fitness_ soluciones.index(max(fitness_soluciones))]) # Generar número aleatorio entre 0 y 1. = random.uniform(0,1) # Calcular X’ aplicando Path-relinking con Xworst, Xprey y . X_prima,TT_X_prima=PATH_RELINKING(Xworst, Xprey, , instancia, archivo) if X_prima!=0: if TT_X_prima < min(fitness_soluciones): Xprey=copy.deepcopy(X_prima) # Como tengo una nueva Xprey, tendré un nuevo vector de posición para Xprey, sec_desag para SPV y fitness. spv[fitness_soluciones.index(min(fitness_soluciones))] = desagregar_asignacion_por_fabrica(Xprey, instancia) sec_val_cont[fitness_soluciones.index(min(fitness_soluciones))] = crear_vector_posicion_por_solucion(spv[fitness_soluciones. index(min(fitness_soluciones))]) fitness_soluciones[fitness_soluciones.index(min(fitness_ soluciones))] = TT_X_prima elif TT_X_prima < max(fitness_soluciones): Xworst=copy.deepcopy(X_prima) # Como tengo una nueva Xworst, tendré un nuevo vector de posició n para Xworst, sec_desag para SPV y fitness. spv[fitness_soluciones.index(max(fitness_soluciones))] = desagregar_asignacion_por_fabrica(Xworst, instancia) sec_val_cont[fitness_soluciones.index(max(fitness_soluciones))] = crear_vector_posicion_por_solucion(spv[fitness_soluciones. index(max(fitness_soluciones))]) fitness_soluciones[fitness_soluciones.index(max(fitness_ soluciones))] = TT_X_prima if TT_X_prima < best_fitness: best_Xprey = copy.deepcopy(X_prima) best_fitness = TT_X_prima # Para plotear gráfica valores_fo_grafica.append(min(fitness_soluciones)) 52 Anexo: Código de programación en Python # COMIENZA BUCLE FOR PARA CADA SOLUCIÓN (ÁGUILA) # Actualizar E usando la ecuación 15. E_0=2*random.random()-1 #Cambia aleatoriamente en el intervalo (-1,1) en cada iteración, ES DECIR, antes bucle EXPLOT. Y EXPLOR. E=2*E_0*(1-(t/T)) #t es la iteración actual y T es el total de iteraciones plot_E.append(E) for i in range(len(population)): # Para |E|>=1 --> EXPLORATION PHASE if abs(E)>=1: # Actualizar el vector de posición (valores continuos) usando ecuación 13. sec_val_cont = copy.deepcopy(exploration_phase(sec_val_cont, fitness_soluciones, i)) # Para |E|<1 --> EXPLOITATION PHASE elif abs(E)<1: r=random.uniform(0, 1) # Soft besiege, actualizar vector posición usando ecuación 16. if r>=0.5 and abs(E)>=0.5: sec_val_cont = copy.deepcopy(soft_besiege(i, sec_val_cont, fitness_soluciones, E)) # Hard besiege, actualizar vector posición usando ecuación 18. elif r>=0.5 and abs(E)<0.5: sec_val_cont = copy.deepcopy(hard_besiege(i, sec_val_cont, fitness_soluciones, E)) # Soft besiege with progressive rapid dives, actualizar vector posición usando ecuación 19. elif r<0.5 and abs(E)>=0.5: sec_val_cont = copy.deepcopy(soft_besiege_with_progressive_ rapid_dives(i, sec_val_cont, fitness_soluciones, population, E, instancia, archivo)) # Hard besiege with progressive rapid dives, actualizar vector posición usando ecuación 22. elif r<0.5 and abs(E)<0.5: sec_val_cont = copy.deepcopy(hard_besiege_with_progressive_ rapid_dives(i, sec_val_cont, fitness_soluciones, population, E, instancia, archivo)) t2 = time() t += 1 print("Tiempo empleado:", t2 - t1) return best_Xprey, best_fitness, valores_fo_grafica, plot_E """""" """ LOCAL SEARCH - IG """ """ Insert Operation para RSLS_s """ Anexo: Código de programación en Python 53 def INSERT_OPERATION(sec_factory_eleg, sec_local_search, selected_factory): #Elijo subsecuencia punto_inicio_subsec=random.randint(0, len(sec_factory_eleg)-1) #Establezco el punto de inicio de la subsecuencia. if punto_inicio_subsec==0 and len(sec_factory_eleg)>1: punto_fin_subsec=random.randint(punto_inicio_subsec, len(sec_factory_ eleg)-2) #Punto fin para evitar sec completa. (-2) else: punto_fin_subsec=random.randint(punto_inicio_subsec, len(sec_factory_ eleg)-1) #Establezco punto de fin. long_subsec=punto_fin_subsec-punto_inicio_subsec+1 #Calculo la longitud de la subsecuencia. (+1 por si los ptos coinciden) subsec=[] for j in range(long_subsec): subsec.append(sec_factory_eleg[punto_inicio_subsec+j]) #Construyo la subsecuencia elegida. #Selecciono el punto de inserción de forma aleatoria. insert_opt=[] #Elaboro una lista con las posiciones posibles para realizar el insert. for j in range(punto_inicio_subsec): insert_opt.append(j) for j in range((punto_fin_subsec+1),len(sec_factory_eleg)): insert_opt.append(j) if insert_opt!=[]: insert_point=random.choice(insert_opt) #Escojo una de las opciones. else: insert_point=0 #Situacion fábrica con un solo elemento que sería una subsecuencia (queda igual), sec_factory vacia. #Inserto la subsecuencia tras el punto de inserción escogido. for j in range(punto_inicio_subsec,punto_fin_subsec+1): sec_factory_eleg.pop(punto_inicio_subsec) #Elimino los trabajos de la subsecuencia en la secuencia completa de la fábrica. if punto_inicio_subsec==(insert_point+1): #Para evitar obtener la misma secuencia repetida. for j in range(long_subsec): sec_factory_eleg.insert(insert_point+j, subsec[j]) #Inserto la subsec. para no repetir original. elif insert_opt!=[]: #En caso de secuencia fabrica unico elemento, no hay opciones como tal y daria error. for j in range(long_subsec): sec_factory_eleg.insert(insert_opt.index(insert_point)+1+j, subsec[j ]) #Inserto la subsecuencia en el punto escogido. elif insert_opt==[]: #Unica posibilidad si solo hay un elemento en la secuencia de la fabrica, lo inserto tal cual y ya. sec_factory_eleg.insert(insert_point, subsec[0]) 54 Anexo: Código de programación en Python #AñADO LA SUBSECUENCIA FINAL ACTUALIZADA A UNA COPIA DE LA SECUENCIA ORIGINAL. sec_local_search[selected_factory]=copy.deepcopy(sec_factory_eleg) return sec_local_search """""" """ Reverse Operation para RSLS_s """ def REVERSE_OPERATION(sec_factory_eleg, sec_local_search, selected_factory): #Elegir subsecuencia (repetido de la opción anterior). punto_inicio_subsec=random.randint(0, len(sec_factory_eleg)-1) #Establezco el punto de inicio de la subsecuencia. if punto_inicio_subsec==0 and len(sec_factory_eleg)>1: punto_fin_subsec=random.randint(punto_inicio_subsec, len(sec_factory_ eleg)-2) #Punto fin para evitar sec completa. (-2) else: punto_fin_subsec=random.randint(punto_inicio_subsec, len(sec_factory_ eleg)-1) #Establezco punto de fin. long_subsec=punto_fin_subsec-punto_inicio_subsec+1 #Calculo la longitud de la subsecuencia. (+1 por si los ptos coinciden) subsec=[] for j in range(long_subsec): subsec.append(sec_factory_eleg[punto_inicio_subsec+j]) #Construyo la subsecuencia elegida. #Invertir la subsecuencia dentro de la secuencia. (1o ¯Elimino subsec de la sec. |2o ¯Inserto la subsec en la sec invirtiendola) for j in range(punto_inicio_subsec,punto_fin_subsec+1): sec_factory_eleg.pop(punto_inicio_subsec) #Elimino los trabajos de la subsecuencia en la secuencia completa de la fábrica. for j in range(long_subsec): sec_factory_eleg.insert(punto_inicio_subsec+j, subsec[long_subsec-1-j]) #Inserto valores subsec de atrás hacia delante. #AñADO LA SUBSECUENCIA FINAL ACTUALIZADA A UNA COPIA DE LA SECUENCIA ORIGINAL. sec_local_search[selected_factory]=copy.deepcopy(sec_factory_eleg) return sec_local_search """""" """ Inicialización RSLS_m """ def INITIALIZATION_RSLS_m(sec, archivo): #Elegir 2 fábricas de forma aleatoria. total_factories=[] for f in range(read_tag(archivo, "FACTORIES")): total_factories.append(f) factory_A=random.choice(total_factories) total_factories.pop(factory_A) Anexo: Código de programación en Python 55 factory_B=random.choice(total_factories) #Escojo la fábrica con la secuencia más corta, elijo una subsecuencia en esta (que será válida para la otra fábrica también). if len(sec[factory_A])<=len(sec[factory_B]): selected_factory=factory_A factory_alternativa=factory_B situacion=0 else: selected_factory=factory_B factory_alternativa=factory_A situacion=1 sec_factory_eleg=copy.deepcopy(sec[selected_factory]) #Fábrica con la secuencia de menor longitud. sec_factory_alternativa=copy.deepcopy(sec[factory_alternativa]) #Fabrica con la secuencia de mayor longitud. #Elegir subsecuencia DE LA FÁBRICA CON SECUENCIA CORTA (repetido de la opci ón anterior). punto_inicio_subsec=random.randint(0, len(sec_factory_eleg)-1) #Establezco el punto de inicio de la subsecuencia. if punto_inicio_subsec==0 and len(sec_factory_eleg)>1: punto_fin_subsec=random.randint(punto_inicio_subsec, len(sec_factory_ eleg)-2) #Punto fin para evitar sec completa. (-2) else: punto_fin_subsec=random.randint(punto_inicio_subsec, len(sec_factory_ eleg)-1) #Establezco punto de fin. long_subsec=punto_fin_subsec-punto_inicio_subsec+1 #Calculo la longitud de la subsecuencia (g). (+1 por si los ptos coinciden) #Elegir PUNTO DE INICIO en la FÁBRICA CON SECUENCIA LARGA (no tiene porque coincidir con el de la otra fabrica). punto_inicio_subsec_larga=random.randint(0, len(sec_factory_alternativa)- long_subsec) subsec_A=[] subsec_B=[] if situacion==0: for j in range(long_subsec): subsec_A.append(sec_factory_eleg[punto_inicio_subsec+j]) #Construyo la subsecuencia de la fábrica A. subsec_B.append(sec_factory_alternativa[punto_inicio_subsec_larga+j ]) elif situacion==1: for j in range(long_subsec): subsec_B.append(sec_factory_eleg[punto_inicio_subsec+j]) #Construyo la subsecuencia de la fábrica A. subsec_A.append(sec_factory_alternativa[punto_inicio_subsec_larga+j ]) return subsec_A, subsec_B, punto_inicio_subsec, punto_fin_subsec, situacion , long_subsec, punto_inicio_subsec_larga, sec_factory_alternativa, factory_A, factory_B, sec_factory_eleg 56 Anexo: Código de programación en Python """""" """ Swap Operation para RSLS_m """ def SWAP_OPERATION(punto_inicio_subsec, punto_fin_subsec, sec_factory_eleg, situacion, long_subsec, subsec_A, subsec_B, punto_inicio_subsec_larga, sec_ factory_alternativa, sec_local_search, factory_A, factory_B): #TENGO: sec_factory_eleg, sec_factory_alternativa (secuencia de cada fab) y subsec_A, subsec_B (intercambiar en sec orig). #Inserto la subsecuencia de sec_factory_alternativa en sec_factory_eleg. for j in range(punto_inicio_subsec,punto_fin_subsec+1): sec_factory_eleg.pop(punto_inicio_subsec) #Elimino los trabajos de la subsecuencia en la secuencia completa de la fábrica. if situacion==0: for j in range(long_subsec): sec_factory_eleg.insert(punto_inicio_subsec+j, subsec_B[j]) #Inserto la subsecuencia en el punto escogido. elif situacion==1: for j in range(long_subsec): sec_factory_eleg.insert(punto_inicio_subsec+j, subsec_A[j]) #Inserto la subsecuencia en el punto escogido. #Inserto la subsecuencia de sec_factory_eleg en sec_factory_alternativa. for j in range(punto_inicio_subsec_larga,punto_inicio_subsec_larga+long_ subsec): sec_factory_alternativa.pop(punto_inicio_subsec_larga) #Elimino los trabajos de la subsec en la sec completa de la fábrica. if situacion==0: for j in range(long_subsec): sec_factory_alternativa.insert(punto_inicio_subsec_larga+j, subsec_A [j]) #Inserto la subsecuencia en el punto escogido. elif situacion==1: for j in range(long_subsec): sec_factory_alternativa.insert(punto_inicio_subsec_larga+j, subsec_B [j]) #Inserto la subsecuencia en el punto escogido. #SOBREESCRIBIR ESAS NUEVAS SECUENCIAS SWAPEADAS EN LA SECUENCIA ORIGINAL. if situacion==0: sec_local_search[factory_A]=copy.deepcopy(sec_factory_eleg) sec_local_search[factory_B]=copy.deepcopy(sec_factory_alternativa) elif situacion==1: sec_local_search[factory_A]=copy.deepcopy(sec_factory_alternativa) sec_local_search[factory_B]=copy.deepcopy(sec_factory_eleg) return sec_local_search """""" Anexo: Código de programación en Python 57 """ Swap + Reverse Operation para RSLS_m """ def SWAP_AND_REVERSE_OPERATION(punto_inicio_subsec, punto_fin_subsec, sec_ factory_eleg, situacion, long_subsec, subsec_A, subsec_B, punto_inicio_ subsec_larga, sec_factory_alternativa, sec_local_search, factory_A, factory _B): #Inserto la subsecuencia de sec_factory_alternativa en sec_factory_eleg. for j in range(punto_inicio_subsec,punto_fin_subsec+1): sec_factory_eleg.pop(punto_inicio_subsec) #Elimino los trabajos de la subsecuencia en la secuencia completa de la fábrica. if situacion==0: for j in range(long_subsec): sec_factory_eleg.insert(punto_inicio_subsec, subsec_B[j]) #Inserto la subsecuencia en el punto escogido. elif situacion==1: for j in range(long_subsec): sec_factory_eleg.insert(punto_inicio_subsec, subsec_A[j]) #Inserto la subsecuencia en el punto escogido. #Inserto la subsecuencia de sec_factory_eleg en sec_factory_alternativa. for j in range(punto_inicio_subsec_larga,punto_inicio_subsec_larga+long_ subsec): sec_factory_alternativa.pop(punto_inicio_subsec_larga) #Elimino los trabajos de la subsec en la sec completa de la fábrica. if situacion==0: for j in range(long_subsec): sec_factory_alternativa.insert(punto_inicio_subsec_larga, subsec_A[j ]) #Inserto la subsecuencia en el punto escogido. elif situacion==1: for j in range(long_subsec): sec_factory_alternativa.insert(punto_inicio_subsec_larga, subsec_B[j ]) #Inserto la subsecuencia en el punto escogido. #SOBREESCRIBIR ESAS NUEVAS SECUENCIAS SWAPEADAS EN LA SECUENCIA ORIGINAL. if situacion==0: sec_local_search[factory_A]=copy.deepcopy(sec_factory_eleg) sec_local_search[factory_B]=copy.deepcopy(sec_factory_alternativa) elif situacion==1: sec_local_search[factory_A]=copy.deepcopy(sec_factory_alternativa) sec_local_search[factory_B]=copy.deepcopy(sec_factory_eleg) return sec_local_search """""" """ RSLS """ def RSLS(sec, instancia, archivo): flag=True 64 Anexo: Código de programación en Python ax.plot(instantes_tiempo[valores_fo.index(min(valores_fo))], valores_fo[ valores_fo.index(min(valores_fo))], linestyle=’ ’, linewidth=0, marker=’ o’, markersize=10, color=’r’, alpha=1, label=’Optimo Local’) ax.set_ylabel(’Valor de la F.O.’) ax.set_xlabel(’Iteraciones’) ax.legend() # Guardar la gráfica plt.savefig("RESULTADOS/small_instances/graficas_IG/IG_I_" + str(ff) + "_" + str(jj) + "_" + str(ii) + "_" + str(kk) + ".png") # Mostrar la gráfica plt.show() def grafica_IG_inst_large(valores_fo, ff, jj, ii, kk): fig, ax = plt.subplots() instantes_tiempo = [j for j in range(len(valores_fo))] # Representación de la solución con una línea ax.plot(instantes_tiempo, valores_fo, linestyle=’-’, linewidth=2, marker=’x ’, markersize=0, color=’b’, alpha=0.7) # Representación de la solución óptima ax.plot(instantes_tiempo[valores_fo.index(min(valores_fo))], valores_fo[ valores_fo.index(min(valores_fo))], linestyle=’ ’, linewidth=0, marker=’ o’, markersize=10, color=’r’, alpha=1, label=’Optimo Local’) ax.set_ylabel(’Valor de la F.O.’) ax.set_xlabel(’Iteraciones’) ax.legend() # Guardar la gráfica plt.savefig("RESULTADOS/large_instances/graficas_IG/IG_Ta" + str(ff) + str( jj) + str(ii) + "_" + str(kk) + ".png") # Mostrar la gráfica plt.show() """""""""""""""""""""""" ##### RESULTADOS EDD INSTANCIAS PEQUEñAS ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl import os """ EDD PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’EDD_INST_SMALL.txt’,’w’) as archivo_resultados_inst_small: archivo_resultados_inst_small.write("") # Escribo titulo en txt with open("EDD_INST_SMALL.txt","a") as RESULTADOS: RESULTADOS.write("RESULTADOS EDD: Instancia, Valor FO, Secuencias, Tiempo de ejecución\n") Anexo: Código de programación en Python 65 # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 ws.cell(row = fila, column = 1, value = "Instancia") ws.cell(row = fila, column = 2, value = "Valor FO") ws.cell(row = fila, column = 3, value = "Secuencias") ws.cell(row = fila, column = 4, value = "Tiempo ejecución") for ff in range(2,5): for jj in range(4,18,2): for ii in range(2,6): for kk in range(1,6): # Instancias automatizadas archivo=’DPFSP_DD/I_’ + str(ff) + ’_’ + str(jj) + ’_’ + str(ii) + ’_’ + str(kk) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia fila += 1 ws.cell(row = fila, column = 1, value = "I_" + str(ff) + "_" + str(jj) + "_" + str(ii) + "_" + str(kk) + ".txt ") t1 = time() secuencias = EDD(instancia, archivo) t2 = time() valor_fo = objective_function(instancia, secuencias, archivo) print("Valor FO:", valor_fo) with open("EDD_INST_SMALL.txt","a") as RESULTADOS: RESULTADOS.write("\nI_" + str(ff) + "_" + str(jj) + "_" + str (ii) + "_" + str(kk) + ".txt | " + "FO=" + str(valor_fo) + " | secs=" + str(secuencias) + " | time ex=" + str(t2-t 1) + "\n") # Escribir valores en las celdas ws.cell(row = fila, column = 2, value = valor_fo) ws.cell(row = fila, column = 3, value = str(secuencias)) ws.cell(row = fila, column = 4, value = (t2-t1)) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\TFG’) # Definir el nombre del archivo archivo_nombre = ’EDD_inst_small.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre) # Guardar el archivo wb.save(archivo_ruta) """""" 66 Anexo: Código de programación en Python """""""""""""""""""""""" ##### RESULTADOS EDD INSTANCIAS GRANDES ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl import os """ EDD PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’EDD_INST_LARGE.txt’,’w’) as archivo_resultados_inst_large: archivo_resultados_inst_large.write("") # Escribo titulo en txt with open("EDD_INST_LARGE.txt","a") as RESULTADOS: RESULTADOS.write("RESULTADOS EDD: Instancia, Valor FO, Secuencias, Tiempo de ejecución\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 ws.cell(row = fila, column = 1, value = "Instancia") ws.cell(row = fila, column = 2, value = "Valor FO") ws.cell(row = fila, column = 3, value = "Secuencias") ws.cell(row = fila, column = 4, value = "Tiempo ejecución") ws.cell(row = fila, column = 5, value = "Large Instances") for pp in range(2): for qq in range(10): for rr in range(10): for ff in range(2,8): if (pp==0 and qq==0 and rr==0): break else: # Instancias automatizadas archivo = ’DPFSP_DD/Ta’ + str(pp) + str(qq) + str(rr) + ’_’ + str(ff) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia fila += 1 ws.cell(row = fila, column = 1, value = "Ta" + str(pp) + str( qq) + str(rr) + "_" + str(ff) + ".txt") t1 = time() secuencias = EDD(instancia, archivo) t2 = time() Anexo: Código de programación en Python 67 valor_fo = objective_function(instancia, secuencias, archivo) print("Valor FO:", valor_fo) with open("EDD_INST_LARGE.txt","a") as RESULTADOS: RESULTADOS.write("\nTa" + str(pp) + str(qq) + str(rr) + "_" + str(ff) + ".txt | " + "FO=" + str(valor_fo) + " | secs=" + str(secuencias) + " | time ex=" + str(t2t1) + "\n") # Escribir valores en las celdas ws.cell(row = fila, column = 2, value = valor_fo) ws.cell(row = fila, column = 3, value = str(secuencias)) ws.cell(row = fila, column = 4, value = (t2-t1)) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\TFG ’) # Definir el nombre del archivo archivo_nombre = ’EDD_inst_large.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre) # Guardar el archivo wb.save(archivo_ruta) """""" """""""""""""""""""""""" ##### RESULTADOS OSL INSTANCIAS PEQUEñAS ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl import os """ OSL PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’OSL_INST_SMALL.txt’,’w’) as archivo_resultados_inst_small: archivo_resultados_inst_small.write("") # Escribo titulo en txt with open("OSL_INST_SMALL.txt","a") as RESULTADOS: RESULTADOS.write("RESULTADOS OSL: Instancia, Valor FO, Secuencias, Tiempo de ejecución\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 ws.cell(row = fila, column = 1, value = "Instancia") ws.cell(row = fila, column = 2, value = "Valor FO") ws.cell(row = fila, column = 3, value = "Secuencias") 68 Anexo: Código de programación en Python ws.cell(row = fila, column = 4, value = "Tiempo ejecución") for ff in range(2,5): for jj in range(4,18,2): for ii in range(2,6): for kk in range(1,6): # Instancias automatizadas archivo=’DPFSP_DD/I_’ + str(ff) + ’_’ + str(jj) + ’_’ + str(ii) + ’_’ + str(kk) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia fila += 1 ws.cell(row = fila, column = 1, value = "I_" + str(ff) + "_" + str(jj) + "_" + str(ii) + "_" + str(kk) + ".txt ") t1 = time() secuencias = OSL(instancia, archivo) t2 = time() valor_fo = objective_function(instancia, secuencias, archivo) print("Valor FO:", valor_fo) with open("OSL_INST_SMALL.txt","a") as RESULTADOS: RESULTADOS.write("\nI_" + str(ff) + "_" + str(jj) + "_" + str (ii) + "_" + str(kk) + ".txt | " + "FO=" + str(valor_fo) + " | secs=" + str(secuencias) + " | time ex=" + str(t2-t 1) + "\n") # Escribir valores en las celdas ws.cell(row = fila, column = 2, value = valor_fo) ws.cell(row = fila, column = 3, value = str(secuencias)) ws.cell(row = fila, column = 4, value = (t2-t1)) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\TFG’) # Definir el nombre del archivo archivo_nombre = ’OSL_inst_small.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre) # Guardar el archivo wb.save(archivo_ruta) """""" """""""""""""""""""""""" ##### RESULTADOS OSL INSTANCIAS GRANDES ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl Anexo: Código de programación en Python 69 import os """ OSL PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’OSL_INST_LARGE.txt’,’w’) as archivo_resultados_inst_large: archivo_resultados_inst_large.write("") # Escribo titulo en txt with open("OSL_INST_LARGE.txt","a") as RESULTADOS: RESULTADOS.write("RESULTADOS OSL: Instancia, Valor FO, Secuencias, Tiempo de ejecución\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 ws.cell(row = fila, column = 1, value = "Instancia") ws.cell(row = fila, column = 2, value = "Valor FO") ws.cell(row = fila, column = 3, value = "Secuencias") ws.cell(row = fila, column = 4, value = "Tiempo ejecución") ws.cell(row = fila, column = 5, value = "Large Instances") for pp in range(2): for qq in range(10): for rr in range(10): for ff in range(2,8): if (pp==0 and qq==0 and rr==0): break else: # Instancias automatizadas archivo = ’DPFSP_DD/Ta’ + str(pp) + str(qq) + str(rr) + ’_’ + str(ff) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia fila += 1 ws.cell(row = fila, column = 1, value = "Ta" + str(pp) + str( qq) + str(rr) + "_" + str(ff) + ".txt") t1 = time() secuencias = OSL(instancia, archivo) t2 = time() valor_fo = objective_function(instancia, secuencias, archivo) print("Valor FO:", valor_fo) with open("OSL_INST_LARGE.txt","a") as RESULTADOS: RESULTADOS.write("\nTa" + str(pp) + str(qq) + str(rr) + "_" + str(ff) + ".txt | " + "FO=" + str(valor_fo) + " 70 Anexo: Código de programación en Python | secs=" + str(secuencias) + " | time ex=" + str(t2t1) + "\n") # Escribir valores en las celdas ws.cell(row = fila, column = 2, value = valor_fo) ws.cell(row = fila, column = 3, value = str(secuencias)) ws.cell(row = fila, column = 4, value = (t2-t1)) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\TFG ’) # Definir el nombre del archivo archivo_nombre = ’OSL_inst_large.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre) # Guardar el archivo wb.save(archivo_ruta) """""" """""""""""""""""""""""" ##### RESULTADOS LSL INSTANCIAS PEQUEñAS ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl import os """ LSL PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’LSL_INST_SMALL.txt’,’w’) as archivo_resultados_inst_small: archivo_resultados_inst_small.write("") # Escribo titulo en txt with open("LSL_INST_SMALL.txt","a") as RESULTADOS: RESULTADOS.write("RESULTADOS LSL: Instancia, Valor FO, Secuencias, Tiempo de ejecución\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 ws.cell(row = fila, column = 1, value = "Instancia") ws.cell(row = fila, column = 2, value = "Valor FO") ws.cell(row = fila, column = 3, value = "Secuencias") ws.cell(row = fila, column = 4, value = "Tiempo ejecución") for ff in range(2,5): for jj in range(4,18,2): for ii in range(2,6): for kk in range(1,6): Anexo: Código de programación en Python 71 # Instancias automatizadas archivo=’DPFSP_DD/I_’ + str(ff) + ’_’ + str(jj) + ’_’ + str(ii) + ’_’ + str(kk) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia fila += 1 ws.cell(row = fila, column = 1, value = "I_" + str(ff) + "_" + str(jj) + "_" + str(ii) + "_" + str(kk) + ".txt ") t1 = time() secuencias = LSL(instancia, archivo) t2 = time() valor_fo = objective_function(instancia, secuencias, archivo) print("Valor FO:", valor_fo) with open("LSL_INST_SMALL.txt","a") as RESULTADOS: RESULTADOS.write("\nI_" + str(ff) + "_" + str(jj) + "_" + str (ii) + "_" + str(kk) + ".txt | " + "FO=" + str(valor_fo) + " | secs=" + str(secuencias) + " | time ex=" + str(t2-t 1) + "\n") # Escribir valores en las celdas ws.cell(row = fila, column = 2, value = valor_fo) ws.cell(row = fila, column = 3, value = str(secuencias)) ws.cell(row = fila, column = 4, value = (t2-t1)) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\TFG’) # Definir el nombre del archivo archivo_nombre = ’LSL_inst_small.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre) # Guardar el archivo wb.save(archivo_ruta) """""" """""""""""""""""""""""" ##### RESULTADOS LSL INSTANCIAS GRANDES ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl import os """ LSL PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’LSL_INST_LARGE.txt’,’w’) as archivo_resultados_inst_large: 72 Anexo: Código de programación en Python archivo_resultados_inst_large.write("") # Escribo titulo en txt with open("LSL_INST_LARGE.txt","a") as RESULTADOS: RESULTADOS.write("RESULTADOS LSL: Instancia, Valor FO, Secuencias, Tiempo de ejecución\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 ws.cell(row = fila, column = 1, value = "Instancia") ws.cell(row = fila, column = 2, value = "Valor FO") ws.cell(row = fila, column = 3, value = "Secuencias") ws.cell(row = fila, column = 4, value = "Tiempo ejecución") ws.cell(row = fila, column = 5, value = "Large Instances") for pp in range(2): for qq in range(10): for rr in range(10): for ff in range(2,8): if (pp==0 and qq==0 and rr==0): break else: # Instancias automatizadas archivo = ’DPFSP_DD/Ta’ + str(pp) + str(qq) + str(rr) + ’_’ + str(ff) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia fila += 1 ws.cell(row = fila, column = 1, value = "Ta" + str(pp) + str( qq) + str(rr) + "_" + str(ff) + ".txt") t1 = time() secuencias = LSL(instancia, archivo) t2 = time() valor_fo = objective_function(instancia, secuencias, archivo) print("Valor FO:", valor_fo) with open("LSL_INST_LARGE.txt","a") as RESULTADOS: RESULTADOS.write("\nTa" + str(pp) + str(qq) + str(rr) + "_" + str(ff) + ".txt | " + "FO=" + str(valor_fo) + " | secs=" + str(secuencias) + " | time ex=" + str(t2t1) + "\n") # Escribir valores en las celdas ws.cell(row = fila, column = 2, value = valor_fo) ws.cell(row = fila, column = 3, value = str(secuencias)) ws.cell(row = fila, column = 4, value = (t2-t1)) Anexo: Código de programación en Python 73 # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\TFG ’) # Definir el nombre del archivo archivo_nombre = ’LSL_inst_large.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre) # Guardar el archivo wb.save(archivo_ruta) """""" """""""""""""""""""""""" ##### RESULTADOS ESL INSTANCIAS PEQUEñAS ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl import os """ ESL PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’ESL_INST_SMALL.txt’,’w’) as archivo_resultados_inst_small: archivo_resultados_inst_small.write("") # Escribo titulo en txt with open("ESL_INST_SMALL.txt","a") as RESULTADOS: RESULTADOS.write("RESULTADOS ESL: Instancia, Valor FO, Secuencias, Tiempo de ejecución\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 ws.cell(row = fila, column = 1, value = "Instancia") ws.cell(row = fila, column = 2, value = "Valor FO") ws.cell(row = fila, column = 3, value = "Secuencias") ws.cell(row = fila, column = 4, value = "Tiempo ejecución") for ff in range(2,5): for jj in range(4,18,2): for ii in range(2,6): for kk in range(1,6): # Instancias automatizadas archivo=’DPFSP_DD/I_’ + str(ff) + ’_’ + str(jj) + ’_’ + str(ii) + ’_’ + str(kk) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia 80 Anexo: Código de programación en Python t1 = time() valor_fo, best_seq_IG, valores_grafica_ig = ITERATED_GREEDY(d, T _0, sec_initializ, local_search, instancia, archivo, tiempo_ compilacion) #Tendre que dar d, T_0, secuencia de inicialización, método búsqueda local y N (numero de iteraciones a realizar) t2 = time() print("Valor F.O.:", valor_fo, "para la mejor secuencia IG:", best_seq_IG) grafica_IG(valores_grafica_ig, ff, jj, ii, kk) # Crear carpeta para guardar gantts carpeta = "RESULTADOS/small_instances/gantt_IG/IG_gantt_I_" + str(ff) + "_" + str(jj) + "_" + str(ii) + "_" + str(kk) if not os.path.exists(carpeta): os.makedirs(carpeta) # Generar y guardar gantts for i in range(len(best_seq_IG)): instancia.print_schedule(best_seq_IG[i],"RESULTADOS/small_ instances/gantt_IG/IG_gantt_I_" + str(ff) + "_" + str(jj) + "_" + str(ii) + "_" + str(kk) + "/factory_" + str(i+1) + ".png") # Escribir en txt with open("IG_INST_SMALL.txt","a") as RESULTADOS: RESULTADOS.write("\nI_" + str(ff) + "_" + str(jj) + "_" + str (ii) + "_" + str(kk) + ".txt | " + "FO=" + str(valor_fo) + " | secs=" + str(best_seq_IG) + " | time ex=" + str(t2t1) + "\n") # Escribir valores en las celdas de excel ws.cell(row = fila, column = 2, value = valor_fo) ws.cell(row = fila, column = 3, value = str(best_seq_IG)) ws.cell(row = fila, column = 4, value = (t2-t1)) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\TFG’) # Definir el nombre del archivo archivo_nombre = ’IG_inst_small.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre) # Guardar el archivo wb.save(archivo_ruta) # Para comparar tiempo con HDHHO indice_tiempo += 1 """""" """""""""""""""""""""""" ##### RESULTADOS IG INSTANCIAS GRANDES ##### """""""""""""""""""""""" Anexo: Código de programación en Python 81 from heuristicas_v8 import * import openpyxl import os """ ITERATED GREEDY PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’IG_INST_LARGE.txt’,’w’) as archivo_resultados_inst_large: archivo_resultados_inst_large.write("") # Escribo titulo en txt with open("IG_INST_LARGE.txt","a") as RESULTADOS: RESULTADOS.write("RESULTADOS IG INST LARGE: Instancia, Valor FO, Secuencias , Tiempo de ejecución. Para secuencia inicialización NEHDedd, d=0.2, T _0=1 y búsqueda local RSLS.\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 ws.cell(row = fila, column = 1, value = "Instancia") ws.cell(row = fila, column = 2, value = "Valor FO") ws.cell(row = fila, column = 3, value = "Secuencias") ws.cell(row = fila, column = 4, value = "Tiempo ejecución") ws.cell(row = fila, column = 5, value = "NEHDedd, d=0.2, T_0=1, RSLS") tiempo_comparativo = [] # Lista de tiempo del HDHHO en cada instancia indice_tiempo = 0 for pp in range(2): for qq in range(10): for rr in range(10): for ff in range(2,8): if (pp==0 and qq==0 and rr==0): break else: # Instancias automatizadas archivo = ’DPFSP_DD/Ta’ + str(pp) + str(qq) + str(rr) + ’_’ + str(ff) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia sec_initializ = NEHDedd # Procedimiento de inicialización de la solución. d = 0.2 # % de destrucción de los trabajos. T_0 = 1 # Parámetro de temperatura. local_search = RSLS # Método de búsqueda local. fila += 1 ws.cell(row = fila, column = 1, value = "Ta" + str(pp) + str( qq) + str(rr) + "_" + str(ff) + ".txt") 82 Anexo: Código de programación en Python tiempo_compilacion = tiempo_comparativo[indice_tiempo] t1 = time() valor_fo, best_seq_IG, valores_grafica_ig = ITERATED_GREEDY(d , T_0, sec_initializ, local_search, instancia, archivo, tiempo_compilacion) #Tendre que dar d, T_0, secuencia de inicialización, método búsqueda local y N (numero de iteraciones a realizar) t2 = time() print("Valor F.O.:", valor_fo, "para la mejor secuencia IG:", best_seq_IG) grafica_IG_inst_large(valores_grafica_ig, pp, qq, rr, ff) # Crear carpeta para guardar gantts carpeta = "RESULTADOS/large_instances/gantt_IG/IG_gantt_Ta" + str(pp) + str(qq) + str(rr) + "_" + str(ff) if not os.path.exists(carpeta): os.makedirs(carpeta) # Generar y guardar gantts for i in range(len(best_seq_IG)): instancia.print_schedule(best_seq_IG[i],"RESULTADOS/large _instances/gantt_IG/IG_gantt_Ta" + str(pp) + str(qq) + str(rr) + "_" + str(ff) + "/factory_" + str(i+1) + ".png") # Escribir en txt with open("IG_INST_LARGE.txt","a") as RESULTADOS: RESULTADOS.write("\nTa" + str(pp) + str(qq) + str(rr) + "_" + str(ff) + ".txt | " + "FO=" + str(valor_fo) + " | secs=" + str(best_seq_IG) + " | time ex=" + str(t2t1) + "\n") # Escribir valores en las celdas de excel ws.cell(row = fila, column = 2, value = valor_fo) ws.cell(row = fila, column = 3, value = str(best_seq_IG)) ws.cell(row = fila, column = 4, value = (t2-t1)) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\TFG ’) # Definir el nombre del archivo archivo_nombre = ’IG_inst_large.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre) # Guardar el archivo wb.save(archivo_ruta) # Para comparar tiempo con HDHHO indice_tiempo += 1 """""" """""""""""""""""""""""" Anexo: Código de programación en Python 83 ##### RESULTADOS HDHHO INSTANCIAS PEQUEñAS ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl import os """ HDHHO PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’HDHHO_INST_SMALL.txt’,’w’) as archivo_resultados_inst_small: archivo_resultados_inst_small.write("") # Escribo titulo en txt with open("HDHHO_INST_SMALL.txt","a") as RESULTADOS: RESULTADOS.write("RESULTADOS HDHHO INST SMALL: Instancia, Valor FO, Secuencias, Tiempo de ejecución. Para población=30 y N=200.\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 ws.cell(row = fila, column = 1, value = "Instancia") ws.cell(row = fila, column = 2, value = "Valor FO") ws.cell(row = fila, column = 3, value = "Secuencias") ws.cell(row = fila, column = 4, value = "Tiempo ejecución") ws.cell(row = fila, column = 5, value = "POB=30, N=200") for ff in range(2,5): for jj in range(4,18,2): for ii in range(2,6): for kk in range(1,6): # Instancias automatizadas archivo=’DPFSP_DD/I_’ + str(ff) + ’_’ + str(jj) + ’_’ + str(ii) + ’_’ + str(kk) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia tam_pob = 30 # Tamaño de la población. N = 200 # Número máximo de iteraciones. fila += 1 ws.cell(row = fila, column = 1, value = "I_" + str(ff) + "_" + str(jj) + "_" + str(ii) + "_" + str(kk) + ".txt") t1 = time() best_Xprey, best_fitness, valores_fo_grafica, plot_E = HDHHO( instancia, N, tam_pob, archivo) t2 = time() print("best Xprey y best fitness",best_Xprey,best_fitness) grafica_HDHHO(valores_fo_grafica, ff, jj, ii, kk) grafica_plot_E(plot_E) 84 Anexo: Código de programación en Python # Crear carpeta para guardar gantts carpeta = "RESULTADOS/small_instances/gantt_HDHHO/HDHHO_gantt_I _" + str(ff) + "_" + str(jj) + "_" + str(ii) + "_" + str(kk) if not os.path.exists(carpeta): os.makedirs(carpeta) # Generar y guardar gantts for i in range(len(best_Xprey)): instancia.print_schedule(best_Xprey[i],"RESULTADOS/small_ instances/gantt_HDHHO/HDHHO_gantt_I_" + str(ff) + "_" + str(jj) + "_" + str(ii) + "_" + str(kk) + "/factory_" + str(i+1) + ".png") # Escribir en txt with open("HDHHO_INST_SMALL.txt","a") as RESULTADOS: RESULTADOS.write("\nI_" + str(ff) + "_" + str(jj) + "_" + str (ii) + "_" + str(kk) + ".txt | " + "FO=" + str(best_ fitness) + " | secs=" + str(best_Xprey) + " | time ex=" + str(t2-t1) + "\n") # Escribir valores en las celdas de excel ws.cell(row = fila, column = 2, value = best_fitness) ws.cell(row = fila, column = 3, value = str(best_Xprey)) ws.cell(row = fila, column = 4, value = (t2-t1)) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\TFG’) # Definir el nombre del archivo archivo_nombre = ’HDHHO_inst_small.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre) # Guardar el archivo wb.save(archivo_ruta) """""" """""""""""""""""""""""" ##### RESULTADOS HDHHO INSTANCIAS GRANDES ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl import os """ HDHHO PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’HDHHO_INST_LARGE.txt’,’w’) as archivo_resultados_inst_large: archivo_resultados_inst_large.write("") # Escribo titulo en txt with open("HDHHO_INST_LARGE.txt","a") as RESULTADOS: Anexo: Código de programación en Python 85 RESULTADOS.write("RESULTADOS HDHHO INST LARGE: Instancia, Valor FO, Secuencias, Tiempo de ejecución. Para población=30 y N=200.\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 ws.cell(row = fila, column = 1, value = "Instancia") ws.cell(row = fila, column = 2, value = "Valor FO") ws.cell(row = fila, column = 3, value = "Secuencias") ws.cell(row = fila, column = 4, value = "Tiempo ejecución") ws.cell(row = fila, column = 5, value = "POB=30, N=200") for pp in range(2): for qq in range(10): for rr in range(10): for ff in range(2,8): if (pp==0 and qq==0 and rr==0): break else: # Instancias automatizadas archivo = ’DPFSP_DD/Ta’ + str(pp) + str(qq) + str(rr) + ’_’ + str(ff) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia tam_pob = 30 # Tamaño de la población. N = 200 # Número máximo de iteraciones. fila += 1 ws.cell(row = fila, column = 1, value = "Ta" + str(pp) + str( qq) + str(rr) + "_" + str(ff) + ".txt") t1 = time() best_Xprey, best_fitness, valores_fo_grafica, plot_E = HDHHO( instancia, N, tam_pob, archivo) t2 = time() print("Valor F.O.:", best_fitness, "para la mejor secuencia HDHHO:", best_Xprey) grafica_HDHHO_inst_large(valores_fo_grafica, pp, qq, rr, ff) grafica_plot_E(plot_E) # Crear carpeta para guardar gantts carpeta = "RESULTADOS/large_instances/gantt_HDHHO/HDHHO_gantt _Ta" + str(pp) + str(qq) + str(rr) + "_" + str(ff) if not os.path.exists(carpeta): os.makedirs(carpeta) # Generar y guardar gantts for i in range(len(best_Xprey)): instancia.print_schedule(best_Xprey[i],"RESULTADOS/large_ instances/gantt_HDHHO/HDHHO_gantt_Ta" + str(pp) + str 86 Anexo: Código de programación en Python (qq) + str(rr) + "_" + str(ff) + "/factory_" + str(i +1) + ".png") # Escribir en txt with open("HDHHO_INST_LARGE.txt","a") as RESULTADOS: RESULTADOS.write("\nTa" + str(pp) + str(qq) + str(rr) + "_" + str(ff) + ".txt | " + "FO=" + str(best_fitness) + " | secs=" + str(best_Xprey) + " | time ex=" + str (t2-t1) + "\n") # Escribir valores en las celdas de excel ws.cell(row = fila, column = 2, value = best_fitness) ws.cell(row = fila, column = 3, value = str(best_Xprey)) ws.cell(row = fila, column = 4, value = (t2-t1)) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\TFG ’) # Definir el nombre del archivo archivo_nombre = ’HDHHO_inst_large.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre) # Guardar el archivo wb.save(archivo_ruta) """""" """""""""""""""""""""""" ##### CALIBRADO IG ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl import os """ ITERATED GREEDY PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’IG_TUNING_AUXILIAR_2.txt’,’w’) as archivo_resultados_tuning: archivo_resultados_tuning.write("") # Escribo titulo en txt with open("IG_TUNING_AUXILIAR_2.txt","a") as RESULTADOS_TUNING_AUX: RESULTADOS_TUNING_AUX.write("TUNING PARÁMETROS PARA IG: sec_initializ, local_search, d, T_0\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 factories = [2,3,4,5,6,7] jobs = [20,50,100] Anexo: Código de programación en Python 87 machines = [5,10,20] for ff,num_fact in enumerate(factories): for jj,num_jobs in enumerate(jobs): for ii,num_maq in enumerate(machines): for kk in range(1,2): # Instancias automatizadas archivo=’TUNING/Instancias_tuning_aux_2/Tuning_’ + str(num_fact) + ’_’ + str(num_jobs) + ’_’ + str(num_maq) + ’_’ + str(kk) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia sec_initializ = [ESL, NEHDedd] # Procedimiento de inicialización de la solución. d = [0.2, 0.3, 0.5] # % de destrucción de los trabajos. T_0 = [0.1, 0.4, 1, 10] # Parámetro de temperatura. local_search = [RSLS, RPLS] # Método de búsqueda local. sec_used = ["ESL","NEHDedd"] # Para excel met_LS = ["RSLS","RPLS"] # Para excel fila += 1 columna = 2 ws.cell(row = fila, column = 1, value = "T_" + str(num_fact) + "_" + str(num_jobs) + "_" + str(num_maq) + "_" + str(kk) + ". txt ") for q in range(len(sec_initializ)): for r in range(len(d)): for s in range(len(T_0)): for t in range(len(local_search)): valor_fo, best_seq_IG, valores_grafica_ig = ITERATED_GREEDY(d[r], T_0[s], sec_initializ[q ], local_search[t], instancia, archivo) # Tendre que dar d, T_0, secuencia de inicialización, método búsqueda local y N ( numero de iteraciones a realizar) print("Valor F.O.:", valor_fo, "para la mejor secuencia IG:", best_seq_IG) grafica_IG(valores_grafica_ig,0,0,0,0) with open("IG_TUNING_AUXILIAR_2.txt","a") as RESULTADOS_TUNING_AUX: RESULTADOS_TUNING_AUX.write("\nT_" + str(num_ fact) + "_" + str(num_jobs) + "_" + str( num_maq) + "_" + str(kk) + ".txt " + "sec =" + str(sec_used[q]) + ", d=" + str(d[r]) + ", T_0=" + str(T_0[s]) + ", LS=" + str( met_LS[t]) + " " + str(valor_fo) + " " + str(best_seq_IG) + "\n") # Escribir valores en las celdas 88 Anexo: Código de programación en Python ws.cell(row = fila, column = columna, value = valor_fo) print("columna:",columna) if fila == 2: ws.cell(row = 1, column = columna, value = " sec=" + str(sec_used[q]) + ", d=" + str(d[ r]) + ", T_0=" + str(T_0[s]) + ", LS=" + str(met_LS[t])) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’ Desktop\TFG’) # Definir el nombre del archivo archivo_nombre = ’IG_tuning_auxiliar_2.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_ nombre) # Guardar el archivo wb.save(archivo_ruta) columna += 1 """""" """""""""""""""""""""""" ##### CALIBRADO HDHHO ##### """""""""""""""""""""""" from heuristicas_v8 import * import openpyxl import os """ HDHHO PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """ # Creo archivo para resultados with open(’HDHHO_TUNING_AUXILIAR_2.txt’,’w’) as archivo_resultados_tuning: archivo_resultados_tuning.write("") # Escribo titulo en txt with open("HDHHO_TUNING_AUXILIAR_2.txt","a") as RESULTADOS_TUNING_AUX: RESULTADOS_TUNING_AUX.write("TUNING PARÁMETROS PARA HDHHO: tamaño_poblacion , max_iteraciones\n") # Crear un nuevo libro de trabajo y seleccionar la hoja activa wb = openpyxl.Workbook() ws = wb.active fila = 1 factories = [2,3,4,5,6,7] jobs = [20,50,100] machines = [5,10,20] for ff,num_fact in enumerate(factories): Anexo: Código de programación en Python 89 for jj,num_jobs in enumerate(jobs): for ii,num_maq in enumerate(machines): for kk in range(1,2): # Instancias automatizadas archivo=’TUNING/Instancias_tuning_aux_2/Tuning_’ + str(num_fact) + ’_’ + str(num_jobs) + ’_’ + str(num_maq) + ’_’ + str(kk) + ’.txt’ instancia=FlowShop(archivo) # Resultados de cada instancia tam_pob = [10, 20, 30] # Tamaño de la población. N = [50, 100, 200] # Número máximo de iteraciones. fila += 1 columna = 2 ws.cell(row = fila, column = 1, value = "T_" + str(num_fact) + "_" + str(num_jobs) + "_" + str(num_maq) + "_" + str(kk) + ". txt ") for q in range(len(tam_pob)): for r in range(len(N)): best_Xprey, best_fitness, valores_fo_grafica, plot_E = HDHHO(instancia, N[r], tam_pob[q], archivo) print("best Xprey y best fitness",best_Xprey,best_fitness ) grafica_HDHHO(valores_fo_grafica) grafica_plot_E(plot_E) with open("HDHHO_TUNING_AUXILIAR_2.txt","a") as RESULTADOS_TUNING_AUX: RESULTADOS_TUNING_AUX.write("\nT_" + str(num_fact) + "_" + str(num_jobs) + "_" + str(num_maq) + "_" + str(kk) + ".txt " + "tam_pob=" + str(tam_pob[q]) + ", num_iter=" + str(N[r]) + " " + str(best_ fitness) + " " + str(best_Xprey) + "\n") # Escribir valores en las celdas ws.cell(row = fila, column = columna, value = best_ fitness) print("columna:",columna) if fila == 2: ws.cell(row = 1, column = columna, value = "tam_pob=" + str(tam_pob[q]) + ", num_iter=" + str(N[r])) # Obtener la ruta a la carpeta deseada carpeta = os.path.join(os.path.expanduser(’~’), ’Desktop\ TFG’) # Definir el nombre del archivo archivo_nombre = ’HDHHO_tuning_auxiliar_2.xlsx’ # Crear la ruta completa al archivo archivo_ruta = os.path.join(carpeta, archivo_nombre)