Análisis del problema Distributed FlowShop con permutación y objetivo de transportes

i Equation Chapter 1 Section 1 Trabajo Fin de Grado Grado en Ingeniería de Tecnologías Industriales Análisis del problema Distributed FlowShop con permutación y objetivo de transportes Autor: Rafael García García Tutor: Paz Pérez González Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Sevilla, 2024 ii iii Trabajo Fin de Grado Ingeniería en Ingeniería de Tecnologías Industriales Análisis del problema Distributed FlowShop con permutación y objetivo de transportes Autor: Rafael García García Tutor: Paz Pérez Gonzaéz Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2024 iv v Proyecto Fin de Carrera: Análisis del problema Distributed FlowShop con permutación y objetivo de transportes Autor: Rafael García García Tutor: Paz Pérez González El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2024 vi El Secretario del Tribunal vii viii Agradecimientos A mis padres, a mi familia y a mis amigos por haberme acompañado a lo largo de estos años y siempre apoyarme. Rafael García García Sevilla, 2023 ix 1 1 INTRODUCCIÓN Y OBJETIVOS DEL ESTUDIO egún (Fu et al., 2022) en los últimos años la globalización y el aumento de la frecuencia de envíos ha provocado que las empresas empiecen a considerar el transporte como una parte importante de su cadena de suministro. El transporte permite la conexión entre proveedores y clientes y en un entorno empresarial cada vez más competitivo la velocidad de entrega juega un factor importante a la hora de mejorar la satisfacción media de los clientes y la respuesta frente a emergencias. Con una buena gestión de la cadena de suministro que se centre en la unión de los procesos de producción y distribución conseguiremos además una reducción en los costes operativos, como son el combustible, seguros o el mantenimiento de vehículos entre otros. 1.1 Objetivo El objetivo de este estudio es analizar, de manera aproximada a través de metaheurísticas, el problema del entorno Distributed Flow Shop con restricción de permutación y con objetivo de minimizar los costes de transporte y el total weighted completion time. El entorno Distributed Flow Shop se caracteriza por estar formado por un conjunto de fábricas siendo cada una de ellas un entorno de tipo taller con máquinas en serie y donde cada una de ellas tiene un propósito diferente. Además, el problema propuesto cuenta con la restricción de permutación, es decir, que la secuencia que siguen los trabajos a través de las máquinas es la misma para todas ellas. Para resolver el problema se plantean en primer lugar cuatro reglas de asignación que serán evaluadas a través de cinco reglas de despacho básicas. Tras esto se propondrán tres metaheurísticas que serán comparadas entre si para analizar cuál de ellas proporciona mejores resultados. 1.2 Estructura El presente documento está compuesto por seis capítulos: • En el primer capítulo se hace una introducción del problema que se tratará, se hace una descripción del objetivo del estudio y se plantea la estructura que seguirá el documento • En el capítulo segundo se hace una introducción a la programación de operaciones donde se definen los conceptos básicos de esta, la forma de representar las soluciones, los diferentes métodos de resolución que existen para un modelo y los distintos entornos, restricciones y objetivos que se pueden encontrar en el ámbito de la programación de operaciones. • En el capítulo tres se describe el problema en función a los conceptos previamente descritos en el capítulo anterior. Se detalla el entorno de trabajo, las restricciones que tendrá el problema y de presenta el objetivo del problema. • En el capítulo cuatro son descritos los diferentes métodos de resolución planteados para resolver el problema. • Posteriormente, en el capítulo 5, se presentan los resultados obtenidos y se analiza que método de los propuestos es el mejor. • Finalmente, el capítulo 6 se exponen las conclusiones a las que se han llegado tras el estudio del problema. S 2 2 INTRODUCCIÓN A LA PROGRAMACIÓN DE OPERACIONES a programación de operaciones es un proceso mediante el cual se determinan el orden y los tiempos en que se realizarán las diferentes tareas o actividades necesarias para completar un proyecto o proceso específico. Este proceso se utiliza comúnmente en la gestión de proyectos y la gestión de la cadena de suministro y juega un papel importante en empresas dedicadas al transporte y distribución, así como en industrias dedicadas a sistemas de fabricación (Pinedo, 2012). La programación de la producción no puede ser vista como un proceso independiente, sino que se encuentra integrada en un conjunto de decisiones de gestión que se denomina comúnmente gestión de la producción (Framinan et al., 2014). Un sistema muy conocido es el de planificación de las necesidades materiales (MRP). Una vez generada la programación es necesario que todos los materiales y recursos estén disponibles en el momento requerido. Tanto el sistema de programación de la producción como el sistema MRP deben colaborar en la determinación de las fechas de preparación de todas las tareas de manera conjunta (Pinedo, 2012). Aunque las decisiones de programación pueden variar de una empresa a otra, todas ellas comparten una serie de puntos en común, estos son (Framinan et al., 2014): • Son decisiones complejas, puesto que implica desarrollar planes detallados para asignar tareas a los recursos a lo largo del tiempo. • Las decisiones de programación son decisiones que se toman a corto plazo y deben ser tomadas de manera recurrente. • La programación determina plazos de entrega del producto y los costes que este implica, por lo que a pesar de ser una decisión a corto plazo, esta juega un papel importante en el nivel de servicio de una empresa. 2.1 Conceptos básicos A continuación, se definen algunos conceptos básicos relacionados con la programación de operaciones junto a la notación normalmente utilizada: • Trabajos: N= {1, 2 , …, n}. Son los productos que deben pasar por las operaciones de las máquinas de las fábricas. Los trabajos tienen el subíndice j, j ∈ N (Framinan et al., 2014). • Máquinas: M= {1, 2, …, m}. Son los recursos productivos capaces de realizar operaciones de transformación y/o transporte de material. Las máquinas tienen el subíndice i, i ∈ M. • Ruta: la ruta indica el orden en el que debe de procesarse el trabajo, es decir por que máquinas debe de pasar. Se denota como 𝑅! . Es un vector de m componentes, formado por la m máquinas, habiendo un total de n rutas, correspondientes a los números de trabajos. • Tiempo de proceso: es el tiempo que la máquina i ∈ M tarda en procesar el trabajo j ∈ N. La notación usada es 𝑝"! . En el caso de que este sea independiente de la máquina se usa 𝑝! . • Fecha de llegada: es el instante de tiempo en el cual el trabajo puede empezar a ser procesado. Para las fechas de llegada usamos 𝑟! . • Fecha de entrega: es el momento en el que el trabajo j debe estar finalizado. Se denota mediante 𝑑! . L 3 • Pesos: es un factor de prioridad del trabajo, 𝑤! . 2.2 Programa Un programa o Schedule es una asignación en una escala temporal concreta de las máquinas de una empresa para la fabricación de un conjunto de trabajos. Un programa establece el comienzo y el final de cada operación a realizar por la máquina, no obstante, como los tiempos de proceso suelen ser conocidos, basta con obtener el tiempo de comienzo o finalización de la tarea. Sin embargo, cuando nos encontramos con operaciones interrumpibles esta información puede no ser suficiente y necesitaremos saber en que momento esta interrupción se llevará a cabo y cuando se retomará la operación. Cuando un programa cumple con todas las restricciones del proceso productivo hablamos de programa admisible. El objetivo principal de la programación de la producción es encontrar un programa admisible y el procedimiento para obtenerlos se denomina algoritmo. Cuando en un programa no es posible adelantar ninguna operación sin que interfiera en el orden en que se procesan los trabajos hablamos de programa semi-activo. La forma más habitual de representar los programas es a través del diagrama de Gantt, donde en el eje horizontal se representa el momento de comienzo y final de todos los trabajos a realizar y en el eje vertical se representa la ruta en cada máquina (Framinan et al., 2014). Ilustración 1. Diagrama de Gantt de un Flowshop (Framinan et al., 2014). 2.3 Métodos de programación Un método de programación es un procedimiento formal que puede aplicarse a cualquier instancia de un modelo de programación con el fin de obtener un programa factible y que obtenga buenos resultados del valor de la función objetivo. Puesto que este procedimiento puede debe formal, puede describirse usando un número finitos de pasos. El nombre técnico de este procedimiento se conoce como algoritmo (Framinan et al., 2014). Estos algoritmos se pueden clasificar en dos grandes grupos, algoritmos exactos y algoritmos aproximados. • Algoritmos exactos: proporcionan la solución óptima para el problema. Dentro de los algoritmos exactos existen dos tipos: o Algoritmos constructivos exactos: son polinomiales, proporcionan el óptimos para problemas específicos. Dentro de este tipo se encuentran algunas reglas de despacho, el algoritmo de Johnson, de Lawler y de Moore. o Algoritmos enumerativos: son no polinomiales, es decir, dan el óptimo para instancias pequeñas. Ejemplos de algoritmos enumerativos son la programación matemática, la enumeración completa y Branch and Bound. 4 • Algoritmos aproximados: estos algoritmos no garantizan la optimalidad. o Heurísticas constructivas: las heurísticas constructivas generan una solución una secuencia factible desde cero. En primer lugar, se ordenan los trabajos, después se elige un trabajo que todavía no ha sido programado y se inserta en los posibles huecos de la secuencia y por último, se guarda la mejor secuencia obtenida como punto de partida para seguir construyendo la secuencia. o Heurísticas de mejora: estas heurísticas tratan de obtener una solución mejor a partir de una secuencia de partida. Un ejemplo de estos algoritmos es la búsqueda local (local search). o Metaheurísticas: estas tratan de ampliar el espacio de búsqueda permitiendo el empeoramiento temporal de las soluciones que se considerarán para la siguiente búsqueda (Framinan et al., 2014). 2.4 Modelos: entorno, restricciones y objetivos Los modelos de programación de la producción se definen a través de tres conceptos fundamentales, propuestos por Graham, Lawler, Lenstra y Rinnooy Kan, que son entorno, restricciones y objetivos. La notación usada para ello es 𝛼(|(𝛽(|(𝛾 (Graham et al., 1979). Ilustración 2. Clasificación de los modelos de producción (Framinan et al., 2014) • Entorno ( 𝛼 ): el entorno o layout indica el número de máquinas en la planta y la disposición de esta. Un buen layout ayudará a la empresa a incrementar la producción, disminuir el manejo de materiales y reducir costes. A continuación, se definen los diferentes entornos junto con la notación utilizada: o Una máquina o single machine ( 𝛼 =1) : el entorno está formado por una sola máquina por la que pasan todos los trabajos, por lo que no existe una ruta. o Máquinas en paralelo o parallel machines: es un entorno formado por m máquinas. Cada trabajo tiene una sola operación y se procesa en una de las máquinas, normalmente todas las máquinas pueden procesar el trabajo. Las máquinas paralelas pueden ser a su vez divididas en tres categorías. § Identical Parallel Machines ( 𝛼 =𝑃#) : todas las máquinas son iguales, es decir, el tiempo de proceso 𝑝! no depende de la máquina § Uniform Parallel Machines ( 𝛼 =𝑄#): en este caso las velocidades de las máquinas, ( 𝑣", son diferentes, lo que da lugar a tiempos de procesos diferentes, 𝑝"! =$! %" . Un valor de 𝑣" mayor a uno quiere decir que esa máquina es más rápida mientras que valores de 𝑣" menores a uno representan máquinas más lentas. 5 § Unrelated Parallel Machines ( 𝛼 =𝑅#): se trata del caso más general, las máquinas son diferentes y el tiempo de proceso del trabajo depende de la máquina en la que es procesado, 𝑝"! . o Taller de flujo regular o Flow Shop ( 𝛼 =𝐹#) : se trata de un entorno formado por m máquinas, cada una de ellas con una función diferente. En este tipo de entornos todos los trabajos tienen que pasar por todas las máquinas, siguiendo la misma ruta 𝑅!(= ((1,2,...,𝑚) . Aquí 𝑝"! denota el tiempo que tarda cada máquina i en procesar el trabajo j. Un caso particular de este entorno es el Permutation Flow Shop, donde la secuencia es la misma para todas las máquinas. o Taller o Job Shop ( 𝛼 =𝐽#) : aquí cada trabajo tiene una ruta diferente. Este tipo de entornos es común cuando la diferenciación entre productos es grande y cada trabajo requiere un tratamiento diferente. o Taller abierto u Open Shop ( 𝛼 =𝑂#) : se trata del caso más general, en este entorno no hay una ruta especificada por lo que cuando se da el programa a su vez se construye una ruta. • Restricciones ( 𝛽 ): las restricciones nos condicionan la forma de procesar y decidir el orden de los trabajos. Aunque no siempre están presentes, hay que tener en cuentas algunas suposiciones generales sobre estas: los trabajos siempre están disponibles al principio del horizonte de programación, siempre y cuando no se tengan restricciones relacionadas con fechas de llegada, los trabajos no se pueden interrumpir, las máquinas siempre están disponibles, el buffer entre máquinas se supone infinito y el tiempo de transporte es despreciable. Algunas de las restricciones más comunes son: o Interrupciones: el trabajo puede interrumpirse una vez que ha comenzado a procesarse, esto se puede deber a llegado un nuevo trabajo que requiere ser procesado urgentemente, por cancelaciones de clientes o por avería de la máquina. Los tipos de interrupción son: § Non-resumable ( 𝛽 = pmtn-non-resumable): el trabajo hecho se pierde y se tiene que iniciar de nuevo. § Semi-resumable ( 𝛽 = pmtn-semi-resumable): sólo se pierde una parte del trabajo realizado. § Resumable ( 𝛽 = pmtn -resumable): el trabajo realizado se conserva y retoma por donde se había dejado tras la interrupción. o Fechas de llegada o release date ( 𝛽 =𝑟!): indica el instante de tiempo en el que el trabajo estará disponible para procesar. o Fechas de entrega de los trabajos: hay dos tipos de restricciones relacionadas con las fechas de entrega § Deadlines ( 𝛽 =𝑑& ; ): indica la fecha en la que, como muy tarde, el trabajo, obligatoriamente debe de ser entregado, para así no acarrear penalización. § Common due date ( 𝛽 =d'=d) : se trata de un número común a todos los trabajos y la entrega en este instante de tiempo no es obligatoria, a diferencia del caso anterior. o Tiempos de setup: es el tiempo que se requiere para preparar la máquina o el trabajo antes de ser procesado. Los tiempos de setup pueden anticipatorios o no anticipatorios, independientes de la secuencia ( 𝛽 =s(') , dependientes de la secuencia ( 𝛽 =s(')) o independientes de la secuencia, en este caso se elimina el subíndice i. o Procesado por lotes: el procesado por lotes puede resultar interesante cuando varios trabajos requieren el mismo setup y estos pueden ser procesados por lotes, las máquinas procesan a la vez lotes de hasta b trabajos. Por lo general, existen dos tipos de procesamiento por lotes: § Lotes en paralelo o parallel batching ( 𝛽 =𝑝−𝑏𝑎𝑡𝑐ℎ(𝑏)) : el tiempo de procesamiento del lote se corresponde con el máximo de los tiempos de proceso de los trabajos que están en dicho lote. 6 § Lotes en serie o serial batching ( 𝛽 =𝑠−𝑏𝑎𝑡𝑐ℎ(𝑏)) : el tiempo de proceso es la suma de los tiempos de proceso de los trabajos en el lote. o Precedencia ( 𝛽 = prec): un trabajo no puede empezar a procesarse hasta que no acaben los trabajos que lo preceden. En los entornos tipo taller nos podemos encontrar las siguientes restricciones: o De permutación ( 𝛽 =𝑝𝑟𝑚𝑢) : donde la secuencia es la misma para todos los trabajos. o Tiempos ociosos no permitidos ( 𝛽 =𝑛𝑜−𝑖𝑑𝑙𝑒) : cuando la máquina empieza a procesar trabajos esta no puede parar. o Los trabajos no pueden esperar ( 𝛽 =𝑛𝑜−𝑤𝑎𝑖𝑡 ): cuando un trabajo comienza a ser procesado este no puede esperar entre máquinas. o Almacenes de una máquina o buffer ( 𝛽 =𝑏"):( es la cantidad de trabajos que pueden esperar en el almacén de una máquina. • Objetivos ( 𝛾 ): es la función a optimizar. En programación de la producción las funciones objetivos suelen clasificarse según coste, tiempo, calidad y flexibilidad (Framinan et al., 2014). Ilustración 3 Clasificación de los objetivos (Framinan et al., 2014) Algunos de los objetivos más comunes en programación de operaciones son los siguientes: el tiempo de finalización o makespan ( 𝛾 =𝐶#*+ ), que es el momento en el que se terminan de procesar todos los trabajos, el total completion time ( 𝛾 = ∑ 𝐶! , !-. ) , que es la suma de todos los tiempos de finalización de los trabajos, el maximun flowtime ( 𝛾 =𝑚á𝑥(𝐹! ), que hace referencia al tiempo que el trabajo se encuentra en el sistema siendo procesado o el total flowtime ( 𝛾 = ∑ 𝐹! , !-. ) , que es la suma de los flowtimes. También hay objetivos relacionados con las fechas de entrega, como son: el maximun lateness ( 𝛾 =𝑚á𝑥(𝐿! ), que indica como de tarde se ha entregado el trabajo, el total lateness ( 𝛾 = ∑ 𝐿! , !-. ) , que es la suma de los lateness de todos los trabajos, estos dos últimos objetivos pueden tomar valores negativos pues son el resultado de restar el tiempo de finalización y la fecha de entrega del trabajo, el maximun tardiness ( 𝛾 =𝑚á𝑥(𝑇! ) y el total tardiness ( 𝛾 = ∑ 𝑇! , !-. ) , que indican lo mismo que los dos últimos objetivos solo que estos no pueden ser valores negativos, el earliness ( 𝛾 =𝑚á𝑥(𝐸! ), y el total earliness ( 𝛾 = ∑ 𝐸! , !-. ) , que indican con cuanta antelación se entregan los trabajos y por último el number of tardy job que indica cuantos trabajos han sido entregados con retraso ( 𝛾 = ∑ 𝑈! , !-. ).( 7 3 DESCRIPCIÓN DEL PROBLEMA n este documento el entorno a estudiar se trata un Distributed Permutation Flowshop, que siguiendo la notación 𝛼|𝛽|𝛾, vista anteriormente, se define como 𝐷𝐹#|𝑝𝑟𝑚𝑢|𝐹"( ∑ 𝑤!𝐶!, ∑ ∑ 𝑤′/𝑥!/ / /-. , !-. , !-. ) . La programación distribuida, según (Toptal & Sabuncuoglu, 2010), se puede definir como un enfoque donde un problema es dividido en partes más pequeñas y donde estas partes se coordinan entre sí, utilizando la información más reciente del sistema, para alcanzar el objetivo global del problema. Un entorno distribuido generalmente responde de manera más efectiva ante cambios imprevistos en la producción, o eventos que no son controlables, como pueden ser averías en las máquinas, le llegada de trabajos con alta preferencia o cancelación de pedidos a última hora. A esta ventaja competitiva se le une el desarrollo de la globalización de la economía, por lo que en los últimos años cada vez son más las empresas que optan por un entorno distribuido para ahorrar costes de fabricación y entrega (Fernandez-Viagas et al., 2018). En comparación con los entornos tradicionales donde sólo hay fábrica, en los entornos distribuidos además de programar los trabajos en un conjunto de máquinas, entra en juego otra decisión, asignar los trabajos a la fábrica adecuada (Naderi & Ruiz, 2010). A continuación, se describe más detalladamente el problema objeto de estudio, definiendo así el entorno, las restricciones y el objetivo de este. • Entorno ( 𝛼 =𝐷𝐹#) : el entorno Distributed Flowshop hay un conjunto N de n trabajos, que tienen que ser procesados en un conjunto F de f fábricas. Cada una de estas fábricas se trata de un Flowshop (descrito en el capítulo anterior) formado por un número m de máquinas, que es constante entre fábricas. Ilustración 4. Ejemplo de Distributed Permutation Flowshop (Framinan et al., 2014). E 8 En la Ilustración 4 se puede observar como un entorno de Permutation Flowshop con diez trabajos y cuatro máquinas es dividido en un Distributed Permutation Flowshop con dos fábricas, cada una con cuatro máquinas. • Restricciones ( 𝛽( = prmu): el problema a tratar tiene la restricción de permutación, es decir que todas las máquinas tienen la misma secuencia, por lo que el orden en el que se ejecutan los trabajos en cada máquina en el mismo para todas. Además de esta restricción hay que tener en cuenta otras restricciones generales: todos los trabajos están disponibles en el instante cero, así como las máquinas. No se disponen de fechas de entrega. Las fábricas son idénticas entre sí y capaces de procesar todos los trabajos. El tiempo de proceso del trabajo j en la máquina i, que definiremos como 𝑝"! , es el mismo para todas las fábricas del conjunto. Una vez que un trabajo empieza a ser procesado en una fábrica, este debe ser acabado en esta, sin posibilidad de interrupción y de ser continuado en una fábrica diferente. El tiempo de transporte entre máquinas se considera despreciable y el buffer entre máquinas se considera infinito. • Objetivo ( 𝛾(=(𝐹"( ∑ 𝑤!𝐶!, ∑ ∑ 𝑤′/𝑥!/ / /-. , !-. , !-. )) : el objetivo del problema consistirá en minimizar el total weighted completion time más la suma de los costes de transporte. Este objetivo tomará un valor normalizado entre 0 y 2. La variable 𝑤′/ representa los costes de transporte y habrá tantos como fábricas tenga el entorno que se esté estudiando. La variable 𝑥!/ de la función objetivo tomará un valor de 0 o 1 y solo se activará si el trabajo j está siendo procesado en la fábrica f. Por tanto, la función objetivo se puede escribir como: 𝐹"( ∑ 𝑤!𝐶!, ∑ ∑ 𝑤′/𝑥!/ / /-. , !-. ) , !-. (=( ∑ 1!2! " !#$ ∑ 1!·2%á' " !#$ (+( ∑ ∑ 14(+!( ( (#$ " !#$ 565/·,·#",(14() /·,·#*+(14()56/·,·#",(14() 3.1 Cálculo del objetivo A continuación, se muestra mediante un ejemplo sencillo el cálculo de la función objetivo para un entorno con f = 3 fábricas, m = 4 máquinas y j = 7 trabajos, donde los costes de transporte de llevar los trabajos desde el centro de distribución a cada una de las tres fábricas son 𝑤/= [ 3,2,1 ] . Trabajos Máquinas 𝑝!" 0 1 2 3 4 5 6 0 5 3 4 2 3 1 1 1 6 2 3 4 4 2 2 2 2 2 6 5 8 7 3 3 5 4 1 2 3 4 4 𝑤" 1 2 3 1 2 1 4 ##𝒑𝒊𝒋 𝟑 𝒊&𝟎 𝟔 𝒋&𝟎 18 11 14 13 18 14 10 Tabla 1. Tiempos de procesos del ejemplo propuesto 9 Para la asignación de trabajos a las fábricas se usará la regla de asignación ECT (Earliest Completion Time), por lo que los trabajos serán asignados a aquella fábrica cuyo tiempo de terminación tras asignar dicho trabajo sea menor. Se tomará como ejemplo la siguiente secuencia: S = [4,0,3,5,2,6,1]. Como puede observarse en Ilustración 5, al comienzo de la programación como todas las fábricas están libres, asignaremos el trabajo 4 a la fábrica 0, el trabajo 0 a la fábrica 1 y el trabajo 3 a la fábrica 2. Tras asignar estos tres primeros trabajos, el siguiente trabajo es el 5, si este es procesado en la fábrica 0, el completion time es 26 u.t, si va a la fábrica 1 este es de 24 u.t, mientras que si va a la fábrica 2 este acabará de procesarse en el instante 22. Viendo estos tiempos de finalización el trabajo 5, será procesado en la fábrica 2 puesto que es la fábrica que finaliza antes con el trabajo. Este proceso se usa a lo largo de toda la programación, obteniendo el diagrama de Gantt que se observa en la Ilustración 5. Ilustración 5. Ejemplo Distributed Flowshop según regla de asignación ECT. Una vez hemos asignado todos los trabajos vemos que los completion times son [18,18,13,22,21,22,26]. Con estos datos podemos calcular la función objetivo de la siguiente forma: 𝐹𝑂(=( 292 14·26+15−7 21−7=1,374 10 4 MÉTODOS DE RESOLUCIÓN n este apartado se exponen las distintas reglas de asignación, reglas de despacho, heurísticas constructivas y metaheurísticas elegidas para resolver el problema. 4.1 Reglas de asignación Para resolver este problema en primer lugar analizaremos qué regla de asignación a fábricas elegir. En este problema se plantean cuatro reglas de asignación que se describen a continuación: • ECT (earliest completion time): consiste en asignar el trabajo j a la fábrica f cuyo tiempo de terminación es menor (Ilustración 5). En caso de empate el trabajo será asignado a la fábrica de menor índice. • FAM (first available machine): esta regla de asignación consiste en asignar los trabajos a la primera fábrica que esté disponible. Esta puede ser utilizada para tomar decisiones rápidas y eficientes sobre como asignar trabajos a una fábrica. La regla de desempate usada en esta regla de asignación será la misma descrita anteriormente. • ECT_minWF: esta regla de asignación sigue el mismo procedimiento que ECT solo que en el caso en el que un determinado trabajo tenga el mismo tiempo de finalización en varias fábricas, este irá a la fábrica cuyo coste de transporte sea menor. • FAM_minWF: en este caso la forma de actuar es la misma que en la regla de asignación anterior, pero siguiendo la regla de asignación FAM. 4.2 Reglas de despacho o priority rules Para evaluar que regla de asignación es mejor usaremos reglas de despacho o priority rules. Una regla de despacho se refiere a un conjunto de criterios utilizados para tomar decisiones sobre el orden en el que se ejecutarán las tareas. En este problema se plantean cinco: • SPT (shortest processing time): consiste en ordenar los trabajos de menor a mayor tiempo de proceso. Para calcular estos tiempos de proceso sumaremos el tiempo que cada trabajo pasa en cada una de las máquinas. Aplicando esto a nuestro ejemplo de Tabla 1 nuestra secuencia es: SSPT = [6,1,3,2,5,0,4]. En caso de empate, se elige el trabajo con menor índice. • LPT (longest processing time): consiste en ordenar los trabajos de mayor a menor tiempo de proceso. La forma de obtener estos tiempos de proceso es igual a la seguida en SPT. SLPT = [0,4,2,5,3,1,6]. Si se produce un empate, el trabajo a insertar será el de menor índice. • WSPT (weighted shortest processing time): el trabajo con mayor valor del cociente entre el peso y el tiempo de proceso se procesa primero. SWSPT = [6,2,1,4,3,5,0]. La regla de desempate usada aquí será la misma que en SPT y LPT. • SPT_INT: esta regla de despacho parte de la secuencia obtenida al aplicar SPT al problema. Una vez tenemos la secuencia iremos intercalando el primer trabajo de esta, seguido del último, estos serán los trabajos con menor y mayor tiempo de proceso respectivamente que aún quedan sin asignar, así hasta recorrer toda la secuencia. Siguiendo estos pasos la secuencia que obtenemos para nuestro ejemplo es: SSPT_INT = [6,4,1,0,3,5,2]. • LPT_INT: esta regla de despacho sigue el mismo procedimiento que la descrita anteriormente, pero esta vez la secuencia de partida es lo obtenida mediante LPT. SSPT_INT = [0,6,4,1,2,3,5]. Para estas dos últimas reglas de despacho en caso de empate se inserta el trabajo que primero se encuentre al recorrer la secuencia correspondiente, SSPT o SLPT, ya sea en sentido ascendente o descendente. E 17 Ilustración 11. Pseudocódigo Iterated Greedy (Adaptado de (Dubois-Lacoste et al., 2017)) 18 4.5 Metaheurística Algortimo Genético (GA) El algoritmo genético al igual que el BWO descrito anteriormente, está inspirado en la naturaleza, y tratan de imitar el comportamiento de las especies a través de la evolución genética, donde las mejores sobreviven y las peores se extinguen. Este algoritmo parte de una población inicial, gran parte de esta se genera aleatoriamente para aumentar la diversidad, pero habrá tres de ellas que se obtengan por el método de búsqueda local first improvement, generando vecinos, a partir de la secuencia obtenida por la heurística NEH (Nawaz et al., 1983), por los métodos de adjacent swap, general swap e insertion. Este último ya ha sido comentado en el apartado 4.3.4 Fase de mutación, mientras que para los dos primeros se muestra en la Ilustración 12 el procedimiento a seguir. Ilustración 12. Creación de vecindades por los métodos adjacent y general swap (Perez-Gonzalez et al., 2022) Una vez la población ha sido creada, es el momento de elegir dos padres de forma aleatoria. A partir de estos dos padres se generará un primer hijo del mismo modo del que se generaron en el algoritmo BWO (Ilustración 6). Partiendo de este primer hijo se crea un segundo por intercambio de pares, se seleccionan aleatoriamente dos posiciones y se intercambian los trabajos que las ocupan. Una vez se tiene el segundo hijo se evalúa el valor de la función objetivo y si es mejor que el de la secuencia de partida se hace una búsqueda local del individuo y este se guarda para compararlo en las siguientes iteraciones. 19 Ilustración 13. Pseudocódigo GA con local search (Adaptado de (Perez-Gonzalez et al., 2022)) 20 5 RESULTADOS OBTENIDOS n este apartado se detalla los programas utilizados para la interpretación de resultados, la resolución de los algoritmos, las instancias empleadas en el problema y los indicadores usados para la interpretación del problema. 5.1 Herramientas utilizadas Para codificar los algoritmos propuestos se hace uso de Python, este se trata de un lenguaje de programación de alto nivel diseñado para ser comprensible por los humanos, e interpretado, es decir, el código se ejecuta línea a línea en lugar de ser compilado antes de la ejecución (Sulbarán, 2023). Python cuenta con una amplia serie de librerías, entre ellas se encuentra la librería scheptk (Librería SCHEPTK – Grupo de Investigación Organización Industrial, n.d), que será usada durante el estudio. Para la interpretación de los resultados se hará uso de Microsoft Excel, que permite realizar operaciones con facilidad y crear tablas y gráficos de forma rápida y sencilla. 5.2 Instancias e indicadores para la evaluación Para la evaluación de los algoritmos se usa un total de 102 instancias de (Naderi & Ruiz, 2010). Estas instancias toman valores de f ∈ [2,3,4,5,6,7], n ∈ [10,12,14,16,20,50,100] y m ∈ [2,3,4,5,10,20]. Los tiempos de proceso de estas instancias comprenden valores entre 1 y 99, y han sido generados siguiendo una distribución uniforme (Taillard, 1993). Los pesos de los trabajos, w, y los costes de transporte, wf, han sido añadidos y toman valores entre 1 y 99, y 10 y 99 respectivamente. Cabe recordar también que en el problema que se plantea, los trabajos se encuentran disponibles en el instante cero y que no hay fechas de entregas, por lo que estas tomarán valores de cero en el momento de la creación de las instancias. Para la evaluación de los resultados obtenidos el indicador elegido es el average relative percentage deviation (ARPD) que es el valor promedio de las desviaciones porcentuales relativas, conocida en sus siglas en inglés por RPD. El RPD muestra la variación de cada instancia con respecto al mejor valor obtenido para esa instancia. Valores cercanos a cero indican que el valor de la función objetivo para esa instancia está próximo al mejor valor de la función objetivo obtenido al evaluar dicha instancia, mientras que valores cercanos a 100 indican que estamos lejos de la mejor solución obtenida. El RPD y el ARPD se describen como siguen: RPD=valorFO(−(ValorMinFO∗ ValorMinFO∗·100((((((((((ARPD=1 k v RPD(((((( ) (-. E 21 5.3 Experimentación 5.3.1 Resultados regla de asignación Como se comentó en la sección 4.1 Reglas de asignación, en primer lugar, se analiza que regla de asignación (RA) de las cuatro propuestas es mejor. Valores ARPD por regla de despacho ECT SPT 0,1575 ECT_minWF SPT 0,1417 LPT 0,3468 LPT 0,3567 WSPT 0,1029 WSPT 0,0984 SPT_INT 0,2451 SPT_INT 0,2228 LPT_INT 0,2517 LPT_INT 0,2783 FAM SPT 0,1491 FAM_minWF SPT 0,1364 LPT 0,3348 LPT 0,3371 WSPT 0,0975 WSPT 0,0848 SPT_INT 0,1055 SPT_INT 0,2240 LPT_INT 0,1928 LPT_INT 0,2758 Tabla 2. Resultados ARPD por regla de despacho Ilustración 14. ARPD por regla de despacho 0 0,02 0,04 0,06 0,08 0,1 0,12 0,14 0,16 0,18 0,2 0,22 0,24 0,26 0,28 0,3 0,32 0,34 0,36 0,38 0,4 SPT LPT WSPT SPT_INT LPT_INT SPT LPT WSPT SPT_INT LPT_INT SPT LPT WSPT SPT_INT LPT_INT SPT LPT WSPT SPT_INT LPT_INT ECT FAM ECT_minWF FAM_minWF Valores promedio del RPD de las reglas de despacho 22 Observando este gráfico se puede ver que el mejor valor del ARPD se obtiene con la cuarta regla de asignación (FAM_minWF) y la regla de despacho weighted shortest processing time (WSPT). Esta primera conclusión puede resultar imprecisa puesto que no se tiene en cuenta el resto de los valores obtenidos para esa mima regla de asignación, pudiendo ignorar así comportamientos menos eficaces en la obtención de resultados con otras reglas de despacho. Es por ello por lo que se calcula a continuación la media de los valores de ARPD obtenidos por las reglas de asignación. Valores ARPD por regla de asignación ECT 0,2208 FAM 0,1759 ECT_minWF 0,2196 FAM_minWF 0,2116 Tabla 3. Valores ARPD por regla de asignación Ilustración 15. Valores ARPD por regla de asignación Como se puede ver en la Tabla 3, el mejor valor de la función objetivo se obtiene con la regla de asignación first avaliable machine (FAM), y desde ahora en adelante será la regla de asignación que se usará a la hora de ejecutar con las metaheurísticas propuestas. 0 0,01 0,02 0,03 0,04 0,05 0,06 0,07 0,08 0,09 0,1 0,11 0,12 0,13 0,14 0,15 0,16 0,17 0,18 0,19 0,2 0,21 0,22 0,23 0,24 0,25 ECT FAM ECT_minWF FAM_minWF Valores promedio globales de las RA 23 5.3.2 Resultados de las metaheurísticas Antes de empezar a comparar los tres algoritmos propuestos, se procederá a analizar los resultados arrojados por la metaheurística BWO en dos situaciones distintas, en la primera se generará una población que se mantendrá fija a lo largo del tiempo de ejecución del algoritmo, mientras que en la segunda se generará una población distinta en cada nueva iteración. En cada caso el algoritmo es ejecutado dos veces, la primera vez se usa la fórmula propuesta por (Fu et al., 2022), 𝑇(=(6(9)69*) :,(;..) , y la segunda se usa una temperatura fija T=50º. Valores ARPD para BWO Población fija Población en cada iteración 𝑇&=&−(𝑂)−𝑂*) 𝐿𝑛(0.1) T=50º 𝑇&=&−(𝑂)−𝑂*) 𝐿𝑛(0.1) T=50º BWO BWO1 BWO2 BWO3 ARPD 0,0274 0,0218 0,0257 0,0108 Media ARPD 0,0246 0,0182 Tabla 4. Valores ARPD para BWO Como se observa, los mejores valores para el algoritmo de viuda negra se obtienen cuando se genera una población nueva en cada iteración y cuando la temperatura inicial es de 50º. A continuación, en la Tabla 5 se muestran los resultados del algoritmo iterated greedy en dos casos distintos, el primero de ellos cuando Tp toma el valor de Tp=0.8 y el segundo cuando Tp=0.4. En cada caso, a su vez se diferencian dos situaciones, una cuando el número de trabajos a borrar es d=2 y otro cuando este es aleatorio. Para el caso de Tp=0.4, como ya se comentó anteriormente, también se evaluará el comportamiento del algoritmo cuando el número de trabajos a borrar toma un valor aleatorio. Como se observa, para el caso de estudio de este documento, se obtienen mejores valores para Tp=0.4 y d=2. Valores ARPD para IG Tp=0.8 Tp=0.4 d=2 d=random d=2 d=random d=4 IG IG1 IG2 IG3 IG4 ARPD 0,0185 0,0297 0,0163 0,0291 0,0235 Media ARPD 0,0241 0,0230 Tabla 5. Resultados ARPD para IG 24 A continuación, se muestran los resultados obtenidos por cada metaheurística. Valores ARPD por metaheurística BWO3 0,0227 IG2 0,0151 GA 0,0128 Tabla 6. Resultados ARPD por metaheurística Ilustración 16. Resultados ARPD por metaheurística En la Tabla 6 se observa que el mejor valor promedio ARPD para las instancias evaluadas es la metaheurística algoritmo genético (GA). Analizando más detalladamente los resultados obtenidos, en la Tabla 7 se analizan los valores promedios del RPD en función del número de fábricas. Como se puede ver, cuando f = 2 la metaheurística IG es la que obtiene mejores resultados, mientras que cuando el número de fábricas es f = 3,4,5,6,7 es el algoritmo genético quien proporciona mejores resultados. Observando los valores medios se observa que es de nuevo el algoritmo genético quien arroja mejores resultados, mejorando significativamente con respecto a los otros dos algoritmos que se proponen cuando va aumentando el número de fábricas. En la Tabla 8 se observa que cuando el número de trabajos es, j = 10,12,16 el algoritmo de IG es el mejor de los estudiados, mientras que cuando j = 14,20,50,100 el algoritmo genético obtiene resultados mejores. Si se estudian los valores medios obtenidos tras la experimentación, se puede ver que el Iterated Greedy es la metaheurística que da mejores resultados. Por último, analizando ahora los resultados en función del número de máquinas, en la Tabla 9 se puede ver que cuando m = 2, BWO aporta los mejores resultados, cuando m = 3,4 es IG quien los arroja, y cuando el número de máquinas es m = 5,10,20 los mejores resultados se obtienen con GA. De nuevo, viendo los valores medios, es la metaheurística IG quien proporciona mejor resultados, aunque se observa que es el algoritmo genético quien tiene un mejor comportamiento conforme se incrementa el número de máquinas. 0 0,002 0,004 0,006 0,008 0,01 0,012 0,014 0,016 0,018 0,02 0,022 0,024 BWO3 IG2 GA ARPD por metaheurística 25 VALORES ARPD POR FÁBRICAS FÁBRICAS BWO3 IG2 GA 2 0,0212 0,0116 0,0216 3 0,0226 0,0165 0,0112 4 0,0291 0,0178 0,0152 5 0,0181 0,0118 0,0075 6 0,0148 0,0144 0,0026 7 0,0222 0,0169 0,001 Media ARPD 0,0213 0,0148 0,0099 Tabla 7. Resultados ARPD por fábricas Ilustración 17. Representación del ARPD por fábricas 0 0,002 0,004 0,006 0,008 0,01 0,012 0,014 0,016 0,018 0,02 0,022 0,024 0,026 0,028 0,03 2 3 4 5 6 7 FÁBRICAS ARPD por fábricas BWO3 IG2 GA 26 VALORES ARPD POR TRABAJOS TRABAJOS BWO3 IG2 GA 10 0,0263 0,0044 0,0223 12 0,03 0,0105 0,0137 14 0,035 0,0113 0,0087 16 0,0188 0,0175 0,0449 20 0,0158 0,0216 0,0099 50 0,0225 0,0202 0,0007 100 0,0173 0,0143 0,0016 Media ARPD 0,0236 0,0143 0,0146 Tabla 8. Resultados ARPD por trabajos Ilustración 18. Representación del ARPD por trabajos 0 0,005 0,01 0,015 0,02 0,025 0,03 0,035 0,04 0,045 0,05 10 12 14 16 20 50 100 TRABAJOS ARPD por trabajos BWO3 IG2 GA 33 # release dates (if not, 0 is assumed) self.check_releasedates(filename) def ct(self,sequence): ct_fabricas = [0 for i in range(self.f)] # print("Inicializamos el vector de ct de las fabricas a cero",ct_fabricas) ct = [[0 for j in range(len(sequence))] for i in range(self.machines)] # print("Vector de ct de cada trabajo en cada máquina", ct) ct_jobs = [[0 for j in range(len(sequence))] for i in range(self.f)] # print("Vector de cada trabajo en cada fábrica", ct_jobs) vector_aux = [[0 for j in range(len(sequence))] for i in range(self.f) for k in range(self.machines)] #vector auxiliar donde guardaremos los timepos de proceso de cada trabajo en cada maquina y en cada fábricas # print("Creamos un vector auxiliar",vector_aux) #Creamos un vector donde guardar los tiempos de proceso de un trabajo pero SOLO en su fábrica asignada vector_ct = [[0 for j in range(len(sequence))] for i in range(self.f) for k in range(self.machines)] aux_ctjobs = [0 for j in range(self.f)] #vector para guardar lo que tarda cada trabajo en cada fábrica for j in range(0,len(sequence)): #0,self.jobs for k in range(self.f): for i in range(self.machines): if k == 0: if i == 0: ct[i][j] = max(max(vector_aux[i]), self.r[sequence[j]]) + self.pt[i][sequence[j]] vector_aux[i][j] = ct[i][j] else: ct[i][j] = max(max(vector_aux[i-1]), max(vector_aux[i])) + self.pt[i][sequence[j]] vector_aux[i][j] = ct[i][j] aux_ctjobs[k] = vector_aux[i][j] else: if i == 0: ct[i][j] = max(self.r[sequence[j]], max(vector_aux[self.machines*k])) + self.pt[i][sequence[j]] vector_aux[self.machines*k][j] = ct[i][j] else: ct[i][j] = max(max(vector_aux[self.machines*k+i]), 34 max(vector_aux[self.machines*k+i-1])) + self.pt[i][sequence[j]] vector_aux[self.machines*k+i][j] = ct[i][j] aux_ctjobs[k] = vector_aux[self.machines*k+i][j] #copy # print("vector auxiliar ", vector_aux) # print("Vector del trabajo en todas las fábricas",aux_ctjobs) fabrica_asignada = find_index_min(aux_ctjobs) # print("El trabajo en la posición {} va a la fábrica {}" .format(j,fabrica_asignada)) for m in range(self.machines): vector_ct[self.machines*fabrica_asignada+m][j] = vector_aux[self.machines*fabrica_asignada+m][j] #copy vector_aux = copy.deepcopy(vector_ct) # print("Vector auxiliar listo para nueva asignación", vector_aux) # print("Vector de ct de cada trabajo en cada máquina de la fábrica asignada",vector_ct) ct_jobs[fabrica_asignada][j] = aux_ctjobs[fabrica_asignada] #copy # print(ct_jobs) return ct_jobs,sequence FAM from scheptk.scheptk import * import sys # to stop the execution (funcion exit() ) from scheptk.util import * import copy,random class DPFS_FAM(Model): def __init__(self, filename): # initializing additional data (not basic) self.machines = 0 # starting reading print("----- Reading Distributed FlowShop instance data from file " + filename + " -------") # jobs (mandatory data) self.jobs = read_tag(filename,"JOBS") # if jobs = -1 the program cannot continue if(self.jobs ==-1): print("No jobs specified. The program cannot continue.") sys.exit() 35 else: print_tag("JOBS", self.jobs) # machines (another mandatory data) self.machines = read_tag(filename, "MACHINES") if(self.machines ==-1): print("No machines specified. The program cannot continue.") sys.exit() else: print_tag("MACHINES", self.machines) #leer el vector f self.f = read_tag(filename,"F") if(self.f == -1): print("No factories specified. The program cannot continue.") sys.exit() else: print_tag("F",self.f) #leer el vector de pesos de la fábrica self.wf = read_tag(filename,"WF") if(self.wf == -1): print("No weights for factories specified. The program cannot continue.") sys.exit() else: if(len(self.wf) != self.f): print("Number of factories does not match the number of weight of the factories (FACTORIES={}, lenght of WF={}). The program cannot continue".format(self.f, len(self.wf))) sys.exit() else: print_tag("WF",self.wf) # processing times (mandatory data, machines in rows, jobs in cols) self.pt = read_tag(filename,"PT") if(self.pt ==-1): print("No processing times specified. The program cannot continue.") sys.exit() else: if(len(self.pt) != self.machines ): print("Number of processing times does not match the number of machines (MACHINES={}, length of PT={}). The program cannot continue".format(self.machines, 36 len(self.pt)) ) sys.exit() else: for i in range(self.machines): if(len(self.pt[i])!= self.jobs): print("Number of processing times does not match the number of jobs for machine {} (JOBS={}, length of col={}). The program cannot continue".format(i, self.jobs, len(self.pt[i])) ) sys.exit() print_tag("PT", self.pt) # weights (if not, default weights) self.check_weights(filename) # due dates (if not, -1 is assumed) self.check_duedates(filename) # release dates (if not, 0 is assumed) self.check_releasedates(filename) def ct(self,sequence): ct = [[0 for j in range(len(sequence))] for i in range(self.machines)] # print("Vector de ct de cada trabajo en cada máquina", ct) ct_jobs = [[0 for j in range(len(sequence))] for i in range(self.f)] # print("Vector de cada trabajo en cada fábrica", ct_jobs) vector_aux = [[0 for j in range(len(sequence))] for i in range(self.f) for k in range(self.machines)] # print("Creamos un vector auxiliar",vector_aux) aux_ctjobs = [0 for j in range(self.f)] #vector para guardar lo que tarda cada trabajo en cada fábrica for j in range(0,len(sequence)): # print("Vector del trabajo en todas las fábricas",aux_ctjobs) fabrica_asignada = find_index_min(aux_ctjobs) # print("El trabajo {} va a la fábrica {}" .format(sequence[j],fabrica_asignada)) for i in range(self.machines): if fabrica_asignada == 0: if i == 0: ct[i][j] = max(max(vector_aux[i]), self.r[sequence[j]]) + self.pt[i][sequence[j]] 37 vector_aux[i][j] = ct[i][j] else: ct[i][j] = max(max(vector_aux[i-1]), max(vector_aux[i])) + self.pt[i][sequence[j]] vector_aux[i][j] = ct[i][j] aux_ctjobs[fabrica_asignada] = vector_aux[i][j] else: if i == 0: ct[i][j] = max(self.r[sequence[j]], max(vector_aux[self.machines*fabrica_asignada])) + self.pt[i][sequence[j]] vector_aux[self.machines*fabrica_asignada][j] = ct[i][j] else: ct[i][j] = max(max(vector_aux[self.machines*fabrica_asignada+i]), max(vector_aux[self.machines*fabrica_asignada+i-1])) + self.pt[i][sequence[j]] vector_aux[self.machines*fabrica_asignada+i][j] = ct[i][j] aux_ctjobs[fabrica_asignada] = copy.deepcopy(vector_aux[self.machines*fabrica_asignada+i][j]) # print("vector auxiliar ", vector_aux) # print("Vector de los completion times finales del trabajo",aux_ctjobs) ct_jobs[fabrica_asignada][j] = copy.deepcopy(aux_ctjobs[fabrica_asignada]) # print(ct_jobs) return ct_jobs,sequence ECT_lowestWF from scheptk.scheptk import * import sys # to stop the execution (funcion exit() ) from scheptk.util import * import copy,random class DPFS_ECT_WF(Model): def __init__(self, filename): # initializing additional data (not basic) self.machines = 0 # starting reading print("----- Reading Distributed FlowShop instance data from file " + filename + " -------") # jobs (mandatory data) 38 self.jobs = read_tag(filename,"JOBS") # if jobs = -1 the program cannot continue if(self.jobs ==-1): print("No jobs specified. The program cannot continue.") sys.exit() else: print_tag("JOBS", self.jobs) # machines (another mandatory data) self.machines = read_tag(filename, "MACHINES") if(self.machines ==-1): print("No machines specified. The program cannot continue.") sys.exit() else: print_tag("MACHINES", self.machines) #leer el vector f self.f = read_tag(filename,"F") if(self.f == -1): print("No factories specified. The program cannot continue.") sys.exit() else: print_tag("F",self.f) #leer el vector de pesos de la fábrica self.wf = read_tag(filename,"WF") if(self.wf == -1): print("No weights for factories specified. The program cannot continue.") sys.exit() else: if(len(self.wf) != self.f): print("Number of factories does not match the number of weight of the factories (FACTORIES={}, lenght of WF={}). The program cannot continue".format(self.f, len(self.wf))) sys.exit() else: print_tag("WF",self.wf) # processing times (mandatory data, machines in rows, jobs in cols) self.pt = read_tag(filename,"PT") if(self.pt ==-1): print("No processing times specified. The program cannot continue.") 39 sys.exit() else: if(len(self.pt) != self.machines ): print("Number of processing times does not match the number of machines (MACHINES={}, length of PT={}). The program cannot continue".format(self.machines, len(self.pt)) ) sys.exit() else: for i in range(self.machines): if(len(self.pt[i])!= self.jobs): print("Number of processing times does not match the number of jobs for machine {} (JOBS={}, length of col={}). The program cannot continue".format(i, self.jobs, len(self.pt[i])) ) sys.exit() print_tag("PT", self.pt) # weights (if not, default weights) self.check_weights(filename) # due dates (if not, -1 is assumed) self.check_duedates(filename) # release dates (if not, 0 is assumed) self.check_releasedates(filename) def ct(self,sequence): ct = [[0 for j in range(len(sequence))] for i in range(self.machines)] #print("Vector de ct de cada trabajo en cada máquina", ct) ct_jobs = [[0 for j in range(len(sequence))] for i in range(self.f)] #print("Vector de cada trabajo en cada fábrica", ct_jobs) vector_aux = [[0 for j in range(len(sequence))] for i in range(self.f) for k in range(self.machines)] #vector auxiliar donde guardaremos los timepos de proceso de cada trabajo en cada maquina y en cada fábricas #print("Creamos un vector auxiliar",vector_aux) #Creamos un vector donde guardar los tiempos de proceso de un trabajo pero SOLO en su fábrica asignada vector_ct = [[0 for j in range(len(sequence))] for i in range(self.f) for k in range(self.machines)] aux_ctjobs = [0 for j in range(self.f)] #vector para guardar lo que tarda cada trabajo en cada fábrica 40 for j in range(len(sequence)): for k in range(self.f): for i in range(self.machines): if k == 0: if i == 0: ct[i][j] = max(max(vector_aux[i]), self.r[sequence[j]]) + self.pt[i][sequence[j]] vector_aux[i][j] = ct[i][j] else: ct[i][j] = max(max(vector_aux[i-1]), max(vector_aux[i])) + self.pt[i][sequence[j]] vector_aux[i][j] = ct[i][j] aux_ctjobs[k] = vector_aux[i][j] else: if i == 0: ct[i][j] = max(self.r[sequence[j]], max(vector_aux[self.machines*k])) + self.pt[i][sequence[j]] vector_aux[self.machines*k][j] = ct[i][j] else: ct[i][j] = max(max(vector_aux[self.machines*k+i]), max(vector_aux[self.machines*k+i-1])) + self.pt[i][sequence[j]] vector_aux[self.machines*k+i][j] = ct[i][j] aux_ctjobs[k] = copy.deepcopy(vector_aux[self.machines*k+i][j]) # print("vector auxiliar tras la asignación", vector_aux) # print("Vector ct del trabajo en todas las fábricas",aux_ctjobs) #asignamos ahora a que fábrica irá el trabajo en función del peso de la fábrica minct = aux_ctjobs[find_index_min(aux_ctjobs)] # print("El mínimo completion time es", minct) index = [] for l in range(len(aux_ctjobs)): if minct == aux_ctjobs[l]: # print("Posible fábrica asiganada",l) index.append(l) # print("Fábricas candidatas a insertar trabajos", index) minwf = self.wf[index[0]] 41 fabrica_asignada = copy.deepcopy(index[0]) for n in range(len(index)): if self.wf[index[n]] < minwf: minwf = copy.deepcopy(self.wf[index[n]]) fabrica_asignada = copy.deepcopy(index[n]) # print("El trabajo {} irá a la fábrica {} cuyo peso es {}" .format(sequence[j],fabrica_asignada,minwf)) for m in range(self.machines): vector_ct[self.machines*fabrica_asignada+m][j] = copy.deepcopy(vector_aux[self.machines*fabrica_asignada+m][j]) vector_aux = copy.deepcopy(vector_ct) # print("Vector auxiliar listo para nueva asignación", vector_aux) # print("Vector de ct de cada trabajo en cada máquina de la fábrica asignada",vector_ct) ct_jobs[fabrica_asignada][j] = copy.deepcopy(aux_ctjobs[fabrica_asignada]) # print(ct_jobs) return ct_jobs,sequence FAM_lowestWF from scheptk.scheptk import * import sys # to stop the execution (funcion exit() ) from scheptk.util import * import copy,random class DPFS_FAM_WF(Model): def __init__(self, filename): # initializing additional data (not basic) self.machines = 0 # starting reading print("----- Reading Distributed FlowShop instance data from file " + filename + " -------") # jobs (mandatory data) self.jobs = read_tag(filename,"JOBS") # if jobs = -1 the program cannot continue if(self.jobs ==-1): print("No jobs specified. The program cannot continue.") sys.exit() else: print_tag("JOBS", self.jobs) # machines (another mandatory data) 42 self.machines = read_tag(filename, "MACHINES") if(self.machines ==-1): print("No machines specified. The program cannot continue.") sys.exit() else: print_tag("MACHINES", self.machines) #leer el vector f self.f = read_tag(filename,"F") if(self.f == -1): print("No factories specified. The program cannot continue.") sys.exit() else: print_tag("F",self.f) #leer el vector de pesos de la fábrica self.wf = read_tag(filename,"WF") if(self.wf == -1): print("No weights for factories specified. The program cannot continue.") sys.exit() else: if(len(self.wf) != self.f): print("Number of factories does not match the number of weight of the factories (FACTORIES={}, lenght of WF={}). The program cannot continue".format(self.f, len(self.wf))) sys.exit() else: print_tag("WF",self.wf) # processing times (mandatory data, machines in rows, jobs in cols) self.pt = read_tag(filename,"PT") if(self.pt ==-1): print("No processing times specified. The program cannot continue.") sys.exit() else: if(len(self.pt) != self.machines ): print("Number of processing times does not match the number of machines (MACHINES={}, length of PT={}). The program cannot continue".format(self.machines, len(self.pt)) ) sys.exit() else: for i in range(self.machines): 49 S,obj = SPT(instancia) nuevaS = [] for i in range(len(S) // 2): nuevaS.append(S[i]) nuevaS.append(S[len(S) - 1 - i]) # Si la longitud del vector original es impar, agregamos el elemento central if len(S) % 2 != 0: nuevaS.append(S[len(S) // 2]) obj = instancia.WjCj_Wf(nuevaS) return nuevaS,obj #LPT INTERCALADO def LPT_INT(instancia): S,obj = LPT(instancia) nuevaS = [] for i in range(len(S) // 2): nuevaS.append(S[i]) nuevaS.append(S[len(S) - 1 - i]) # Si la longitud del vector original es impar, agregamos el elemento central if len(S) % 2 != 0: nuevaS.append(S[len(S) // 2]) obj = instancia.WjCj_Wf(nuevaS) return nuevaS,obj resultados = [] #empezamos evaluando las instancias pequeñas for f in range(2,5): for j in range (10,18,2): for m in range(2,6): archivo = 'instancia_f' + str(f) + '_j' + str(j) + '_m' + str(m) + '.txt' instancia = DPFS_FAM(archivo) S0,obj0 = SPT(instancia) S1,obj1 = LPT(instancia) S2,obj2 = WSPT(instancia) S3,obj3 = SPT_INT(instancia) S4,obj4 = LPT_INT(instancia) 50 with open('resultadosFAM.txt','a') as resultadosFAM: resultadosFAM.write(archivo + ' objSPT: ' + str(obj0) + ' objLPT: ' + str(obj1) + ' objWSPT: ' + str(obj2) + ' objSPT_INT: ' + str(obj3) + ' objLPT_INT: ' + str(obj4) + '\n') datos = [obj0,obj1,obj2,obj3,obj4] resultados.append(datos) #evaluamos ahora las instancias grandes for f in range(2,8): for j in (20,50,100): for m in (5,10,20): archivo = 'instancia_f' + str(f) + '_j' + str(j) + '_m' + str(m) + '.txt' instancia = DPFS_FAM(archivo) S0,obj0 = SPT(instancia) S1,obj1 = LPT(instancia) S2,obj2 = WSPT(instancia) with open('resultadosFAM.txt','a') as resultadosFAM: resultadosFAM.write(archivo + ' objSPT: ' + str(obj0) + ' objLPT: ' + str(obj1) + ' objWSPT: ' + str(obj2) + ' objSPT_INT: ' + str(obj3) + ' objLPT_INT: ' + str(obj4) + '\n') datos = [obj0,obj1,obj2,obj3,obj4] resultados.append(datos) doc = xlsxwriter.Workbook('resultadosFAM.xlsx') hoja = doc.add_worksheet() for k in range(len(resultados)): for i in range(len(resultados[k])): hoja.write(k,i,resultados[k][i]) doc.close() evaluaECT_lowestWF from DPFS_ECT_lowestWF import * from scheptk.util import * import xlsxwriter #SHORTEST PROCESSING TIME def SPT(instancia): 51 pijtot = [0 for i in range(instancia.jobs)] for i in range (instancia.jobs): for j in range(instancia.machines): pijtot[i] = sum(instancia.pt[j][i] for j in range(instancia.machines)) S = sorted_index_asc(pijtot) obj = instancia.WjCj_Wf(S) return S,obj #LARGEST PROCESSING TIME def LPT(instancia): pijtot = [0 for j in range(instancia.jobs)] for i in range(instancia.jobs): for j in range(instancia.machines): pijtot[i] = sum(instancia.pt[j][i] for j in range(instancia.machines)) S = sorted_index_desc(pijtot) obj = instancia.WjCj_Wf(S) return S,obj #WEIGHTED SHORTEST PROCESSING TIME def WSPT(instancia): pijtot = [0 for j in range(instancia.jobs)] for i in range(instancia.jobs): for j in range(instancia.machines): pijtot[i] = sum(instancia.pt[j][i] for j in range(instancia.machines)) cociente = [0 for j in range(instancia.jobs)] for j in range(instancia.jobs): cociente[j] = instancia.w[j]/pijtot[j] S = sorted_index_desc(cociente) obj = instancia.WjCj_Wf(S) return S,obj #SPT INTERCALADO def SPT_INT(instancia): S,obj = SPT(instancia) nuevaS = [] for i in range(len(S) // 2): nuevaS.append(S[i]) nuevaS.append(S[len(S) - 1 - i]) # Si la longitud del vector original es impar, agregamos el elemento central if len(S) % 2 != 0: 52 nuevaS.append(S[len(S) // 2]) obj = instancia.WjCj_Wf(nuevaS) return nuevaS,obj #LPT INTERCALADO def LPT_INT(instancia): S,obj = LPT(instancia) nuevaS = [] for i in range(len(S) // 2): nuevaS.append(S[i]) nuevaS.append(S[len(S) - 1 - i]) # Si la longitud del vector original es impar, agregamos el elemento central if len(S) % 2 != 0: nuevaS.append(S[len(S) // 2]) obj = instancia.WjCj_Wf(nuevaS) return nuevaS,obj resultados = [] #empezamos evaluando las instancias pequeñas for f in range(2,5): for j in range (10,18,2): for m in range(2,6): archivo = 'instancia_f' + str(f) + '_j' + str(j) + '_m' + str(m) + '.txt' instancia = DPFS_ECT_WF(archivo) S0,obj0 = SPT(instancia) S1,obj1 = LPT(instancia) S2,obj2 = WSPT(instancia) S3,obj3 = SPT_INT(instancia) S4,obj4 = LPT_INT(instancia) with open('resultadosECTlowestWF.txt','a') as resultadosECTlowestWF: resultadosECTlowestWF.write(archivo + ' objSPT: ' + str(obj0) + ' objLPT: ' + str(obj1) + ' objWSPT: ' + str(obj2) + ' objSPT_INT: ' + str(obj3) + ' objLPT_INT: ' + str(obj4) + '\n') datos = [obj0,obj1,obj2,obj3,obj4] 53 resultados.append(datos) #evaluamos ahora las instancias grandes for f in range(2,8): for j in (20,50,100): for m in (5,10,20): archivo = 'instancia_f' + str(f) + '_j' + str(j) + '_m' + str(m) + '.txt' instancia = DPFS_ECT_WF(archivo) S0,obj0 = SPT(instancia) S1,obj1 = LPT(instancia) S2,obj2 = WSPT(instancia) S3,obj3 = SPT_INT(instancia) S4,obj4 = LPT_INT(instancia) with open('resultadosECTlowestWF.txt','a') as resultadosECTlowestWF: resultadosECTlowestWF.write(archivo + ' objSPT: ' + str(obj0) + ' objLPT: ' + str(obj1) + ' objWSPT: ' + str(obj2) + ' objSPT_INT: ' + str(obj3) + ' objLPT_INT: ' + str(obj4) + '\n') datos = [obj0,obj1,obj2,obj3,obj4] resultados.append(datos) doc = xlsxwriter.Workbook('resultadosECTlowestWF.xlsx') hoja = doc.add_worksheet() for k in range(len(resultados)): for i in range(len(resultados[k])): hoja.write(k,i,resultados[k][i]) doc.close() evaluaFAM_lowestWF from DPFS_FAM_lowestWF import * from scheptk.util import * import xlsxwriter #SHORTEST PROCESSING TIME def SPT(instancia): pijtot = [0 for i in range(instancia.jobs)] for i in range (instancia.jobs): for j in range(instancia.machines): pijtot[i] = sum(instancia.pt[j][i] for j in range(instancia.machines)) 54 S = sorted_index_asc(pijtot) obj = instancia.WjCj_Wf(S) return S,obj #LARGEST PROCESSING TIME def LPT(instancia): pijtot = [0 for j in range(instancia.jobs)] for i in range(instancia.jobs): for j in range(instancia.machines): pijtot[i] = sum(instancia.pt[j][i] for j in range(instancia.machines)) S = sorted_index_desc(pijtot) obj = instancia.WjCj_Wf(S) return S,obj #WEIGHTED SHORTEST PROCESSING TIME def WSPT(instancia): pijtot = [0 for j in range(instancia.jobs)] for i in range(instancia.jobs): for j in range(instancia.machines): pijtot[i] = sum(instancia.pt[j][i] for j in range(instancia.machines)) cociente = [0 for j in range(instancia.jobs)] for j in range(instancia.jobs): cociente[j] = instancia.w[j]/pijtot[j] S = sorted_index_desc(cociente) obj = instancia.WjCj_Wf(S) return S,obj #SPT INTERCALADO def SPT_INT(instancia): S,obj = SPT(instancia) nuevaS = [] for i in range(len(S) // 2): nuevaS.append(S[i]) nuevaS.append(S[len(S) - 1 - i]) # Si la longitud del vector original es impar, agregamos el elemento central if len(S) % 2 != 0: nuevaS.append(S[len(S) // 2]) obj = instancia.WjCj_Wf(nuevaS) return nuevaS,obj 55 #LPT INTERCALADO def LPT_INT(instancia): S,obj = LPT(instancia) nuevaS = [] for i in range(len(S) // 2): nuevaS.append(S[i]) nuevaS.append(S[len(S) - 1 - i]) # Si la longitud del vector original es impar, agregamos el elemento central if len(S) % 2 != 0: nuevaS.append(S[len(S) // 2]) obj = instancia.WjCj_Wf(nuevaS) return nuevaS,obj resultados = [] #empezamos evaluando las instancias pequeñas for f in range(2,5): for j in range (10,18,2): for m in range(2,6): archivo = 'instancia_f' + str(f) + '_j' + str(j) + '_m' + str(m) + '.txt' instancia = DPFS_FAM_WF(archivo) S0,obj0 = SPT(instancia) S1,obj1 = LPT(instancia) S2,obj2 = WSPT(instancia) S3,obj3 = SPT_INT(instancia) S4,obj4 = LPT_INT(instancia) with open('resultadosFAMlowestWF.txt','a') as resultadosFAMlowestWF: resultadosFAMlowestWF.write(archivo + ' objSPT: ' + str(obj0) + ' objLPT: ' + str(obj1) + ' objWSPT: ' + str(obj2) + ' objSPT_INT: ' + str(obj3) + ' objLPT_INT: ' + str(obj4) + '\n') datos = [obj0,obj1,obj2,obj3,obj4] resultados.append(datos) #evaluamos ahora las instancias grandes for f in range(2,8): 56 for j in (20,50,100): for m in (5,10,20): archivo = 'instancia_f' + str(f) + '_j' + str(j) + '_m' + str(m) + '.txt' instancia = DPFS_FAM_WF(archivo) S0,obj0 = SPT(instancia) S1,obj1 = LPT(instancia) S2,obj2 = WSPT(instancia) S3,obj3 = SPT_INT(instancia) S4,obj4 = LPT_INT(instancia) with open('resultadosFAMlowestWF.txt','a') as resultadosFAMlowestWF: resultadosFAMlowestWF.write(archivo + ' objSPT: ' + str(obj0) + ' objLPT: ' + str(obj1) + ' objWSPT: ' + str(obj2) + ' objSPT_INT: ' + str(obj3) + ' objLPT_INT: ' + str(obj4) + '\n') datos = [obj0,obj1,obj2,obj3,obj4] resultados.append(datos) doc = xlsxwriter.Workbook('resultadosFAMlowestWF.xlsx') hoja = doc.add_worksheet() for k in range(len(resultados)): for i in range(len(resultados[k])): hoja.write(k,i,resultados[k][i]) doc.close() BWO from DPFS_FAM import * from scheptk.util import * import random,copy,math,time import numpy as np def BWO(instancia,PS,PP,CR,PM): # creamos la población inicial fija # IND = [] # while len(IND)<PS: # S = random_sequence(instancia.jobs) # # print(S) # if S not in IND: # IND.append(S) # print("Tenemos ya la población de {} individuos" .format(len(IND)),IND) 57 #vector para guardar los mejores individuos en cad iteración mejores_ind = [] #establecemos el número de individuos elegidos igual a 4 a = 4 # it = 0 tiempo_maximo = instancia.jobs*instancia.machines*60/1000 # print(tiempo_maximo) tpo = 0 #(fin - inicio) ini = time.time() while tpo<tiempo_maximo: # creamos la población inicial en cada it IND = [] while len(IND)<PS: S = random_sequence(instancia.jobs) # print(S) if S not in IND: IND.append(S) # print("Tenemos ya la población de {} individuos" .format(len(IND)),IND) ####################FASE DE PROCREACIÓN#################### #elegimos nr indiviudos como población candidata nr = int(PS*PP) # print(nr) pares_padres = [] # creamos nr pares de padres a partir de la población candidata de nr individuos while len(pares_padres)<nr: candidatos = random.sample(IND,nr) # print("Población candidata", candidatos) #seleccionamos cuatro individuos y nos quedamos con el mejor individuos_torneo1 = random.sample(candidatos,a) # print("Indiviudos del torneo 1",individuos_torneo1) padre1 = min(individuos_torneo1, key=instancia.WjCj_Wf) # print("Padre 1",padre1) #volvemos a seleecionar cuatro individuos y nos quedamos con el mejor, si coincide con el padre1 repetimos individuos_torneo2 = random.sample(candidatos,a) # print("Indiviudos del torneo 2",individuos_torneo2) padre2 = min(individuos_torneo2, key=instancia.WjCj_Wf) # print("Padre 2 provisonal", padre2) 58 #si el padre 2 es igual que el padre 1 volvemos a realizar el torneo de selección hasta que sean distintos while padre1 == padre2: # print("El padre 2 es igual que el padre 1", padre1,padre2) individuos_torneo2 = random.sample(candidatos,a) padre2 = min(individuos_torneo2, key=instancia.WjCj_Wf) # print("Tras comprobar que los padres son distintos:") # print("Padre 2", padre2) # cuando ya tenemos los dos pares de padres el que tenga menor valor de la FO será la hembra # print("Los valores de las funciones objetivos son: FO padre1: {}, FO padre 2: {}".format(instancia.WjCj_Wf(padre1),instancia.WjCj_Wf(padre2))) if instancia.WjCj_Wf(padre1) > instancia.WjCj_Wf(padre2): hembra = padre2[:] macho = padre1[:] else: hembra = padre1[:] macho = padre2[:] # print("Hembra y macho",hembra,macho) if [hembra,macho] not in pares_padres: pares_padres.append([hembra,macho]) # print("Pares de padres sin elementos repetido",pares_padres,len(pares_padres)) #una vez tenemos los padres generamos dos hijos por cada par de padres, esto lo repetimos 4 veces, obteniendo un total de 8·nr nuevos individuos #vector para guardar los hijos que se van creando hijos = [] hijos_set = set() for k in range(len(pares_padres)): while len(hijos)<(8*(k+1)): # definimos dos puntos, los elementos del padre que se encuentren entre estos dos puntos, serán heredados directamente por los hijos punto = sorted(random.sample(range(instancia.jobs), 2)) # print("Punto",punto) child1 = [None] * instancia.jobs child2 = [None] * instancia.jobs child1[punto[0]:punto[1]+1] = pares_padres[k][0][punto[0]:punto[1]+1] child2[punto[0]:punto[1]+1] = pares_padres[k][1][punto[0]:punto[1]+1] 65 pid = best_sec[:] # print("Secuencia tras hacer la inserción",pid,instancia.WjCj_Wf(pid)) pid_ls = localSearch(pid, instancia) pip = pid_ls[:] objp = instancia.WjCj_Wf(pip) # print("Secuencia definitva tras hacer la búsqueda local",pid_ls,objp) if objp < obj_ini: pi = pip[:] obj_ini = objp if obj_ini < objb: pib = pi[:] objb = obj_ini else: if random.uniform(0,1)<= math.exp(-(objp-objb)/T): # print("Se cumple el criterio de aceptación") pi = pip[:] fin = time.time() tpo = fin - ini # v = v + 1 # print("Iteraciones",v) # print(tpo) # print("La secuencia obtenida por Iterated Greedy es:", pib,objb) return pib,objb evaluaIG from DPFS_FAM import DPFS_FAM from IteratedGreedy import IG import xlsxwriter resultados = [] #empezamos evaluando las instancia pequeñas for f in range(2,5): for j in range(10,18,2): for m in range(2,6): archivo = 'instancia_f' + str(f) + '_j' + str(j) + '_m' + str(m) + '.txt' instancia = DPFS_FAM(archivo) S,obj = IG(instancia) with open('resultadosIG2.txt','a') as resultadosIG2: resultadosIG2.write(archivo + ' FO ' + str(obj) + '\n') 66 datos = [obj] resultados.append(datos) #evaluamos ahora las instancias grandes for f in range(2,8): for j in (20,50,100): for m in (5,10,20): archivo = 'instancia_f' + str(f) + '_j' + str(j) + '_m' + str(m) + '.txt' instancia = DPFS_FAM(archivo) S,obj = IG(instancia) with open('resultadosIG2.txt','a') as resultadosIG2: resultadosIG2.write(archivo + ' FO ' + str(obj) + '\n') datos = [obj] resultados.append(datos) doc = xlsxwriter.Workbook('resultadosIG2.xlsx') hoja = doc.add_worksheet() for k in range(len(resultados)): for i in range(len(resultados[k])): hoja.write(k,i,resultados[k][i]) doc.close() NEH_FO from DPFS_FAM import * from scheptk.util import * import copy,time def NEH_FO(instancia): pijtot = [0 for i in range(instancia.jobs)] for i in range (instancia.jobs): for j in range(instancia.machines): pijtot[i] = sum(instancia.pt[j][i] for j in range(instancia.machines)) S = sorted_index_desc(pijtot) # print("Secuencia",S) pi = [S[0]] # print("Pi",pi) tpo = 0 #(fin - inicio) ini = time.time() for j in range(1,instancia.jobs): best_obj = float('inf') 67 best_sec = [None] for i in range(len(pi)+1): # print("Mejor secuencia y valor objetivo", best_sec,best_obj) sec = pi[:] # print("Secuencia antes de insertar",sec) sec.insert(i,S[j]) # print("Tras insertar {} en la posicion {} nos queda {}" .format(S[j],i,sec)) obj = instancia.WjCj_Wf(sec) # print("Valor objetivo d1e la función", obj) if obj < best_obj or i==0: # print("La secuencia es mejor porque {} ({}) < {} ({})" .format(obj,sec,best_obj,best_sec)) best_obj = obj best_sec = sec[:] # cuando encontramos una solución mejor paramos y no seguimos explorando insertando en el resto de posiciones if i>0: # print("BREAK") break #si la longitud de la secuencia es mayor de 25 y no se han encontrado mejoras tras 10 movimientos paramos if len(sec)>25 and i>10: # print("Se ha alcanzado el número máximo de iteraciones") break pi = best_sec[:] # print("Secuencia defenitiva",pi) fin = time.time() tpo = fin - ini # print(tpo) # print("Secuencia final", pi) return pi,best_obj 68 Localsearch import copy,time from DPFS_FAM import * from scheptk.util import random_sequence #VECINDAD INSERTION(LOCAL SEARCH --> FIRST IMPROVEMENT) def localSearch(seq, instancia): best_obj = instancia.WjCj_Wf(seq) # print("Valor inicial de la FO",best_obj) best_seq = seq[:] # print("Secuencia inicial",best_seq) tpo = 0 #(fin - inicio) ini = time.time() for j in range(len(seq)): elemento = seq[j] # Elemento a insertar temp_seq = seq[:j] + seq[j+1:] # Creamos una copia temporal sin el elemento en la posición j # print("Secuencia temporal", temp_seq) for i in range(len(seq)): if j != i and j!=i+1: vecino = temp_seq[:i] + [elemento] + temp_seq[i:] # Insertamos en la posición i el elemento # print("Vecino tras insertar el elemento borrado {} en {}: {}" .format(seq[j],i,vecino)) # Calculamos el valor de la función objetivo una vez obj = instancia.WjCj_Wf(vecino) # print("Valor de la FO", obj) #cuando la secuencia obtenida es mejor, paramos if obj < best_obj: # print("Esta secuencia es mejor porque el valor de la FO es menor {}<{}".format(obj,best_obj)) best_obj = obj best_seq = vecino[:] # if len(seq)>=20: # print("BREAK",i,j) break if obj == best_obj: break 69 fin = time.time() tpo = fin - ini # print(tpo) return best_seq GA from NEH_FO import NEH_FO from funcionesvecindades import FIAdjacent,FIGeneral,FIInsertion from scheptk.util import * from DPFS_FAM import * from localSearch import localSearch import random,time def GA(instancia): #creamos la población inicial S,valorFO = NEH_FO(instancia) obj1,S1 = FIAdjacent(S,instancia) obj2,S2 = FIGeneral(S,instancia) obj3,S3 = FIInsertion(S,instancia) # print(S1,S2,S3) pop = [] pop = [S1] + [S2] + [S3] while len(pop)<50: Spop = random_sequence(instancia.jobs) if Spop not in pop: pop.append(Spop) # print(pop,len(pop)) pib = pop[0] objb = instancia.WjCj_Wf(pib) # print("Mejor valor",objb) for j in range(len(pop)): objc = instancia.WjCj_Wf(pop[j]) # print("Valor de la FO",objc) if objc < objb: # print("El valor de la FO es menor") pib = pop[j] objb = objc # print("El nuevo valor de pib es {}, cuyo valor de la FO es {}".format(pib,objb)) 70 tiempo_maximo = instancia.jobs*instancia.machines*60/1000 tpo = 0 #(fin - inicio) ini = time.time() # it = 0 while tpo<tiempo_maximo: # for j in range(1): #primero elegimos dos padres de la población inicial parent1,parent2 = random.sample(pop,2) # print("Par de padres",parent1,parent2) #construimos ahora los hijos punto = sorted(random.sample(range(instancia.jobs), 2)) # print("Punto",punto) child1 = [None] * instancia.jobs child1[punto[0]:punto[1]+1] = parent1[punto[0]:punto[1]+1] # print(child1) for i in range(instancia.jobs): if parent2[i] not in child1: index = child1.index(None) child1[index] = parent2[i] # print("Hijo 1",child1) #construimos el hijo 2 x = random.randint(0,len(parent1)-1) # print("X",x) longitudchild1 = len(child1)-1 if x == longitudchild1: child2 = copy.deepcopy(child1) child2[x] = child1[x-1] child2[x-1] = child1[x] else: child2 = copy.deepcopy(child1) child2[x] = child1[x+1] child2[x+1] = child1[x] # print("Hijo2",child2) obj = instancia.WjCj_Wf(child2) if obj < objb: pib = localSearch(child2, instancia) 71 objb = instancia.WjCj_Wf(pib) # print("Individuo y valor FO",pib,objb) fin = time.time() tpo = fin - ini # it = it+1 # print("IT",it) return(pib,objb) evaluaGA from DPFS_FAM import DPFS_FAM from GA import GA import xlsxwriter resultados = [] #empezamos evaluando las instancia pequeñas for f in range(2,5): for j in range(10,18,2): for m in range(2,6): archivo = 'instancia_f' + str(f) + '_j' + str(j) + '_m' + str(m) + '.txt' instancia = DPFS_FAM(archivo) S,obj = GA(instancia) with open('resultadosGA.txt','a') as resultadosGA: resultadosGA.write(archivo + ' FO ' + str(obj) + '\n') datos = [obj] resultados.append(datos) #evaluamos ahora las instancias grandes for f in range(2,8): for j in (20,50,100): for m in (5,10,20): archivo = 'instancia_f' + str(f) + '_j' + str(j) + '_m' + str(m) + '.txt' instancia = DPFS_FAM(archivo) S,obj = GA(instancia) with open('resultadosGA.txt','a') as resultadosGA: resultadosGA.write(archivo + ' FO ' + str(obj) + '\n') datos = [obj] resultados.append(datos) 72 doc = xlsxwriter.Workbook('resultadosGA.xlsx') hoja = doc.add_worksheet() for k in range(len(resultados)): for i in range(len(resultados[k])): hoja.write(k,i,resultados[k][i]) doc.close() funcionesvecindades from scheptk.scheptk import * import sys # to stop the execution (funcion exit() ) import copy #Intercambio por adyacentes con first improvement def FIAdjacent(S,instancia): best_obj = instancia.max_WjLj(S) best_vecino = copy.deepcopy(S) for j in range(instancia.jobs-1): vecino = copy.deepcopy(S) vecino[j] = S[j+1] vecino[j+1] = S[j] obj = instancia.max_WjLj(vecino) if obj<best_obj: break; return(best_obj,best_vecino) #General swap con first improvement def FIGeneral(S,instancia): best_obj = instancia.max_WjLj(S) best_vecino = copy.deepcopy(S) for j in range(instancia.jobs): for i in range(instancia.jobs): if j<i: vecino = copy.deepcopy(S) vecino[j] = S[i] vecino[i] = S[j] obj = instancia.max_WjLj(vecino) if obj<best_obj: best_obj = copy.deepcopy(obj) best_vecino = copy.deepcopy(vecino) break; if obj == best_obj: 73 break; return(best_obj,best_vecino) #Insertion con first improvement def FIInsertion(S,instancia): best_obj = instancia.max_WjLj(S) best_vecino = copy.deepcopy(S) for j in range(instancia.jobs): for i in range(instancia.jobs): if j!= i and j!=i+1: vecino = copy.deepcopy(S) vecino.pop(j) vecino.insert(i,S[j]) obj = instancia.SumLj(vecino) if obj<best_obj: best_obj = copy.deepcopy(obj) best_vecino = copy.deepcopy(vecino) break; if obj == best_obj: break; return(best_obj,best_vecino) crea_instancias_grandes from scheptk.util import write_tag import numpy as np import random as rd def generainstancia(): for f in range(2,8): for num in range(1,2): with open("DPFSP/DPFSP_Large/" + str(f) + "/Ta00" + str(num)+ "_" +str(f)+".txt",'r') as f_obj: archivo = f_obj.read() # print("Contenido del archivo:\n",archivo) #transformamos el archivo en una lista de cadenas lista = archivo.split() #transformamos esta lista en un lista de enteros datos = [] for j in range(len(lista)): datos.append(int(lista[j])) # print(datos) 74 jobs = datos[0] # print("El número de trabajos es", jobs) maq = datos[1] # print("El número de máquinas es", maq) fab = datos[2] # print("El número de fábricas es", fab) #leemos ahora los tiempos de proceso tpo = [] i = 0 for j in range(maq): i = 4 + i for k in range(jobs): tpo.append(datos[i]) i = i + maq*2 i = 2*(j+1) # print("Los tiempos de procesos son",tpo) #dividimos el vector tpo en el número de máquinas que tenemos pt = np.array(tpo) tiempos= np.split(pt, maq) #trasnformamos el vector tiempos a un formato admisible para nuestra forma de leer instancias pij = [[0 for j in range(jobs)] for i in range(maq)] for i in range(maq): for j in range(jobs): pij[i][j] = tiempos[i][j] # print("Los processing times son",pij) r = [0 for j in range(jobs)] w = [rd.randint(1,99) for j in range(jobs)] wf = rd.sample(range(10,100),fab) dd = [0 for j in range(jobs)] documento = 'instancia' + '_f' + str(fab) + '_j' + str(jobs) + '_m' + str(maq) + '.txt' write_tag('JOBS', jobs, documento) write_tag('MACHINES', maq, documento) write_tag('F', fab, documento)