Estudio de modelos de programación lineal entera para el taller de flujo regular con esperas no permitidas

I PROYECTO FIN DE GRADO INGENIERÍA DE LAS TECNOLOGÍAS INDUSTRIALES ESTUDIO DE MODELOS DE PROGRAMACIÓN LINEAL ENTERA PARA EL TALLER DE FLUJO REGULAR CON ESPERAS NO PERMITIDAS Autor: Jose Luis Fernández-Figueroa González Tutor: Víctor Fernández-Viagas Escudero Dep. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 II III Proyecto Fin de Grado Ingeniería en Tecnologías Industriales ESTUDIO DE MODELOS DE PROGRAMACIÓN LINEAL ENTERA PARA EL TALLER DE FLUJO REGULAR CON ESPERAS NO PERMITIDAS Autor: Jose Luis Fernández-Figueroa González Tutor: Víctor Fernández-Viagas Escudero Profesor ayudante doctor Dep. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 IV V A mi familia A mis amigos VI Resumen Este trabajo de Fin de Grado trata de resolver un problema de análisis de modelos de programación lineal en un entorno de un taller de flujo con permutación adaptando varios modelos generales de taller de flujo con permutación a un taller de flujo con esperas no permitidas. La metodología seguida en este trabajo, es la utilización de un algoritmo, de los llamados algoritmos exactos, como es el método MILP que consiste en establecer una función objetivo sujeta a unas restricciones para resolver los modelos. Finalmente, se hará una evaluación computacional de varios aspectos a todos los modelos a partir del cual se obtendrá cual es el mejor modelo comparándolos entre ellos. VII Índice Resumen ............................................................................................................................................. VI Índice ................................................................................................................................................. VII Índice de figuras ................................................................................................................................... IX Índice de tablas ..................................................................................................................................... X 1. Introducción .................................................................................................................................. 1 1.1. Organización de la producción ............................................................................................. 1 1.2. Programación de la producción ............................................................................................ 1 1.3. α|β|γ ...................................................................................................................................... 2 1.4. FlowShop ............................................................................................................................. 3 1.5. No-wait (nwt) ....................................................................................................................... 4 1.6. Cmax y ∑Cj .......................................................................................................................... 4 1.7. Diagramas de Gantt .............................................................................................................. 5 2. Objeto del proyecto ....................................................................................................................... 6 2.1. Objeto del proyecto .............................................................................................................. 6 2.2. Justificación.......................................................................................................................... 6 3. Modelos de programación lineal de las familias Wagner y Manne para el permutation flowshop clásico ................................................................................................................................................... 8 3.1. Introducción ......................................................................................................................... 8 3.2. Descripción de los modelos y sus variables ......................................................................... 8 3.2.1. Familia Wagner ............................................................................................................ 8 3.2.2. Familia Manne ........................................................................................................... 10 3.2.3. Modelo adicionales familia Wagner .......................................................................... 11 4. Herramientas y metodologías utilizadas ..................................................................................... 12 4.1. MILP .................................................................................................................................. 12 4.2. CodeBlocks y C.................................................................................................................. 13 4.3. Gurobi ................................................................................................................................ 15 4.4. Batch y Registro ................................................................................................................. 15 5. MILPs para el problema bajo consideración ............................................................................... 17 5.1. Familia Wagner .................................................................................................................. 17 5.2. Familia Manne ................................................................................................................... 21 5.3. Modelos adicionales familia Wagner ................................................................................. 24 6. Evaluación computacional .......................................................................................................... 27 6.1. Datos del problema ............................................................................................................ 27 6.2. Evaluación numérica .......................................................................................................... 28 VIII 6.2.1. Evaluación numérica Cmax ....................................................................................... 30 6.2.2. Evaluación numérica ∑Cj .......................................................................................... 33 7. Conclusión .................................................................................................................................. 36 8. Bibliografía ................................................................................................................................. 37 9. Anexos ........................................................................................................................................ 38 9.1. Familia Wagner .................................................................................................................. 38 9.1.1. Modelo WST.............................................................................................................. 38 9.1.2. Modelo Wilson .......................................................................................................... 43 9.1.3. Modelo TS2 ............................................................................................................... 49 9.1.4. Modelo TBA .............................................................................................................. 54 9.1.5. Modelo TS3 ............................................................................................................... 60 9.2. Familia Manne ................................................................................................................... 69 9.2.1. Modelo SGST ............................................................................................................ 70 9.2.2. Modelo LYeq ............................................................................................................. 74 9.3. Archivo BATCH ................................................................................................................ 79 IX Índice de figuras Figura 1: Ejemplo diagrama de Gantt ........................................................................................... 5 Figura 2: Ejemplo cadena de frío .................................................................................................. 7 Figura 3: Modelo general maximizar MILP................................................................................ 12 Figura 4: Ejemplo del formato LP en Gurobi.............................................................................. 15 Figura 5: Código del archivo .bat ................................................................................................ 16 Figura 6: Datos de archivo de ejemplo ........................................................................................ 27 6 2. Objeto del proyecto 2.1. Objeto del proyecto El objetivo del proyecto, consiste en darle una solución óptima a los problemas de producción en los que se tienen varias máquinas que trabajan en serie y cuyas tareas no pueden esperar en un buffer hasta que termine la tarea que les precede. En este proyecto, se van a analizar siete modelos de programación lineal generales en los que se trabaja en un entorno flowshop con permutación para el cálculo del makespan. Una vez estudiados y analizados estos modelos provenientes de dos familias de modelos diferentes en los que cambia el enfoque del modelo y el uso de las variables, se procederá a adaptar y moldear esos modelos a la restricción no-wait que es la que nos ocupa en este proyecto y ver cómo se comportan y los resultados que se obtienen al comprobarlos con varias baterías de datos. Para ello, se han analizado, estudiado y resuelto todos los modelos comprendiendo y entendiendo todas las variables y restricciones de los modelos, así como las funciones objetivo. Tras ello, en algunos casos, se han tenido que modificar algunas restricciones, en otros casos, ha bastado con añadir o eliminar alguna restricción, todo ello para adaptarlos a la restricción general del problema que es no-wait. 2.2. Justificación Este proyecto, cuyo fin es analítico, trata de resolver un problema muy común y presente en una gran variedad de empresas como es el hecho de que los productos no puedan o deban esperar en un buffer una vez empiece su proceso de fabricación. Esto suele ser muy común en empresas del sector químico y farmacéutico debido a la importancia de mantener una serie de condiciones de presión y temperaturas constantes a lo largo de los procesos, así como en el sector farmacéutico donde mantener los medicamentos en unas condiciones óptimas de luz y temperatura garantiza en todo momento la inmunogenicidad y eficacia de estos; en el sector del acero, por también tener que mantener los productos a cierta temperatura durante su tratamiento para mantener o variar las propiedades del acero. 7 Finalmente, se encuentra uno de los sectores de mayor importancia como es el sector alimenticio, donde la manutención de las cadenas de frío de los alimentos se revela de vital importancia para evitar que estos se pongan malos y haya que desecharlos o en los que puedan aparecer bacterias o virus y que deriven en enfermedades. Además, una vez se rompe la cadena de frío de los alimentos en algún momento, ya no hay vuelta atrás y estos quedan inservibles. Figura 2: Ejemplo cadena de frío [Fuente: https://gpslogistica.com/services/cadena-de-frio/] 8 3. Modelos de programación lineal de las familias Wagner y Manne para el permutation flowshop clásico 3.1. Introducción En esta sección, se van a presentar los modelos de programación lineal de las familias Wagner y Manne para el problema de flowshop con permutación clásico desarrollados en Stafford Jr et al. (2005) y Tseng y Stafford Jr. (2008), es decir, el problema genérico a partir del cual se adaptarán los modelos al problema bajo consideración en este documento, un problema de flowshop con la restricción global nowait que conlleva permutación, sirviéndome de ayuda los libros de Pinedo (2011) y Framiñán et al. (2014). 3.2. Descripción de los modelos y sus variables Los modelos que se van a utilizar este documento, tienen como función objetivo el makespan, Cmax y serán adaptados a la misma función objetivo Cmax y SumCj. 3.2.1. Familia Wagner En primer lugar, se estudiaran los modelos de la familia Wagner, en este caso, el primer modelo es el modelo “WST” y tras analizar todas las restricciones de las que se compone el modelo, se ha podido comprobar que este primer modelo se basa en cuatro variables fundamentales, que son: Tri, que normalmente se escribe como una matriz de M máquinas por N trabajos y que se define como los tiempos de proceso de cada trabajo i en la máquina r; la variable Zij, se trata una variable binaria que vale 1 si el trabajo i está asignado a la posición j de la secuencia o 0 en cualquier otro caso; Xr,j, que se define como, el tiempo ocioso de la máquina r antes de que empiece el trabajo en la posición j de la secuencia e Yr,j, el tiempo de espera del trabajo de la posición j en la secuencia después de que haya sido procesado en la máquina r. 9 VARIABLES SIGNIFICADO Tri Tiempos de proceso del trabajo i en la máquina r Zij Variable binaria; 1 si el trabajo i está en la posición j; 0 eoc Xrj Tiempo ocioso en la máquina r antes de que empiece el trabajo en la posición j Yrj Tiempo de espera del trabajo en la posición j después de que acabe de procesarse en la máquina r Tabla 1: Resumen variables modelo WST En segundo lugar, otro modelo de la familia Wagner es el modelo “WILSON” que en este caso se basa en tres variables que son: Tri y Zij, definidas en el modelo anterior ya que tienen el mismo significado al ser de la misma familia y ejercen la misma función y la variable Brj, que se define como, el tiempo de comienzo del trabajo en la posición j de la secuencia en la máquina r. VARIABLES SIGNIFICADO Tri Tiempos de proceso del trabajo i en la máquina r Zij Variable binaria; 1 si el trabajo i está en la posición j; 0 eoc Brj Tiempos de comienzo del trabajo en la posición j en la máquina r Tabla 2: Resumen variables modelo Wilson En tercer lugar, analizamos el último modelo de la familia Wagner que es el modelo “TS2” que se basa en tres variables como son: Tri y Zij, definidas en el primer modelo ya que tienen el mismo significado al ser de la misma familia y ejercen la misma función y en la variable Erj, definida como, el tiempo de terminación del trabajo en la posición j de la secuencia en la máquina r. Tabla 3: Resumen variables modelo TS2 VARIABLES SIGNIFICADO Tri Tiempos de proceso del trabajo i en la máquina r Zij Variable binaria; 1, si el trabajo i está en la posición j; 0, eoc Erj Tiempo de terminación del trabajo en la posición j 10 3.2.2. Familia Manne A continuación, en cuarto lugar, pasamos a los modelos de la familia Manne, concretamente al modelo “SGST”, cuyas principales variables son: Cri, que se define como, el tiempo de procesado del trabajo i en la máquina r; Tri, tiempos de proceso de cada trabajo i en la máquina r; Dik, que se trata de una variable binaria que vale 1 si el trabajo i está programado en cualquier momento que el trabajo k o 0 en cualquier otro caso y P, una constante cuyo valor ha de ser bastante grande aunque también se suele calcular como la suma de todos los tiempos de proceso de todos los trabajos en todas las máquinas. VARIABLES SIGNIFICADO Tri Tiempos de proceso del trabajo i en la máquina r Dik Variables binaria; 1, si el trabajo i está programado antes que el k Cri Tiempo de finalización del trabajo i en la máquina r P Constante de valor igual a la suma de todos los tiempos de proceso Tabla 4: Resumen variables modelo SGST Finalmente, en quinto lugar, el otro modelo de la familia Manne a tratar es el modelo “Lyeq”. Este modelo al ser ambos de la familia Manne comparten algunas variables como son: Cri, Tri y la constante P. Además, se caracteriza por el uso de Qrik, una variable que sirve para evaluar el hecho de que un gran problema con muchas máquinas y trabajos puede ser resuelto en cualquier ordenador por conseguir agrupar dos restricciones en una sola variable. VARIABLES SIGNIFICADO Tri Tiempos de proceso del trabajo i en la máquina r Dik Variables binaria; 1, si el trabajo i está programado antes que el k Cri Tiempo de finalización del trabajo i en la máquina r Qrik Variables que recoge la agrupación de varias restricciones en una P Constante de valor igual a la suma de todos los tiempos de proceso Tabla 5: Resumen variables modelo LYeq 11 3.2.3. Modelo adicionales familia Wagner Por otra parte, como trabajo adicional, se van a analizar dos nuevos modelos derivados de la familia Wagner usando la técnica JALM, (job-adjacency and machinelinkage), trabajos adyacentes y vinculación de las máquinas, usado por primera vez por Tseng y Stafford (2001) para referirse a una serie de restricciones en uno de los modelos MILP para el problema de flowshop SDST, (sequence-dependent setup times), tiempos de setup dependientes de la secuencia. Estos dos modelos se caracterizan por aunar la mayor parte de las restricciones en una sola simplificando en una gran medida los tiempos de análisis de los modelos. El primer modelo que se va a tratar de los modelos derivados de la familia Wagner es el modelo “TBA”, este modelo se basa principalmente en tres variables las cuales ya conocemos sus significados expuestos en los modelos anteriores, principalmente en el modelo “WST” estas variables son: Xr,j, Tri y Zij. VARIABLES SIGNIFICADO Tri Tiempos de proceso del trabajo i en la máquina r Zij Variable binaria; 1 si el trabajo i está en la posición j; 0 eoc Xrj Tiempo ocioso en la máquina r antes de que empiece el trabajo en la posición j Tabla 6: Resumen variables modelo TBA El segundo y último modelo que se va a tratar en este proyecto, es el modelo “TS3”, este modelo se basa al igual que el modelo anterior en tres variables donde coinciden en las variables Tri y Zij y la variable Yr,j, también explicadas anteriormente en el modelo “WST”. VARIABLES SIGNIFICADO Tri Tiempos de proceso del trabajo i en la máquina r Zij Variable binaria; 1 si el trabajo i está en la posición j; 0 eoc Yrj Tiempo de espera del trabajo en la posición j después de que acabe de procesarse en la máquina r Tabla 7: Resumen variables modelo TS3 12 4. Herramientas y metodologías utilizadas 4.1. MILP La metodología que se va a utilizar en este caso son los modelos de programación linela entera MILP (mixed-integer linear programming). 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. La metodología MILP se caracteriza por tener la siguiente estructura: Esta estructura, se compone en primer lugar, de un primer término donde se indica si se trata de un problema de maximizar, por ejemplo, los beneficios, o en su defecto, minimizar, por ejemplo, los costes. Junto a este término, aparece representado por “cTx” la función objetivo en cuestión la cual se quiere maximizar o minimizar. La variable “x”, representa todas las variables que forman parte del modelo de forma genérica, mientras que el término “c” son los coeficientes asociados a las variables en la función objetivo, estos costes, se llaman también costes relativos. En la siguiente línea, aparece el término “subject to”, que significa ‘‘sujeto a’’ e indica que a continuación van a aparecer todas las restricciones que forman parte del modelo. Estas restricciones se representan de la forma “Ax < = > b”, donde “A” representa la matriz de coeficientes tecnológicos del modeo, es decir, los coeficientes de las variables que forman las restricciones del modelo; “x”, representa las variables del modelo y “b”, los términos independientes de las restricciones. Además, las restricciones se pueden escribir con cualquier restricción de signo (<, =, >, ≤, ≥). Finalmente, el modelo se cierra acotando los límites de las variables indicando si estas son mayores o iguales que cero, variables libres o binarias. Figura 3: Modelo general maximizar MILP [Fuente: https://en.wikipedia.org/wiki/Integer_programming] 13 4.2. CodeBlocks y C El programa que se utilizará para aplicar esta metodología MILP es CodeBlocks en el que se utilizará el lenguaje de programación C/C++. Se trata de un sistema de compilación personalizado que se creó orientado hacia los lenguajes C, C++ y Fortran y que funciona con un conjunto de compiladores de software libre. Aunque en este proyecto, solo se utilizará el lenguaje C. Además, este programa tiene la posibilidad de hacer uso de librerías, que como su propio nombre indica son librerías de funciones ya creadas y definidas de las que se puede hacer uso en cualquier momento para facilitar y simplificar la creación de los códigos. Por ejemplo, una función que se utilizará en este proyecto, es la función <schedule_lib.h> especialmente diseñada para el scheduling (programación de operaciones) y que una de las funciones que trae, por ejemplo, es la función “loadPTimes_nrows” que sirve para leer los tiempos de proceso de una matriz de n filas. En este programa, se desarrollarán los catorce modelos de programación (siete modelos por dos funciones objetivo cada uno) de modo que estos códigos generen un archivo .txt con el modelo enteramente desarrollado en el que deberá aparecer la función objetivo en cuestión, las restricciones, los límites de las variables y todas las variables que formen parte del modelo definidas, este archivo .txt, estará escrito en formato LP “.lp”, linear programming - programación lineal, este formato LP es el que necesita Gurobi, programa de evaluación computacional que resuelve los modelos proporcionándonos la solución óptima del modelo al pasarle una batería de datos, para poder leer y analizar los modelos codificados en C en CodeBlocks. El lenguaje C/C++ es uno de los lenguajes más utilizados en programación. A continuación, se explicarán los comandos más importantes que se usarán en el desarrollo del código de los modelos. Estos comandos son: COMANDO SIGNIFICADO fprintf Sirve para escribir en un fichero de texto fscanf Sirve para leer dentro de un fichero for Sirve para hacer bucle if/else Sirve para comparar dos índices int Sirve para declarar variables enteras char Sirve para declarar cadenas de caracteres FILE Sirve para indicar al programa el fichero que se está usando 14 sprintf Sirve para escribir en una cadena de caracteres DIM_MAT_INT Sirve para establecer la dimensión de una matriz de números enteros fclose Sirve para cerrar un fichero Tabla 8: Resumen de los comandos más usados en C De esta forma con el comando fprintf podemos escribir el código dentro de un archivo de texto para su posterior lectura. Su modo de funcionamiento es el siguiente: fprintf (nombre del fichero,”cadena de caracteres a escribir en el fichero”, índices) Por ejemplo: int n=5; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if (j=n) { fprintf(ejemplo,”X_%d_%d + Y_%d_%d + ”,i,j); } else { fprintf(ejemplo,”X_%d_%d + Y_%d_%d = 0 ”,i,j); } } } Esto hace que en el fichero ‘ejemplo’ se escriba: “X11 + Y11 + X12 + Y12 + … = 0” hasta que los índices i y j lleguen al valor N, en este caso 5. De esta forma se escribirán todas las restricciones de los modelos junto con su función objetivo en un fichero de texto para que posteriormente pueda ser resuelto por Gurobi. 15 4.3. Gurobi En este proyecto, al trabajar con el programa de optimización Gurobi, se necesita un formato muy concreto para leer y analizar los modelos y resolverlos, detallado en la propia página de la guía de gurobi donde se explica el uso de este formato ver “Formato LP en Gurobi”. Este formato, antes mencionado, se denomina Linear Programming (programación lineal) y su extensión es el .lp. Son pequeñas diferencias las que difieren entre el modelo general y el formato LP pero necesarias para su correcta lectura por parte de Gurobi, que se muestran en el siguiente ejemplo: Una vez adaptados todas las restricciones de los modelos a la restricción global y escritas las dos funciones objetivo en cada modelo con sus variables correspondientes, al código en C se le pasa una batería de datos, también en formato .txt, en la que aparecen el número de máquinas, el número de trabajos y los tiempos de proceso de cada trabajo en cada máquina de cada instancia. Con estos datos y el código en C que genera el archivo .lp, se le pasa a Gurobi con un comando y éste te resuelve el modelo dándote como resultado la solución óptima del problema en cuestión. 4.4. Batch y Registro Por otra parte, se va a hacer uso del lenguaje BATCH, que se trata de un archivo de procesamiento por lotes. Se trata de archivos de texto con extensión .bat que contienen un conjunto de instrucciones MS-DOS (Sistema Operativo de disco de Microsoft) permitiendo automatizar varias tareas como se detalla en el blog Comando FOR para archivos BAT (2012) de la página blogspot del profesor Emilio Barco. Este archivo se Figura 4: Ejemplo del formato LP en Gurobi [Fuente: https://www.gurobi.com/documentation/8.0/refman/lp_format.html] 22 ese trabajo en la primera máquina. La segunda restricción, establece que el instante de terminación de un trabajo en una máquina menos ese instante en la máquina anterior tiene que ser mayor o igual al tiempo de proceso de ese trabajo en la primera máquina mencionada. La tercera restricción, establece que el instante de terminación de un trabajo menos el instante de terminación del trabajo que le sigue más la multiplicación de una constante de valor la suma de todos los tiempos de proceso de todos los trabajos en todas las máquinas por una variable binaria que vale 1 si el trabajo i está antes que el trabajo j y 0 en cualquier otro caso tiene que ser mayor o igual que el tiempo de proceso del primer trabajo en esa máquina. La cuarta restricción, es igual que la tercera, pero cambiando el orden de los índices i y k y por ello el tercer término es 1 menos la variable binaria. La quinta restricción, establece simplemente que el mayor instante de finalización tiene que ser mayor o igual que el instante de finalización de cada uno de los trabajos de la última máquina. A la hora de adaptar el modelo a la restricción global no-wait, nos centramos en la segunda restricción de tal forma que, cambiamos el signo de la restricción de ‘≥’ a ‘=’ para que el tiempo de terminación de un trabajo en una máquina menos el tiempo de terminación de ese mismo trabajo en la máquina anterior sea igual al tiempo de proceso de ese trabajo en la máquina siguiente. De esta forma, la segunda restricción queda de la siguiente manera: Para el modelo SGST, la función objetivo adaptada para ∑Cj quedaría de la siguiente forma: 1, 1, (1 1;1 ) (2) r i ri r i C C T r M i N          1 min N Mi i SumCj C   23 El modelo LYeq de la familia Manne se caracteriza por basar sus restricciones en la variable C al igual que el modelo anterior y la variable Q, que representa la combinación de una pareja de restricciones. Por lo tanto, el modelo general se representa por: En este modelo, como pasó con la familia anterior, al ser también de la misma familia comparten varias restricciones, en este caso, son las restricciones (3), (4) y (5) que coinciden con las restricciones (1), (2) y (5) del modelo anterior. La primera restricción, establece que la multiplicación de la constante P por la variable binaria más el instante de terminación del trabajo i en una máquina menos su tiempo de proceso y menos el instante de terminación del trabajo que le sigue en la misma máquina tiene que ser igual que la variable Qrik que representa la unión de varias restricciones en una. La segunda restricción, establece que la variable Qrik tiene que ser mayor o igual que la constante P menos el tiempo de proceso de un trabajo en una máquina menos el tiempo de proceso del trabajo que le sigue en la misma máquina. En la adaptación del modelo LYeq, se procede igual que con el modelo anterior SGST, ya que la adaptación consiste en modificar la misma restricción, aunque en este caso sea el número 4 pero consiste en cambiar el signo ‘≥’ por ‘=’ por la misma razón que en el modelo anterior. Con lo cual, quedaría de la siguiente manera: Si la adaptación de las restricciones es la misma en los dos modelos, lo mismo pasa con la función objetivo ∑Cj, con lo que la función objetivo queda de la siguiente forma: 11 1, 1, min . : (1 ;1 ) (1) (1 ;1 ) (2) (1 ) (3) (1 1;1 ) (4) (1 ) (5) MAX MAX ik ri rk ri rik rik ri rk ii r i ri r i MAX Mi makespan F C s a PD C C T Q r M i k N Q P T T r M i k N C T i N C C T r M i N C C i N                                 1, 1, (1 1;1 ) (4) r i ri r i C C T r M i N          1 min N Mi i SumCj C   24 5.3. Modelos adicionales familia Wagner El modelo TBA de la familia Wagner se caracteriza por aunar las restricciones más características del modelo en una sola utilizando principalmente los tiempos de proceso y la variable X, que representa los tiempos ociosos de las máquinas. Con lo que el modelo queda de la siguiente forma: En la adaptación de las restricciones del modelo TBA a la restricción general no-wait, nos encontramos con que este modelo tienes menos restricciones sobre las que trabajar que los modelos anteriores, este hecho, puede hacer que su adaptación tenga mayor o menor dificultad, aunque una vez estudiadas y analizadas las 4 restricciones, se puede comprobar que en las dos primeras no se puede hacer nada, mientras que a simple vista por definición de la variable X que la última restricción solo debería afectar al primer trabajo de la primera máquina y no a todos; mientras que en la tercera restricción basta con hacer que sea igual a cero. De tal forma que las dos restricciones quedarían de la siguiente forma: 1 1 1 1 1 2 1 1 1 1, 1 1, 1, 1, 1 1 1 2 1 1 min makespan = F . : 1 (1 ) (1) 1 (1 ) (2) ( ) ( ) 0(2 ;2 )(3) 0 (2 M N N N MAX pi i Mi Ms p i i s N ij j N ij i jj N N N r i i ri r i iq rs r s r i ij i q i s i j T Z T X s a Z i N Z j N T Z T T Z X X T Z r M j N X                                                ) (4)jN 1 1, 1 1, 1, 1, 1 1 1 2 1 11 ( ) ( ) 0(2 ;2 )(3) 0 (2 ) (4 ) jj N N N r i i ri r i iq rs r s r i ij i q i s i T Z T T Z X X T Z r M j N X j N                              25 Debido a la gran semejanza entre este modelo y el primer modelo, el modelo WST, se ha comprobado que a lo hora de escribir la función objetivo para ‘SumCj’, resulta ser la misma función debido a las variables que comparten. Por ello, la función objetivo quedaría de la siguiente manera: El modelo TS3 de la familia Wagner se caracteriza al igual que el modelo anterior por aunar las restricciones más características del modelo en una sola pero esta vez, en vez de usar la variable X, se utiliza la variable Y, que representa los tiempos de espera de los trabajos en las máquinas. Por lo tanto, el modelo general quedaría de la siguiente forma: Finalmente, llegamos a la adaptación del último modelo del proyecto, el cual llega a ser el más difícil de modelar debido a las variables propias del modelo ya que únicamente se compone de los tiempos de proceso de los trabajos en las máquinas y de los tiempos de espera de los trabajos. Además, para mayor dificultad, sabemos que por definición de la variable Y que es a la que están asignados los tiempos de espera de los trabajos en las máquinas tiene que ser igual a cero para adecuar las restricciones a la restricción global no-wait (sin esperas), con lo cual nos quedamos únicamente con la variable T, es decir, los tiempos de proceso de los trabajos en las máquinas. Con ello el modelo no se podría resolver porque nos faltarían datos de modo que lo que se ha hecho ha sido modificar el significado de la variable Yq para que, en vez de mostrarnos el tiempo de espera entre un mismo trabajo entre varias máquinas, nos muestre el tiempo de espera entre los trabajos de la primera máquina. Con lo cual, al hacer este cambio, se ha tenido que cambiar 1 1 1 2 1 1 1 1 11 1 , 1 , 1 , 1 , 1 1 1 1 1 1 1 min makespan = F . : 1 (1 ) (1) 1 (1 ) (2) ( ) ( ) 0 (2 ;2 )(3) 0 N M N M MAX p qi iN qN p q i q N ij j N ij i N N r N r i i j ri i j qi ij i j qj q j i i q i q r T T Z Y s a Z i N Z j N T Z T Z T Z Z Y Y r M j N Y                                               (1 1) (4)rM   1 1 1 min ( 1) ( 1) N N N Mj Mi ij j j i SumCj n j X n j T Z            26 también la función objetivo del modelo adaptándola al nuevo significado de la variable Yq. Y con ello, desaparece la ecuación (4). 1 1 2 1 2 min makespan = F N M N N MAX p qi iN q p q i q T T Z Y           1 1 , 1 , 1 , 1 1 1 1 1 1 2 ( ) ( ) 0 (2 ;2 )(3) j N N r N i i j ri i j qi ij i j q q i i q i q T Z T Z T Z Z Y Y r M j N                          Por último, la función objetivo ∑Cj con la modificación de la variable Yq quedaría de la siguiente manera: 1 2 1 2 2 1 1 min ( 1) ( 1) M N N N N N qi i ij q i j q j i SumCj T n j Yq n j T Z                 27 6. Evaluación computacional 6.1. Datos del problema Este proyecto, se basa en unos modelos generales de programación lineal para un entorno de flowshop con permutación para la función objetivo Cmax y la función objetivo ∑Cj. Estos modelos descritos en los documentos mencionados en la sección 3.2, descripción del modelo y sus variables, son la base del proyecto sobre la que se trabajará. Además, para posteriormente comprobar todas las adaptaciones de los modelos, se utilizarán una serie de instancias de datos que van desde 5 a 20 trabajo y desde 2 a 5 máquinas. Estas instancias de datos vienen recogidas en ficheros de texto de tal manera que se leen así (ver figura) donde el primer término ‘3’ es el número de máquinas, ‘4’ es el número de trabajos y la matriz que le sigue son los tiempos de proceso de cada trabajo en cada máquina. Figura 6: Datos de archivo de ejemplo 28 6.2. Evaluación numérica En este punto, se analizarán y evaluarán los resultados computacionales de los modelos ya adaptados descritos previamente en el punto anterior para comprobar numéricamente si realmente están bien adaptados a la restricción general no-wait o existe algún fallo en algunas restricciones o alguna función objetivo no funciona como debiera. Para ello, primero se comprobaron todos los modelos con un pequeño ejemplo previo que consistía en establecer 3 máquinas (m=3) y 4 trabajos (n=4) y cuya matriz de tiempos de procesos es: Tabla 9: Matriz de tiempos de proceso del ejemplo Con estos datos de ejemplo, se comprobaron previamente (con la ayuda del Excel y de los diagramas de Gantt) cuales eran las secuencias óptimas del problema y los valores de la función objetivo Cmax (makespan) y ∑Cj óptimos de los modelos, dando como resultado las siguientes secuencias óptimas que dan lugar a las soluciones del problema (ver tabla 10): [1-3-2-4], [1-4-3-2], [3-2-1-4] y [4-1-3-2], a partir de estas secuencias óptimas, se obtienen también los resultados de las funciones objetivo. Por una parte, tenemos la función objetivo Cmax o makespan cuyo resultado o valor óptimo es 16, que quiere decir, que el menor tiempo en el que puede terminar de procesarse el último trabajo en la última máquina es 16, y, por otra parte, tenemos la función objetivo ∑Cj cuyo resultado o valor óptimo es 48, es decir, que el conjunto de los 4 trabajos, en este caso, no acabaran nunca de procesarse en la última máquina antes de las 48 unidades de tiempo dadas como solución. A continuación, se presentan los 4 diagramas de Gantt que representan las 4 secuencias óptimas asociadas a los datos concretos y a las funciones objetivo propuestas. m/n 1 2 3 4 1 3 4 2 3 2 2 3 3 2 3 3 1 3 2 29 Tras mostrar estos ejemplos, se procede a reanalizar todos los modelos con una batería de datos para diferentes números de trabajos y de máquinas. Esta batería de datos consiste en 160 instancias o ficheros con máquinas que van de 2 a 5 y los trabajos de 5 a 20. A continuación, se presentan los resultados del análisis de las 160 instancias en cada uno de los modelos y de sus variantes (cuando se habla de variantes, se habla de que la función objetivo principal es el makespan y que, por lo tanto, su variante es el ∑Cj). En este análisis, se han recogido los datos correspondientes a los tiempos de computación de cada modelo para cada tamaño de problema, los valores de las funciones objetivo y los casos en los que el modelo no llega a encontrar el óptimo en el tiempo límite establecido, que era de 600 segundos. Trabajo 1: Trabajo 2: Trabajo 3: Trabajo 4: M1 Secuencia: 1324 M2 Cmax = 16 SumCj = 48 M3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 M1 Secuencia: 1432 M2 Cmax = 16 SumCj = 48 M3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 M1 Secuencia: 3214 M2 Cmax = 16 SumCj = 48 M3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 M1 Secuencia: 4132 M2 Cmax = 16 SumCj = 48 M3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Tabla 10: Diagramas de Gantt del ejemplo 30 6.2.1. Evaluación numérica Cmax En primer lugar, analizaremos los casos en los que los modelos no te dicen cuál es el óptimo del problema por llegar al límite de tiempo. En este caso, definiremos #O, como el número de veces en las que el modelo encuentra el óptimo para cada tamaño de problema (siendo 0 el mínimo y 10 el máximo, al haber 10 instancias por cada bloque); #F, es el número de veces en las que el modelo encuentra una solución, es decir, es factible, pero no sabe si es o no la óptima al alcanzar el límite de tiempo de 600 segundos; y #N, es el número de veces en las que el modelo no es capaz de encontrar una solución al problema. Como se puede apreciar en la tabla de la que se pueden sacar varias conclusiones, vemos que los modelos de la familia Wagner, tienen mayor facilidad de encontrar el óptimo del problema si se trata de la función objetivo Cmax; por otra parte, a los modelos de la familia Manne le pasa lo contrario y es que estos dos modelos son especialmente lentos ya que no llegan a encontrar el óptimo en ningún caso cuando se llegan a analizar 20 trabajos. Además, podemos comprobar que todos los modelos como es lógico siempre encuentran el óptimo en los problemas pequeños de pocos trabajos y pocas máquinas mientras que cuando nos vamos a 15 o 20 trabajos y 4 o 5 máquinas ya les cuesta más al tener que realizar muchas más iteraciones. Finalmente, podemos comprobar que los mejores modelos son los modelos WST y TS3, ambos de la familia Wagner. Tabla 11: Análisis de resultados de la función objetivo Cmax 31 En segundo lugar, analizaremos los tiempos de computación de los modelos, es decir, lo que tarda cada modelo en analizar todas las instancias de datos agrupadas por número de máquinas y trabajos. Como se ve en la tabla, podemos apreciar los tiempos de proceso de todos los modelos para todos los bloques de instancias y vemos que al igual que se mencionó anteriormente, los modelos WST y TS3 son los mejores en este apartado y son los que menos tardan en procesar todas las instancias de media, recalcando que el modelo TS3 el ligeramente más rápido que el modelo WST. Finalmente, en tercer lugar, se calculará el valor de ARPD (Average Relative Percentage Deviation) para todos los modelos, análisis de las desviaciones medias relativas de los porcentajes, es decir, se analizarán los valores de las funciones objetivo de cada modelo en cada instancia comparando el valor de la función objetivo de un modelo con el valor mínimo que ha obtenido otro modelo o él mismo en esa instancia (se compara con el mínimo ya que el problema es de minimizar, por lo tanto, si el problema fuera de maximizar, se compararía con el máximo). Tabla 12: Tiempos de computación en la función objetivo Cmax 38 9. Anexos En este anexo, se detallan los códigos en C y el archivo BATCH utilizados en el desarrollo del estudio. Para cada modelo, se muestra el código general para la función objetivo Cmax o makespan y aparte, se muestra el código únicamente de la función objetivo ∑Cj para no volver a escribir el resto del modelo ya que es el mismo, con lo que el modelo es el mismo y lo único que cambia son las dos funciones objetivo. 9.1. Familia Wagner 9.1.1. Modelo WST 9.1.1.1. Modelo general y FO: Cmax #include <stdio.h> #include <stdlib.h> #include <schedule_lib.h> //The WST model void modeloWST(int n, int m, MAT_INT Tri, FILE *fichero2); int main() { printf("The WST model\n"); int i,j,k,m,n; int cont=0; char cadena[50]={0}; char cadena2[50]={0}; for (j=5;j<=20;) { for (k=2;k<=5;k++) { for (i=1;i<=10;i++) { sprintf(cadena,"Bateria Sin fechas/inst_%d_%d_p_%d",j,k,i); FILE * fichero = fopen(cadena,"r"); fscanf(fichero,"%d %d",&m,&n); printf("El numero de maquinas es: %d \n",m); printf("El numero de trabajos es: %d \n",n); sprintf(cadena2,"modelos/WSTmodel_%d_%d_%d.lp",j,k,i); FILE * fichero2=fopen(cadena2,"w"); 39 MAT_INT Tri = DIM_MAT_INT(m,n); Tri=loadPTimes_nrows(cadena,&n,&m,YES); modeloWST(n,m,Tri,fichero2); fclose(fichero); fclose(fichero2); fflush(stdin); cont=cont+1; } } j=j+5; } return cont; } void modeloWST (int n, int m, MAT_INT Tri, FILE *fichero2) { int i,j,r,p; //fprintf(fichero2,"Funcion objetivo CMAX \n"); fprintf(fichero2,"Minimize \n"); for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"T_%d_%d + ",m,i); } else { fprintf(fichero2,"T_%d_%d + ",m,i); } } for (p=1;p<=n;p++) { if(p<n) { fprintf(fichero2,"X_%d_%d + ",m,p); } else { 40 fprintf(fichero2,"X_%d_%d \n",m,p); } } //RESTRICCIONES DEL MODELO fprintf(fichero2,"Subject To \n"); //fprintf(fichero2,"Primera restriccion \n"); for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if (j<n) { fprintf(fichero2,"Z_%d_%d + ",i,j); } else { fprintf(fichero2,"Z_%d_%d = 1 \n",i,j); } } } //fprintf(fichero2,"Segunda restriccion \n"); for (j=1;j<=n;j++) { for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"Z_%d_%d + ",i,j); } else { fprintf(fichero2,"Z_%d_%d = 1 \n",i,j); } } } //fprintf(fichero2,"Tercera restriccion \n"); for (r=1;r<=m-1;r++) 41 { for (j=1;j<=n-1;j++) { for (i=1;i<=n;i++) { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] + ",r,i,i,j+1); } fprintf(fichero2,"X_%d_%d - ",r,j+1); for (i=1;i<=n;i++) { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] - ",r+1,i,i,j); } fprintf(fichero2,"X_%d_%d = 0 \n",r+1,j+1); } } //fprintf(fichero2,"Cuarta restriccion \n"); for (r=1;r<=m-1;r++) { fprintf(fichero2,"X_%d_1 - ",r+1); fprintf(fichero2,"X_%d_1 - ",r); for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"[ T_%d_%d * Z_%d_1 ] - ",r,i,i); } else { fprintf(fichero2,"[ T_%d_%d * Z_%d_1 ] = 0 \n",r,i,i); } } } //Tiempos de proceso for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { 42 fprintf(fichero2,"T_%d_%d = %d \n",r,i,Tri[r-1][i-1]); } } fprintf(fichero2,"X_1_1 = 0 \n"); //ACOTACIONES fprintf(fichero2,"Bounds \n"); for (i=1;i<=m-1;i++) { for (j=1;j<=n;j++) { fprintf(fichero2,"X_%d_%d >= 0 \n",i,j); } } //VARIABLES fprintf(fichero2,"Generals \n"); for (i=1;i<=m-1;i++) { for (j=1;j<=n;j++) { fprintf(fichero2,"X_%d_%d \n",i,j); } } fprintf(fichero2,"Binary \n"); for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { fprintf(fichero2,"Z_%d_%d \n",i,j); } } //FIN fprintf(fichero2,"End"); } 9.1.1.2.FO: ∑Cj //fprintf(fichero2,"Funcion objetivo SUMCj \n"); fprintf(fichero2,"Minimize \n"); for (j=1;j<=n;j++) 43 { fprintf(fichero2,"%d X_%d_%d + ",n-j+1,m,j); } for (j=1;j<=n;j++) { for (i=1;i<=n;i++) { if (i==n && j==n) { fprintf(fichero2,"[ %d T_%d_%d * Z_%d_%d ] \n",n-j+1,m,i,i,j); } else { fprintf(fichero2,"[ %d T_%d_%d * Z_%d_%d ] + ",n-j+1,m,i,i,j); } } } 9.1.2. Modelo Wilson 9.1.2.1. Modelo general y FO: Cmax #include <stdio.h> #include <stdlib.h> #include <schedule_lib.h> //The Wilson model void modeloWilson (int n, int m, MAT_INT Tri, FILE *fichero2); int main() { printf("The Wilson model\n"); int i,j,k,m,n; int cont=0; char cadena[50]={0}; char cadena2[50]={0}; for (j=5;j<=20;) { for (k=2;k<=5;k++) { for (i=1;i<=10;i++) 44 { sprintf(cadena,"Bateria Sin fechas/inst_%d_%d_p_%d",j,k,i); FILE * fichero = fopen(cadena,"r"); fscanf(fichero,"%d %d",&m,&n); printf("El numero de maquinas es: %d \n",m); printf("El numero de trabajos es: %d \n",n); sprintf(cadena2,"modelos/Wilsonmodel_%d_%d_%d.lp",j,k,i); FILE * fichero2=fopen(cadena2,"w"); MAT_INT Tri = DIM_MAT_INT(m,n); Tri=loadPTimes_nrows(cadena,&n,&m,YES); modeloWilson(n,m,Tri,fichero2); fclose(fichero); fclose(fichero2); fflush(stdin); cont=cont+1; } } j=j+5; } return cont; } void modeloWilson(int n, int m, MAT_INT Tri, FILE *fichero2) { int i,j,r; //fprintf(fichero2,"Funcion objetivo CMAX \n"); fprintf(fichero2,"Minimize \n"); fprintf(fichero2,"B_%d_%d + ",m,n); for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] + ",m,i,i,n); } else { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] \n",m,i,i,n); } 45 } //RESTRICCIONES DEL MODELO fprintf(fichero2,"Subject To \n"); //fprintf(fichero2,"Primera restriccion \n"); for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if (j<n) { fprintf(fichero2,"Z_%d_%d + ",i,j); } else { fprintf(fichero2,"Z_%d_%d = 1 \n",i,j); } } } //fprintf(fichero2,"Segunda restriccion \n"); for (j=1;j<=n;j++) { for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"Z_%d_%d + ",i,j); } else { fprintf(fichero2,"Z_%d_%d = 1 \n",i,j); } } } //fprintf(fichero2,"Tercera restriccion \n"); for (j=1;j<=n-1;j++) { fprintf(fichero2,"B_1_%d + ",j); 46 for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"[ T_1_%d * Z_%d_%d ] + ",i,i,j); } else { fprintf(fichero2,"[ T_1_%d * Z_%d_%d ] - ",i,i,j); } } fprintf(fichero2,"B_1_%d <= 0 \n",j+1); } //fprintf(fichero2,"Cuarta restriccion \n"); fprintf(fichero2,"B_1_1 = 0 \n"); //fprintf(fichero2,"Quinta restriccion \n"); for (r=1;r<=m-1;r++) { fprintf(fichero2,"B_%d_1 + ",r); for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"[ T_%d_%d * Z_%d_1 ] + ",r,i,i); } else { fprintf(fichero2,"[ T_%d_%d * Z_%d_1 ] - ",r,i,i); } } fprintf(fichero2,"B_%d_1 = 0 \n",r+1); } //fprintf(fichero2,"Sexta restriccion \n"); for (r=1;r<=m-1;r++) { for (j=2;j<=n;j++) { 47 fprintf(fichero2,"B_%d_%d + ",r,j); for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] + ",r,i,i,j); } else { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] - ",r,i,i,j); } } fprintf(fichero2,"B_%d_%d = 0 \n",r+1,j); } } //fprintf(fichero2,"Séptima restriccion \n"); for (r=2;r<=m;r++) { for (j=1;j<=n-1;j++) { fprintf(fichero2,"B_%d_%d + ",r,j); for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] + ",r,i,i,j); } else { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] - ",r,i,i,j); } } fprintf(fichero2,"B_%d_%d <= 0 \n",r,j+1); } } //Tiempos de proceso for (r=1;r<=m;r++) 54 fprintf(fichero2,"End"); } 9.1.3.2. FO: ∑Cj //fprintf(fichero2,"Funcion objetivo SUMCj \n"); fprintf(fichero2,"Minimize \n"); for (i=1;i<=n;i++) { if (i==n) { fprintf(fichero2,"E_%d_%d \n",m,i); } else { fprintf(fichero2,"E_%d_%d + ",m,i); } } 9.1.4. Modelo TBA 9.1.4.1. Modelo general y FO: Cmax #include <stdio.h> #include <stdlib.h> #include <schedule_lib.h> //The TBA model void modeloTBA(int n, int m, MAT_INT Tri, FILE *fichero2); int main() { printf("The TBA model\n"); int i,j,k,m,n; int cont=0; char cadena[50]={0}; char cadena2[50]={0}; for (j=5;j<=20;) { for (k=2;k<=5;k++) { for (i=1;i<=10;i++) 55 { sprintf(cadena,"Bateria Sin fechas/inst_%d_%d_p_%d",j,k,i); FILE * fichero = fopen(cadena,"r"); fscanf(fichero,"%d %d",&m,&n); printf("El numero de maquinas es: %d \n",m); printf("El numero de trabajos es: %d \n",n); sprintf(cadena2,"modelos/TBAmodel_%d_%d_%d.lp",j,k,i); FILE * fichero2=fopen(cadena2,"w"); MAT_INT Tri = DIM_MAT_INT(m,n); Tri=loadPTimes_nrows(cadena,&n,&m,YES); modeloTBA(n,m,Tri,fichero2); fclose(fichero); fclose(fichero2); fflush(stdin); cont=cont+1; } } j=j+5; } return cont; } void modeloTBA(int n, int m, MAT_INT Tri, FILE *fichero2) { int i,j,p,q,r,s; //FUNCION OBJETIVO //fprintf(fichero2,"Funcion objetivo CMAX \n"); fprintf(fichero2,"Minimize \n"); for (p=1;p<=m-1;p++) { for (i=1;i<=n;i++) { fprintf(fichero2,"[ T_%d_%d * Z_%d_1 ] + ",p,i,i); } } for (i=1;i<=n;i++) { fprintf(fichero2,"T_%d_%d + ",m,i); 56 } for (s=2;s<=n;s++) { if (s<n) { fprintf(fichero2,"X_%d_%d + ",m,s); } else { fprintf(fichero2,"X_%d_%d \n",m,s); } } //RESTRICCIONES DEL MODELO fprintf(fichero2,"Subject To \n"); //fprintf(fichero2,"Primera restriccion \n"); for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if (j<n) { fprintf(fichero2,"Z_%d_%d + ",i,j); } else { fprintf(fichero2,"Z_%d_%d = 1 \n",i,j); } } } //fprintf(fichero2,"Segunda restriccion \n"); for (j=1;j<=n;j++) { for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"Z_%d_%d + ",i,j); 57 } else { fprintf(fichero2,"Z_%d_%d = 1 \n",i,j); } } } //fprintf(fichero2,"Tercera restriccion \n"); for (r=2;r<=m;r++) { for (j=2;j<=n;j++) { for (i=1;i<=n;i++) { fprintf(fichero2,"[ T_%d_%d * Z_%d_1 ] + ",r-1,i,i); } for (q=1;q<=j-1;q++) { for (i=1;i<=n;i++) { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] - [ T_%d_%d * Z_%d_%d ] + ",r,i,i,q,r-1,i,i,q); } } for (s=2;s<=j;s++) { if (s<j) { fprintf(fichero2,"X_%d_%d - ",r,s); fprintf(fichero2,"X_%d_%d + ",r-1,s); } else { fprintf(fichero2,"X_%d_%d - ",r,s); fprintf(fichero2,"X_%d_%d - ",r-1,s); } } 58 for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] - ",r-1,i,i,j); } else { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] = 0 \n",r-1,i,i,j); } } } } //fprintf(fichero2,"Cuarta restriccion \n"); { fprintf(fichero2,"X_1_1 = 0 \n"); } //Tiempos de proceso for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { fprintf(fichero2,"T_%d_%d = %d \n",r,i,Tri[r-1][i-1]); } } //ACOTACIONES fprintf(fichero2,"Bounds \n"); for (r=1;r<=m;r++) { for (s=2;s<=n;s++) { fprintf(fichero2,"X_%d_%d >= 0 \n",r,s); } } //VARIABLES fprintf(fichero2,"Generals \n"); for (r=1;r<=m;r++) 59 { for (s=2;s<=n;s++) { fprintf(fichero2,"X_%d_%d \n",r,s); } } fprintf(fichero2,"Binary \n"); for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { fprintf(fichero2,"Z_%d_%d \n",i,j); } } //FIN fprintf(fichero2,"End"); } 9.1.4.2. FO: ∑Cj //FUNCION OBJETIVO //fprintf(fichero2,"Funcion objetivo SumCj \n"); fprintf(fichero2,"Minimize \n"); for (j=1;j<=n;j++) { fprintf(fichero2,"%d X_%d_%d + ",s,m,j); s--; } for (j=1;j<=n;j++) { for (i=1;i<=n;i++) { if (i==n && j==n) { fprintf(fichero2,"[ %d T_%d_%d * Z_%d_%d ] \n",c,m,i,i,j); } else { 60 fprintf(fichero2,"[ %d T_%d_%d * Z_%d_%d ] + ",c,m,i,i,j); } } c--; } 9.1.5. Modelo TS3 9.1.5.1. Modelo general y FO: Cmax #include <stdio.h> #include <stdlib.h> #include <schedule_lib.h> //The TS3 model void modeloTS3(int n, int m, MAT_INT Tri, FILE *fichero2); int main() { printf("The TS3 model\n"); int i,j,k,m,n; int cont=0; char cadena[50]={0}; char cadena2[50]={0}; for (j=5;j<=20;) { for (k=2;k<=5;k++) { for (i=1;i<=10;i++) { sprintf(cadena,"Bateria Sin fechas/inst_%d_%d_p_%d",j,k,i); FILE * fichero = fopen(cadena,"r"); fscanf(fichero,"%d %d",&m,&n); printf("El numero de maquinas es: %d \n",m); printf("El numero de trabajos es: %d \n",n); sprintf(cadena2,"modelos/TS3model_%d_%d_%d.lp",j,k,i); FILE * fichero2=fopen(cadena2,"w"); MAT_INT Tri = DIM_MAT_INT(m,n); Tri=loadPTimes_nrows(cadena,&n,&m,YES); modeloTS3(n,m,Tri,fichero2); fclose(fichero); 61 fclose(fichero2); fflush(stdin); cont=cont+1; } } j=j+5; } return cont; } void modeloTS3(int n, int m, MAT_INT Tri, FILE *fichero2) { int i,j,r,p,q; //FUNCION OBJETIVO //fprintf(fichero2,"Funcion objetivo CMAX \n"); fprintf(fichero2,"Minimize \n"); for (p=1;p<=n;p++) { fprintf(fichero2,"T_1_%d + ",p); } for (q=2;q<=m;q++) { for (i=1;i<=n;i++) { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] + ",q,i,i,n); } } for (q=2;q<=n;q++) { if (q<n) { fprintf(fichero2,"Y_%d + ",q); } else { fprintf(fichero2,"Y_%d \n",q); } } 62 //RESTRICCIONES DEL MODELO fprintf(fichero2,"Subject To \n"); //fprintf(fichero2,"Primera restriccion \n"); for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if (j<n) { fprintf(fichero2,"Z_%d_%d + ",i,j); } else { fprintf(fichero2,"Z_%d_%d = 1 \n",i,j); } } } //fprintf(fichero2,"Segunda restriccion \n"); for (j=1;j<=n;j++) { for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"Z_%d_%d + ",i,j); } else { fprintf(fichero2,"Z_%d_%d = 1 \n",i,j); } } } //fprintf(fichero2,"Tercera restriccion \n"); for (r=2;r<=m;r++) { for (j=2;j<=n;j++) { 63 for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"[ T_1_%d * Z_%d_%d ] + ",i,i,j-1); } else { fprintf(fichero2,"[ T_1_%d * Z_%d_%d ] - ",i,i,j-1); } } for (i=1;i<=n;i++) { if (i<n) { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] - ",r,i,i,j-1); } else { fprintf(fichero2,"[ T_%d_%d * Z_%d_%d ] + ",r,i,i,j-1); } } for (q=1;q<=r-1;q++) { for (i=1;i<=n;i++) { fprintf(fichero2,"[ Z_%d_%d * T_%d_%d ] - [ Z_%d_%d * T_%d_%d ] + ",i,j,q,i,i,j-1,q,i); } } for (q=2;q<=j;q++) { if (q<j) { fprintf(fichero2,"Y_%d - Y_%d + ",q,q-1); } else 70 9.2.1. Modelo SGST 9.2.1.1. Modelo general y FO: Cmax #include <stdio.h> #include <stdlib.h> #include <schedule_lib.h> //The SGST model void modeloSGST(int n, int m, MAT_INT Tri, FILE *fichero2); int main() { printf("The SGST model\n"); int i,j,k,m,n; int cont=0; char cadena[50]={0}; char cadena2[50]={0}; for (j=5;j<=20;) { for (k=2;k<=5;k++) { for (i=1;i<=10;i++) { sprintf(cadena,"Bateria Sin fechas/inst_%d_%d_p_%d",j,k,i); FILE * fichero = fopen(cadena,"r"); fscanf(fichero,"%d %d",&m,&n); printf("El numero de maquinas es: %d \n",m); printf("El numero de trabajos es: %d \n",n); sprintf(cadena2,"modelos/SGSTmodel_%d_%d_%d.lp",j,k,i); FILE * fichero2=fopen(cadena2,"w"); MAT_INT Tri = DIM_MAT_INT(m,n); Tri=loadPTimes_nrows(cadena,&n,&m,YES); modeloSGST(n,m,Tri,fichero2); fclose(fichero); fclose(fichero2); fflush(stdin); cont=cont+1; } } j=j+5; 71 } return cont; } void modeloSGST(int n, int m, MAT_INT Tri, FILE *fichero2) { int i,k,r,s; //FUNCION OBJETIVO //fprintf(fichero2,"Funcion objetivo CMAX \n"); fprintf(fichero2,"Minimize \n"); fprintf(fichero2,"CMAX \n"); //RESTRICCIONES DEL MODELO fprintf(fichero2,"Subject To \n"); //fprintf(fichero2,"Primera restriccion \n"); for (i=1;i<=n;i++) { fprintf(fichero2,"C_1_%d - T_1_%d >= 0 \n",i,i); } //fprintf(fichero2,"Segunda restriccion \n"); for (r=1;r<=m-1;r++) { for (i=1;i<=n;i++) { fprintf(fichero2,"C_%d_%d - C_%d_%d - T_%d_%d = 0 \n",r+1,i,r,i,r+1,i); } } //fprintf(fichero2,"Tercera restriccion \n"); for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { for (k=2;k<=n;k++) { if (k>i) { fprintf(fichero2,"C_%d_%d - C_%d_%d + [ P * D_%d_%d ] - T_%d_%d >= 0 \n",r,i,r,k,i,k,r,i); 72 } } } } //fprintf(fichero2,"Cuarta restriccion \n"); for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { for (k=2;k<=n;k++) { if (k>i) { fprintf(fichero2,"C_%d_%d - C_%d_%d + P - [ P * D_%d_%d ] - T_%d_%d >= 0 \n",r,k,r,i,i,k,r,k); } } } } //fprintf(fichero2,"Quinta restriccion \n"); for (i=1;i<=n;i++) { fprintf(fichero2,"CMAX - C_%d_%d >= 0 \n",m,i); } //Tiempos de proceso for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { fprintf(fichero2,"T_%d_%d = %d \n",r,i,Tri[r-1][i-1]); s=s+Tri[r-1][i-1]; } } fprintf(fichero2,"P = %d \n",s); //ACOTACIONES fprintf(fichero2,"Bounds \n"); for (r=1;r<=m;r++) 73 { for (i=1;i<=n;i++) { fprintf(fichero2,"C_%d_%d >= 0 \n",r,i); } } fprintf(fichero2,"CMAX >= 0 \n"); //VARIABLES fprintf(fichero2,"Generals \n"); for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { fprintf(fichero2,"C_%d_%d \n",r,i); } } fprintf(fichero2,"CMAX \n"); fprintf(fichero2,"Binary \n"); for (i=1;i<=n;i++) { for (k=1;k<=n;k++) { if (k>i) { fprintf(fichero2,"D_%d_%d \n",i,k); } } } //FIN fprintf(fichero2,"End"); } 9.2.1.2. FO: ∑Cj //FUNCION OBJETIVO //fprintf(fichero2,"Funcion objetivo SUMCj \n"); fprintf(fichero2,"Minimize \n"); for (i=1;i<=n;i++) 74 { if (i==n) { fprintf(fichero2,"C_%d_%d \n",m,i); } else { fprintf(fichero2,"C_%d_%d + ",m,i); } } 9.2.2. Modelo LYeq 9.2.2.1. Modelo general y FO: Cmax #include <stdio.h> #include <stdlib.h> #include <schedule_lib.h> //The LYeq model void modeloLYeq(int n, int m, MAT_INT Tri, FILE *fichero2); int main() { printf("The LYeq model\n"); int i,j,k,m,n; int cont=0; char cadena[50]={0}; char cadena2[50]={0}; for (j=5;j<=20;) { for (k=2;k<=5;k++) { for (i=1;i<=10;i++) { sprintf(cadena,"Bateria Sin fechas/inst_%d_%d_p_%d",j,k,i); FILE * fichero = fopen(cadena,"r"); fscanf(fichero,"%d %d",&m,&n); printf("El numero de maquinas es: %d \n",m); printf("El numero de trabajos es: %d \n",n); sprintf(cadena2,"modelos/LYeqmodel_%d_%d_%d.lp",j,k,i); 75 FILE * fichero2=fopen(cadena2,"w"); MAT_INT Tri = DIM_MAT_INT(m,n); Tri=loadPTimes_nrows(cadena,&n,&m,YES); modeloLYeq(n,m,Tri,fichero2); fclose(fichero); fclose(fichero2); fflush(stdin); cont=cont+1; } } j=j+5; } return cont; } void modeloLYeq(int n, int m, MAT_INT Tri, FILE *fichero2) { int r,i,k,s,j; //FUNCION OBJETIVO //fprintf(fichero2,"Funcion objetivo CMAX \n"); fprintf(fichero2,"Minimize \n"); fprintf(fichero2,"CMAX \n"); //RESTRICCIONES DEL MODELO fprintf(fichero2,"Subject To \n"); //fprintf(fichero2,"Primera restriccion \n"); for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { for (k=2;k<=n;k++) { if (k>i) { fprintf(fichero2,"[ P * D_%d_%d ] + C_%d_%d - C_%d_%d - T_%d_%d - Q_%d_%d_%d = 0 \n",i,k,r,i ,r,k,r,i,r,i,k); } } 76 } } //fprintf(fichero2,"Segunda restriccion \n"); for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { for (k=2;k<=n;k++) { if (k>i) { fprintf(fichero2,"Q_%d_%d_%d - P + T_%d_%d + T_%d_%d <= 0 \n",r,i,k,r,i,r,k); } } } } //fprintf(fichero2,"Tercera restriccion \n"); for (i=1;i<=n;i++) { fprintf(fichero2,"C_1_%d - T_1_%d >= 0 \n",i,i); } //fprintf(fichero2,"Cuarta restriccion \n"); for (r=1;r<=m-1;r++) { for (i=1;i<=n;i++) { fprintf(fichero2,"C_%d_%d - C_%d_%d - T_%d_%d = 0 \n",r+1,i,r,i,r+1,i); } } //fprintf(fichero2,"Quinta restriccion \n"); for (i=1;i<=n;i++) { fprintf(fichero2,"CMAX - C_%d_%d >= 0 \n",m,i); } //Tiempos de proceso 77 for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { fprintf(fichero2,"T_%d_%d = %d \n",r,i,Tri[r-1][i-1]); s=s+Tri[r-1][i-1]; } } fprintf(fichero2,"P = %d \n",s); //ACOTACIONES fprintf(fichero2,"Bounds \n"); for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { fprintf(fichero2,"C_%d_%d >= 0 \n",r,i); } } for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { for (k=2;k<=n;k++) { if (k>i) { fprintf(fichero2,"Q_%d_%d_%d >= 0 \n",r,i,k); } } } } fprintf(fichero2,"CMAX >= 0 \n"); //VARIABLES fprintf(fichero2,"Generals \n"); for (i=1;i<=m;i++) { for (j=1;j<=n;j++) 78 { fprintf(fichero2,"C_%d_%d \n",i,j); } } for (r=1;r<=m;r++) { for (i=1;i<=n;i++) { for (k=2;k<=n;k++) { if (k>i) { fprintf(fichero2,"Q_%d_%d_%d \n",r,i,k); } } } } fprintf(fichero2,"CMAX \n"); fprintf(fichero2,"Binary \n"); for (i=1;i<=n;i++) { for (k=2;k<=n;k++) { if (k>i) { fprintf(fichero2,"D_%d_%d \n",i,k); } } } //FIN fprintf(fichero2,"End"); } 9.2.2.2. FO: ∑Cj //FUNCION OBJETIVO //fprintf(fichero2,"Funcion objetivo SUMCj \n"); fprintf(fichero2,"Minimize \n"); 79 for (i=1;i<=n;i++) { if (i==n) { fprintf(fichero2,"C_%d_%d \n",m,i); } else { fprintf(fichero2,"C_%d_%d + ",m,i); } } 9.3. Archivo BATCH FOR /L %%x IN (5,5,20) DO ( FOR /L %%y IN (2,1,5) DO ( FOR /L %%z IN (1,1,10) DO ( gurobi_cl TimeLimit=600 LogFile=C:\Users\Usuario\Dropbox\TFG\EjecutableLectura_gurobi_lo g1\Debug\gurobi.log C:\Users\Usuario\Dropbox\TFG\EjecutableLectura_gurobi_log\Debug\ modelos\WSTmodel_%%x_%%y_%%z.lp gurobi_cl TimeLimit=600 LogFile=C:\Users\Usuario\Dropbox\TFG\EjecutableLectura_gurobi_lo g1\Debug\gurobi.log C:\Users\Usuario\Dropbox\TFG\EjecutableLectura_gurobi_log\Debug\ modelos\Wilsonmodel_%%x_%%y_%%z.lp gurobi_cl TimeLimit=600 LogFile=C:\Users\Usuario\Dropbox\TFG\EjecutableLectura_gurobi_lo g1\Debug\gurobi.log C:\Users\Usuario\Dropbox\TFG\EjecutableLectura_gurobi_log\Debug\ modelos\TS2model_%%x_%%y_%%z.lp gurobi_cl TimeLimit=600 LogFile=C:\Users\Usuario\Dropbox\TFG\EjecutableLectura_gurobi_lo g1\Debug\gurobi.log C:\Users\Usuario\Dropbox\TFG\EjecutableLectura_gurobi_log\Debug\ modelos\SGSTmodel_%%x_%%y_%%z.lp