Resolución exacta de problemas de programación operacional de trabajos en intervalos

i Trabajo Fin de Grado Ingeniería de Organización Industrial Resolución exacta de problemas de programación operacional de trabajos en intervalos Autor: Pedro Giménez Molina Tutor: José Manuel García Sánchez Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 iii Trabajo Fin de Grado Ingeniería de Organización Industrial Resolución exacta de problemas de programación operacional de trabajos en intervalos Autor: Pedro Giménez Molina Tutor: José Manuel García Sánchez Profesor titular: Dpto. de Organización industrial y gestión de empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 v Proyecto Fin de Carrera: Resolución exacta de problemas de programación operacional de trabajos en intervalos Autor: Pedro Giménez Molina Tutor: José Manuel García Sánchez El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2021 El Secretario del Tribunal vii A mi familia A mis maestros ix Resumen En este trabajo estudiamos de forma general la programación de trabajos en intervalos, centrándonos en los problemas de programación de trabajos en intervalos variables. En su inicio se desarrolla una visión más teórica de este tipo de problemas para, a continuación, adentrarse en la experimentación con tres modelos, los cuales se verán primero de forma matemática, para luego implementarlos a lenguaje Lingo. Se incluye, además, un algoritmo y su implementación en Python para extraer los datos del modelo desde una batería de problemas. Por último, a partir de los tiempos de ejecución de los problemas generados, realizaremos una comparación entre los comportamientos de los tres modelos estudiados frente a los problemas ejecutados para terminar encontrando el más adecuado para resolverlos. xvii ÍNDICE DE FIGURAS Figura 2-1. Clasificación de los problemas de programación de trabajos en intervalos 4 Figura 2-2. Fixed Job Scheduling Problem (FSP) 5 Figura 2-3. Variable Job Scheduling Problem (VSP) 6 Figura 4-1. MODEL del modelo 1 en Lingo. 22 Figura 4-2. Función objetivo, actividades de decisión y especificaciones del modelo 1 en Lingo. 23 Figura 4-3. MODEL del modelo 2 en Lingo. 24 Figura 4-4. Función objetivo, actividades de decisión y especificaciones del modelo 2 en Lingo. 25 Figura 4-5. MODEL del modelo 3 en Lingo. 25 Figura 4-6. Función objetivo y actividades de decisión del modelo 3 en Lingo. 26 Figura 4-7. Especificaciones del modelo 3 en Lingo. 26 Figura 5-1. Interior de un archivo de texto de la batería 28 Figura 5-2. Celda de lectura del algoritmo 30 Figura 5-3. Celda de creación del algoritmo 30 Figura 5-4. Celda de escritura del algoritmo 31 Figura 6-1. Datos de un problema de la batería 34 Figura 6-2. DATA y SETS del modelo 1 35 Figura 6-3. DATA del modelo 3 35 Figura 6-4. Lingo. Solver Status. Versión 1 36 Figura 6-5. Valores de los datos y variables 37 Figura 6-6. Lingo. Solver Status. Versión 2 38 Figura 6-7. Lingo. Solver Status. Versión 3 38 1 1 INTRODUCCIÓN a optimización de procesos de cualquier sector productivo puede ser llevada a cabo resolviendo un conjunto de problemas conocidos como problemas de programación de trabajos en intervalos. Esto permite determinar la mejor formar de organizar las tareas o trabajos, ya sea dentro de sistemas pequeños como un centro de logística o abarcando la totalidad del funcionamiento de una empresa, teniendo como meta una mejoría económica. Dentro de esta categoría de problemas, existen numerosas variantes como el Fixed Job Scheduling, en el cual los trabajos deberán ser realizados en intervalos de tiempo que coincidan de forma exacta con la duración de cada trabajo. Sin embargo, la variante que estudiaremos en este proyecto será el Variable Job Scheduling Problem, donde la extensión en el tiempo de cada trabajo no coincidirá con la del intervalo donde se realice, será menor. Por lo tanto, existirán inevitablemente holguras entre la realización de cada trabajo. Este problema puede ser enfocado de diferentes formas. Por un lado, desde un punto de vista operacional, asignando los recursos (máquinas) que estén disponibles a los trabajos a realizar siguiendo un criterio de optimización, o desde un punto de vista táctico, en el que se buscará calcular la capacidad necesaria para la consecución de todos los trabajos pendientes. En el proyecto tendremos como meta el objetivo operacional. Partiremos de tres modelos matemáticos. En ellos, el criterio de optimización será maximizar el peso de los trabajos procesados. Estudiaremos los elementos, las actividades de decisión, las especificaciones y las funciones objetivo de cada modelo. Realizaremos su implementación en las librerías de optimización Lingo, con el que podremos simular cada modelo a partir de los datos necesarios procedentes de una batería de problemas, los cuales representan diferentes valores en los parámetros del problema, aportando numerosos datos como el número de trabajos a procesar o el número de máquinas de las que se dispone para tratarlos. Una vez obtenidos los datos de las simulaciones de los tres modelos, desarrollaremos un análisis de esos resultados y compararemos la eficiencia y la rapidez entre los modelos. A continuación, explicaremos la estructura general de este trabajo, adjuntando una breve descripción de lo que veremos en cada capítulo:  El capítulo 2 contendrá una visión fundamentalmente teórica sobre la programación de trabajos en intervalos y más concretamente sobre el Variable Job Scheduling Problem. Además, explicaremos de una forma más gráfica dos casos prácticos de esta variante.  El capítulo 3 ahondará en las explicaciones de los modelos matemáticos: Cómo interactuarán los elementos que los componen entre ellos, qué activades de decisión se realizarán, cuál será el objetivo a maximizar o minimizar en sus funciones objetivo, o el significado que encierra cada una de las L INTRODUCCIÓN 2 especificaciones que limitarán cada modelo.  El capítulo 4 tratará la implementación de los modelos a las librerías de optimización Lingo, pasando por una previa descripción de este procesador.  El capítulo 5 se dedica a presentar la clasficación de los problemas que se encuentran dentro de la batería y los datos que podremos obtener de cada uno de ellos. También se incluye la explicación de cómo obtener los archivos que representan cada problema en el formato adecuado para Lingo a partir de un algoritmo desarrollado en lenguaje Python.  En el capítulo 6, veremos la ejecución de los modelos en Lingo introduciendo los datos de los problemas de la batería, comparando los resultados en términos de eficiencia y tiempo entre ellos para evaluar cuál es el mejor para afrontar cada problema que se ejecute.  Y, en el capítulo 7, expondremos una valoración global del trabajo y de los resultados obtenidos. 3 2 PROGRAMACIÓN DE TRABAJOS EN INTERVALOS N este capítulo ahondaremos en la programación de trabajos en intervalos en general y sus diferentes variantes. Además, de forma más explicita más veremos el problema Variable Job Scheduling Problem, objetivo fundamental de nuestro trabajo. También hemos desarrollado dos casos prácticos sobre este problema, uno con máquinas que procesen los mismos trabajos y otro con distintas máquinas capaces de soportar distintos trabajos cada una. 2.1. Programación de trabajos en intervalos La programación de trabajos en intervalos surge de la necesidad organizativa de las empresas de conseguir realizar tanto sus productos como sus proyectos en la menor cantidad de tiempo posible sin superar los límites que tenga establecidos tanto la propia empresa como sus clientes. También se pretende ordenar que cada uno de esos productos se procese en los recursos que tenga disponible la empresa adecuados para ellos, ya sea en máquinas o asignándolos a equipos de trabajo determinados en el caso de los proyectos más extensos. Respecto a situaciones reales en las que se aplique este procedimiento tenemos como ejemplos la distribución de piezas que formen parte de un conjunto ensamblable en las diferentes máquinas de un taller tipo job shop; el reparto de clases de diferentes asignaturas en una universidad en las diferentes aulas disponibles sin que se rebase el tiempo disponible del que dispone el horario establecido de uso de cada aula; el proceso de fabricación y mantenimiento de las diferentes partes de un avión, el cual se va desplazando lentamente, consiguiendo así que los operarios acaben su parte del proceso de construcción en un tiempo determinado de forma extricta; el proceso de asignación de tareas a distintos equipos de trabajo dentro de una empresa, cada uno de ellos especializados en una tarea, cuyos posibles inicios dependan de que se hayan realizado anteriores tareas; el sistema de luces de los semáforos en una ciudad; el sistema de cita previa para un proceso de vacunación, distribuyendo a los pacientes en distintos centros según su edad y repartiéndolos en horarios lo suficientemente espaciados para no colapsar esos centros; la asignación de turistas a habitaciones libres de un hotel teniendo en cuenta el tiempo de su estancia; la distribución de conductores a coches disponibles y a zonas determinadas en una empresa de transporte privada,etc. [1,2] Retomando el tema que nos ocupa, la programación de trabajos en intervalos en genenal consiste en adjudicar un conjunto de trabajos pendientes a un grupo de recursos, que desde ahora trataremos siempre como máquinas, en el menor tiempo posible, limitado por un horizonte temporal predeterminado de antemano. Esta limitación de tiempo se debe a que cada trabajo, en su descripción, tendrá asociado un intervalo de tiempo en el que deberá comenzar. En el caso de que el trabajo se programe fuera de ese intervalo, generará la prohibición de que ese trabajo se programe en cualquier otro momento fuera del intervalo, lo que derivará en costes importantes al responsable del proyecto o directamente a su empresario supervisor. Cada intervalo de cada trabajo estará delimitado por el instante de posible inicio más temprano y el instante de E PROGRAMACIÓN DE TRABAJOS EN INTERVALOS 4 posible inicio más tardío. Si el trabajo se comienza a procesar fuera de esos límites, ya no será valido. La otra característica de los trabajos, presente siempre en todas las variantes del problema, es su duración. Si el trabajo se empieza a realizar correctamente dentro de su intervalo asignado, lo que dure a partir de ese instante ya no será importante. Sin embargo, sí influirá respecto al número de recursos disponibles. Si los tiempos de duración de los trabajos que se encuentran en proceso son muy elevados y hay pocas máquinas con las que contar para acogerlos, puede ocurrir que no se cumplan los intervalos de los siguientes trabajos en la lista por no tener máquinas disponibles. También contarán los trabajos con otras dos carácterísticas, aunque estas no serán fijas para todos los tipos de problemas en la programación de trabajos en intervalos. Por un lado, tenemos los pesos de cada trabajo, es decir, el valor que tiene para el empresario el que se realize correctamente. Siempre se intentará priorizar la consecución de los trabajos con mayor peso. Por otra parte, está la clase o tipo de cada trabajo. Existirán casos en los que todos los trabajos a procesar sean del mismo tipo y puedan desarrollarse de la misma forma, con lo que no importará esta característica, pero en su mayoría tendremos casos en los que los trabajos se dividan en diferentes clases. En consecuencia, se dispondrá de distintas máquinas capaces de recibir cada uno de estos tipos de trabajos. A continuación, disponemos de una gráfica que clasifica las distintas características que pueden tener los problemas de programación de trabajos en intervalos, las cuales, combinadas entre sí de distintas formas, dan lugar a numeros tipos de problemas diferentes. Figura 2-1. Clasificación de los problemas de programación de trabajos en intervalos En la primera clasificación, se dividen los problemas según su objetivo, o lo que es lo mismo la solución última a la que se quiere llegar. Según la que se pretenda, cambiará la forma de resolver el problema. Contamos con dos tipos de objetivos principales:  Objetivo táctico. Partimos de la idea de que no tenemos de antemano un número de recursos, máquinas, inalterable. A partir de ahí, buscaremos cuál sería el número de máquinas mínimo suficiente para procesar el conjunto de trabajos a cumplir dentro de sus intervalos señalados [1,3]. Esto se debe a que, para estos casos, el uso de cada máquina llevará asociado un coste que habrá que reducir. También se intentará utilizar más frecuentemente aquellas máquinas con costes de uso más bajo cuando sea posible. El hecho de tener cierta libertad en elegir el total de máquinas que queremos a nuestra disposición hará que, a la hora de programar los trabajos, lo hagamos siempre para casos en los que podemos programar todos ellos, aunque el coste del uso de las máquinas aumente.  Objetivo operacional. Con este objetivo, sin embargo, el problema estará restringido desde el comienzo a un número de máquinas fijo. De esta manera, se genera un cierto grado de libertad para resolver el problema, aunque la forma más usada para hacerlo es teniendo en cuenta la característica del peso de 5 Resolución exacta de problemas de programación operacional de trabajos en intervalos los trabajos. La meta será maximizar el peso total de los trabajos que se realicen. [1,3] De esto último se deduce que, al contrario que con el objetivo táctico, ahora si puede existir la posibilidad de que alguno de los trabajos pendientes no se programe al tener fijado el número de máquinas disponible. Estas dos formas de resolver los problemas, aunque lo pueda parecer, no son del todo incompatibles. Pueden aparecer problemas que tengan rasgos de ambos y podrán resolverse igualmente. [1,3] La siguiente clasificación propuesta va en función de cuántas clases de máquinas tengamos disponibles. Existirá el caso en el que contemos con un único tipo de máquinas, provocando que todos los trabajos a realizar puedan acceder a cualquiera de esas máquinas. Es un caso sencillo, pero a la vez poco común. Es más corriente encontrarnos con problemas en los que tengamos varios grupos de máquinas cada uno de una clase distinta. Para estos tipos de problemas entrarán en juego la característica clase de cada trabajo. Estará establecida una compatibilidad previa entre determinadas clases de trabajos y máquinas. Cada trabajo irá únicamente a una máquina que sea aceptable para él. Los problemas que contengan máquinas de varias clases, a su vez estarán divididos en otras dos categorías:  Shift Class Scheduling. En esta ocasión, las máquinas tendrán una carácteristica extra, tendrán asociados intervalos de disponibilidad temporal. Esto quiere decir que, en determinados instantes de tiempo durante el procesamiento de los trabajos, las máquinas podrán estar bloqueadas según sus tiempos de descanso o indisponibilidad [1,3]. Los trabajos que lleguen a estas máquinas en esos intervalos deberán ser desviados a otras máquinas o introducidos en almacenes de espera dentro del proceso. Como ejemplo de este caso tenemos un horno, el cuál mientras no alcance las temperaturas adecuadas no podrá recibir unidades productivas.  License Class Scheduling. Esta variante considera que todas las máquinas del proceso se encuentran en funcionamiento en todo momento, en definitiva, no estarán restringidas por el tiempo. De modo que su única limitación será el que sean o no compatibles con los trabajos a procesar. [1,3] Para finalizar, la última forma de clasificar los problemas será según el tipo de intervalo que tengan sus trabajos:  Fixed Job Scheduling Problem (FSP). En ellos, la duración de cada uno de los trabajos concuerda exactamente en el tiempo con cada uno de sus respectivos intervalos [1,4]. En la siguiente imagen tenemos una representación gráfica de un trabajo en concreto, i, dentro de su intervalo definido por los límites I y F, instantes de inicio y de finalización obligatorios respectivamente. Al ser un FSP, la duración del trabajo i, d, encaja de lleno en la duración permitida por el intervalo. Figura 2-2. Fixed Job Scheduling Problem (FSP)  Variable Job Scheduling Problem (VSP). Para este tipo de problemas, las duraciones de los trabajos no tendrán por qué coincidir con la longitud de sus intervalos preasignados. Esto supone que siempre tendremos duraciones menores o iguales que las extensiones de sus respectivos trabajos. El hecho de que también puedan coincidir hace posible considerar que los problemas VSP abarcan de alguna forma también a los problemas FSP [1,4]. De nuevo, hemos realizado otro ejemplo gráfico para representar cómo se vería un intervalo en estos problemas. Ahora la duración d del trabajo i no abarca por completo la extension del intervalo. Existen holguras tanto antes como después del tiempo en el que se realiza el trabajo, por lo que hay más libertad PROGRAMACIÓN DE TRABAJOS EN INTERVALOS 6 para procesarlo en un momento u otro. Figura 2-3. Variable Job Scheduling Problem (VSP) Según los científicos Arkin y Silverberg, los problemas FSP pueden considerarse por lo general de tipo NP- complejo hasta el momento en el que cada trabajo individualmente, se pueda procesar en 3 o más de las máquinas disponibles. Por otra parte, los problemas VSP siempre serán tratados como problemas NP-complejo. [1,2] A lo largo de los siguientes capítulos, los problemas que estudiaremos tendrán las mismas características. Partiremos de un objetivo operacional, en concreto el definido antes como el más común, maximizar el sumatorio de los pesos cuyos trabajos son finalmente realizados en el proceso. Tendremos máquinas y trabajos con diferentes clases y, por tanto, con posibles disponibilidades entre ellos. Consideraremos que todas las máquinas con las que dispongamos, estarán listas para procesar trabajos en todo momento, o lo que es lo mismo, seguiremos la variante License Class Scheduling. Además, todos los problemas serán del tipo VSP, es decir, la duración de cada trabajo no tendrá por qué coincidir en el tiempo exacto que proporciona el intervalo de posibles inicios de cada uno. Como consideraciones externas a las vistas en este capítulo tendremos que cada máquina que forme parte del sistema no tendrá la capacidad de tratar más de un trabajo a la vez y que, en el instante en el que se empieza a procesar un trabajo en el interior de una máquina, el tratamiento no podrá ser interrumpido ni para remplazarlo por otro trabajo, ni pausado para terminar el resto de su proceso más adelante. 2.2. Casos prácticos Para facilitar la major comprensión de este tipo de problemas, hemos resuelto manualmente, de forma gráfica, dos casos en los que hay que optimizar de acuerdo a las condiciones de un problema VSP. En el primero, los elementos del problema serán iguales y, en el segundo, las máquinas solo podrán realizer determinados trabajos. 2.1.1 Con máquinas sin clases En este primer caso, partimos de una situacíon determinada en la que se tienen que procesar 12 trabajos, numerados en la columna TR, cada uno con su correspondiente duración (di) y sus delimitaciones de inicio temprana (Ii) y tardía (Fi). Los datos pertenencientes a estos tres parámetros coinciden con la cuarta, segunda y tercera columnas de la siguiente tabla, respectivamente. Por otro lado, suponemos que contamos con dos recursos o máquinas (R1 y R2), ambos con las mismas características. Cualquiera de los trabajos se podrá hacer en una u otra sin distinción. En la cuarta columna de la tabla aparece un diagrama de Gantt en el que vienen representados los intervalos donde se podrá realizar cada trabajo (casillas blancas), cuya longitud dependerá de las condiciones de inicio ai y bi. Dentro de ellos, las casillas verdes marcan en qué momento del intervalo se ha terminado realizando el trabajo. El eje de abcisas del diagrama marca el tiempo y el eje de ordenadas relaciona cada trabajo con su intervalo. Al final de cada fila aparece el recurso encargado de operar cada trabajo (R1 o R2). Como el objetivo que tendremos a lo largo del Proyecto es operacional y no táctico, el número de recursos disponibles siempre estará prefijado. Esto puede generar un problema grave que he representado en este caso. 7 Resolución exacta de problemas de programación operacional de trabajos en intervalos TR Ii Fi di 1 2 4 3 2 3 7 4 3 5 6 2 4 6 9 5 5 7 9 3 6 8 10 5 7 8 12 4 8 13 14 2 9 16 17 3 10 15 17 4 11 16 18 5 12 19 21 4 Tabla 2-1. Caso con máquinas sin clases El trabajo 8 no puede comenzar a ser realizado dentro de sus límites prefijados, entre 13 y 14, debido a que durante ese tiempo los recursos 1 y 2 siguen estando ocupados con los trabajos 6 y 7 respectivamente. Lo mismo ocurre con el trabajo 11, ya que tampoco hay recursos disponibles en su plazo de realización. El hecho de que no sea posible realizarlas a tiempo da lugar a que esos trabajos no sean procesados, ni siquiera fuera de plazo. Este problema, en una situación real, desembocaría en daños económicos y organizativos graves. 2.1.2 Con máquinas con clases Existen otros casos más comunes, como el del siguiente ejemplo, en los que los trabajos son de diferentes tipos o clases y los recursos disponibles sólo están preparados para procesar trabajos de determinadas clases específicas. Para aclarar esto disponemos de la matriz de compatibilidad (ADC), la cual determina si un recurso (columna) está capacitado para interactuar con una clase de trabajo (fila), marcando su casilla intersección con un 1. En el caso de que el recurso no soporte una clase de trabajo, marca un 0. [1,2] A continuación, adjunto la matriz en cuestión para este ejemplo: ADC R1 R2 R3 C1 0 1 0 C2 1 0 1 C3 1 1 0 Tabla 2-2. Matriz de compatiblidad(ADC) A raíz de ella conocemos que hay tres clases de trabajos y tres recursos en total. Los de clase C1 solo pueden ser procesados por el recurso R2, los de clase C2, por los recursos R1 y R3, Y los de clase C3, por los recursos R1 y R2. Por otro lado, volvemos a crear la misma tabla de datos que en el ejemplo anterior puesto que vuelven a ser 12 tareas a procesar, cada una con su instante de inicio más temprano (Ii), su instante de inicio más tardío (Fi) y su duración. Sin embargo, es necesario añadir una columna más (ci) en la que se indique la clase del trabajo (1,2 o 3). En la sexta columna de la tabla vuelve a aparecer otro diagrama de Gantt en el que vienen representados los MODELOS VSP 14 resultado de la suma entre el instante de inicio del trabajo i y su duración (d), deben superar al instante de inicio más temprano del trabajo i’. La tercera condición es que la suma del instante de inicio más temprano del trabajo i’ y su duración iguale o supere a la diferencia entre el instante de inicio más tardío y la duración del trabajo i. Como las tres condiciones están conectadas por conjunciones, las tres deberán de cumplirse a la vez. También recorreremos las máquinas (j), aunque únicamente las que sean a la vez compatibles con el trabajo i y el i’, o, lo que es lo mismo, que la compatibilidad de cada trabajo (A) con la máquina en cuestión, sea igual a uno.  La primera especificación recogida dentro de las condiciones anteriores nos dice que en el momento en el que se confirme que se han programado dos trabajos distintos en la misma máquina, es decir, que las alfas de i y i’ respecto a j sean igual a uno, se deberá cumplir que el instante de programación de i más su duración (d) sea menor que el instante en el que se programa i’ para que no coincidan.  La segunda es otra forma de ver la primera. Si se cumple que la suma de las alfas de los trabajos i y i’ respecto a la misma máquina j es igual o mayor que 2, se dará también que la diferencia entre los instantes de programación (x) de los trabajos i e i’ es menor o igual que la duración del trabajo i.  Las otras tres especificaciones son proposiciones simples en las que interviene una nueva variable auxiliar, pi, la cual esta referida a un trabajo i, otro trabajo i’ y una máquina j. En la primera de ellas, la suma de las alfas de cada trabajo i y i’ procesados en la misma máquina j es superior o igual que dos veces la variable auxiliar pi de esos mismos trabajos. En la segunda, esa misma suma tiene que ser menor que la de la variable pi más una unidad más. Y en la tercera, la diferencia entre los instantes de programación x de los trabajos i e i’ es menor que la duración d del trabajo i más el producto de la diferencia entre el instante de programación más tardío (F) y la duración del trabajo i entre la diferencia entre una unidad menos la variable pi. Continuamos con el segundo grupo de especificaciones. ' ' ' ' ' ' ' ' ' ' ' ' ' '' '' ' , '/ & , / 1 1: 11 2 1 ( )(1 ) (9) ( )(1 i j i j i i i i i i i i i C D C D ij i j i i i i i i ij i j i i i i i i i i i ii i i i i i ii i i i i i I I I d I I d F d j A A Si Y entonces x d x O x d x Si entonces x x d O x x d x x d sss x x d F d x x d                                         ' ' ' ' ' ' ' ' ' '' '' ' ' ' ) (10) 2 1 1 21 2 (6) 1 (7) 2 (11) ii i ii ij i j ii i i ij i j ii i i ij i j ii j ij i j ii j ii i i ii j I Si entonces O Si entonces                                   La forma de recorrerlas será idéntica a la del primer grupo exceptuando la tercera condición al recorrer los trabajos i e i’. La suma del instante de inicio más temprano del trabajo i’ (I) y su duración d, debrá ser inferior que la diferencia entre el instante de incio más tardío del trabajo i (F) y su duración (d). 3.2 Variable scheduling problem-Versión 2 (Trabajos unitarios) Para este segundo problema, los trabajos a programar tendrán duración entera, es decir serán unitarios. Este caso 15 Resolución exacta de problemas de programación operacional de trabajos en intervalos si coincidiría con los dos ejemplos vistos en el anterior capítulo. 3.2.1 Tabla de elementos La tabla de elementos de este problema es muy similar a la del primer problema, por lo que incidiré sólo en las pequeñas variaciones apreciables. ELEMENTOS CJTO NC DATOS Nombre Parámetro Tipo valor Pertenencia Valor Trabajos i=1..n IU Inicio Ventana Ii O P - Fin Ventana Fi O P - Duración di E P - Clase Ci O P - Peso Bi C P - Máquinas j=1..m IU Clase Dj O P - Periodos t=1…L IU Clases Trabajos k=1..CT IU Compatibilidad Akr B C - Clases Máquinas r=1..CM IU Akr Tabla 3-2. Tabla de elementos de un problema VSP, versión 2 Se mantienen los mismos 4 elementos del primer problema, más un quinto, los períodos, que se recorrerán con el subíndice t, tendrán tamaño L y no contarán con características asociadas. Las características de cada elemento vistas en el anterior problema se mantienen. Sin embargo, al ser los trabajos unitarios, su duración pasará a ser de tipo entero y sus instantes de inicio y fin ventana serán ordinales. 3.2.2 Función objetivo La función objetivo es exactamente la misma que en el primer problema, maximizar el peso de la realización de los trabajos. 1 / 1 CD ij n i ij i j A Max B    3.2.3 Actividades de decisión Identificamos de nuevo dos actividades de decisión:  Programar los trabajos dentro de los periodos. Usaremos la variable binaria beta, que estará compartida por los trabajos y los periodos. Tomara un valor u otro según se programe un trabajo dentro de un periodo o no. , : 1 si programo trabajo en el periodo ;0 si no i i it i t I F i t     Los periodos estarán comprendidos entre el inicio y el fin ventana de cada elemento. MODELOS VSP 16  Asignar las máquinas a los trabajos. Para cada trabajo i junto con cada una de las máquinas j compatibles con cada uno, creamos la variable binaria alfa (α), la cual tendrá valor uno en el caso de que el trabajo i se haya asignado a la máquina compatible j, o valor cero si no se ha producido esa asignación. , / 1: 1si asigno maquina a trabajo ; 0 si no ij C D ij i j A j i     3.2.4 Especificaciones 3.2.4.1 Relación implícita entre actividades En este grupo de especificaciones tenemos dos proposiciones compuestas y una simple. /1 /1 /1 : 0 0 : 1 1 : (1) i C D i ij i C D i ij i C D i ij F ij it j A t I F ij it j A t I F ij it j A t I i sss i sss i                  La primera indica que para cada trabajo i, se cumplirá que el sumatorio de sus variables alfa asignadas recorrido exclusivamente por las máquinas j compatibles con el trabajo es mayor que cero con la extricta condición de que el sumatorio de las variables beta para periodos t que se encuentren dentro del intervalo de posibles inicios de ese trabajo tiene que ser mayor que cero. De esta manera conseguimos que, si cualquier trabajo se asigna a una máquina, previamente tenga ya asignado también un periodo o instante de programación.  La segunda, viene con la misma estructura que la primera, aunque esta vez los resultados de los dos sumatorios tendrán que ser mayor o igual que uno.  Y la tercera es la proposición simple, que iguala los dos sumatorios vistos en las otras dos especificaciones. 3.2.4.2 Un trabajo procesado por una máquina a lo sumo Esta restricción evita que un mismo trabajo sea programado en más de una de sus máquinas compatibles. /1 : 1 (2) CD ij ij jA i     Para cada trabajo, el sumatorio de sus variables alfa recorrido por las máquinas j compatibles con cada uno, debe 17 Resolución exacta de problemas de programación operacional de trabajos en intervalos ser inferior o igual a uno. Esto tiene sentido ya que si valiese 2 significaría que ese trabajo se ha asignado a dos máquinas diferentes, situación prohibida en el modelo. 3.2.4.3 Solapamiento de trabajos en una máquina En este grupo constan seis especificaciones recorridas de la misma manera. ''' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' , ', / 1 1, [ , ], ' [ , ]/ ': 1 1 ( 1 1) 1 1 1 21 2 (3) 1 (4) i j i j C D C D i i i i i it i t ij i j it i t ij i j it i t ij i j it i t ii t it i t ii t i i i j A A t I F t I F t d t Si Y entonces NO Y Si Y entonces Si entonces                                            '' 2 (5) j i j ii t     Para cada trabajo i y cada trabajo i’ se van probando una a una las máquinas j que sean compatibles con ambos trabajos y los periodos t y t’, cada uno para su correspondiente trabajo, verificando que se encuentren dentro de los respectivos intervalos delimitados por los inicio y fin de ventana de cada trabajo. Además, tendrá que darse la condición de que el periodo (t) del trabajo i más su duración (d) sea mayor que el periodo (t) del trabajo i’. Comentar que en la primera especificación de este grupo, surge una nueva conectiva lógica, NO, que representa una negación. Todas las proposiciones que se encuentren incluidas dentro de esta conectiva no se cumplirán. Si retomamos la primera especificación, en ella se establece que en el momento en el que dos trabajos distintos i e i’ se programen en dos periodos distintos t y t’ respectivamente, es decir, que sus variables beta (β) se activen, será imposible que esos dos trabajos se programen en la misma máquina. Sus respectivas variables alfa (α) para una misma máquina j no podrán valer 1 a la vez. Con la segunda se quiere incidir en la misma prohibición que la primera expresadolo de una forma diferente. Si las dos variables beta de cada trabajo se activan, la suma de las variables alfa tendrá que ser igual o inferior a uno. En la tercera se vuelve a repetir el enfoque de las otras dos, aunque la primera proposición que tiene que cumplirse en ella es que la suma de las dos variables beta sea mayor o igual que dos. Las tres últimas son proposiciones simples más sencillas. Añadir que en todas ellas se usa una nueva variable auxiliar binaria denominada omega (ω). Estará en función de los trabajos i e i’ y de los periodos t. 3.3 Variable scheduling problem-Versión 3 (Trabajos unitarios) Esta última versión es parecida al segundo problema, de nuevo con trabajos unitarios. Las diferencias las comentaremos en el subapartado de la tabla de elementos. 3.3.1 Tabla de elementos En este problema se prescinde de tratar a las máquinas como elementos. MODELOS VSP 18 ELEMENTOS CJTO NC DATOS Nombre Parámetro Tipo valor Pertenencia Valor Trabajos i=1..n IU Inicio Ventana Ii O P - Fin Ventana Fi O P - Duración di E P - Clase Ci O P - Peso Bi C P - Periodos t=1…L IU Clases Trabajos k=1..CT IU Compatibilidad Akr B C - Clases Máquinas r=1..CM IU Num máquinas Mr E P - Akr Tabla 3-3, Tabla de elementos de un problema VSP, versión 3 El resto de elementos y sus características se mantienen con respecto al segundo problema. El otro cambio es que los elementos Clases Máquinas tendrán una nueva característica, el número de máquinas (Mr), el cual indicará cuantas máquinas habrá de cada clase. Será de tipo entero y exclusiva de los elementos Clases máquinas. 3.3.2 Función objetivo La función objetivo vuelve a querer maximizar los pesos de la realización de trabajos. La otra variable que aparece, además del peso, beta (β), será desarrollada en el siguiente subapartado. 1 / 1 i C r i i F n i itr i r A t I Max B        La FO está constituida por el producto del peso por beta dentro de tres sumatorios. Uno recorre los n trabajos, otro, las clases de maquinas compatibles con los trabajos y, el último, los periodos, comenzado cada uno por el inicio ventana de cada trabajo y terminando con el fin ventana. 3.3.3 Actividades de decisión Contaremos en este caso con una única actividad de decisión, programar cada trabajo en un periodo con una clase de máquina determinada. A raíz de ella definimos la variable binaria beta (β), que estará en función de los trabajos, los periodos y las clases, y se activará si se programan a la vez cada uno de esos elementos. , , / 1: 1 si programo trabajo en el periodo con la clase ;0 si no i i i Cr itr i t I F r A i t r      También será necesario que la clase del trabajo sea compatible con la clase de la máquina. 3.3.4 Especificaciones 3.3.4.1 Un trabajo procesado por una clase máquina y un periodo a lo sumo Esta especificación evita que un mismo trabajo se programe de nuevo en una misma máquina y un mismo periodo. /1 : 1 (1) i C r i i F itr r A t I i     Para cada trabajo el sumatorio de su variable beta asignada, recorriendo todas las clases de máquinas compatibles 19 Resolución exacta de problemas de programación operacional de trabajos en intervalos y los instantes de tiempo dentro de su periodo t, deberá ser menor o igual que 1. 3.3.4.2 Solapamiento de trabajos en una máquina Por otra parte, tenemos la restricción que evita que los trabajos que se activen en un intervalo de tiempo determinado y en máquinas de una misma clase, sean los mismos o menos que las máquinas disponibles de esa clase (Mr), evitando así el solapamiento de trabajos. ' '/ ' [ , ]& ' , : (2) i i i it r r i t t I F t d t r t M       También especifica que los períodos t donde finalmente se comienzan a operar los trabajos se encuentren dentro de los límites de inicio temprano y tardío de cada uno y que el momento de inicio del siguiente trabajo sea después del fin de la duración del anterior si ambos trabajos se realizan seguidos en una misma máquina. 21 4 IMPLEMENTACIÓN DE MODELOS EN LINGO n este capítulo explicaremos brevemente el funcionamiento del programa Lingo en el que introduciremos los problemas desarrollados en el capítulo anterior para su posterior análisis y simulación. Veremos cómo se traspasa cada parte de los modelos al lenguaje Lingo y los cambios que se producen. 4.1 Introducción a Lingo Lingo es un software capacitado para recrear modelos de optimización lineales o no, y encontrarles la mejor solución posible. Consigue que, tanto la construcción del modelo como la búsqueda de su solución óptima, se realicen de forma más sencilla y efectiva que de la forma manual. [6] Posee, además, un lenguaje de programación fácil de entender, con el que, con unas pocas líneas de código, podremos representar modelos matemáticos con un gran número de variables y restricciones. [6] Otra facultad clave de Lingo es que es capaz de tratar los datos númericos de forma externa al resto del modelo. Lee datos de sitios ajenos al modelo, ya sean hojas de cálculo, archivos de texto o bases de datos. De esta forma consigue evaluar un mismo problema con diferentes datos sin necesidad de cambiar el código, evitando así posibles errores. [6] 4.2 Versión 1 en Lingo Al ser éste el primer modelo de Lingo descrito, además de comentar el modelo en sí, veremos también de forma general la estructura del modelo en Lingo. Comenzamos creando la sección SETS, donde designamos los distintos conjuntos referidos a los diferentes elementos que aparecían en la tabla de elementos del modelo visto en el capítulo anterior. Cada conjunto referido a un solo elemento se denomina conjunto primitivo. En estos conjuntos, aparece primero el nombre, que corresponde con el del elemento en cuestión, seguido del tamaño del conjunto y, por ultimo, de los datos pertenecientes al elemento, que estaban recogidos igualmente en la tabla de elementos. [5,6] E IMPLEMENTACION DE MODELOS EN LINGO 22 Figura 4-1. MODEL del modelo 1 en Lingo. En el modelo, los conjuntos referidos a los elementos trabajos, máquinas, clases de trabajos y clases de máquinas son los únicos conjuntos primitivos. Los variables dato que aparecen dentro de cada conjunto son las que en la tabla de elementos estaban recorridas por el mismo subíndice del elemento al que se refiere el conjunto. Por ejemplo, las variables inicio ventana (I) y fin ventana (F) aparecen con el subíndice i en la tabla de elementos, el correspondiente a los trabajos. Sin embargo, en esta parte del modelo en Lingo, no es necesario introducir los subíndices que recorrían cada elemento. Como puede observarse en la imagen anterior, estos conjuntos no son los únicos que aparecen en la sección SETS. Tenemos también otras variables compartidas entre dos o más elementos y, por tanto, con dos o más subíndices que las recorren, como son la compatibilidad entre máquinas y trabajos (A), o variables que creamos en el desarrollo de las especificaciones y las actividades de decisión, como la variable alfa que marcaba si se asignaba o no un trabajo a una máquina o las variables auxiliares pi y sigma. Para estas variables compartidas es necesario crear los llamados conjuntos derivados a partir de la combinación de dos o más conjuntos primitivos. Véase el caso del conjunto derivado ASIGNAR, que recoje los conjuntos primitivos TRABAJOS y MÁQUINAS, los cuales usan los subíndices i y j respectivamente. A su vez dentro del conjunto ASIGNAR se encuentra la variable Alfa recorrida por los dos subíndices de los conjuntos primitivos que constituyen el conjunto derivado. [5,6] Otro tema clave a tratar es que, en el interior de algunos de los conjuntos derivados, aparece repetido uno de los conjuntos primitivos que lo forman. Esto ocurre debido a que hay algunas variables en el modelo recorridas por un mismo subíndice duplicado. Por ejemplo, la variable auxiliar sigma tiene como subíndices i e i’. Recordamos que la i hace referencia a un trabajo en concreto y la i’ a otro trabajo diferente a el primero. Por ello, este tipo de variables necesitarán de la creación de un nuevo conjunto derivado que contenga doblemente ese conjunto primitivo. Una vez completada la sección SETS, procedemos con la sección DATA. En esta sección, se definen todos los posibles valores numéricos de todas las variables con las que cuenta el modelo. [5,6] Sin embargo, en el código anterior aparece completamente vacía. Esto se debe a que los datos que vamos a usar provienen de una batería de problemas externa que comentaremos en el siguiente capítulo. Esta forma de obtención de los datos es la que exponíamos al inicio de este capítulo en la introdución a Lingo. Tras la sección DATA, se agrupa el resto de partes de modelo matemático traducidas a lenguaje Lingo, es decir, la función objetivo, las actividades de decision y las especificaciones. 23 Resolución exacta de problemas de programación operacional de trabajos en intervalos Figura 4-2. Función objetivo, actividades de decisión y especificaciones del modelo 1 en Lingo. La primera línea del código representa la función objetivo. En nuestro caso siempre será de tipo maximizar (MAX). Los sumatorios que aparecen tanto dentro de ella como en el resto de los modelos aparecen en lenguaje Lingo como @SUM (⅀). Dentro de sus paréntesis se engloba todo lo que estaba dentro de cada sumatorio en el modelo matemático escrito. Se puede incluir sumatorios dentro de otros, como es el caso en esta función objetivo. [6] La simbología matemática entre esta última parte del modelo escrito y en Lingo es muy similar. A simple vista se puede identificar qué especificación corresponde a qué linea de código en Lingo. Además, se han añadido comentarios (frases en verde) para una mejor diferenciación. Sin embargo, dentro del calificador condicional de los sumatorios, el formato de signo de las expresiones condicionales cambia en Lingo. Una prueba de ello está en la función objetivo: Su segundo sumatorio, el que recorre las máquinas con el subíndice j, solo recorrerá las máquinas cuya compatibilidad (A) con el trabajo en cuestión sea apta, es decir igual a 1. Ese signo igual es sustituido por la expression #EQ#. A lo largo del resto de los modelos se irán comentando este tipo de cambios en cuanto vayan apareciendo. [6] Hay que aclarar también que, a partir de aquí, sí usaremos los subíndices entre paréntesis junto a sus respectivos conjuntos y variables. Respecto a las actividades de decisión, es donde empiezan a aparecer los @FOR (), los cuales sirven para delimitar a los miembros de un conjunto sobre los que se va a trabajar. La forma de leer la actividad de decisión “Programar trabajos” sería: para todo trabajo i, hay una variable x que representa el instante en el tiempo en el que se programa ese trabajo. El que la variable x esté dentro de un @GIN quiere decir que esa variable será entera. [5,6] El funcionamiento de los @FOR es muy similar al de los @SUM. Estos también pueden tener calificadores condicionales con las mismas características que los de los @SUM. Los @FOR pueden contener además otros @FOR u otros @SUM, algo que ocurrirrá con mucha frecuencia en las especificaciones. De la misma forma que el @GIN se refería a una variable entera, el @BIN que aparece al final de la actividad de decision “Asignar máquinas a trabajos”, marca la variable alfa como binaria. [5,6] Al momento de entrar en las especificaciones del grupo Relación implícita de actividades, se puede apreciar que sólo hay dos especificaciones en lugar de las cuatro que había en el modelo matemático original. Esto es debido a qué Lingo no es capaz de procesar las proposiciones lógicas compuestas que utilizan operadores o conectivas lógicas, tales como sí solo sí (SSS), SI-ENTONCES, Y, O, O BIEN, NO. [5,6] BATERÍA DE PROBLEMAS 30 Por último, recorremos en otro bucle for el resto de números (y) del fichero y eliminamos los saltos de línea. Figura 5-2. Celda de lectura del algoritmo  Celda de creación. En esta parte crearemos una cadena (string) para cada característica, e iremos introduciendo los valores que teníamos en sus respectivas listas, pero ahora irán separados por comas, algo necesario para su introducción en Lingo. Esto lo conseguimos mediante las funciones join. Es necesario también que dentro de cada función join se realize otro bucle para que la coma se introduzca entre todos los números de la cadena representante de una característica. Para la cadena de la carácteristica clase (c) hay que realizar un preproceso antes de introducir las comas al ser el ultimo elemento del Array. De nuevo hay que eliminar los saltos de línea ya que esta característica es la última de cada línea en el fichero inicial y también lo llevaban. Figura 5-3. Celda de creación del algoritmo  Celda de escritura. Aquí generamos un nuevo fichero con el mismo nombre que tenga el problema que estemos convirtiendo y sobre el que vamos a escribir mediante la función write. En primer lugar, convertimos el entero “n” a un string mediante la función “str”. Posteriormente escribimos el número de trabajos (n) seguido de un salto de línea. A continuación, escribimos las cinco cadenas creadas en la celda anterior, precedidas de su respectivo símbolo y un igual, y delimitadas por un “;”. Así conseguimos que en cada fichero que se vaya creando se mantenga la estructura de datos apropiada para Lingo. De nuevo, también escribiremos el resto de números almacenados en Array2, sustituyendo los saltos de 31 Resolución exacta de problemas de programación operacional de trabajos en intervalos línea por espacios en blanco. Figura 5-4. Celda de escritura del algoritmo 33 6 SIMULACIÓN Y ANÁLISIS DE LOS RESULTADOS n este capítulo realizaremos primeramente una simulación manual de los 3 modelos, tras la que comentaremos y explicaremos los resultados obtenidos. Acto seguido, recogereremos los resultados de una serie de distintos casos de la batería de problemas a través del código generador de problemas que programamos al final del capítulo anterior. 6.1 Simulación manual El motivo de esta simulación previa es introducir a mano los datos de uno de los problemas de la batería al azar en la sección DATA de los modelos en Lingo, la cual, recordemos, dejamos vacía en el capítulo 4, y en menor medida en la sección SETS, para mostrar cómo quedaría el código completo en Lingo para cada modelo. Otro motivo es el de explicar el cuadro de resultados que ofrece Lingo una vez se corre el modelo en el programa, y empezar a comentarlos. Así, en el momento de adentrarnos en la siguiente simulación, en la que corremos grupos de problemas más grandes gracias al código generador de archivos Lingo, podremos centrarnos en el objetivo final de este trabajo, que no es otro que el de estudiar los tiempos de simulación de cada modelo para ver cual de ellos es el más potente, es decir, el que menos tiempo necesita para encontrar el resultado óptimo. Para mayor facilidad, hemos escogido un problema de la batería de tan solo 25 trabajos. El nombre del archivo que lo contiene es el “File_1_0, 8_25_4_3_2_2.txt”. Del capítulo 5 sabemos que será un problema de intervalos de inicio para cada trabajo no superiores a 5 unidades de tiempo, con un nivel bajo de solapamiento entre ellos. Contaremos con cuatro máquinas que podrán ser de dos clases distintas y, como siempre, los trabajos podrán ser de tres clases. Los datos que contiene son los que aparecen a continuación: E SIMULACIÓN Y ANÁLISIS DE RESULTADOS 34 Figura 6-1. Datos de un problema de la batería Con ellos ya podremos completar las secciones DATA y SETS de los modelos. Para los modelos 1 y 2, la forma de introducir esos datos será idéntica, por lo que solo mostraremos el modelo 1. Respecto a la sección SETS, los cambios están en los números que marcan el tamaño de los conjuntos simples, los cuales sustituyen a las constantes que los representaban en los capítulos anteriores con los modelos incompletos. Por ejemplo, sabemos que tenemos 25 trabajos, con lo que la constante que marcaba el tamaño del conjunto TRABAJOS será igual a 25. Lo mismo ocurre con los tamaños de los conjuntos CLASES_TRABAJOS y CLASES_MAQUINAS, de los que ahora conocemos sus tamaños. Como hay tres clases de trabajos, CT valdrá 3 y, como hay dos clases de máquinas, CM será igual a 2. Por ultimo, el tamaño del conjunto PERIODOS lo obtenemos fijándonos en el posible instante de inicio más tardío del ultimo trabajo a procesar (el trabajo 25), el instante 69. Esto se debe a que, si cada periodo t es el momento en el que finalmente se realiza cada trabajo, el instante t=69 será el ultimo posible ya que el resto de trabajos se realizan antes. En la sección DATA, vamos introduciendo los 25 valores de cada parámetro asociados cada uno a uno de los 25 trabajos disponibles. Con ello completamos todos los inicios tempranos (I) y tardíos (F) de programación, duraciones (d), pesos (B), clases (C) y compatibilidades (A) posibles. Por otro lado, para el parámetro D, que indicaba la clase a la que pertenecía cada máquina disponible, como sabemos que hay cuatro máquinas en total en este problema y que hay 2 de un tipo y dos de otro, rellenamos sus 4 valores con dos 1 y dos 2. 35 Resolución exacta de problemas de programación operacional de trabajos en intervalos Figura 6-2. DATA y SETS del modelo 1 Respecto al modelo 3, tenemos una sección SETS con los mismos tamaños que los dos modelos anteriores y una sección DATA también idéntica, aunque hay que añadir los valores del parámetro M, que indicaba cuantas máquinas se contabilizaban en cada clase. Como hay dos clases de máquinas y dos máquinas de cada clase, sus valores serán 2 y 2. Figura 6-3. DATA del modelo 3 En el momento en el que ya están introducidos todos los datos necesarios y el resto del código del modelo en Lingo no contiene errores, ya podemos proceder con la simulación. Una vez ejecutamos el Solver en cada modelo, aparecerán cuadros de resultados de la simulación como el que vemos a continuación: SIMULACIÓN Y ANÁLISIS DE RESULTADOS 36 Figura 6-4. Lingo. Solver Status. Versión 1 Este en concreto pertenece al primero de los tres modelos. Está dividido en varios bloques:  En el bloque variables se encuentra el total de variables con las que cuenta el modelo (3000). Dentro de esas variables, indica cuales son no lineales (0) o enteras (2970). Al no existir variables no lineales en el modelo (aquellas que cuentan con alguna relación no lineal en una restricción determinada) en proporción al total de variables, se consigue resolver el modelo de forma más rápida. [6]  Existe un bloque referido a las restricciones (constraints), en el que aparece la cantidad final de las mismas, junto al número de restricciones no lineales de entre ellas. [6]  El bloque nonzeros enseña cuantos coeficientes no ceros contabiliza el modelo y cuantos de ellos son no lineales. [6]  También se indica la capacidad de memoria que usa el programa Lingo para resolver el modelo (507 K) en el bloque Generator Memory Used. [6]  En el bloque Solver Status aparecen la clase de modelo que se resuelve y el tipo de óptimo que se calcula, en este caso un óptimo global (aquel que es la mejor solución posible) junto a su valor numérico (13011). Otros datos presentes en este bloque son la cantidad por la cual todas las restricciones han sido violadas (infeasibility), y las iteraciones (iterations), que señalan cuántas veces ha recorrido el software Lingo el modelo (0) para su resolución. [6]  El bloque Extended Solver Status contiene la forma en la que se ha resuelto el modelo. Para esta ocasión ha optado por el método de eliminación Branch and Bound (B-and-B). Por otro lado, obtenemos de aquí el mejor objetivo alcanzado hasta el momento (Best Obj) y el número que representa la distancia entre el objetivo en el que se encuentra el procesador Lingo en determinado momento y el mejor objetivo que se haya encontrado hasta ese instante (Obj Bound). Ambos números son idénticos en este caso (13011), debido a que el modelo ya ha sido completamente resuelto en la simulación. [6]  Por último y más importante, contamos con el bloque Elapsed Runtime, el cual indica la duración que ha necesitado el software para simular el modelo en horas, minutos y segundos. No tiene que marcar el 37 Resolución exacta de problemas de programación operacional de trabajos en intervalos tiempo total, ya que mientras se esté simulando, existe la posibilidad de parar la simulación, lo que llevará a que este bloque marque el tiempo justo en el que se para. En este caso en particular, la simulación ha sido inmediata. [6] Además de este cuadro de simulación, al resolver el modelo también aparece otra pantalla extra: Figura 6-5. Valores de los datos y variables En ella vienen recogidos todos los valores de los datos del problema y de las variables que se han ido activando o no, en la columna valor (Value). [6] La última columna, denominada coste reducido (Reduced cost), se refiere a la cantidad por la que el coeficiente objetivo de cada variable debería de mejorar para que empezara a aportar un valor positivo a la solución óptima. [6] Finalmente, incluiremos además los cuadros de simulación de los otros dos modelos para este problema: SIMULACIÓN Y ANÁLISIS DE RESULTADOS 38 Figura 6-6. Lingo. Solver Status. Versión 2 Figura 6-7. Lingo. Solver Status. Versión 3 Cabe resaltar que, para este problema, los tres modelos poseen un tiempo de resolución ínfimo. Esto es debido a que el problema simulado consta sólo de 25 trabajos, algo que si se hiciese a mano resultaría tedioso, pero para un software como Lingo es muy sencillo de resolver. De los tres modelos, el tercero se realiza prácticamente de forma inmediata, gracias a que tiene una estructura mucho menos compleja que los otros dos. Más adelante en cuanto resolvamos problemas que tengan una mayor cantidad de trabajos a procesar veremos como los tiempos de simulación aumentarán. 39 Resolución exacta de problemas de programación operacional de trabajos en intervalos 6.2 Simulación de la batería de problemas Una vez realizada la primera simulación a mano, procederemos a simular un grupo concreto de problemas de la batería, en concreto 135 problemas. Se ha intentado que en su mayoría sean problemas con características principales distintas, para explorar la mayor cantidad de combinaciones diferentes posibles, y que cada tamaño de problema según el número de trabajos (25, 50, 100, 200, 400) tenga la misma representación. En la tabla que veremos en este subcapítulo, están recogidos los números que marcan algunas de las principales características de cada uno de los problemas simulados, junto a los tiempos de simulación que supone procesarlos en cada uno de los modelos estudiados. Añadir también, que solo incluiremos en este capítulo una pequeña parte de la tabla por su extensión, con el objetivo de explicar todos sus componentes. La tabla aparece completa en el anexo de este trabajo para su visualización. Como características diferenciales de los problemas tenemos: en la primera columna, la amplitud de los intervalos, en la segunda, el solapamiento de los trabajos, en la tercera, el número de trabajos a procesar, en la cuarta, el número de máquinas disponibles y, en la quinta, el número de clases de máquinas que hay. Hemos obviado el número de clases de trabajos, ya que siempre será 3, y el número que diferenciaba a cada problema de los de su mismo subgrupo, porque se ha intentado simular en su mayoría problemas de diferentes subgrupos. Por otro lado, en las últimas tres columnas, aparecen los tiempos de simulación del primero modelo (Tiempo V1), del segundo (Tiempo V2) y del tercero (Tiempo V3) para cada problema. Los tres se medirán en segundos. Amplitud Solapamiento Nº Trabajos Nº Máq Clases máq Tiempo V1 Tiempo V2 Tiempo V3 1 0,8 25 4 2 0 1 0 1 0,8 25 4 2 1 2 1 1 0,8 25 4 2 2 1 1 1 0,8 50 4 2 0 3 1 1 0,8 50 4 2 1 4 1 1 0,8 50 8 3 3 10 3 1 0,8 100 4 2 8 21 2 1 0,8 100 8 3 16 33 5 1 0,8 100 16 4 14 55 5 1 0,8 200 4 2 266 76 5 1 0,8 200 8 3 * 123 10 1 0,8 200 16 4 40 240 11 1 0,8 400 4 2 523 * 11 1 0,8 400 8 3 * * 16 1 0,8 400 16 4 * * 22 1 1,4 25 4 2 0 1 0 1 1,4 25 4 2 1 2 2 1 1,4 25 4 2 0 3 1 1 1,4 50 4 2 3 5 2 1 1,4 50 4 2 5 6 1 1 1,4 50 8 3 16 10 2 Tabla 6-1. Muestra de la batería de problemas 47 ANEXO Tabla de resultados de la simulación de la batería de problemas Amplitud Solapamiento Nº Trabajos Nº Máq Clases máq Tiempo V1 Tiempo V2 Tiempo V3 1 0,8 25 4 2 0 1 0 1 0,8 25 4 2 1 2 1 1 0,8 25 4 2 2 1 1 1 0,8 50 4 2 0 3 1 1 0,8 50 4 2 1 4 1 1 0,8 50 8 3 3 10 3 1 0,8 100 4 2 8 21 2 1 0,8 100 8 3 16 33 5 1 0,8 100 16 4 14 55 5 1 0,8 200 4 2 266 76 5 1 0,8 200 8 3 * 123 10 1 0,8 200 16 4 40 240 11 1 0,8 400 4 2 523 * 11 1 0,8 400 8 3 * * 16 1 0,8 400 16 4 * * 22 1 1,4 25 4 2 0 1 0 1 1,4 25 4 2 1 2 2 1 1,4 25 4 2 0 3 1 1 1,4 50 4 2 3 5 2 1 1,4 50 4 2 5 6 1 1 1,4 50 8 3 16 10 2 1 1,4 100 4 2 16 19 3 1 1,4 100 8 3 * 24 4 1 1,4 100 16 4 42 66 6 1 1,4 200 4 2 * 76 5 1 1,4 200 8 3 * 93 8 1 1,4 200 16 4 415 223 11 1 1,4 400 4 2 * * 11 1 1,4 400 8 3 * * 17 1 1,4 400 16 4 * * 22 1 2 25 4 2 0 1 0 1 2 25 4 2 0 1 1 1 2 25 4 2 0 1 0 1 2 50 4 2 6 4 1 1 2 50 4 2 6 4 1 1 2 50 8 3 5 10 2 1 2 100 4 2 40 21 2 48 1 2 100 8 3 * 22 4 1 2 100 16 4 * 46 5 1 2 200 4 2 * 78 6 1 2 200 8 3 * 91 8 1 2 200 16 4 231 203 11 1 2 400 4 2 * * 11 1 2 400 8 3 * * 16 1 2 400 16 4 * * 22 2 0,8 25 4 2 1 2 0 2 0,8 25 4 2 0 3 0 2 0,8 25 4 2 0 4 0 2 0,8 50 4 2 2 12 1 2 0,8 50 4 2 4 9 1 2 0,8 50 8 3 3 24 3 2 0,8 100 4 2 6 35 2 2 0,8 100 8 3 23 39 4 2 0,8 100 16 4 12 95 5 2 0,8 200 4 2 84 * 6 2 0,8 200 8 3 * * 9 2 0,8 200 16 4 17 * 11 2 0,8 400 4 2 * * 11 2 0,8 400 8 3 * * 17 2 0,8 400 16 4 62 * 23 2 1,4 25 4 2 0 3 0 2 1,4 25 4 2 0 4 0 2 1,4 25 4 2 0 2 0 2 1,4 50 4 2 4 9 1 2 1,4 50 4 2 1 8 1 2 1,4 50 8 3 11 20 3 2 1,4 100 4 2 16 38 2 2 1,4 100 8 3 * 46 4 2 1,4 100 16 4 * 234 6 2 1,4 200 4 2 * * 6 2 1,4 200 8 3 * * 9 2 1,4 200 16 4 162 515 11 2 1,4 400 4 2 * * 12 2 1,4 400 8 3 * * 17 2 1,4 400 16 4 * * 24 2 2 25 4 2 0 2 0 2 2 25 4 2 0 2 0 2 2 25 4 2 1 3 0 2 2 50 4 2 5 10 1 2 2 50 4 2 5 8 1 2 2 50 8 3 31 23 2 2 2 100 4 2 60 35 2 49 2 2 100 8 3 * 43 4 2 2 100 16 4 * 133 6 2 2 200 4 2 * * 6 2 2 200 8 3 * * 9 2 2 200 16 4 * 547 10 2 2 400 4 2 * * 12 2 2 400 8 3 * * 17 2 2 400 16 4 * * 23 3 0,8 25 4 2 0 7 1 3 0,8 25 4 2 0 8 1 3 0,8 25 4 2 2 9 1 3 0,8 50 4 2 2 31 1 3 0,8 50 4 2 3 27 2 3 0,8 50 8 3 5 49 2 3 0,8 100 4 2 5 80 3 3 0,8 100 8 3 7 98 5 3 0,8 100 16 4 22 93 6 3 0,8 200 4 2 15 * 6 3 0,8 200 8 3 8 * 9 3 0,8 200 16 4 17 * 12 3 0,8 400 4 2 64 * 9 3 0,8 400 8 3 525 * 19 3 0,8 400 16 4 30 * 25 3 1,4 25 4 2 1 11 1 3 1,4 25 4 2 0 10 1 3 1,4 25 4 2 0 8 0 3 1,4 50 4 2 1 28 1 3 1,4 50 4 2 1 30 1 3 1,4 50 8 3 82 82 3 3 1,4 100 4 2 40 79 3 3 1,4 100 8 3 * 111 4 3 1,4 100 16 4 * * 6 3 1,4 200 4 2 221 * 7 3 1,4 200 8 3 526 * 9 3 1,4 200 16 4 453 * 13 3 1,4 400 4 2 231 * 14 3 1,4 400 8 3 * * 19 3 1,4 400 16 4 45 * 26 3 2 25 4 2 0 6 0 3 2 25 4 2 0 5 0 3 2 25 4 2 0 5 0 3 2 50 4 2 4 27 1 3 2 50 4 2 4 25 1 3 2 50 8 3 12 51 2 3 2 100 4 2 71 110 2 50 3 2 100 8 3 * 130 5 3 2 100 16 4 197 424 7 3 2 200 4 2 * * 7 3 2 200 8 3 * * 10 3 2 200 16 4 * * 13 3 2 400 4 2 * * 14 3 2 400 8 3 * * 18 3 2 400 16 4 * * 25