Aplicación de MILP para flowshop sin permutación

Equation Chapter 1 Section 1 Trabajo Fin de Grado Grado en Ingeniería de las Tecnologías Industriales Aplicación de MILP para flowshop sin permutación Autora: Beatriz Pérez Barranco Tutor: Víctor Fernández-Viagas Escudero Dpto. Organización Industrial y Gestión de Empresas Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 II III Trabajo Fin de Grado Grado en Ingeniería de las Tecnologías Industriales Aplicación de MILP para flowshop sin permutación Autora: Beatriz Pérez Barranco Tutor: Víctor Fernández-Viagas Escudero Dpto. de Organización Industrial y Gestión de Empresas Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 IV V Trabajo Fin de grado: Aplicación de MILP para flowshop sin permutación Autora: Beatriz Pérez Barranco Tutor: Víctor Fernández-Viagas Escudero El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2020 El Secretario del Tribunal VI VII Agradecimientos A mi familia, que me ha apoyado incondicionalmente. Mis padres y mi hermano, que confían en mí más que yo misma y sin los que no habría llegado a dónde estoy ahora. A mis amigos, que siguen ahí después de tantos años y altibajos que han sufrido como si fueran suyos. A Javi, que llegaste justo en el momento que necesitaba ese empujón. Al tutor de este proyecto, Víctor Fernández-Viagas Escudero, por su paciencia y dedicación durante todos estos meses. Siempre atento y dispuesto a ayudarme cuando fuera necesario. Beatriz Pérez Barranco Sevilla, 2020 VIII IX Resumen En este trabajo fin de grado (TFG) se aborda la adaptación de una serie de modelos matemáticos a un entorno productivo habitual. Se propone así un entorno de taller de flujo regular sin permutación, comparable a alguno de los entornos reales encontrados en la industria de manufactura. La adaptación se lleva a cabo mediante el desarrollo de los modelos de programación lineal entera mixta, llamados MILP, definiendo una función objetivo con una serie de restricciones para cada modelo. Este procedimiento se hace mediante programación en lenguaje C para automatizar los procesos y llamar al solver Gurobi para obtener los resultados. Por último, se estudiará el rendimiento de los modelos con respecto a diferentes parámetros. XVI XVII ÍNDICE DE DIAGRAMAS Diagrama 1. Gantt de la solución según el modelo WST original 8 Diagrama 2. Gantt de la solución según el modelo WILSON original 10 Diagrama 3. Gantt de la solución según el modelo TS2 original 11 Diagrama 4. Gantt de la solución según el modelo SGST original 13 Diagrama 5. Gantt de la solución según el modelo LYeq original 14 Diagrama 6. Gantt de la solución según el modelo WILSON modificado 16 Diagrama 7. Gantt de la solución según el modelo TS2 modificado 17 Diagrama 8. Gantt de la solución según el modelo SGST modificado 18 Diagrama 9. Gantt de la solución según el modelo LYeq modificado 20 XVIII XIX ÍNDICE DE GRÁFICAS Gráfica 1. Representación del número de soluciones halladas según modelos 24 Gráfica 2. Dispersión de los valores RPD con respecto a NxM 25 Gráfica 3. Dispersión RPD - NxM, en escala logarítmica 26 Gráfica 4. Medias de los valores ARPD respecto a los modelos 27 Gráfica 5. Medias de los valores ARPD con respecto a los modelos y agrupados según M 29 Gráfica 6. Medias de los valores ARPD con respecto a los modelos y agrupados según N 31 Gráfica 7. Medias del CPU Time con respecto a los modelos 34 Gráfica 8. Medias del CPU Time con respecto a los modelos y agrupadas según M 36 Gráfica 9. Medias del CPU Time con respecto a los modelos y agrupadas según N 37 XX 1 1 INTRODUCCIÓN Este apartado trata de hacer una introducción al tema de la programación de la producción, así como poner en situación al lector sobre el objetivo de este proyecto y el contenido del documento. Se introduce terminología en inglés, entre paréntesis y en cursiva, que se irá explicando conforme aparezca. Una vez se tienen los términos definidos, se utilizará frecuentemente la expresión en inglés o sus siglas por conveniencia. Se tomarán como referencia para estas definiciones (Framinan, Leisten and Ruiz García, 2014; Pérez, Fernández-Viagas and Framinan, 2017) 1.1 Programación de la producción En términos generales, la programación y el control de la producción se inscriben dentro de la organización de la producción (production management) La programación de la producción (manufacturing scheduling) es un proceso de toma de decisiones que se usa sobre todo en las industrias de fabricación y producción o en el sector servicios, así como en entornos de tratamiento de información. Se trata de la asignación de los trabajos o tareas a los recursos existentes o disponibles de la empresa. También es útil en el ámbito del transporte y de la distribución y en otro tipo de industrias de servicio. Al aplicar esta asignación lo que se obtiene es un programa (production schedule) donde se identifica el trabajo que debe entrar en cada recurso y cuándo debe hacerlo. Los recursos y los trabajos pueden definirse de diferente forma según el entorno. Sin embargo, se llega a un consenso para denominar “de forma genérica” dichos factores. Los productos fabricados o las unidades de trabajo en las que puede ser dividida una actividad de fabricación se denomina trabajo (job). A su vez, las operaciones o tareas requeridas por los trabajos están provistos por diferentes recursos productivos disponibles en el taller, y además se asume que es posible identificar dichas unidades de recursos como máquinas (machines) Los recursos pueden ser máquinas en una fábrica, un operario o trabajador, una carretilla elevadora, pistas en un aeropuerto, etc. De igual forma, las tareas pueden ser operaciones en un proceso de producción, una plancha de metal, una caja, despegues y aterrizajes en el aeropuerto, etc. El fin de un proceso de programación de la producción es encontrar, al menos, un programa admisible (feasible schedule) que minimice un cierto objetivo. Dicho programa debe cumplir con todas las restricciones y características del proceso. El método de obtención de un programa se denomina algoritmo. Una vez encontrado al menos un programa admisible, es el momento de elegir. Para elegirlo, se trata de definir uno o más objetivos o parámetros a alcanzar y así comparar los resultados obtenidos en cada programa. Los objetivos también pueden tomar diferentes formas según el ambiente de trabajo. A esta definición se le conoce como la función objetivo. La aplicación de este proceso de programación de la producción en la “vida real” se lleva a cabo de diferente forma según la entidad que lo gestione. Dicha actividad incumbe a las diferentes áreas de una empresa (área de fabricación, de producción, compras, ventas, etc) y que deben tener una buena comunicación entre ellos para lograr sus objetivos. A menudo las empresas utilizan un sistema de información que es transversal a toda la empresa. Una fábrica moderna, por ejemplo, suele tener un sistema de información complejo. Este se basa en un ordenador central y una base de datos. Las redes de los ordenadores y los terminales son utilizados para recibir información de la base de datos, así como introducir nueva información a esta. El software que controla este elaborado sistema de información se llama sistema ERP (Enterprise Resource Planning) y aunque muchas compañías desarrollan sus propios sistemas, el más conocido y utilizado actualmente es SAP. Estos sistemas ERP actúan como una red de información que atraviesa la empresa con enlaces a sistemas de apoyo para la toma de decisiones. 2 La programación de la producción se puede hacer de forma interactiva utilizando cualquier sistema de apoyo para la toma de decisiones que se instala en un terminal conectado al sistema ERP. Sin embargo, también hay entornos donde la comunicación entre la función de la programación y otras entidades de toma de decisión se hacen presencialmente en reuniones o mediante comunicados. En un futuro se prevé que la comunicación entre empresa y cliente o empresa y proveedor se haga enteramente mediante este tipo de sistemas. Todos los datos necesarios para hacer compras, ventas o gestiones estarán incluidos en el sistema. Por último, en lo que se refiere a la representación gráfica, el método más utilizado para ilustrar un programa es el diagrama de Gantt. Este diagrama fue desarrollado por Henry Laurence Gantt en 1917. El diagrama proporciona una descripción gráfica y la programación temporal de todas las actividades y elementos de un proyecto. Se construye con un eje horizontal que representa la duración total del proyecto, dividido en incrementos temporales (días, semanas, meses…) En el eje vertical se pueden representar bien los recursos o bien los trabajos que componen el proyecto. 1.2 Objetivo del proyecto y estructura del documento El objetivo de este proyecto es resolver el problema de forma óptima, con ayuda de los modelos de la literatura existente. Para resolver el problema que se propone en este proyecto y encontrar el programa que logre el mejor resultado de la función objetivo, se llevarán a cabo una serie de adaptaciones de los modelos originales, descritos en el artículo (Stafford, Tseng and Gupta, 2005) Para proceder con la resolución de los modelos, se lleva a cabo la programación en lenguaje C de cada uno de ellos. Con ayuda de esta programación en C también se automatizará la toma de datos de la batería de instancias dada y la generación de los archivos adecuados para su resolución con el software Gurobi. Por último, se hará un análisis de los resultados para concluir con el mejor modelo en cuanto a tiempo de cómputo y obtención de la mejor solución. En cuanto a la estructura del proyecto se diferenciarán los siguientes puntos: ▪ En este primer apartado se hace una introducción al tema de la programación de operaciones. Se exponen los objetivos del proyecto y la estructura del documento. ▪ En el segundo apartado se describirá en profundidad el problema propuesto, además de mostrarse el problema original que se toma de base para el desarrollo del proyecto. ▪ El tercer apartado trata fundamentalmente la descripción de los modelos del problema original, así como de los modelos adaptados para que cumplan las restricciones del problema propuesto. Todos los modelos irán acompañados de un ejemplo explicativo para clarificar las diferencias entre ellos. ▪ En el cuarto, se lleva a cabo el proceso de resolución. En primer lugar, se explica la generación de los archivos necesarios para la ejecución con el software Gurobi. Se completa con un análisis de los resultados obtenidos, teniendo en cuenta varios parámetros como son la factibilidad de las soluciones, la obtención de la mejor solución o la desviación de las soluciones con respecto a la mejor encontrada. ▪ Por último, en el quinto apartado se expondrán las conclusiones obtenidas a partir del análisis de los resultados del apartado anterior. ▪ Además, se añade un anexo con el código en lenguaje de programación C de los modelos descritos. 3 2 CARACTERIZACIÓN DEL PROBLEMA 2.1 Términos generales Para comenzar la caracterización, se definen una serie de términos esenciales para la comprensión del proyecto: Las máquinas son recursos productivos que transforman un material. En este documento se hará referencia a este concepto con la letra 𝑀. Los trabajos son los productos que sufren transformación de las máquinas del taller. Se nombran con la letra 𝑁. Por último, cabe destacar el tiempo de proceso, variable que indica la duración del proceso de transformación de un trabajo dado en una máquina en concreto. Se denomina con 𝑇𝑖𝑗. Por otro lado, para trabajar con los modelos de programación de la producción (scheduling model), conviene tener claras varias definiciones antes de entrar en la descripción del problema en concreto. Un modelo es la abstracción de un problema real de decisión, puede ser de forma matemática, algorítmica, etc. Una vez se ha pasado del problema de programación de la producción al modelo, se lleva a cabo un método de resolución por el cual se obtiene la solución del modelo que se aplicará al caso inicial. Es importante recalcar la diferencia entre problema y modelo. La solución que se obtiene para el problema de programación de la producción es un programa. De este programa se puede deducir la asignación de los trabajos a las máquinas y los instantes de inicio y fin de cada trabajo. Para escribir un modelo de programación de operaciones se acude a la notación procedente de (Graham et al., 1979) en tomando el esquema de clasificación de la Figura 1. Se necesita la definición de α, β y γ para un modelo: • Entorno (α): define las características de la máquina y puede estar formada por dos elementos: α = α1α2 o α1 siendo un 1 si se refiere a un entorno de una sola máquina o una letra indicando la disposición de las máquinas en el caso de haber más de una. Por ejemplo, α1:𝑃 se referiría a un entorno de máquinas idénticas en paralelo (parallel machines); α1:𝐹 si se trata de un taller de flujo regular (flowshop); α1:𝐽 cuando se tiene un entorno taller de trabajos (job shop). o α2 siendo el número de máquinas en el caso de que sean un conjunto de máquinas en serie o en paralelo. Figura 1. Clasificación α/β/γ de los modelos de programación de la producción 4 • Restricciones (β): indica las restricciones del proceso. En este caso se pueden tener restricciones o no. Si hay más de una restricción se separará con comas. En el caso de no haber restricciones hay unas suposiciones generales a considerar como son la disponibilidad de los trabajos al inicio del horizonte de la programación, la ininterrupción de los trabajos o la continua disponibilidad de las máquinas, así como que cada máquina puede hacer un solo trabajo al igual que un trabajo puede ser realizado solo en una máquina. Además, se supone el espacio de almacenamiento de productos (buffer) entre máquinas, infinito y el tiempo de transporte, despreciable. • Criterio (γ): hace referencia a la función objetivo que se quiere alcanzar según el problema. Suelen estar enfocados al tiempo de finalización del proceso. Antes de profundizar en la caracterización del problema, a continuación, se exponen dos ejemplos detallados de cómo pueden presentarse algunos modelos: 1 | 𝑟𝑗 | ∑𝐶𝑗 Este modelo representa un entorno en el que solo se dispone de una máquina, que tiene la restricción 𝑟𝑗 que indica el instante a partir del que los trabajos están disponibles. Con respecto a la función objetivo que se define es ∑𝐶𝑗 e indica la suma de los tiempos de finalización de cada trabajo. 𝐹3 | 𝑝𝑟𝑚𝑢,𝑛𝑜− 𝑖𝑑𝑙𝑒 | 𝐶𝑚𝑎𝑥 Para este ejemplo se tiene un entorno de tipo taller con 3 máquinas en serie donde todos los trabajos tienen que pasar por todas las máquinas. Las restricciones a cumplir son: todas las máquinas tienen la misma secuencia de trabajos y no puede haber tiempos ociosos de máquina entre los trabajos. La función objetivo definida es el mayor tiempo finalización de entre los trabajos procesados (makespan) 2.2 Caracterización Como se ha expuesto anteriormente, para delimitar el problema objeto de estudio hay que definir primero las tres variables α|β|γ: • Entorno (α: 𝐹𝑚): en este caso se tiene un entorno tipo taller de flujo regular (Flowshop) con M máquinas en serie. Cada trabajo debe pasar por todas las máquinas sucesivamente. • Restricciones (β: ø): a parte de las suposiciones generales, no se va a tener en cuenta ninguna restricción adicional. • Criterio (γ: 𝐶𝑚𝑎𝑥): la función objetivo más común es minimizar la duración total del programa (makespan) que se definirá de forma diferente según las variables que precise cada modelo. En resumen, el problema propuesto queda definido tal que así: 𝐹𝑚 | | 𝐶𝑚𝑎𝑥 Por otro lado, el problema que se toma de referencia se define se la siguiente forma: 𝐹𝑚 | 𝑝𝑟𝑚𝑢 |𝐶𝑚𝑎𝑥 Como se puede observar, la diferencia fundamental es la restricción de permutación existente en el modelo de apoyo. Para explicar la diferencia es importante tener claras varias definiciones sobre dichos entornos: ▪ En los entornos de tipo taller de flujo regular (Flowshop) las máquinas se disponen en serie y todos los trabajos tienen que pasar por todas las máquinas con una ruta predeterminada. La ruta es el orden de máquinas que tiene que seguir un trabajo para ser procesado. ▪ Sin embargo, la secuencia de todas las máquinas puede ser la misma (Flowshop de permutación) o diferente (Flowshop sin permutación) La secuencia es el orden en que los trabajos son procesados en una máquina. El hecho de plantear este caso: 𝐹𝑚 | | 𝐶𝑚𝑎𝑥, hace que el problema se acerque lo máximo posible a cualquier caso real. No en todos los entornos industriales se tienen iguales secuencias en todas las máquinas. 5 3 DESCRIPCIÓN DE LOS MODELOS 3.1 Introducción Durante este apartado se expone la notación utilizada junto a la definición de un ejemplo sencillo que se utilizará para esclarecer cada modelo utilizado. Además, se describen los modelos de programación lineal entera que se proponen para resolver el problema original, así como los modelos adaptados al problema propuesto. Antes de adaptar los modelos al problema en cuestión, se ha trabajado en profundidad el problema original, definido como: 𝐹𝑚 | 𝑝𝑟𝑚𝑢 | 𝐶𝑚𝑎𝑥, de acuerdo con lo descrito en (Stafford, Tseng and Gupta, 2005). Otra literatura de referencia utilizada para el desarrollo ha sido (Pinedo, 2012) y (Framinan, Leisten and Ruiz García, 2014) En los modelos de programación de la producción se puede observar la complejidad que van adquiriendo los problemas según se vayan aumentando el número de trabajos, 𝑁, y el número de máquinas, 𝑀. Además, al añadir restricciones se aumenta la complejidad del problema y pueden aparecer soluciones no factibles. En general, para el entorno Flowshop, el número de soluciones está acotada: si la restricción es Flowshop de permutación, el número de soluciones será 𝑁! y si la restricción es de Flowshop sin permutación, el número de soluciones se incrementa notablemente: (𝑁!)𝑀 Debido al intratable número de soluciones se acude a la teoría de complejidad computacional que se desarrolló en los años 70. Consiste en la clasificación de los problemas computacionales de acuerdo a su estructura y dificultad. En cuanto a la clasificación de los modelos, estos pueden ser modelos con algoritmos polinomiales (P) o no polinomiales (NP-hard) Se utilizan los modelos de programación lineal entera mixta (mixed-integer linear programing (MILP)) para solucionar de forma eficiente un problema de este tipo. De esta forma, estos problemas se consideran como un híbrido entre varias categorías de modelamiento, siendo el caso más típico el de mezclar variables enteras, binarias y variables continuas. El tiempo computacional es prácticamente despreciable en comparación con lo que se puede tardar en solucionar un solo problema manualmente. Relacionado con la complejidad de los problemas y ahondando en los modelos matemáticos de las familias de Wagner y Manne, en el análisis de los modelos de (Stafford, Tseng and Gupta, 2005) se explica que la complejidad se usa para referirse a lo “grande” que se convierte cada problema, en términos de número de variables reales requeridas, variables binarias enteras y restricciones como una función de M y N. Dependiendo de cada uno de los aspectos, cada modelo o cada familia de modelos tiene unas características diferentes y son más o menos complejos. 3.2 Notación matemática La notación que se utilizará sigue la notación convencional extraída de (Stafford, Tseng and Gupta, 2005) Los datos considerados son: ▪ 𝑀, siendo el número de máquinas. ▪ 𝑁, siendo los trabajos. ▪ 𝑇𝑟𝑖, indica el tiempo de proceso del trabajo 𝑖 en la máquina 𝑟. ▪ 𝑃, representando un valor suficientemente grande como para asegurar que se cumple solamente una relación del par de restricciones dicotómicas. Para calcularlo: 𝑃 = 100×𝑁 Los índices usados son: 12 𝑀𝑖𝑛 𝐶𝑀𝐴𝑋 (4.1) 𝑠.𝑎: 𝐶1𝑖 ≥𝑇1𝑖 (1≤𝑖≤𝑁) (4.2) 𝐶𝑟+1,𝑖−𝐶𝑟𝑖 ≥𝑇𝑟+1,𝑖 (1≤𝑟≤𝑀− 1;1≤𝑖≤𝑁) (4.3) 𝐶𝑟𝑖−𝐶𝑟𝑘+𝑃𝐷𝑖𝑘 ≥𝑇𝑟𝑖 (1≤𝑟≤𝑀;1≤𝑖<𝑘≤𝑁) (4.4) 𝐶𝑟𝑘−𝐶𝑟𝑖+𝑃(1−𝐷𝑖𝑘)≥𝑇𝑟𝑘 (1≤𝑟≤𝑀;1≤𝑖<𝑘≤𝑁) (4.5) 𝐶𝑀𝐴𝑋 ≥𝐶𝑀𝑖 (1≤𝑖≤𝑁) (4.6) 𝐶𝑟𝑖,𝐶𝑀𝐴𝑋 ≥0 (1≤𝑟≤𝑀,1≤𝑖≤𝑁) 𝐷𝑖𝑘 ∈{0,1} (1≤𝑖<𝑘≤𝑁) En cuanto a las restricciones, (4.2) indica que ningún trabajo pueda terminar en la primera máquina antes de ser completamente procesado en ella. La ecuación (4.3) expresa que cada trabajo no puede ser completado en la máquina 𝑟+1 hasta que no haya sido completado en la máquina anterior y completamente procesado en la máquina actual, en conclusión, esto quiere decir que cada trabajo solo puede ser procesado en una máquina al mismo tiempo. El siguiente par de ecuaciones, (4.4) y (4.5) forman los pares de restricciones dicotómicas que relacionan cada par de trabajos 𝑖 y 𝑘 (𝑖≠𝑘), de modo que cualquiera de los trabajos 𝑖 o precede al 𝑘, o sigue al 𝑘 en la secuencia, pero no ambas cosas. Por último, la restricción (4.6) trata de asegurar que el makespan del programa es, al menos, igual que el tiempo de finalización del último trabajo de la secuencia. Resolución del ejemplo: Para el modelo SGST, los resultados son los recogidos en la Tabla 5. En este caso se obtienen los valores de las variables 𝐶𝑟𝑖 que indican el tiempo de finalización del trabajo 𝑖 en la máquina 𝑟. Por ejemplo, el valor de la variable 𝐶24=16 significa que el trabajo 4 en la máquina 2 termina de procesarse en 16 unidades de tiempo. Además, se saca la secuencia gracias a las variables 𝐷𝑖𝑘, que toman valores de 0 o 1 según si se cumple que el trabajo 𝑖 se sitúe antes del trabajo 𝑘 o no. En el caso de 𝐷13=1 significa que el trabajo 1 se encuentra antes del 3 en la secuencia. El valor de 𝐷45=0 quiere decir que es el trabajo 5 el que está por delante del trabajo 4. De esta forma se obtiene la secuencia: 1, 4, 3, 5, 2. C11 = 2 C12 = 31 C13 = 15 C14 = 8 C15 = 25 D12 = 1 D13 = 1 D14 = 1 D15 = 1 D35 = 1 C21 = 7 C22 = 33 C23 = 26 C24 = 16 C25 = 32 D45 = 1 D23 = 0 D24 = 0 D25 = 0 D34 = 0 C31 = 17 C32 = 34 C33 = 32 C34 = 19 C35 = 33 Tabla 5. Valores obtenidos para las variables del modelo SGST original 13 A partir de los valores obtenidos tras solucionar el problema con el modelo original de SGST, se crea el diagrama de Gantt de forma que se tiene la solución visual recogida en el Diagrama 4. 3.4.2.2 Modelo LYeq Este modelo tiene en común con el anterior las restricciones siguientes: (5.2), (5.3), (5.4) además de la función objetivo (5.1). Y las dos ecuaciones restantes (5.5) y (5.6) se refieren de la misma forma, al par de restricciones dicotómicas. 𝑀𝑖𝑛 𝐶𝑀𝐴𝑋 (5.1) 𝑠.𝑎: 𝐶1𝑖 ≥𝑇1𝑖 (1≤𝑖≤𝑁) (5.2) 𝐶𝑟+1,𝑖−𝐶𝑟𝑖 ≥𝑇𝑟+1,𝑖 (1≤𝑟≤𝑀− 1;1≤𝑖≤𝑁) (5.3) 𝐶𝑀𝐴𝑋 ≥𝐶𝑀𝑖 (1≤𝑖≤𝑁) (5.4) 𝑃𝐷𝑖𝑘+𝐶𝑟𝑖−𝐶𝑟𝑘−𝑇𝑟𝑖 =𝑄𝑟𝑖𝑘 (1≤𝑟≤𝑀;1≤𝑖<𝑘≤𝑁) (5.5) 𝑄𝑟𝑖𝑘 ≤𝑃−𝑇𝑟𝑖−𝑇𝑟𝑘 (1≤𝑟≤𝑀;1≤𝑖<𝑘≤𝑁) (5.6) 𝐶𝑟𝑖,𝐶𝑀𝐴𝑋,𝑄𝑟𝑖𝑘 ≥0 (1≤𝑟≤𝑀,1≤𝑖<𝑘≤𝑁) 𝐷𝑖𝑘 ∈{0,1} (1≤𝑖<𝑘≤𝑁) Resolución del ejemplo: Ahora se resuelve según el modelo LYeq original que cuenta con las mismas variables que el modelo SGST para definirse. Los resultados se muestran en la Tabla 6. Para las variables 𝐶𝑟𝑖 se obtienen valores como los siguientes: C24=16 significa que el trabajo 4 en la máquina 2 termina en 16 unidades de tiempo. Además, las variables 𝐷𝑖𝑘, toman valores de 0 o 1 según si se cumple que el trabajo 𝑖 se sitúe antes del trabajo 𝑘 o no. Al igual que en el caso de la resolución según el modelo SGST, gracias a esta variable se obtiene la secuencia para todas las máquinas. En el caso de 𝐷13=1 significa que el trabajo 1 se encuentra antes del 3 en la secuencia. El valor de 𝐷45=0 quiere decir que es el trabajo 5 el que está por delante del trabajo 4. De esta forma se obtiene la secuencia: 1, 4, 3, 5, 2. Diagrama 4. Gantt de la solución según el modelo SGST original 14 C11 = 2 C12 = 32 C13 = 15 C14 = 8 C15 = 25 D12 = 1 D13 = 1 D14 = 1 D15 = 1 D35 = 1 C21 = 8 C22 = 33 C23 = 26 C24 = 16 C25 = 32 D45 = 1 D23 = 0 D24 = 0 D25 = 0 D34 = 0 C31 = 24 C32 = 34 C33 = 30 C34 = 26 C35 = 33 Tabla 6. Valores obtenidos para las variables del modelo LYeq original A partir de los valores obtenidos tras solucionar el problema con el modelo original de LYeq, se crea el diagrama de Gantt asociado. Es representado en Diagrama 5. 3.5 Modelos adaptados al problema A partir de los modelos originales se ha llegado a la adaptación de cuatro de ellos. En la familia de modelos de Wagner se encontrarán los modelos de WILSON y TS2 y, por lo que respecta a la familia de modelos de Manne se tienen los modelos SGST y LYeq. La adaptación de estos modelos se ha llevado a cabo de forma que se alteraran lo menos posible y no se volvieran más complejos. Se ha tratado de no añadir restricciones ni variables diferentes a las existentes en los modelos originales. Este es el motivo principal por el que en este apartado no se cuenta con el primer modelo de Wagner descrito anteriormente, el modelo WST. 3.5.1 Familia de modelos de Wagner Para adaptar los modelos originales, que están particularizados para el caso de Flowshop de permutación, hay que añadir la condición de que cada máquina tiene una secuencia diferente. Las restricciones comunes, quedan de la siguiente forma: ∑𝑍𝑖𝑗𝑟 𝑁 𝑗=1 =1 (1≤𝑖≤𝑁;1≤𝑟≤𝑀) (1) ∑𝑍𝑖𝑗𝑟 𝑁 𝑖=1 =1 (1≤𝑗≤𝑁;1≤𝑟≤𝑀) (2) Ahora, a las restricciones originales de los modelos de Wagner basadas en que cada trabajo está asignado a una sola posición en la secuencia, y, que cada posición tiene asignada únicamente un trabajo, se le añade que dicha condición se debe cumplir para cada una de las máquinas. Esto se traduce en que, para cada máquina hay una matriz 𝑍𝑖𝑗 diferente. El subíndice 𝑟, utilizado anteriormente, es el indicador para las máquinas. Diagrama 5. Gantt de la solución según el modelo LYeq original 15 3.5.1.1 Modelo Wilson Para poder adaptar el modelo de Wilson, se ha modificado la ecuación (2.5) del modelo original añadiendo un término en la desigualdad que hace que el paréntesis se anule cuando los subíndices 𝑗1 y 𝑗2 coincidan, es decir, cuando el trabajo 𝑖 ocupe la misma posición en ambas máquinas 𝑟 y 𝑟+1, siendo 𝑃 la variable anteriormente definida como un valor lo suficientemente grande como para asegurar que se cumple solamente una relación del par de restricciones dicotómicas. 𝑀𝑖𝑛 𝐵𝑀𝑁+∑𝑇𝑀𝑖𝑍𝑖𝑁𝑀 𝑁 𝑖=1 (2.1) 𝑠.𝑎: 𝐵1𝑗+∑𝑇1𝑖𝑍𝑖𝑗1= 𝑁 𝑖=1 𝐵1,𝑗+1 (1≤𝑗≤𝑁− 1) (2.2) 𝐵11=0 (2.3) 𝐵𝑟1+∑𝑇𝑟𝑖𝑍𝑖1𝑟 𝑁 𝑖=1 =𝐵𝑟+1,1 (1≤𝑟≤𝑀− 1) (2.4) 𝐵𝑟,𝑗1+𝑇𝑟,𝑖𝑍𝑖,𝑗1,𝑟≤ 𝐵𝑟+1,𝑗2+𝑃(2−𝑍𝑖,𝑗1,𝑟−𝑍𝑖,𝑗2,𝑟+1) (1≤𝑖,𝑟≤𝑀− 1,1≤𝑗1,𝑗2≤𝑁) (2.5’) 𝐵𝑟𝑗+∑𝑇𝑟𝑖𝑍𝑖𝑗𝑟 𝑁 𝑖=1 ≤𝐵𝑟,𝑗+1 (2≤𝑟≤𝑀;1≤𝑗≤𝑁− 1) (2.6) 𝐵𝑟𝑗 ≥0 (1≤𝑟≤𝑀,1≤𝑗≤𝑁) 𝑍𝑖𝑗𝑟 ∈{0,1} (1≤𝑟≤𝑀,1≤𝑖,𝑗≤𝑁) Resolución del ejemplo: Tras la modificación del modelo WILSON enfocado a la resolución del problema propuesto, se aplica para obtener numéricamente la solución óptima del ejemplo utilizado anteriormente. Los resultados están recogidos en la Tabla 7. En cuanto a las variables que se utilizan para caracterizar la solución son las siguientes: la variable 𝐵𝑟𝑗 igual que en el modelo original y la variable 𝑍𝑖𝑗𝑟 que tomará valor 1 cuando cumpla que el trabajo 𝑖 va en la posición 𝑗 en la máquina 𝑟, por tanto, a diferencia del modelo original, con ayuda de esa variable se definen las secuencias para cada una de las máquinas. En el caso de este problema ejemplo se obtienen las siguientes secuencias: para las máquinas 1 y 2, los trabajos se procesan en el orden 1,4,3,5,2; y para la máquina 3 se obtiene la secuencia 1,3,4,5,2. Tabla 7. Valores obtenidos para las variables del modelo WILSON modificado A continuación, se expone el diagrama de Gantt representado partir de los valores obtenidos tras solucionar el B11 = 0 B12 = 2 B13 = 8 B14 = 15 B15 = 25 Z111=1 Z251=1 Z331=1 Z421=1 Z541=1 B21 = 2 B22 = 8 B23 = 16 B24 = 26 B25 = 32 Z112=1 Z252=1 Z332=1 Z422=1 Z542=1 B31 = 7 B32 = 26 B33 = 30 B34 = 32 B35 = 33 Z113=1 Z253=1 Z323=1 Z433=1 Z543=1 16 problema con el modelo adaptado de WILSON. 3.5.1.2 Modelo TS2 En el caso del modelo TS2 se ha utilizado la misma técnica que para el modelo Wilson, se modifica la restricción (3.3) añadiendo el término que se cancela cuando coincide que el trabajo 𝑖 se encuentra en la misma posición para máquinas sucesivas. 𝑀𝑖𝑛 𝐸𝑀𝑁 (3.1) 𝑠.𝑎: 𝐸𝑟𝑗+∑𝑇𝑟𝑖𝑍𝑖,𝑗+1,𝑟 𝑁 𝑖=1 ≤𝐸𝑟,𝑗+1 (1≤𝑟≤𝑀;1≤𝑗≤𝑁− 1) (3.2) 𝐸𝑟,𝑗1+𝑇𝑟+1,𝑖𝑍𝑖,𝑗2,𝑟+1≤ 𝐸𝑟+1,𝑗2+𝑃(2−𝑍𝑖,𝑗1,𝑟−𝑍𝑖,𝑗2,𝑟+1) (1≤𝑖,𝑟≤𝑀− 1,1≤𝑗1,𝑗2≤𝑁) (3.3’) 𝐸11≥∑𝑇1𝑖𝑍𝑖11 𝑁 𝑖=1 (3.4) 𝐸𝑟𝑗 ≥0 (1≤𝑟≤𝑀,1≤𝑗≤𝑁) 𝑍𝑖𝑗𝑟 ∈{0,1} (1≤𝑟≤𝑀,1≤𝑖,𝑗≤𝑁) Resolución del ejemplo: Al solucionar el ejemplo mediante el modelo TS2 modificado para el caso de Flowshop sin permutación, los resultados obtenidos son los recogidos en la Tabla 8. Las variables son: 𝐸𝑟𝑗, igual que el modelo original y 𝑍𝑖𝑗𝑟 que difiere del modelo original pues se le añade un subíndice que indica que para cada máquina se puede obtener una secuencia diferente. Las secuencias de las máquinas 1 y 2 son: 1,4,3,5,2 y la de la tercera máquina: 4,1,3,5,2. Diagrama 6. Gantt de la solución según el modelo WILSON modificado 17 E11 = 2 E12 = 8 E13 = 15 E14 = 25 E15 = 31 Z111=1 Z251=1 Z331=1 Z421=1 Z541=1 E21 = 8 E22 = 16 E23 = 26 E24 = 32 E25 = 33 Z112=1 Z252=1 Z332=1 Z422=1 Z542=1 E31 = 18 E32 = 28 E33 = 32 E34 = 33 E35 = 34 Z123=1 Z253=1 Z333=1 Z413=1 Z543=1 Tabla 8. Valores obtenidos para las variables del modelo TS2 modificado A partir de los valores obtenidos tras solucionar el problema con el modelo modificado de TS2, se crea el diagrama de Gantt representado en el Diagrama 7. 3.5.2 Familia de modelos de Manne Igual que se ha expuesto en los modelos originales, en lo referente a la familia de modelos de Manne, no se utiliza el término “posición del trabajo” por lo que, al trabajar solo con trabajos y máquinas, se simplifica la adaptación de dichos modelos. En definitiva, se prescinde del uso del índice 𝑗. 3.5.2.1 Modelo SGST El modelo SGST solo necesita añadir el subíndice 𝑟 en la variable 𝐷𝑖𝑘𝑟 para que se tenga en cuenta que es posible que cada máquina tenga un orden de proceso de los trabajos diferente. 𝑀𝑖𝑛 𝐶𝑀𝐴𝑋 (4.1) 𝑠.𝑎: 𝐶1𝑖 ≥𝑇1𝑖 (1≤𝑖≤𝑁) (4.2) 𝐶𝑟+1,𝑖−𝐶𝑟𝑖 ≥𝑇𝑟+1,𝑖 (1≤𝑟≤𝑀− 1;1≤𝑖≤𝑁) (4.3) 𝐶𝑟𝑖−𝐶𝑟𝑘+𝑃𝐷𝑖𝑘𝑟≥𝑇𝑟𝑖 (1≤𝑟≤𝑀;1≤𝑖<𝑘≤𝑁) (4.4’) 𝐶𝑟𝑘−𝐶𝑟𝑖+𝑃(1−𝐷𝑖𝑘𝑟)≥𝑇𝑟𝑘 (1≤𝑟≤𝑀;1≤𝑖<𝑘≤𝑁) (4.5’) 𝐶𝑀𝐴𝑋 ≥𝐶𝑀𝑖 (1≤𝑖≤𝑁) (4.6) Diagrama 7. Gantt de la solución según el modelo TS2 modificado 18 𝐶𝑟𝑖,𝐶𝑀𝐴𝑋 ≥0 (1≤𝑟≤𝑀,1≤𝑖≤𝑁) 𝐷𝑖𝑘𝑟 ∈{0,1} (1≤𝑟≤𝑀,1≤𝑖<𝑘≤𝑁) Resolución del ejemplo: En este caso, se exponen dos tipos de variables como resultado de la aplicación del modelo SGST al ejemplo, que se exponen en la Tabla 9: la variable 𝐶𝑟𝑖 que indican el tiempo de finalización del trabajo 𝑖 en la máquina 𝑟, como en el modelo original, y la variable 𝐷𝑖𝑘𝑟, que toma valores de 0 o 1 según si se cumple que el trabajo 𝑖 se sitúe antes del trabajo 𝑘 en la máquina 𝑟. Y de la misma forma que en la adaptación de los modelos de Wagner, se pueden obtener secuencias diferentes en cada una de las máquinas. En este caso sale para las máquinas 1 y 2 la secuencia: 1,4,3,5,2 y para la máquina 3, la secuencia: 1,3,4,5,2. C11 = 2 C12 = 31 C13 = 15 C14 = 8 C15 = 25 D121 = D131 = D141 = D151 = D351 = D451 = 1 D231 = D241 = D251 = D341 = 0 C21 = 7 C22 = 33 C23 = 26 C24 = 16 C25 = 32 D122 = D132 = D142 = D152 = D352 = D452 = 1 D232 = D242 = D252 = D342 = 0 C31 = 26 C32 = 34 C33 = 30 C34 = 32 C35 = 33 D123 = D133 = D143 = D153 = D343 = D353 = D453 = 1 D233 = D243 = D253 = 0 Tabla 9. Valores obtenidos para las variables del modelo SGST modificado Tras el análisis de los resultados obtenidos tras aplicar el algoritmo del modelo SGST modificado al ejemplo, se crea el diagrama de Gantt representado a continuación: 3.5.2.2 Modelo LYeq De la misma forma que se ha modificado el modelo SGST se hace el modelo LYeq, puesto que se utilizan las mismas variables con la salvedad de la variable 𝑄𝑟𝑖𝑘 que ya se encuentra definida en el modelo original LYeq para cada máquina 𝑟. Diagrama 8. Gantt de la solución según el modelo SGST modificado 19 𝑀𝑖𝑛 𝐶𝑀𝐴𝑋 (5.1) 𝑠.𝑎: 𝐶1𝑖 ≥𝑇1𝑖 (1≤𝑖≤𝑁) (5.2) 𝐶𝑟+1,𝑖−𝐶𝑟𝑖 ≥𝑇𝑟+1,𝑖 (1≤𝑟≤𝑀− 1;1≤𝑖≤𝑁) (5.3) 𝐶𝑀𝐴𝑋 ≥𝐶𝑀𝑖 (1≤𝑖≤𝑁) (5.4) 𝑃𝐷𝑖𝑘𝑟+𝐶𝑟𝑖−𝐶𝑟𝑘−𝑇𝑟𝑖 =𝑄𝑟𝑖𝑘 (1≤𝑟≤𝑀;1≤𝑖<𝑘≤𝑁) (5.5’) 𝑄𝑟𝑖𝑘 ≤𝑃−𝑇𝑟𝑖−𝑇𝑟𝑘 (1≤𝑟≤𝑀;1≤𝑖<𝑘≤𝑁) (5.6) 𝐶𝑟𝑖,𝐶𝑀𝐴𝑋,𝑄𝑟𝑖𝑘 ≥0 (1≤𝑟≤𝑀,1≤𝑖<𝑘≤𝑁) 𝐷𝑖𝑘𝑟 ∈{0,1} (1≤𝑟≤𝑀,1≤𝑖<𝑘≤𝑁) Resolución del ejemplo: El modelo LYeq cuenta con las mismas variables que el modelo SGST para definirse. Los resultados se muestran en la Tabla 10. Al igual que en el caso de la resolución según el modelo SGST, gracias a la variable 𝐷𝑖𝑘𝑟 se obtiene la secuencia para cada máquina. Se obtiene la secuencia: 1,4,3,5,2 para las máquinas 1 y 2, y la secuencia: 4,1,3,5,2 para la tercera máquina. C11 = 2 C12 = 31 C13 = 15 C14 = 8 C15 = 25 D121 = D131 = D141 = D151 = D351 = D451 = 1 D231 = D241 = D251 = D341 = 0 C21 = 7 C22 = 33 C23 = 26 C24 = 16 C25 = 32 D122 = D132 = D142 = D152 = D352 = D452 = 1 D232 = D242 = D252 = D342 = 0 C31 = 28 C32 = 34 C33 = 32 C34 = 18 C35 = 33 D123 = D133 = D153 = D353 = D453 = 1 D143 = D233 = D243 = D253 = D343 = 0 Tabla 10. Valores obtenidos para las variables del modelo LYeq modificado 20 Se obtiene entonces el Diagrama de Gantt gracias a los resultados obtenidos al resolver el problema con el modelo modificado de LYeq mostrado en el Diagrama 9. Diagrama 9. Gantt de la solución según el modelo LYeq modificado 21 4 RESOLUCIÓN Y ANÁLISIS DE LOS RESULTADOS 4.1 Proceso de resolución Tras la modificación de los modelos originales, se dispone de cuatro modelos adaptados al entorno de Flowshop sin permutación, problema propuesto para este proyecto. Cada modelo resolverá una batería de 160 instancias o problemas. Los problemas se diferencian por el número de máquinas y el número de trabajos. El número de máquinas se genera de 2 a 5, y el número de trabajos será 5, 10, 15 o 20. De cada una de las combinaciones se tienen, además, 10 instancias diferentes. La resolución de la batería de instancias llevará a la ejecución de un total de 4[𝑁] 𝑥 4[𝑀] 𝑥 10[𝑖𝑛𝑠𝑡] 𝑥 4[𝑀𝑂𝐷]=640 problemas diferentes mediante el solver Gurobi. Gurobi es un solver comercial de optimización de programación lineal (Optimization, 2018). Se aclara lo que se tiene y lo que se necesita para ejecutar el solver de Gurobi: ▪ En primer lugar, se dispone de: la definición de los modelos en forma de algoritmo además de una batería de instancias en archivos de texto con sus datos. Igual que se muestra en la Figura 2. ▪ Se necesita obtener un archivo de extensión .𝑙𝑝 para cada una de las instancias formuladas y para cada modelo. Este archivo debe tener una sintaxis determinada y tendrá una apariencia del estilo de la Figura 3. Para obtener el archivo ejecutable por Gurobi se ha escrito en leguaje C un programa que automatiza todas las acciones. ▪ Primero se generan varios archivos auxiliares donde se almacenan los nombres de los archivos de Figura 2. Disposición de los datos de la instancia número 3 para M=5 y N=4 Figura 3. Sintaxis del modelo SGST de un ejemplo de M=2 y N=2 28 de la familia de Manne. Esto se traduce en la existencia de un mayor rango de valores obtenidos para los modelos de la familia de Wagner. De este análisis se puede concluir que los modelos que dan mejor resultado al resolver las instancias del problema serían los modelos de la familia de Manne ya que obtienen el mejor valor de entre los encontrados, o para expresarlo de otra forma, el valor óptimo de la función objetivo o uno muy próximo a este. Tras esta conclusión, se puede plantear otro enfoque: hacer desglose de los valores obtenidos según el número de máquinas y según el número de trabajos, para cada modelo. Se procede a la explicación de los resultados de dicho análisis. 4.2.2.2 ARPD con respecto al número de máquinas Los valores obtenidos son recogidos en la Tabla 13. En esta tabla se muestra la media de cada modelo respecto al número de máquinas, además de la desviación estándar y el número de instancias consideradas 𝑁. M WILSON TS2 SGST LYeq 2 Media 0,0000% 0,0000% 0,0000% 0,0281% N 40 40 40 40 Desviación 0,00000% 0,00000% 0,00000% 0,17781% 3 Media 1,4948% 2,7318% 0,0000% 0,3826% N 40 40 40 40 Desviación 2,86957% 4,61139% 0,00000% 1,16601% 4 Media 8,6868% 12,3387% 0,0281% 1,9977% N 40 40 40 40 Desviación 10,63408% 13,23340% 0,17746% 4,82671% 5 Media 14,5563% 30,8281% 0,0017% 3,6832% N 34 40 40 40 Desviación 16,71314% 27,72418% 0,01096% 5,97777% Tabla 13. Resultados obtenidos de la media ARPD con respecto a los modelos y agrupados según M Los valores de la tabla anterior son representados en la Gráfica 5 con el software SPSS. Con ayuda del código de colores se observan fácilmente los diferentes resultados para cada número de máquinas: 29 De los resultados representados en la Gráfica 5 se puede obtener la información siguiente: ▪ Para valores de 𝑀=2, representado en azul en la gráfica, los resultados obtenidos por todos los modelos coinciden entre ellos y con el mejor resultado de la función objetivo hallado. ▪ Para valores de 𝑀=3 la desviación de los resultados en los modelos de la familia de Wagner es mínima, pero algo mayor que en el caso de la familia de modelos de Manne, que es nula. ▪ En el caso de la existencia de 4 máquinas en el problema, representado con el color verde en la gráfica, la desviación con respecto a la mejor solución encontrada se incrementa. Para los modelos de WILSON y TS2, la media de la desviación gira en torno al 10% con una desviación típica también de aproximadamente un 10%. Sin embargo, el modelo SGST se mantiene con una desviación prácticamente nula y el modelo LYeq con una desviación también insignificante. ▪ Por último, para valores de 𝑀=5, los problemas considerados más complejos, se obtiene lo siguiente: en los dos primeros modelos, WILSON y TS2, se tiene una media de la desviación que supera el 20% y una desviación típica bastante considerable en comparación a las demás. Por su parte, los modelos SGST y LYeq se mantienen en la misma línea que para el caso anterior. De este análisis se puede sacar una conclusión clara, el modelo que mejor funciona, en términos de encontrar la mejor solución, sería el modelo SGST que obtiene, para todos los valores de 𝑀, una media de desviación casi nula con respecto a la mejor solución. 4.2.2.3 ARPD con respecto al número de trabajos Se procede de la misma forma que se ha hecho anteriormente: se exponen los resultados obtenidos en la Tabla 14, agrupados por modelo y según el número de trabajos. Para mostrarlo de forma visual se hace uso de la representación en la Gráfica 6. Gráfica 5. Medias de los valores ARPD con respecto a los modelos y agrupados según M 30 N WILSON TS2 SGST LYeq 5 Media 0,1499% 0,0000% 0,0000% 0,0000% N 40 40 40 40 Desviación 0,79224% 0,00000% 0,00000% 0,00000% 10 Media 2,4337% 4,7316% 0,0000% 0,0685% N 40 40 40 40 Desviación 4,58536% 6,76007% 0,00000% 0,33486% 15 Media 8,0017% 16,6807% 0,0281% 1,2841% N 40 40 40 40 Desviación 9,51467% 23,55813% 0,17746% 2,59644% 20 Media 14,0814% 24,4862% 0,0017% 4,7389% N 34 40 40 40 Desviación 17,70590% 24,07453% 0,01096% 6,85542% Tabla 14. Resultados obtenidos de la media ARPD con respecto a los modelos y agrupados según N En este caso, en la tabla se exponen los resultados divididos por modelos y para cada uno de los valores de 𝑁 (5, 10, 15 y 20) se obtienen los valores de la media de ARPD, la desviación típica de este valor y 𝑁, el número de instancias tomadas para dicho cálculo. Los resultados obtenidos en cuanto a los modelos son parecidos a los obtenidos hasta el momento: ▪ Para los modelos WILSON y TS2 se observa que, según el número de trabajos aumenta, la media del porcentaje de ARPD también lo hace, y lo que es más significativo, la desviación típica es significativamente mayor. Esto supone que para dichos modelos se obtienen resultados en un amplio rango. ▪ En el caso de los modelos de la familia de Manne los valores de la media de dispersión son muy cercanos a cero y la desviación típica es muy pequeña en casi todos los casos. Cabe destacar el modelo SGST, que resuelve los problemas para todo valor de N de forma que encuentra siempre el mejor valor de la función objetivo. En conclusión, se llega a la misma deducción, el modelo SGST sería el indicado si se quiere obtener con seguridad los mejores valores para la función objetivo. En segundo lugar, se puede aconsejar el uso del modelo LYeq que obtiene resultados comparables al modelo anterior. 31 4.2.3 Análisis de la varianza, ANOVA A continuación, se plantean una serie de preguntas que se podrían predecir sin necesidad de la resolución del análisis de la varianza. Sin embargo, con ayuda de este análisis se confirmará la dependencia de los valores obtenidos de ARPD con respecto de las variables que cambian en la resolución de los problemas: el modelo utilizado, el número de máquinas M y el número de trabajos N. ▪ ¿Afecta el modelo utilizado para resolver los problemas al valor de ARPD? ▪ ¿Afecta el número de máquinas de los problemas al valor de ARPD? ▪ ¿Afecta el número de trabajos de los problemas al valor de ARPD? Para cada una de las preguntas anteriores se utiliza un contraste de hipótesis. Se necesita proponer una hipótesis nula y una hipótesis alternativa. En el primer caso se va a explicar detalladamente el procedimiento seguido y para los siguientes casos se seguirá un proceso análogo. 4.2.3.1 Dependencia con el modelo En el caso de la dependencia con el modelo utilizado se propone lo siguiente: 𝜇𝑀𝑂𝐷1:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑒𝑙 𝑚𝑜𝑑𝑒𝑙𝑜 𝑊𝐼𝐿𝑆𝑂𝑁 𝜇𝑀𝑂𝐷2:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑒𝑙 𝑚𝑜𝑑𝑒𝑙𝑜 𝑇𝑆2 𝜇𝑀𝑂𝐷3:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑒𝑙 𝑚𝑜𝑑𝑒𝑙𝑜 𝑆𝐺𝑆𝑇 𝜇𝑀𝑂𝐷4:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑒𝑙 𝑚𝑜𝑑𝑒𝑙𝑜 𝐿𝑌𝑒𝑞 𝐻0: 𝜇𝑀𝑂𝐷1= 𝜇𝑀𝑂𝐷2=𝜇𝑀𝑂𝐷3=𝜇𝑀𝑂𝐷4 𝑒𝑙 𝑚𝑜𝑑𝑒𝑙𝑜 𝑛𝑜 𝑎𝑓𝑒𝑐𝑡𝑎 𝑎 𝑙𝑜𝑠 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝑑𝑒 𝐴𝑅𝑃𝐷 𝑜𝑏𝑡𝑒𝑛𝑖𝑑𝑜𝑠 𝐻1: 𝜇𝑀𝑂𝐷𝑖 ≠ 𝜇𝑀𝑂𝐷𝑗 𝑝𝑎𝑟𝑎 𝑖≠𝑗 𝑒𝑙 𝑚𝑜𝑑𝑒𝑙𝑜 𝑎𝑓𝑒𝑐𝑡𝑎 𝑎 𝑙𝑜𝑠 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝑑𝑒 𝐴𝑅𝑃𝐷 𝑜𝑏𝑡𝑒𝑛𝑖𝑑𝑜𝑠 Con ayuda del programa SPSS y haciendo uso de la herramienta análisis de la ANOVA de un factor se obtienen Gráfica 6. Medias de los valores ARPD con respecto a los modelos y agrupados según N 32 los valores de la siguiente tabla: Suma de cuadrados gl Media cuadrática F Sig. Entre grupos 12688,166 3 4229,389 32,241 ,000 Dentro de grupos 82642,677 630 131,179 Total 95330,843 633 Tabla 15. ANOVA con dependencia del modelo Para aceptar o rechazar la hipótesis expuesta anteriormente se analiza el p-valor. El nivel de error del contraste que se toma por defecto es del 5% (𝛼=0,05). Se comprueba entonces que el p-valor, marcado en negrita en la tabla, es menor que el nivel de significación definido (o alfa). La muestra presenta suficiente evidencia como para rechazar la hipótesis nula de que las medias de los valores sean iguales para todos los modelos. Se llega a la conclusión de que el modelo utilizado al resolver los problemas influye en los valores obtenidos de ARPD. 4.2.3.2 Dependencia con el número de máquinas De la misma forma, se procede para el caso de la dependencia con el número de máquinas: 𝜇𝑀2:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑀=2 𝜇𝑀3:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑀=3 𝜇𝑀4:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑀=4 𝜇𝑀5:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑀=5 𝐻0: 𝜇𝑀2= 𝜇𝑀3=𝜇𝑀4=𝜇𝑀5, 𝑒𝑙 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑚á𝑞𝑢𝑖𝑛𝑎𝑠 𝑛𝑜 𝑎𝑓𝑒𝑐𝑡𝑎 𝑎 𝑙𝑜𝑠 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝑑𝑒 𝐴𝑅𝑃𝐷 𝑜𝑏𝑡𝑒𝑛𝑖𝑑𝑜𝑠 𝐻1: 𝜇𝑀𝑖 ≠ 𝜇𝑀𝑗 𝑝𝑎𝑟𝑎 𝑖≠𝑗, 𝑒𝑙 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑚á𝑞𝑢𝑖𝑛𝑎𝑠 𝑎𝑓𝑒𝑐𝑡𝑎 𝑎 𝑙𝑜𝑠 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝑑𝑒 𝐴𝑅𝑃𝐷 𝑜𝑏𝑡𝑒𝑛𝑖𝑑𝑜𝑠 Se obtienen ahora los siguientes resultados: Suma de cuadrados gl Media cuadrática F Sig. Entre grupos 14330,396 3 4776,799 37,153 ,000 Dentro de grupos 81000,447 630 128,572 Total 95330,843 633 Tabla 16. ANOVA con dependencia del número de máquinas M De este resultado también se puede confirmar que el número de máquinas afecta en los valores de ARPD. 4.2.3.3 Dependencia con el número de trabajos Por último, se estudia la dependencia con el número de trabajos del problema y se propone: 33 𝜇𝑁5:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑁=5 𝜇𝑁10:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑁=10 𝜇𝑁15:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑁=15 𝜇𝑁20:𝑚𝑒𝑑𝑖𝑎 𝑑𝑒 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝐴𝑅𝑃𝐷 𝑝𝑎𝑟𝑎 𝑁=20 𝐻0: 𝜇𝑁5= 𝜇𝑁10=𝜇𝑁15=𝜇𝑁20, 𝑒𝑙 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 𝑛𝑜 𝑎𝑓𝑒𝑐𝑡𝑎 𝑎 𝑙𝑜𝑠 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝑑𝑒 𝐴𝑅𝑃𝐷 𝑜𝑏𝑡𝑒𝑛𝑖𝑑𝑜𝑠 𝐻1: 𝜇𝑁𝑖 ≠ 𝜇𝑁𝑗 𝑝𝑎𝑟𝑎 𝑖≠𝑗, 𝑒𝑙 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 𝑎𝑓𝑒𝑐𝑡𝑎 𝑎 𝑙𝑜𝑠 𝑣𝑎𝑙𝑜𝑟𝑒𝑠 𝑑𝑒 𝐴𝑅𝑃𝐷 𝑜𝑏𝑡𝑒𝑛𝑖𝑑𝑜𝑠 Tras ejecutar el análisis de la varianza se obtiene para este caso: Suma de cuadrados gl Media cuadrática F Sig. Entre grupos 10878,100 3 3626,033 27,049 ,000 Dentro de grupos 84452,743 630 134,052 Total 95330,843 633 Tabla 17. ANOVA con dependencia del número de trabajos N Se obtiene un p-valor inferior al valor de alfa definido, por tanto, también se confirma que el número de trabajos del problema afecta a los valores obtenidos de ARPD. En resumen, este análisis confirma la dependencia de la variable ARPD con el número de máquinas y el número de trabajos, así como con el modelo de resolución utilizado. 4.2.4 Análisis CPU Time Como se ha comentado anteriormente, el análisis del tiempo de cómputo se puede ver perturbado por la restricción del límite de tiempo de resolución. Este límite está en 900 segundos, y muchas de las soluciones se encuentran en torno a ese instante. 4.2.4.1 CPU Time con respecto al modelo Se muestra en la Tabla 18 la media de CPU Time total de todos los casos, sin diferenciar por número de máquinas M o número de trabajos N. Además, se indica el valor de la desviación estándar de esta medida. Modelo Media N Desv. Estándar WILSON 476,371625 160 441,5528949 TS2 499,78975 160 438,6533359 SGST 470,6953125 160 438,2783187 LYeq 524,907125 160 431,9190949 Tabla 18. Resultados obtenidos de la media de CPU Time con respecto a los modelos 34 En la Gráfica 7 se puede observar la representación del valor medio del CPU Time con respecto a los diferentes modelos, con un intervalo de confianza del 95%. De dichos resultados se pueden sacar algunas conclusiones: ▪ Las medias de los tiempos de cómputo se encuentran en torno a los 500s. El modelo que menos tarda, de media, en la resolución de las instancias es el modelo SGST. El modelo que más tarda sería el modelo LYeq. ▪ Las desviaciones estándar con respecto a los valores medios son muy grandes. Estos rangos tan amplios son debidos a la cantidad de instancias que dan su resultado en el instante 900 o alrededor. 4.2.4.2 CPU Time con respecto al número de máquinas En la Tabla 19 se observan los valores de la media de CPU Time, junto a la desviación típica de sus valores, divididos según modelos y para cada número de máquinas: 2, 3, 4 y 5 respectivamente. Además, se ha representado gráficamente en la Gráfica 8. Gráfica 7. Medias del CPU Time con respecto a los modelos 35 M WILSON TS2 SGST LYeq 2 Media 79,8147 19,3633 454,9798 462,0225 N 40 40 40 40 Desviación 238,66141 44,02092 450,89506 444,31054 3 Media 495,0053 620,7228 454,1293 470,339 N 40 40 40 40 Desviación 434,53043 406,30174 451,61651 438,36862 4 Media 654,7808 676,2658 460,3773 554,0993 N 40 40 40 40 Desviación 399,18521 392,57657 446,29861 432,15447 5 Media 675,8857 682,8073 513,295 613,1677 N 40 40 40 40 Desviación 393,23076 381,19387 417,344 410,1911 Tabla 19. Resultados obtenidos de la media CPU Time con respecto al modelo y M En cuanto a las ideas extraídas de estos resultados: ▪ El menor valor medio de CPU Time se da para problemas pequeños, de solo 2 máquinas, resueltos con los modelos de la familia de Wagner. ▪ A partir de 3 máquinas, para los modelos WILSON y TS2, los valores medios de tiempo de cómputo se disparan. ▪ Para la familia de modelos de Manne, los resultados de todos los casos son bastante parecidos. Además, los valores medios son menores que los modelos de Wagner. Entre ellos prácticamente se solapan, aunque se puede apreciar el modelo SGST como algo más rápido que el LYeq. 36 4.2.4.3 CPU Time con respecto al número de trabajos Para terminar, se procede de igual forma con los siguientes resultados: se exponen en la Tabla 20 los valores desglosados por modelo y por número de trabajos (5, 10, 15 y 20) En cuanto a la representación gráfica de dichos valores, se puede encontrar en la Gráfica 9 y se muestra con el código de colores para diferenciar cada agrupación de instancias según el número de trabajos. N WILSON TS2 SGST LYeq 5 Media 1,3512 9,319 0,0688 0,106 N 40 40 40 40 Desviación 1,49369 16,35624 0,03653 0,04634 10 Media 550,0448 620,8873 82,6823 299,4833 N 40 40 40 40 Desviación 430,80397 406,01692 153,17106 370,5874 15 Media 611,7845 677,568 900,017 900,0135 N 40 40 40 40 Desviación 403,3979 390,28358 0,01572 0,01642 20 Media 742,306 691,3848 900,0132 900,0257 N 40 40 40 40 Desviación 343,81828 367,68729 0,01421 0,04012 Tabla 20. Resultados obtenidos de la media CPU Time con respecto al modelo y N Gráfica 8. Medias del CPU Time con respecto a los modelos y agrupadas según M 37 Las ideas que se pueden obtener de este análisis son muy similares al anterior apartado: ▪ Los problemas más simples, aquellos con 5 trabajos, se resuelven en un tiempo casi despreciable. Conforme aumenta la cantidad de trabajos, el tiempo de computo también lo hace. ▪ En el caso de los modelos de WILSON y TS2, la media de valores y su desviación típica son muy similares y casi coincidentes las barras del intervalo de confianza. ▪ El modelo SGST podría considerarse perfecto para solucionar problemas con 5 trabajos y con 10. Sin embargo, cuando los trabajos aumentan a 15 y 20, son problemas tan complejos que se para la simulación en el tiempo límite. ▪ El modelo LYeq se asemeja al SGST exceptuando el valor algo mayor para problemas de 10 trabajos. Gráfica 9. Medias del CPU Time con respecto a los modelos y agrupadas según N 44 char tcomp [] = "C"; char dicot [] = "D"; char nuev [] = "Q"; char obj [] = "max"; //Creación lista de nombres(lista_nombres.txt) de la batería de archivos FILE *nombres; nombres = fopen("lista_nombres.txt","wt"); for (j=0; j<=ln; j++) { for (i=0; i<=lm; i++) { for (iter=1; iter<=10; iter++) { fprintf (nombres,"inst_%d_%d_p_%d \n", trabajo[j], maquina[i], iter); } } } fclose (nombres); //Creación lista de nombres modelo WILSON (lista_WILSON.txt) de la batería de archivos FILE *nombresWILSON; nombresWILSON = fopen ("lista_WILSON.txt","wt"); for (j=0; j<=ln; j++) { for (i=0; i<=lm; i++) { for (iter=1; iter<=10; iter++) { fprintf (nombresWILSON, "WILSON_inst_%d_%d_p_%d.lp \n", trabajo[j], maquina[i], iter); } } } fclose (nombresWILSON); //Creación lista de nombres modelo TS2 (lista_TS2.txt) de la batería de archivos FILE *nombresTS2; nombresTS2 = fopen ("lista_TS2.txt","wt"); for (j=0; j<=ln; j++) { for (i=0; i<=lm; i++) { for (iter=1; iter<=10; iter++) { fprintf (nombresTS2,"TS2_inst_%d_%d_p_%d.lp \n", trabajo[j], maquina[i], iter); } } } fclose (nombresTS2); //Creación lista de nombres modelo SGST (lista_SGST.txt) de la batería de archivos 45 FILE *nombresSGST; nombresSGST = fopen ("lista_SGST.txt","wt"); for (j=0; j<=ln; j++) { for (i=0; i<=lm; i++) { for (iter=1; iter<=10; iter++) { fprintf (nombresSGST,"SGST_inst_%d_%d_p_%d.lp \n", trabajo[j], maquina[i], iter); } } } fclose (nombresSGST); //Creación lista de nombres modelo LYeq (lista_LYeq.txt) de la batería de archivos FILE *nombresLYeq; nombresLYeq = fopen ("lista_LYeq.txt","wt"); for (j=0; j<=ln;j ++) { for (i=0; i<=lm; i++) { for (iter=1; iter<=10; iter++) { fprintf (nombresLYeq,"LYeq_inst_%d_%d_p_%d.lp \n", trabajo[j], maquina[i], iter); } } } fclose(nombresLYeq); //Lectura del archivo para contabilizar la longitud del fichero de los nombres nombres = fopen ("lista_nombres.txt","rt"); while ((ch = fgetc (nombres)) != EOF) { if (ch == '\n') { longfichero++; } } fclose (nombres); //Lectura de cada nombre de la lista de nombres y apertura de cada uno de los archivos en cuestión nombres = fopen ("lista_nombres.txt","rt"); //abrir en modo lectura el fichero lista_nombres.txt nombresWILSON = fopen ("lista_WILSON.txt","rt"); //abrir en modo lectura el fichero lista_WILSON.txt nombresTS2 = fopen ("lista_TS2.txt","rt"); //abrir en modo lectura el fichero lista_TS2.txt nombresSGST = fopen ("lista_SGST.txt","rt"); //abrir en modo lectura el fichero lista_SGST.txt nombresLYeq = fopen ("lista_LYeq.txt","rt"); //abrir en modo lectura el fichero lista_LYeq.txt FILE *gurobiWILSON; FILE *gurobiTS2; FILE *gurobiSGST; 46 FILE *gurobiLY; gurobiWILSON = fopen ("FicheroWILSON.txt","wt"); gurobiTS2 = fopen ("FicheroTS2.txt","wt"); gurobiSGST = fopen ("FicheroSGST.txt","wt"); gurobiLY = fopen ("FicheroLY.txt","wt"); FILE *archivo; FILE *modelo_WILSON; FILE *modelo_TS2; FILE *modelo_SGST; FILE *modelo_LYeq; For (k=1; k<=longfichero; k++) { fscanf (nombres, "%s\n", cadenanombre); //leer cada línea del fichero lista_nombres.txt y asigno cada nombre a la variable cadenanombre fscanf (nombresWILSON, "%s\n", nombreWILSON); //leer cada línea del fichero lista_WILSON.txt y asigno cada nombre a la variable nombreWILSON fscanf (nombresTS2, "%s\n", nombreTS2); //leer cada línea del fichero lista_TS2.txt y asigno cada nombre a la variable nombreTS2 fscanf (nombresSGST, "%s\n", nombreSGST); //leer cada línea del fichero lista_SGST.txt y asigno cada nombre a la variable nombreSGST fscanf (nombresLYeq, "%s\n", nombreLY); //leer cada línea del fichero lista_LYeq.txt y asigno cada nombre a la variable nombreLY archivo = fopen (cadenanombre, "rt"); //abrir en modo lectura cada fichero con el nombre asignado a la variable cadena nombre fscanf (archivo, "%d \n", &M); //leer la primera línea del fichero y asignarla a la variable M fscanf (archivo, "%d \n", &N); //leer la segunda línea del fichero y asignarla a la variable N for (j=0; j<N; j++) { for (i=0; i<M; i++) { fscanf (archivo, "%d ", &T[i][j]); //leer los tiempos de proceso del fichero y asignarlos a Tij } fscanf (archivo, "\n"); } P = 100*N; //Aplicación del modelo WILSON: modelo_WILSON = fopen (nombreWILSON, "wt"); //Función objetivo fprintf (modelo_WILSON, "Minimize \n"); fprintf (modelo_WILSON, "%s%d%d ", tini, M, N); for (i=1; i<=N; i++) { fprintf (modelo_WILSON, "+ %d %s%d%d%d ", T[M-1][i-1], cadena, i, N, M); } 47 //Restricciones fprintf (modelo_WILSON, "\nSubject To \n"); for (r=1; r<=M; r++) { for (i=1; i<=N; i++) { for (j=1; j<N; j++) { fprintf (modelo_WILSON, "%s%d%d%d + ", cadena, i, j, r); } if (j=N) { fprintf (modelo_WILSON, "%s%d%d%d ", cadena, i, j, r); } fprintf (modelo_WILSON, "= 1\n"); } } for (r=1; r<=M; r++) { for (j=1; j<=N; j++) { for (i=1; i<N; i++) { fprintf (modelo_WILSON, "%s%d%d%d + ", cadena, i, j, r); } if (i=N) { fprintf (modelo_WILSON, "%s%d%d%d ", cadena, i, j, r); } fprintf (modelo_WILSON, "= 1\n"); } } for (j=1; j<N; j++) { fprintf (modelo_WILSON, "%s%d%d ", tini, 1, j); for (i=1; i<=N; i++) { fprintf (modelo_WILSON, "+ %d %s%d%d%d ", T[0][i-1], cadena, i, j, 1); } fprintf(modelo_WILSON, "- %s%d%d = 0\n", tini,1,j+1); } fprintf (modelo_WILSON, "%s%d%d = 0\n", tini, 1, 1); for (r=1; r<M; r++) { fprintf (modelo_WILSON, "%s%d%d ", tini, r, 1); for (i=1; i<=N; i++) { fprintf (modelo_WILSON, "+ %d %s%d%d%d ", T[r-1][i-1], cadena, i, 1, r); } fprintf (modelo_WILSON, "- %s%d%d = 0\n", tini, r+1, 1); 48 } for (r=1; r<M; r++) { for (x1=1; x1<=N; x1++) { for (x2=1; x2<=N; x2++) { for (i=1; i<=N; i++) { fprintf (modelo_WILSON, "%s%d%d - %s%d%d ", tini, r, x1, tini, r+1, x2); fprintf (modelo_WILSON, "+ %d %s%d%d%d + %d %s%d%d%d ", P, cadena, i, x1, r, P, cadena, i, x2, r+1); fprintf (modelo_WILSON, "+ %d %s%d%d%d ", T[r-1][i-1], cadena, i, x1, r); fprintf (modelo_WILSON, "<= %d\n", 2*P); } } } } for (r=2; r<=M; r++) { for (j=1; j<N; j++) { fprintf (modelo_WILSON, "%s%d%d ", tini, r, j); for (i=1; i<=N; i++) { fprintf (modelo_WILSON, "+ %d %s%d%d%d ", T[r-1][i-1], cadena, i, j, r); } fprintf (modelo_WILSON, "- %s%d%d <= 0\n", tini, r, j+1); } } //Variables fprintf (modelo_WILSON, "Binary \n"); for (r=1; r<=M; r++) { for (i=1; i<=N; i++) { for (j=1; j<=N; j++) { fprintf (modelo_WILSON, "%s%d%d%d ", cadena, i, j, r); } } } fprintf (modelo_WILSON, "\nGeneral \n"); for (r=1; r<=M; r++) { for (j=1; j<=N; j++) { fprintf (modelo_WILSON, "%s%d%d ", tini, r, j); } } 49 fprintf (modelo_WILSON, "\nEnd"); fclose (modelo_WILSON); fprintf (gurobiWILSON, "gurobi_cl TimeLimit=900 C:/Users/Beatriz/…/%s \n", nombreWILSON); P = 100*N; //Aplicación del modelo TS2: modelo_TS2 = fopen (nombreTS2,"wt"); //Función objetivo fprintf (modelo_TS2, "Minimize \n"); fprintf (modelo_TS2, "%s%d%d", tfin, M, N); //Restricciones fprintf (modelo_TS2, "\nSubject To \n"); for (r=1; r<=M; r++) { for (i=1; i<=N; i++) { for (j=1; j<N; j++) { fprintf (modelo_TS2, "%s%d%d%d + ", cadena, i, j, r); } if (j=N) { fprintf (modelo_TS2, "%s%d%d%d ", cadena, i, j, r); } fprintf (modelo_TS2, "= 1\n"); } } for (r=1; r<=M; r++) { for (j=1; j<=N; j++) { for (i=1; i<N; i++) { fprintf (modelo_TS2, "%s%d%d%d + ", cadena, i, j, r); } if (i=N) { fprintf (modelo_TS2, "%s%d%d%d ", cadena, i, j, r); } fprintf (modelo_TS2, "= 1\n"); } } for (r=1; r<=M; r++) { for (j=1; j<N; j++) { fprintf (modelo_TS2, "%s%d%d ", tfin, r, j); for (i=1; i<=N; i++) { fprintf (modelo_TS2, "+ %d %s%d%d%d ", T[r-1][i-1], cadena, i, j+1, r); 50 } fprintf (modelo_TS2, "- %s%d%d <= 0\n", tfin, r, j+1); } } for (r=1; r<M; r++) { for (x1=1; x1<=N; x1++) { for (x2=1; x2<=N; x2++) { for (i=1; i<=N; i++) { fprintf (modelo_TS2, "%s%d%d - %s%d%d ", tfin, r, x1, tfin, r+1, x2); fprintf (modelo_TS2, "+ %d %s%d%d%d + %d %s%d%d%d ", P, cadena, i, x1, r, P, cadena, i, x2, r+1); fprintf (modelo_TS2, "+ %d %s%d%d%d ", T[r][i-1], cadena, i, x2, r+1); fprintf (modelo_TS2, "<= %d\n", 2*P); } } } } fprintf (modelo_TS2, "%s%d%d ", tfin, 1, 1); for (i=1; i<=N; i++) { fprintf (modelo_TS2, "- %d %s%d%d%d ", T[0][i-1], cadena, i, 1, 1); } fprintf (modelo_TS2, ">= 0\n"); //Variables fprintf (modelo_TS2, "Binary \n"); for (r=1; r<=M; r++) { for (i=1; i<=N; i++) { for (j=1; j<=N; j++) { fprintf (modelo_TS2, "%s%d%d%d ", cadena, i, j, r); } } } fprintf (modelo_TS2, "\nGeneral \n"); for (r=1; r<=M; r++) { for (j=1; j<=N; j++) { fprintf (modelo_TS2, "%s%d%d ", tfin, r, j); } } fprintf (modelo_TS2, "\nEnd"); 51 fclose (modelo_TS2); fprintf (gurobiTS2, "gurobi_cl TimeLimit=900 C:/Users/Beatriz/…/%s \n", nombreTS2); P = 100*N; //Aplicación del modelo SGST: modelo_SGST = fopen (nombreSGST,"wt"); //Función objetivo fprintf (modelo_SGST, "Minimize\n"); fprintf (modelo_SGST, "%s%s\n", tcomp, obj); //Restricciones fprintf (modelo_SGST, "Subject To \n"); for (i=1; i<=N; i++) { fprintf (modelo_SGST, "%s%d%d >= %d\n", tcomp, 1, i, T[0][i-1]); } for (r=1; r<M; r++) { for (i=1; i<=N; i++) { fprintf (modelo_SGST, "%s%d%d - %s%d%d >= %d\n", tcomp, r+1, i, tcomp, r, i, T[r][i-1]); } } for (r=1; r<=M; r++) { for (i=1; i<l; i++) { for (l=i+1; l<=N; l++) { fprintf (modelo_SGST, "%s%d%d - %s%d%d + %d %s%d%d%d >= %d\n", tcomp, r, i, tcomp, r, l, P, dicot, i, l, r, T[r-1][i-1]); } } } for (r=1; r<=M; r++) { for (i=1; i<l; i++) { for (l=i+1; l<=N; l++) { fprintf (modelo_SGST, "%s%d%d - %s%d%d - %d %s%d%d%d >= %d\n", tcomp, r, l, tcomp, r, i, P, dicot, i, l, r, T[r-1][l-1]-P); } } } for (i=1; i<=N; i++) { fprintf (modelo_SGST, "%s%s - %s%d%d >= 0\n", tcomp, obj, tcomp, M, i); } //Variables fprintf (modelo_SGST, "General \n"); 52 for (r=1; r<=M; r++) { for (i=1; i<=N; i++) { fprintf (modelo_SGST, "%s%d%d ", tcomp, r, i); } } fprintf (modelo_SGST, "\nBinary \n"); for (r=1; r<=M; r++) { for (i=1; i<N; i++) { for (l=i+1; l<=N; l++) { fprintf (modelo_SGST, "%s%d%d%d ", dicot, i, l, r); } } } fprintf (modelo_SGST, "\nEnd"); fclose (modelo_SGST); fprintf (gurobiSGST, "gurobi_cl TimeLimit=900 C:/Users/Beatriz/…/%s \n", nombreSGST); P = 100*N; //Aplicación del modelo LYeq: modelo_LYeq = fopen (nombreLY,"wt"); //Función objetivo fprintf (modelo_LYeq, "Minimize\n"); fprintf (modelo_LYeq, "%s%s\n", tcomp, obj); //Restricciones fprintf (modelo_LYeq, "Subject To \n"); for (i=1; i<=N; i++) { fprintf (modelo_LYeq, "%s%d%d >= %d\n", tcomp, 1, i, T[0][i-1]); } for (r=1; r<M; r++) { for (i=1; i<=N; i++) { fprintf (modelo_LYeq, "%s%d%d - %s%d%d >= %d\n", tcomp, r+1, i, tcomp, r, i, T[r][i-1]); } } for (i=1; i<=N; i++) { fprintf (modelo_LYeq, "%s%s - %s%d%d >= 0\n", tcomp, obj, tcomp, M, i); } for (r=1; r<=M; r++) { for (i=1; i<l; i++) { for (l=i+1; l<=N; l++) { 53 fprintf (modelo_LYeq, "%d %s%d%d%d + %s%d%d - %s%d%d - %s%d%d%d = %d\n", P, dicot, i, l, r, tcomp, r, i, tcomp, r, l, nuev, i, l, r, T[r-1][i-1]); } } } for (r=1; r<=M; r++) { for (i=1; i<l; i++) { for (l=i+1; l<=N; l++) { fprintf (modelo_LYeq, "%s%d%d%d <= %d\n", nuev, i, l, r, P-T[r-1][i-1]-T[r-1][l-1]); } } } //Variables fprintf (modelo_LYeq, "General \n"); for (r=1; r<=M; r++) { for (i=1; i<=N; i++) { fprintf (modelo_LYeq, "%s%d%d ", tcomp, r, i); } } fprintf (modelo_LYeq, "\nBinary \n"); for (r=1; r<=M; r++) { for (i=1; i<N; i++) { for (l=i+1; l<=N; l++) { fprintf (modelo_LYeq, "%s%d%d%d ", dicot, i, l, r); } } } fprintf (modelo_LYeq, "\nEnd"); fclose (modelo_LYeq); fprintf (gurobiLY, "gurobi_cl TimeLimit=900 C:/Users/Beatriz/…/%s \n", nombreLY); } }