Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo

Equation Chapter 1 Section 1 Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo Autor: Isaac Fernández Montilla Tutora: Paz Pérez González Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 iii Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo Autor: Isaac Fernández Montilla Tutor: Paz Pérez González Profesor titular Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 v Trabajo Fin de Grado: Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo Autor: Isaac Fernández Montilla Tutora: Paz Pérez González El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2020 El Secretario del Tribunal vii A mi familia A mis maestros A mis amigos ix Agradecimientos Me gustaría dar las gracias a varias personas por su ayuda durante la realización de este trabajo de fin de grado. A mi tutora Paz Pérez González, por aceptar mi petición para tutorarme en este proyecto, así como por su tiempo y dedicación durante todo el proceso. A mi familia y amigos por ayudarme y darme ánimos siempre durante todos estos años y por estar siempre a mi lado cuando los necesitaba. A mi apoyo incondicional, Lara, porque sin su ayuda no hubiese terminado todo esto y sobretodo, nada sería igual sin ella. A todos ellos, gracias. Isaac Fernández Montilla Sevilla, 2020 ÍNDICE DE TABLAS Tabla 1: Problema generado para n=20 y m=5. 26 Tabla 2: ARDI de cada problema para cada delta. 27 Tabla 3: ARDI en función del número de tabajos. 28 Tabla 4: ARDI en función del valor delta. 29 xvii ÍNDICE DE FIGURAS Figura 1. Representación de un programa, Gantt Chart. 2 Figura 2. Clasificación de los modelos de programación de la producción 4 Figura 3: Esquema de máquinas paralelas. 5 Figura 4: Esquema de un taller de flujo regular (flowshop). 5 Figura 5: Clasificación de las metaheurísticas. 11 Figura 6: Intercambio (Swap). 14 Figura 7: Inserción (Insertion). 14 Figura 8: Vecindad Learner. 14 Figura 9: Pseudocódigo de la función de cálculo de la función objetivo de los trabajos del conjunto A. 18 Figura 10: Pseudocódigo de la función de cálculo del tiempo total de terminación. 18 Figura 11: Pseudocódigo de la función de cálculo de la vecindad General Swap. 20 Figura 12: Pseudocódigo de la función de cálculo de la vecindad Insertion. 20 Figura 13: Pseudocódigo de la función de cálculo de la vecindad Learner. 22 Figura 14: Pseudocódigo del cálculo de la solución inicial. 23 Figura 15: Pseudocódigo del cálculo de la metaheurística VNS. 24 Figura 16: ARDI de cada tamaño para cada delta. 27 Figura 17: ARDI de cada delta para cada tamaño. 28 Figura 18: ARDI en función del número de trabajos. 29 Figura 19: ARDI en función del valor delta. 30 xix 1 1 INTRODUCCIÓN a Programación de la Producción se define como el conjunto de procesos y técnicas cuyo objetivo es la asignación de los recursos de la empresa para la fabricación de un conjunto de productos. Estos recursos se asignan a unas tareas, cada una de las cuáles debe ser procesada de la forma correcta y en el lugar y momento adecuado de manera que se maximice la eficacia respecto a uno o más objetivos que se desean optimizar y la eficiencia de los recursos. Por otro lado, el Control de la Producción es el conjunto de mecanismos y herramientas utilizados para poder monitorizar un seguimiento del programa de producción y, cuando sea necesario, ejecutar acciones correctoras (Pérez González, Fernández-Viagas & Framiñán, 2020). Este proyecto se encuentra en el ámbito de la Programación y Control de la Producción, que es un proceso que ha tomado mucha relevancia actualmente en el sector industrial, y que está contenido dentro de la Organización de la Producción (Production Management). La Organización de la Producción, consiste en la toma de un número elevado de decisiones a lo largo del tiempo para tratar de asegurar la máxima productividad con el mínimo coste posible (Pérez González, Fernández-Viagas & Framiñán, 2020). Dentro de la programación de la producción no todos los problemas son iguales. La función objetivo que se quiera optimizar será muy diferente en cada problema, pudiendo ser por ejemplo la minimización del tiempo total de terminación de los trabajos o del número de trabajos que se entregan con retraso. Tanto los recursos como las tareas pueden variar mucho en función de la organización a la que se haga referencia. Por tanto, se pueden por ejemplo identificar como recursos las máquinas en un taller, las pistas de aterrizaje en un aeropuerto o las unidades de procesamiento en un entorno de computación. Las tareas asociadas con estos recursos pueden ser respectivamente las operaciones en un proceso productivo, los despegues y aterrizajes en un aeropuerto o las ejecuciones de un programa de ordenador (Ballesteros Silva, Ballesteros Riveros & Bravo Bolívar, 2013). Los elementos principales de un modelo de programación son un número M de máquinas y un número N de trabajos. Con esto se puede elaborar el programa de producción. El objetivo de un modelo de programación es generar un programa, con una asignación de operaciones que sea factible y lo más eficiente posible o incluso óptima. En la Figura 1 se puede observar un diagrama de Gantt como ejemplo de un modelo de programación de la producción. L La mente que se abre a una nueva idea jamás volverá a su tamaño original. - Albert Einstein- Introducción 2 Figura 1: Representación de un programa, Gantt Chart. Fuente: Diapositivas Programación y Control de la Producción (2020). 1.1 Conceptos básicos En todos los problemas de programación considerados, siempre se supone que tanto el número de trabajos como el número de máquinas son finitos. Como ya se ha expuesto anteriormente, se va a denotar con n el número de trabajos y con m el número de máquinas. También se usará habitualmente el subíndice j para hacer referencia a un trabajo y el subíndice i para una máquina. Si un trabajo pasa por una serie de procesos, el par (i, j) hace referencia a la operación del trabajo j en la máquina i. Los elementos principales, según Pérez González, Fernández-Viagas & Framiñán (2020) son los siguientes: - Máquina (machine): Recurso productivo con capacidad para realizar operaciones de transformación/transporte de material. - Trabajo (job): Producto que es objeto de una operación en alguna de las máquinas de la fábrica. - Secuencia (sequence): Orden en el que cada trabajo comienza a procesarse en cada máquina. - Programa (schedule): Asignación en la escala temporal completa de las máquinas de una empresa para la fabricación de un conjunto de trabajos. Por tanto, el programa determina el comienzo y final de cada operación a realizar en cada recurso productivo. Los programas pueden ser admisibles (feasible schedule) que son los que cumplen todas las características y restricciones que deben cumplir, o no admisibles que son aquellos que no cumplen alguna o todas las restricciones. Además de esto, se pueden distinguir tres tipos de programas admisibles: • Programa semi-activo (semi-active schedule): No es posible adelantar ninguna operación (desplazar a la izquierda en el Gantt) sin cambiar el orden en el que alguna máquina procesa los trabajos. • Programa activo: No es posible adelantar ninguna operación sin retrasar alguna otra. • Programa sin retraso: No se mantiene ninguna operación en espera mientras la máquina asignada a esta operación está disponible para procesarla. 3 3 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo 1.2 Notación Para la definición de todos estos elementos y su notación se ha tomado como referencia la definida por Pinedo (2012). En primer lugar, se exponen los principales datos que se van a utilizar: - Tiempo de proceso (𝑝ij): Duración que requiere una operación de un trabajo j en una máquina i. El subíndice 𝑖 se omite cuando el tiempo de proceso es independiente de la máquina o el trabajo solo puede ser procesado en una máquina (pj). - Fecha de llegada (𝑟ij): representa el instante a partir del cual el trabajo 𝑗 se encuentra listo para ser procesado en la máquina 𝑖. - Fecha de entrega (𝑑𝑗): representa el instante en el cual el trabajo 𝑗 debe estar terminado. La finalización después de la fecha de entrega se puede producir en algunas ocasiones, aunque normalmente conlleva una penalización. En el caso de que la fecha de entrega sea obligatoria, se denota como 𝑑 𝑗. - Peso (𝜔𝑗): representa un indicador para establecer una prioridad entre el conjunto de trabajos 𝑗 del modelo. Por otra parte, se tienen una serie de medidas o variables las cuáles aparecerán en los distintos problemas de programación de la producción: - Tiempo de terminación o completion time (𝐶𝑖j): representa el instante en el que el trabajo 𝑗 termina de ser procesado en la máquina 𝑖. Cuando se hable del momento en el cuál el trabajo 𝑗 haya sido procesado por la última máquina, se denotará como 𝐶𝑗. - Tiempo de flujo o flowtime (Fj): representa el tiempo que el trabajo j se encuentra en el entorno. Se define como: Fj = Cj – rj - Retraso del trabajo o lateness (Lj): representa la diferencia entre el tiempo de terminación y la fecha de entrega del trabajo j. Si el trabajo se ha completado antes de su fecha de entrega será positivo, y si no, será negativo. Se define como: Lj = Cj – dj - Tardanza del trabajo o tardiness (Tj): representa el cuánto se ha retrasado un trabajo. En caso de que el trabajo haya sido completado antes de su fecha de entrega, su valor será 0. Se define como: Tj = max (0, Cj - dj) = max (0, Lj) - Adelanto del trabajo o earliness (Tj): representa el cuánto se ha adelantado un trabajo. En caso de que el trabajo haya sido completado después de su fecha de entrega, su valor será 0. Se define como: Ej = max (0, dj - Cj) = max (0, -Lj) Introducción 4 - Trabajo tardío o tardy job (Uj): expresa si un trabajo ha finalizado después de su fecha de entrega. Se define como: Uj = 1 si Cj > dj 0 en caso contrario 1.3 Clasificación de los modelos de programación de la producción Cuando se describe un modelo de programación de la producción se deben tener en cuenta varios elementos, por ello existe una clasificación en la que se definen tres conceptos. Éstos forman la siguiente notación α | β | γ (Pinedo, 2012), quedando así caracterizado cualquier problema. Cada concepto queda definido como sigue: - α: tipo de entorno de fabricación (layout). Representa el número y la disposición de las máquinas. - β: restricciones que caracterizan el sistema productivo. - γ: objetivo (u objetivos) que se quiere minimizar o maximizar para obtener la solución más eficaz posible de cada modelo. 1.3.1 Características de las máquinas. Tipos de entornos (α) La disposición y el número de máquinas es fundamental para definir y resolver problemas de programación de la producción. Existen varios tipos de entornos según Pérez González, Fernández-Viagas & Framiñán (2020): - Single machine (1): todos los trabajos son procesados por una única máquina. Es el caso más simple de todos los entornos. Figura 2. Clasificación de los modelos de programación de la producción. Fuente: Diapositivas Programación y Control de la Producción (2020). 5 5 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo - Identical parallel machines (Pm): consiste en m máquinas idénticas en paralelo. Cada trabajo j requiere ser procesado una vez y puede serlo en cualquiera de las m máquinas. Al ser todas las máquinas idénticas, el tiempo de proceso pij será el mismo para todas. - Uniform parallel machines (Qm): consiste en m máquinas en paralelo, pero cada una tiene una velocidad distinta de procesado. Esta velocidad de cada máquina se denota como vi. El tiempo de proceso puede por tanto calcularse como: pij = pj / vi - Unrelated parallel machines (Rm): consiste en m máquinas distintas en paralelo. El tiempo de proceso de cada trabajo depende de la máquina a la que sea asignado, ya que son diferentes en cada una. - Flowshop (Fm): consiste en m máquinas en serie. Todos los trabajos deben ser procesados en todas y cada una de las m máquinas. Además, todos los trabajos tienen la misma ruta, es decir, deben pasar por las máquinas en el mismo orden. - Jobshop (Jm): consiste en m máquinas. Cada trabajo tiene una ruta diferente y predeterminada. Esta es su diferencia con el flowshop, la ruta puede ser diferente para cada trabajo. - Openshop (Om): consiste en m máquinas en las que cada trabajo debe ser procesado en todas las máquinas. Sin embargo, su peculiaridad es que no hay ruta predeterminada para cada trabajo. 1.3.2 Características de los trabajos. Restricciones (β) Las características de los trabajos, habitualmente llamadas restricciones sirven para identificar consideraciones Figura 3: Esquema de máquinas paralelas. Fuente: Diapositivas Programación y Control de la Producción (2020). Figura 4: Esquema de un taller de flujo regular (flowshop). Fuente: Diapositivas Programación y Control de la Producción (2020). Metaheurísticas aplicables 12 simples, ya que para escapar de un óptimo local, se aplica una perturbación a la solución obtenida en la búsqueda local. Para todos los métodos que se van a definir a continuación, es necesario definir un criterio de parada (para establecer el fin del proceso). Este criterio puede ser el establecimiento de un número de iteraciones para que cuando se llegue a la última acabe el proceso, encontrar una solución que sea muy buena o detectar un estancamiento del proceso. Las metaheurísticas basadas en trayectoria también pueden denominarse basadas en vecindad, y las más usadas (Lozano Segura, 2020) son: - Simulated Annealing (SA): el método intenta simular los principios de enfriamiento de los metales. Se parte de una solución inicial a la que se le aplica una perturbación. Este método, para evitar caer en óptimos locales, acepta empeoramientos con una probabilidad que depende de T (parámetro de temperatura). El parámetro T se va modificando, por lo que al principio la probabilidad de aceptar una solución peor es alta, pero luego se va minimizando. Este método encontraría el óptimo del problema si se realizasen infinitas iteraciones, pero es un método muy lento y en caso de no realizar las infinitas iteraciones, sus resultados son poco fiables. - Iterated Local Search (ILS): el método ILS parte de una solución inicial a la que se le aplica búsqueda local para llegar a un óptimo local. A continuación, se le aplica una perturbación para alejarse del óptimo local y llegar así a otro “valle”, donde se vuelve a hacer búsqueda local y así sucesivamente. Existes dos criterios diferentes para elegir si un óptimo local es aceptado o no, ya que se puede seleccionar la mejor solución, o bien se puede seleccionar siempre la nueva solución, y así diversificar. - GRASP: sus siglas provienen de Greedy Randomized Adaptative Search Procedure y esta metaheurística se caracteriza por ser un proceso iterativo con dos fases (constructiva y de mejora). La primera fase o fase constructiva, parte de una solución parcial vacía a la que habrá que ir añadiendo aleatoriamente elementos que se encuentran en una “candidate list”. Estos elementos tienen un índice Greedy, que muestra las ventajas de añadir ese elemento. Cuando se construye la solución, se pasa a la fase de mejora, que consiste en aplicar una búsqueda local para mejorar la solución. - Tabu Search (TS): es un procedimiento de búsqueda por entornos cuya característica es que hace uso de una memoria adaptativa. Utiliza una memoria a corto plazo, creando una Lista Tabú en la cuál se encuentran las últimas soluciones que se han encontrado para evitar seleccionarlas otra vez en las siguientes iteraciones. Esta técnica permite el empeoramiento, lo que se utiliza para evitar caer en óptimos locales. Cuando se obtiene una solución mejor, ésta se añade a la lista tabú. - Búsqueda en vecindad variable (Variable Neighbourhood Search VNS): esta es una metaheurística que se basa en el uso de diferentes vecindades durante el proceso. Al inicio, además de una solución de partida, se definen un conjunto de vecindarios, con los que se va a trabajar. Una vez se establezcan los vecindarios se procede a seleccionar un vecino de dicho vecindario, con el cuál se hace una búsqueda local. Cuando ésta finaliza, se compara la mejor solución obtenida con la que había inicialmente. Si la nueva solución mejora a la original, la sustituye y la nueva se convierte en la solución actual, volviendo a realizar el mismo proceso. Si no se produce mejora, se repite el proceso, pero usando la siguiente vecindad. 2.1.2 Metaheurísticas basadas en población Estos métodos se difrencian de aquellos basados en trayectoria en que los basados en población parten de un conjunto de soluciones iniciales para cada iteración, mientras los de trayectoria partían de una única solución inicial. Algunas de las metaheurísticas basadas en población más extendidas (Sebastián Lozano, 2020) son: - Algoritmos genéticos (Genetic Algorithm GA): son metaheurísticas basadas en población muy robusta y se basan en la teoría de la evolución. Consisten en crear secuencias, evaluarlas y reutilizar las mejores soluciones para generar descendencia. Para llevar a cabo estos algoritmos lo hacemos mediante tres fases: selección, reproducción y reemplazo. Primero se seleccionan las mejores soluciones para que pasen a la fase de reproducción. Después estas son modificadas mediante operadores de mutación y cruce. Por último, hay que decidir si entran en la población y, en caso de 13 13 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo que lo hagan, a que otra solución sustituye. Cuando se termina, se vuelve a hacer otra iteración y así sucesivamente hasta llegar al criterio de parada. - Scatter Search (SS): este método utiliza estrategias sistemáticas para conseguir soluciones que mejoren a las que había anteriormente y que pasen a la siguiente generación. Parte de una población inicia a la que se le aplica un método de mejora. Después se crean de forma sistemática subconjuntos a los que se aplican un operador de orden definido y se combinan para crear soluciones. A cada solución creada se le vuelve a aplicar un método de mejora y se actualiza el conjunto de soluciones sustituyéndo con las nuevas, siempre que superen a las existentes en calidad o diversidad. Dependiendo del momento en el que se realice la actualización se diferencia entre Scatter Search estática (actualizamos tras la combinación y mejora) y Scatter Search dinámica (actualizamos el conjunto cada vez que generamos una nueva solución). - Differential Evolution (DE): esta metaheurística se emplea para problemas de optimización global con codificación real. El método es similar al del algortimo genético. Se parte de una población inicial formada por vectores y obtenida de manera aleatoria, definiendo los valores máximos y mínimos que se pueden adoptar. Para pasar a la siguiente generación se comienza calculando vectores mutantes. Dependiendo de cómo se lleva a cabo la fase de mutación se distinguen los diferentes tipos de Differential Evolution que se denotan como DE/x/y/z. Una vez obtenido el vector mutante, se aplica un operador de cruce y se genera una nueva solución. Finalmente hay que seleccionar una de las dos (la obtenida de la mutación o la obtenida del cruce) para que pase a la siguiente generación. Sólo una puede pasar para poder mantener constante el tamaño de la población. 2.2 Variable Neighbourhood Search En este capítulo se va a comentar la metaheurística que se usará para resolver el problema expuesto en el capítulo 2. El problema consistía en un entorno flowshop de permutación con minimización del total weighted completion time para dos conjuntos de trabajos. Para resolverlo, de entre todas las metaheurísticas posibles expuestas en el capítulo anterior, se va a utilizar la VNS (Búsqueda en Vecindad Variable). La metaheurística VNS se ha utilizado mucho en los últimos años para problemas de programación de la producción, como por ejemplo en Lei & Guo (2011, 2014) o en el artículo de Deming Lei “Variable neighborhood search for two-agent flow shop scheduling problem” el cuál se va a utilizar como base para este trabajo, ya que se seguirá el mismo método de resolución seguido por Lei (2015). Sin embargo, apenas se ha usado para programación multiobjetivo. Aunque ya se ha explicado un poco el algoritmo anteriormente, ahora se verá con más detalle. Para comenzar, hay que crear una solución inicial o de partida que será además la mejor solución hasta que sea mejorada por alguna otra. Para la creación de la solución inicial se cuenta con muchas formas de generar esta solución, ya que puede hacerse de manera aleatoria, siguiendo alguna regla de despacho o mediante alguna otra heurística que nos puede proporcionar una solución. En este caso concreto, para calcular esta solución de partida, se va a usar una de las reglas básicas de despacho conocida como Weighted Shortest Processing Time first. Esta regla de despacho, cuyas siglas que vamos a usar de ahora en adelante son WSPT, consiste en procesar siempre en primer lugar el trabajo con mayor valor del cociente entre el peso y el tiempo de proceso. Por tanto, se partirá de una solución en la que los trabajos están ordenados de mayor a menor cociente entre peso y tiempo de proceso wj / pj. Una vez tenemos la solución inicial (WSPT), trabajaremos con ella para buscar posibles soluciones que mejoren el valor de la función objetivo. Esta búsqueda hay que realizarla usando la metaheurística VNS, la cual es una familia de metaheurísticas basadas en vecindades que usan diferentes tipos de vecindades para la búsqueda del óptimo local. Estas vecindades hay que elegirlas antes de comenzar, ya que existen varios tipos de ellas muy diferentes unas de otras. Para el problema en cuestión, se van a usar tres vecindades (Lei, 2015) que se explicarán a continuación: - Intercambio (swap): este tipo consiste en el intercambio de dos trabajos cualesquiera que sean dentro de la secuencia. No tienen por qué ser adyacentes (esa sería otra vecindad conocida como adjacent swap). Una secuencia de n trabajos tiene 𝑛(𝑛−1) 2 vecinos. Metaheurísticas aplicables 14 Figura 7: Inserción (Insertion). Fuente: Diapositivas Programación y Control de la Producción (2020). Figura 8: Vecindad Learner. Fuente: Computers and Industrial Engineering, Deming Lei (2015). Figura 6: Intercambio (Swap). Fuente: Diapositivas Programación y Control de la Producción (2020). - Inserción (insertion): esta vecindad consiste en extraer un elemento de la secuencia de n trabajos que tenemos e insertarlo en alguna de las posiciones posibles de la secuencia. Una secuencia de n trabajos tiene (n-1)2 vecinos por inserción. - Learner: es más compleja que las anteriores. En primer lugar, copiamos y vaciamos la secuencia inicial S de n trabajos. Luego generamos aleatoriamente otra secuencia de la cual elegiremos, también aleatoriamente, algunos trabajos (entre 1 y n/2). Estos trabajos elegidos se insertan en la secuencia que S que teníamos vacía en las posiciones en los que estaban en la otra. Por último, los trabajos que aún no han sido insertados de la copia de S, se insertan también en S en el orden en el que estaban. 15 15 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo Teniendo en cuenta que estas son las tres vecindades que se van a usar para llevar a cabo la metaheurística, también hay que saber que existen diferentes variantes de Variable Neighbourhood Search. La VNS se puede realizar de varias formas, de hecho, cualquier metaheurística que de alguna forma utilice más de una vecindad se puede catalogar como VNS, por lo que a continuación se explicarán dos de las más sencillas (Lozano Segura, 2020). 2.2.1 Variable Neighbourhood Descent (VND) La primera variante que se va a ver parte de una solución inicial y, definiendo los tres tipos de vecindades que se han visto anteriormente (V1, V2, V3), se aplica primero la vecindad V1 a la solución inicial. Hay que buscar en toda la vecindad al completo y pueden presentarse dos opciones: - Se encuentra una solución mejor que la de partida. En este caso se toma la nueva solución como base y volvemos a aplicar V1. - En toda la vecindad no se encuentra ninguna solución que mejore a la que había, entonces se aplica V2 a la solución actual. Al aplicar V2 se vuelve a tener las dos mismas opciones, por lo que en caso de que algún vecino mejore la actual solución se tomaría como base y se volvería a aplicar V1 (primer paso). En caso contrario se seguiría aplicando el mismo método con la vecindad V3. Al terminar el proceso, se toma la solución que se haya obtenido como solución de partida y se vuelve a realizar otra vez el mismo proceso, iterando sucesivamente hasta alcanzar el criterio de terminación. Este método no garantiza optimalidad, pero sí que la solución obtenida sea óptimo local de varias vecindades diferentes al mismo tiempo. 2.2.2 Reduced Variable Neighbourhood Search (RVNS) La otra variante, RVNS, también parte de una solución inicial y se definen los tres tipos de vecindades que se han visto anteriormente (V1, V2, V3). Luego se aplica primero la vecindad V1 a la solución inicial para obtener de forma aleatoria un único vecino, el cual se compara con la solución inicial y pueden presentarse dos opciones: - El vecino obtenido aleatoriamente es mejor que la solución de partida. En este caso se toma como base y se vuelve a aplicar V1. - El vecino aleatorio no mejora a la solución que había, entonces se aplica V2 a la solución actual para volver a obtener de forma aleatoria un vecino. Al aplicar V2 se vuelven a tener las dos mismas opciones, por lo que en caso de que el vecino mejore la solución actual se tomaría como base y se volvería a aplicar V1 (primer paso). En caso contrario se seguiría aplicando el mismo método con la vecindad V3. Al terminar el proceso, se toma la solución que se haya obtenido como solución de partida y se volvería a realizar otra vez el mismo proceso, iterando sucesivamente hasta alcanzar el criterio de terminación (número máximo de iteraciones). Metaheurísticas aplicables 16 17 3 MÉTODO DE RESOLUCIÓN ara continuar, en este capítulo se va a proceder a describir todo lo que se refiere a la implementación del algoritmo explicado en el apartado anterior (capítulo 2) para la resolución del modelo de programación de la producción comentado en el capítulo 1. Dicho modelo estaba compuesto por dos conjuntos de trabajos y tenía como objetivo la minimización de la función objetivo (en este caso el total weighted completion time) de ambos conjuntos. Para resolver este problema se va a utilizar la metaheurística VNS. Para llevar a cabo la implementación se ha decidido utilizar el lenguaje de programación C. Hay que codificar el algoritmo VNS que se ha descrito anteriormente, codificando los tres tipos de vecindades que íbamos a usar para llevar a cabo el proceso. Además, hay que ser capaz de calcular la función objetivo de ambos conjuntos, ya que, como se explicó, hay que minimizar la del conjunto A, siendo la del B menor que el valor de épsilon (ε). Para poder comparar las soluciones que ofrece el programa se usará una batería de instancias con distintos números de trabajos y dos máquinas. Para el desarrollo de los códigos se ha utilizado el compilador Code::Blocks, que es un entorno de desarrollo integado de código abierto y permite el uso de los lenguajes de programación C y C++. Dentro de este compilador, se ha usado la librería Schedule que ha sido aportada por el personal docente de la asignatura de “Programación y Control de la Producción”, perteneciente al Grado en Ingeniería de Organización Industrial. Finalmente, una vez se han obtenido las soluciones a través de nuestro código, éstas han sido pasadas a Microsoft Excel para su estudio. Aunque en este capítulo se van a explicar las partes más importantes del código que se ha generado, es posible encontrar el código completo al final del proyecto, en el apartado Anexo. 3.1 Cálculo de la Función Objetivo En primer lugar, hay que recordar que la función objetivo que se está buscando minimizar es el total weighted completion time para ambos conjuntos. El cálculo de esta función objetivo (FO) es una de las partes más importante de este código, ya que esta será la base para que después se calcule de forma correcta la metaheurística. Por ello se debe recordar primero que el problema es biobjetivo, por lo que hay que calcular dos funciones objetivo, una para el conjunto A y otra para el conjunto B. Para el cálculo de las FO se utilizarán dos funciones en C en las que realizará el mismo proceso en ambas, pero al llegar al final una calculará la FO de A y la otra la de B. Las funciones que se van a usar, denominadas “FObjConjuntoA” y “FObjConjuntoB”, recibirán como parámetros el número de trabajos total y el número de trabajos de los conjuntos (que será la mitad), los valores P El primer paso es establecer que algo es posible, entonces la probabilidad ocurrirá. -Elon Musk- Método de resolución 18 Figura 9: Pseudocódigo de la función de cálculo de la función objetivo de los trabajos del conjunto A. Figura 10: Pseudocódigo de la función de cálculo del tiempo total de terminación. de los pesos para cada trabajo y del vector secuencia al que se quiere calcular la FO y por último un vector con los valores del completion time (tiempo de terminación) de cada trabajo. La función devolverá el valor de la FO obtenida para dicha secuencia. Dentro de estas funciones, se realizará el proceso de dividir el vector de tiempos de terminación en dos vectores, uno para cada conjunto separando así los elementos pertenecientes a cada conjunto. Se hará también lo mismo con los pesos, y una vez se haya hecho esto, solo quedará emplear la fórmula de la función objetivo. Para ello, se utilizará un bucle for para ir sumando los valores, ya que esta FO es un sumatorio (∑wjCj), como se muestra en el pseudocódigo que se puede ver en la Figura 9: FObjConjuntoA Input: instance data (WA, CA) Output: FOA begin for j=0 to M do FOA := FOA+WA(j)*CA (j); return FOA Para poder llegar a calcular estas funciones objetivo será necesario obtener dicho valor del tiempo de terminación, lo cual se conseguirá mediante otra función que se llamará “completiontime” y se encargará de calcular los completion time en función del número de máquinas que se tienen en cada instancia de entrada. Dicha función recibirá los valores del número total de trabajos N, el vector secuencia con el que se esté trabajando y la matriz de tiempos de proceso, los cuales son generados de manera aleatoria. Primero, lógicamente hay que definir e inicializar todas las variables y vectores que se van a usar para poder llevar a cabo esta función. En este caso, la función se hace como un puntero, ya que deberá devolver un vector con memoria dinámica. Dicho vector será el de los tiempos de terminación, y para ello se trabajará con un bucle for, dentro del cual se aplicará una fórmula u otra en función de si se cumple o no la condición marcada por el if. En la Figura 10, se muestra el cálculo de los tiempos de terminación: Completiontime Input: instance data (C1, p2) Output: C2 begin for j=1 to N do if C2(j-1) <= C1(j) then C2(j) = C1(j) + p2(j); else C2(j) = C2(j-1) + p2(j); return C2 19 19 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo Una vez realizados estos cálculos, se incluirá el resultado del completion time en las funciones de cálculo de la FO que vimos anteriormente, y con estas se podrá calcular las FO de cualquier secuencia que se introduzca, lo cual será muy importante para llevar a cabo el proceso de resolución de la metaheurística. 3.2 Cálculo de las vecindades Lo segundo que hay que hacer para poder después construir la metaheurística (VNS) será ser capaces de calcular los tres tipos de vecindades que se habían definido en el capítulo 2. Estas tres vecindades serán la base para la posterior realización de las metaheurísticas, por lo que es muy importante definirlas correctamente. Para ello, se han utilizado tres funciones diferentes, una para cada una de las vecindades que luego serán incluidas en el cáculo de la metaheurística, y ahora nos se explicará paso a paso cómo han sido calculadas. 3.2.1 General Swap En primer lugar, se comenzará con la primera de ellas, que como ya se ha explicado se conoce como General Swap (Intercambio general). Es importante distinguirla de otro tipo de vecindad como es el Adjacent Swap (Intercambio adyacente). El adyacente se basa, como su propio nombre indica en intercambiar los valores de la secuencia que se tenga por aquellos que están a sus lados. Sin embargo, el General permite cambiar la posición de un valor de la secuencia por la de cualquier otro, por lo que se consiguen muchas más posibilidades y muchos más vecinos para calcular. Para este caso que se nos presenta se crea una función que se denominará “v1_swap” y recibirá como parámetros los valores de número de trabajos (N) y un vector secuencia. Esta secuencia que hay que pasarle a la función será, al principio, la secuencia inicial obtenida, y después con las iteraciones que se realicen se le pasará la que en ese momento constituya la mejor solución, es decir el vecino con mejor valor de la FO. En esta función, lo primero que se debe hacer es inicializar y definir los vectores y variables que se vayan a utilizar. En este caso concreto, debemos definir un vector con memoria dinámica (función malloc), que será el que devuelva la función al final. Este vector será el vecino que se conseguirá calcular con nuestra vecindad Swap. Además, para poder llegar a calcularlo se definirán dos números enteros a los que luego se les dará valores aleatorios desde 0 hasta el número de trabajos que haya en cada caso. Esto servirá para conseguir calcular un vecino por general swap de forma aleatoria, sin que se deba participar en el proceso de selección de las posiciones que serán intercambiadas. Para ello, como se puede ver continuación, se coge la secuencia que se había pasado como parámetro a la función y una copia de esta, y se intercambian las posiciones escogidas por los valores enteros aleatorios que habíamos calculado. Para el cálculo de números aleatorios se utilizará la función rand (), una función de C que ya viene incluida en las librerías que se han usado y a la que solo hay que darle el valor máximo hasta el que puede llegar el número (en nuestro caso N), por lo que los números aleatorios se generan automáticamente. Hay que tener en cuenta que, si los valores aleatorios que se generen son iguales, hay que cambiarlos volviendo a generar dos valores nuevos, ya que, en caso de calcular el vecino con dos iguales, se quedaría la misma secuencia que había al comenzar. V1_swap Input: A, a1, a2 Output: resultado begin a1, a2 generate random for j=0 to N do resultado (j) = A(j); if a1 != a2 then resultado(a1) := A(a2); resultado(a2) := A(a1); Método de resolución 20 Figura 11: Pseudocódigo de la función de cálculo de la vecindad General Swap. Figura 12: Pseudocódigo de la función de cálculo de la vecindad Insertion. return resultado Hay que recordar siempre liberar la memoria del vector, sobre todo en los casos en los que se van a usar vectores con memoria dinámica. Esto se hace utilizando la función free () y poniendo dentro del paréntesis el vector que se quieran liberar. 3.2.2 Insertion En segundo lugar, se tiene la segunda de las vecindades que se van a usar para el cálculo de nuestra metaheurística. Se trata de la conocida como Insertion (Inserción) y consiste en seleccionar uno de los elementos de la secuencia que haya en el momento de su cálculo y extraerlo de su posición, insertándolo después en otra posición aleatoria. A diferencia del caso anterior, la secuencia a la que se le calculará la inserción será, en teoría siempre, al mejor vecino que haya en cada iteración. Sin embargo, se puede dar el caso de que la que llegue sea la secuencia inicial, ya que es posible que el vecino calculado en la primera vecindad no la haya mejorado. Para este caso, al igual que para la vecindad anterior, se crea una función llamada “v2_insert” que recibirá como parámetros los valores de número de trabajos (N) y un vector secuencia. Para esta función, lo primero que se va a hacer es inicializar y definir los vectores y variables que se vayan a utilizar. En primer lugar, al igual que se hizo en la primera vecindad, hay que definir un vector con memoria dinámica (función malloc) que será el que la función devolverá al final como resultado. Este vector será el vecino que se conseguirá calcular con nuestra vecindad Insertion. Para poder llegar a calcularlo, primero se realizará una copia de la secuencia introducida como parámetro en este vector resultado y se definirán dos números enteros a los que luego habrá que dar valores aleatorios desde 0 hasta el número de trabajos que haya en cada caso (N). Esto servirá para calcular los vecinos de forma aleatoria, sin que haya que intervenir introduciendo los valores que se van a usar. Para el cálculo de números aleatorios, como en el caso anterior, se utiliza la función rand (). Además de esta, habrá que usar otras tres funciones que están incluidas en la librería Schedule, la cuál se está usando. La primera de ellas será search_vector () y se utilizará para buscar en la secuencia el primer valor aleatorio que se haya calculado. Esta función devuelve la posición de dicho valor, por lo que se guardará en una variable entera. La segunda función que se va a usar es extract_vector (), que se encargará de extraer de la secuencia resultado el valor de la posición que se había guardado en una variable. Para terminar, está la última, que será insert_vector (), y lo que hará será insertar el valor que marca el número que se había extraído como posición de la secuencia inicial, en la posición de la secuencia resultado que se obtenga del segundo número aleatorio que se haya calculado. Se puede ver lo explicado en el siguiente pseudocódigo: V2_insert Input: B, a, random1, random2 Output: resultado begin random1, random2 generate random a := random1 position in vector resultado; Extract value a from vector resultado; Insert value B(a) in position random2 from vector resultado; return resultado 21 21 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo Con esto se habría calculado la segunda de las tres vecindades que hay que usar para el cálculo de la metaheurística, por lo que queda ver la última de ellas. 3.2.3 Learner Para terminar, hay que ver la última y más compleja de las vecindades que se van a utilizar, denotada como Learner en el artículo Variable neighborhood search for two-agent flow shop scheduling problem, Lei (2015). Como en el caso anterior, la secuencia a la que se le calculará la inserción será al mejor vecino que haya en cada iteración, a no ser que el vecino calculado en las primeras vecindades no haya mejorado a la solución inicial, en cuyo caso llegará esta misma. Para este caso, al igual que para las otras vecindades, se crea una función llamada “v3_learner” que recibirá como parámetros los valores de número de trabajos (N) y un vector secuencia. Lo primero que hay que hacer es, como en las anteriores, inicializar y definir los vectores y variables que se van a utilizar. En primer lugar, al igual que se hizo en las vecindades anteriores, hay que definir un vector con memoria dinámica (malloc) que será el que la función devolverá al final como resultado. Este vector será el vecino que se conseguirá calcular con la vecindad Learner. Además de este, también se definirá de la forma habitual otros vectores. Para uno de ellos se generará una secuencia aleatoria y se le realizará una copia. Otro servirá como vector que habrá que rellenar y con el que se trabajará. Una vez todo esté definido, habrá que calcular un número aleatorio desde 1 hasta N/2 (la mitad del número de trabajos que haya) que será el número de trabajos que se van a coger de la secuencia aleatoria para formar la solución. Después se generan tantos números aleatorios como indicara el número generado anteriormente. Estos últimos serán los trabajos que, de forma parecida a lo visto en Insertion, se extraerán de la secuencia aleatoria y se insertarán en la secuencia que había que rellenar en sus mismas posiciones. La forma de hacer este proceso es la que se puede observar en la Figura 13, mediante un bucle for para que se realice tantas veces como indique el número aleatorio calculado al principio. Una vez que se tienen estos valores insertados en la secuencia que será la solución, ya sólo quedaría un paso. Esta vez habrá que coger los trabajos que falten por insertar en la secuencia solución y buscarlos e insertarlos en el orden en el que estuvieran en la secuencia inicial que se pasó como parámetro, pero en las posiciones que falten por rellenar. Todos estos procesos se harán también con las funciones de C search_vector (), extract_vector () e insert_vector (), como se puede ver en la Figura 13: V3_learner Input: C, sec, aleatorio, L Output: resultado begin aleat generate random for i=0 to aleat do c1 := aleatorio (i) position in vector sec; c2 := aleatorio (i) position in vector C; Extract value c2 from vector C; Extract value c1 from vector L; Insert value aleatorio(i) in position c1 from vector L; j :=0; for i=0 to N do if sec(i) != L(i) then Extract value i from vector L; Análisis computacional 28 Figura 17: ARDI de cada delta para cada tamaño Tabla 3: ARDI en función del número de tabajos. Otra forma de reflejar estos datos es como se aprecia en la Figura 17, invirtiendo los datos de la gráfica. En esta se pueden apreciar perfectamente los valores para δ =0 y δ =0,5 como límites, ya que hacen el ARDI=0 y ARDI=1 respectivamente. A partir de ahora se van a analizar los diferentes valores de la función objetivo (total weighted completion time) que hemos obtenido para cada problema, es decir, para cada grupo de diez instancias dependiendo del número de trabajos y valores de delta. Para comenzar, vamos a estudiar los valores medios del factor RDI para las soluciones que hemos obtenido basándonos en el número de trabajos. Para ello tenemos la Tabla 3 que se muestra a continuación: num trabajos ARDI 10 0.48 20 0.49 50 0.42 70 0.41 100 0.43 200 0.44 29 29 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo Tabla 4: ARDI en función del valor delta. Figura 18: ARDI en función del número de tabajos. 0,36 0,38 0,40 0,42 0,44 0,46 0,48 0,50 10 20 50 70 100 200 ARDI en función de n De los valores de la Figura 18 se puede extraer, por tanto, que este algoritmo ofrece mejores soluciones para un mayor número de trabajos, ya que para los dos primeros tamaños calculados n=10 y n=20 el valor del factor ARDI es considerablemente mayor que para el resto de los problemas estudiados. Sin embargo, a medida que se aumenta el número de trabajos, los valores obtenidos son menores y similares. A continuación, se pueden seguir estudiando los resultados del factor ARDI, clasificando los problemas en función del valor de delta que tengamos. En la Tabla 4 se puede ver la variación del índice ARDI en función del valor de delta (δ), es decir, según los diferentes valores que se hayan obtenido de épsilon a partir de la FO del conjunto B su disminución aplicándole la fórmula establecida (ε= ε ·(1-δ)). delta ARDI 0 0.00 0.1 0.06 0.2 0.18 0.3 0.46 0.4 0.95 0.5 1.00 Análisis computacional 30 Figura 19: ARDI en función del valor delta. 0,00 0,20 0,40 0,60 0,80 1,00 1,20 0 0,1 0,2 0,3 0,4 0,5 ARDI en función de δ ARDI En esta Figura 19 se puede apreciar que, como se explicó en la primera gráfica, las mejores soluciones se alcanzan para el valor de δ=0. Cuando se tiene este valor, el valor de épsilon es el original, hallado a partir de la función objetivo del conjunto B. Sin embargo, cuando se empieza a aumentar el valor de delta, el valor de épsilon disminuye, por lo que se restringen las posibles soluciones estableciendo un upper bound (límite superior) más pequeño. Esto hace que las soluciones que se encuentren sean peores que cuando δ=0, llegando a la peor solución estudiada cuando δ=0,5. Por tanto, se ha presentado el ARDI de cada problema (grupo de instancias según su tamaño) para cada delta, así como los resultados de dicho índice para cada valor del número de trabajos y delta. 31 5 CONCLUSIONES n la actualidad la optimización de procesos y la programación de la producción están adquiriendo una importancia mucho mayor de la que habían tenido a lo largo de la historia. En los procesos de fabricación, por ejemplo, la optimización cobra mucha importancia dentro de una empresa, ya que debemos llevar a cabo dicha producción de una forma lo más eficiente posible para intentar conseguir los objetivos de minimización de costes y maximización de la calidad y los volúmenes de producción. Este trabajo de fin de grado se ha centrado en el estudio de un problema de flowshop de permutación con dos conjuntos de trabajos y objetivo de minimización del total weighted completion time. Este es un problema sobre el que no se ha escrito mucho, ya que llegar a buenas soluciones con dos conjuntos de trabajos es complicado debido al problema multi objetivo y a la dificultad de minimizar los objetivos de ambos conjuntos. Para llevar a cabo la resolución de dicho problema se ha usado la metaheurística llamada Variable Neighbourhood Search. El trabajo sigue una estructura que está compuesta para comenzar de un capítulo introductorio teórico en el que se expone la teoría de la programación y control de la producción, así como su notación habitual con el objetivo de aclarar todas las herramientas que usaremos posteriormente. A continuación en este capítulo teórico se procede a realizar una descripción completa del problema que se va a tratar de resolver y sus características principales. Una vez finalizado el capítulo 1, continúa con el apartado de las metaheurísticas. En él, se explican los diferentes tipos de metaherísticas que hay, así como las metaheurísticas más importantes de cada tipo. Tras esta breve presentación se procede a explicar con mayor detalle la metaheurística VNS, la cuál se usará para resolver el problema de programación de la producción presentado en este trabajo. Después de haber comentado y explicado paso a paso todas las herramientas que se van a usar para realizar y resolver nuestro modelo, llegamos al capítulo 3, en el que se verá y se explicará con detalle el código que se ha generado para llevar a cabo la resolución del problema. Se analizará cada parte del código y se explicará cómo se ha realizado y qué función tiene cada parte. Para finalizar, está el capítulo 4, en el cuál se ha utilizado el código para llegar a unas secuencias y sus funciones objetivo solución, las cuáles se han usado, a través de la herramienta Microsoft Excel, para realizar un análisis de todos los resultados que ha aportado la metaheurística utilizada. Para ello se usa una serie de instancias, divididas por números de trabajos y de máquinas. En conclusión, el desarrollo de este trabajo, del modelo y de la metaheurística de resolución ha sido un trabajo complicado y ha requerido de muchas modificaciones, búsqueda y pruebas para llevar a cabo todo el problema y su resolución. Con todos los datos obtenidos a través del estudio y el análisis de las soluciones se puede concluir que se han hallado soluciones factibles a través del estudio de las vecindades de una secuencia de partida, y estas soluciones son peores para números de trabajos más pequeños y mejores para los más grandes. Además de esto, como ya se ha explicado, E Aquel que lo intentó y no lo consiguió es superior al que ni lo intentó. - Arquímedes- Conclusiones 32 las mejores soluciones se obtienen para los valores de δ=0 en todos los casos estudiados, ya que es en ese momento cuando el valor de épsilon es mayor. A partir de aquí, éste va disminuyendo, dejando menos posibilidad a secuencias factibles, por lo que los valores del total weighted completion time del conjunto A van empeorando a medida que épsilon disminuye. Esto se debe a que, aunque al principio tenemos que los trabajos de B están más a la derecha en la secuencia y los de A más a la izquierda, a medida que delta aumente (épsilon disminuye) la factibilidad será más difícil, por lo que los trabajos de B tendrán que desplazarse más a la izquierda y los de A más a la derecha, aumentando así el valor de la FO de A. Con este objetivo que se ha propuesto (total weighted completion time), si cada conjunto de trabajos pertenece a unos clientes diferentes y cada trabajo tiene una prioridad (peso) distinta, se pretende minimizar el tiempo medio de terminación de los trabajos de cada conjunto teniendo en cuenta dichas prioridades. Como se ha dicho, cada conjunto de trabajos pertenecerá a un agente, y ambos agentes competirán en el uso de unos recursos comunes en el proceso de fabricación. Por tanto, la meta será encontrar un programa que minimice una combinación de los objetivos de ambos agentes, que dependen del tiempo de finalización de sus trabajos. Poniendo como ejemplo una empresa que fabrique productos para dos clientes diferentes, deberá tratar de satisfacer los objetivos de ambos clientes. Con el método expuesto, se intentan satisfacer estos objetivos. Sin embargo, debido a la dificultad de minimizar ambos objetivos a la vez, se tomará como principal a uno de estos clientes (en el caso estudiado es el conjunto A), minimizando sus tiempos de fabricación, mientras se establecen unos límites de tiempo que los objetivos del segundo cliente (conjunto B) no podrán sobrepasar. De esta forma, siempre uno de los dos clientes, cuyos objetivos son los que se minimizarán, obtendrá unos resultados más beneficiosos. 33 6 REFERENCIAS Lei, D. (2015). Variable neighborhood search for two-agent flow shop scheduling problem. Ahmadi-Darania, M. H., Moslehia, G. & and Reisi-Nafchia, M. (2018). A two-agent scheduling problem in a two-machine flowshop. Pérez González, P., Fernández-Viagas, V. & Framiñán, J. M. (2020). Programación y Control de la Producción. Ballesteros Silva, P. P., Ballesteros Riveros, D. P. & Bravo Bolívar, J. E. (2013). Application a constructive heuristic sequential programming for assigning multiple jobs to multiple machines in parallel. Pinedo, M. L. (2012). Scheduling: Theoty, Algotithms, and Systems. Lozano Segura, S. (2020). Métodos de optimización Hansen, P., Mladenovic, N. & Moreno Pérez, J. A. (2003). Variable Neighbourhood Search. Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial. (No.19). Osorio Muriel, A. F., Brailsford, S. & Smith, H. (2014). Un modelo de optimización bi-objetivo para la selección de tecnología y asignación de donantes en la cadena de suministro de sangre. Revista S&T, 12(30). Laumanns, M., Thiele, L. & Zitzler, E. (2006). An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. European Journal of Operational Research (169). Pérez González, P., Fernández-Viagas, V. & Framiñán, J. M. (2020). Permutation flowshop scheduling with periodic maintenance and makespan objective. Mavrotas, G. (2009). Effective implementation of the e-constraint method in Multi-Objective Mathematical Programming problems. Chicano García, J. F. (2007). Tesis doctoral: Metaheurísticas e Ingeniería del Software. Alancay, N., Villagra, S. & Villagra. A. (2014). Metaheurísticas de trayectoria y poblacional aplicadas a problemas de optimización combinatoria. Referencias 34 35 7 ANEXO ara concluir, en este último apartado se incluye el código en C completo que se ha programado para el estudio del problema de flowshop de permutación de dos máquinas con dos conjuntos de trabajos para el total weighted completion time. Además, se incluye también el código elaborado para la generación de las instancias que posteriormente has sido resueltas y estudiadas. 7.1 Código en c #include <schedule.h> #include <stdio.h> #include <stdlib.h> #include <time.h> int *processtime(int N, int M, MAT_INT PT); double FObjConjuntoA (int N, int M, VECTOR_DOUBLE Wj, VECTOR_INT orden, VECTOR_INT Ctime); double FObjConjuntoB (int N, int M, VECTOR_DOUBLE Wj, VECTOR_INT orden, VECTOR_INT Ctime); int *v1_swap(int N, VECTOR_INT A); int *v2_insert(int N, VECTOR_INT B); int *v3_learner(int N, VECTOR_INT C); void output(char*entrada,char*salida,int N,VECTOR_INT secuenciafinal,double FO_final, double epsilon); int *completiontime(int N, VECTOR_INT orden, MAT_INT PT); MAT_INT LecturaInstancias(char *filename, int *jobs, int *machs, double *epsilon, int print_flag); VECTOR_DOUBLE LecturaInstancias2(char *filename, int *jobs, int *machs, double *epsilon, int print_flag); int main(int argc, char *argv[]) { int n; int n_a; int m; P Anexo 36 36 int j, k, i; double eps; srand(time(NULL)); LecturaInstancias(argv[1],&n,&m,&eps,YES); LecturaInstancias2(argv[1],&n,&m,&eps,NO); MAT_INT tiempos_proceso = DIM_MAT_INT(m,n); tiempos_proceso = LecturaInstancias(argv[1],&n,&m,&eps,NO); VECTOR_DOUBLE w = DIM_VECTOR_DOUBLE(n); w = LecturaInstancias2(argv[1],&n,&m,&eps,NO); n_a = n/2; VECTOR_INT suma_p = DIM_VECTOR_INT(n); suma_p = processtime(n, m, tiempos_proceso); VECTOR_INT p_a = DIM_VECTOR_INT(n_a); VECTOR_INT p_b = DIM_VECTOR_INT(n_a); for(j=0; j<n_a; j++) { p_a[j]=suma_p[j]; } j=n_a; for(k=0; k<n_a; k++) { p_b[k]=0; if(j<n) { p_b[k] = suma_p[j]; j++; } } //CREAR SECUENCIA DE PARTIDA WSPT 37 37 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo VECTOR_DOUBLE v = DIM_VECTOR_DOUBLE(n); VECTOR_DOUBLE v_a = DIM_VECTOR_DOUBLE(n_a); VECTOR_DOUBLE v_b = DIM_VECTOR_DOUBLE(n_a); for(j=0; j<n_a; j++) { v_a[j]=w[j]/p_a[j]; } j=n_a; for(k=0; k<n_a; k++) { v_b[k]=0; if(j<n) { v_b[k] = w[j]/p_b[k]; j++; } } for(j=0; j<n; j++) { v[j]=w[j]/suma_p[j]; } VECTOR_INT WSPT = DIM_VECTOR_INT(n); VECTOR_INT WSPT_a = DIM_VECTOR_INT(n_a); VECTOR_INT WSPT_B = DIM_VECTOR_INT(n_a); sort_vector(v_a, WSPT_a, n_a, 'D'); sort_vector(v_b, WSPT_B, n_a, 'D'); VECTOR_INT WSPT_b = DIM_VECTOR_INT(n_a); for(j=0; j<n_a; j++) { WSPT_b[j]=WSPT_B[j]+n_a; } for(j=0;j<n_a;j++){ WSPT[j]=WSPT_b[j]; } Anexo 44 44 { CB[k]=Ctime[j]; WB[k]=W[j]; k++; } } double FOA=0; for(j=0; j<M; j++) { FOA=FOA+WA[j]*CA[j]; } return FOA; } double FObjConjuntoB (int N, int M, VECTOR_DOUBLE Wj, VECTOR_INT orden, VECTOR_INT Ctime) { int j,i,k; double W[N]; for(j=0; j<N; j++) { W[j]=Wj[orden[j]]; } //FUNCION OBJETIVO CONJUNTO B VECTOR_DOUBLE WA = DIM_VECTOR_DOUBLE(M); VECTOR_DOUBLE WB = DIM_VECTOR_DOUBLE(M); i=0; k=0; int CA[M]; int CB[M]; for(j=0; j<N; j++) { if(orden[j]<M) { CA[i]=Ctime[j]; 45 45 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo WA[i]=W[j]; i++; } else { CB[k]=Ctime[j]; WB[k]=W[j]; k++; } } double FOB=0; for(j=0; j<M; j++) { FOB=FOB+WB[j]*CB[j]; } return FOB; } int *v1_swap(int N, VECTOR_INT A) { int *resultado = malloc(N*sizeof(int)); copy_vector(A,resultado,N); int a1 = rand()%N; int a2 = rand()%N; if(a1==a2) { a1 = rand()%N; a2 = rand()%N; } resultado[a1]=A[a2]; resultado[a2]=A[a1]; return resultado; free(resultado); resultado=NULL; } Anexo 46 46 int *v2_insert(int N, VECTOR_INT B) { int *resultado = malloc(N*sizeof(int)); copy_vector(B,resultado,N); int random1 = rand()%N; int random2 = rand()%N; int a = search_vector(resultado,N,random1); extract_vector(resultado,N,a); insert_vector(resultado,N,B[a],random2); return resultado; free(resultado); resultado=NULL; } int *v3_learner(int N, VECTOR_INT C) { int i, j; int *resultado = malloc(N*sizeof(int)); int L[N]; for(i=0; i<N; i++) { L[i]=10000; } VECTOR_INT sec = DIM_VECTOR_INT(N); VECTOR_INT copia_sec = DIM_VECTOR_INT(N); randSequence(sec,N); copy_vector(sec,copia_sec,N); int aleat = rand()% N/2 + 1; VECTOR_INT aleatorio = DIM_VECTOR_INT(aleat); for(i=0; i<aleat; i++) { int num=rand()%N; if(i>0) { for(j=0; j<i; j++) 47 47 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo { if(num==aleatorio[j]) { num=rand()%N; j=-1; } } } aleatorio[i]=num; } int c1, c2; for(i=0; i<aleat; i++) { c1 = search_vector(sec,N,aleatorio[i]); c2 = search_vector(C,N,aleatorio[i]); extract_vector(C,N,c2); extract_vector(L,N,c1); extract_vector(copia_sec,N,c1); insert_vector(L,N,aleatorio[i],c1); } j=0; for(i=0; i<N; i++) { if(sec[i]!=L[i]) { extract_vector(L,N,i); insert_vector(L,N,C[j],i); j++; } } copy_vector(L,resultado,N); return resultado; free(resultado); resultado=NULL; } void output(char*entrada,char*salida,int N,VECTOR_INT secuenciafinal,double FO_final, double epsilon) Anexo 48 48 { FILE *fichero; int j; fichero = fopen(salida, "a"); if(fichero==NULL) { printf("\nNo se puede abrir el archivo de salida\n"); return -1; } else { fprintf(fichero,"\nSecuencia= "); for(j=0; j<N; j++) { fprintf(fichero,"%d ",secuenciafinal[j]); fprintf(fichero,"\nValor %d de la secuencia final:: %d \n", j, secuenciafinal[j]); } fprintf(fichero, "\nEpsilon vale: %f\n", epsilon); fprintf(fichero,"%f\n", FO_final); } fclose(fichero); } int *completiontime(int N, VECTOR_INT orden, MAT_INT PT) { int j,i; int *resultado = malloc(N*sizeof(int)); VECTOR_INT C1 = DIM_VECTOR_INT(N); VECTOR_INT C2 = DIM_VECTOR_INT(N); VECTOR_INT p1 = DIM_VECTOR_INT(N); VECTOR_INT p2 = DIM_VECTOR_INT(N); for(j=0; j<N; j++) { i=0; 49 49 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo p1[j]=PT[i][orden[j]]; i=1; p2[j]=PT[i][orden[j]]; } C1[0]=p1[0]; C2[0]=C1[0]+p2[0]; for(j=1; j<N; j++) { C1[j]=C1[j-1]+p1[j]; } for(j=1; j<N; j++) { if(C2[j-1]<=C1[j]) { C2[j]=C1[j]+p2[j]; } else { C2[j]=C2[j-1]+p2[j]; } } copy_vector(C2,resultado,N); return resultado; free(resultado); resultado=NULL; } MAT_INT LecturaInstancias(char *filename, int *jobs, int *machs, double *epsilon, int print_flag) { FILE *data; int temp_data; register int i,j; Anexo 50 50 MAT_INT pt; VECTOR_DOUBLE W; if (!(data = fopen(filename,"rt"))) error(2,STOP, filename); fscanf(data,"%d\n", &temp_data); *(machs) = temp_data; fscanf(data,"%d\n", &temp_data); *(jobs) = temp_data; pt = DIM_MAT_INT((*machs),(*jobs)); W = DIM_VECTOR_DOUBLE((*jobs)); for(i=0; i<(*machs); i++) { for(j=0; j<*(jobs); j++) { fscanf(data,"%10d", &temp_data ); pt[i][j] = temp_data; } fscanf(data,"\n"); } for(j=0; j<(*jobs); j++){ fscanf(data,"%10d", &temp_data ); W[j]=temp_data; } fscanf(data,"\n"); fscanf(data,"%d\n", &temp_data); *(epsilon) = temp_data; fclose(data); if(print_flag == YES) { printf("Instance %s - n: %d m: %d\n",filename, *(jobs), *(machs)); 51 51 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo print_int_matrix(pt, *(machs), *(jobs) ); print_double_vector(W,*(jobs)); printf("EPSILON = %f\n", *(epsilon)); } return pt; } VECTOR_DOUBLE LecturaInstancias2(char *filename, int *jobs, int *machs, double *epsilon, int print_flag) { FILE *data; int temp_data; register int i,j; MAT_INT pt; VECTOR_DOUBLE W; if (!(data = fopen(filename,"rt"))) error(2,STOP, filename); fscanf(data,"%d\n", &temp_data); *(machs) = temp_data; fscanf(data,"%d\n", &temp_data); *(jobs) = temp_data; pt = DIM_MAT_INT((*machs),(*jobs)); W = DIM_VECTOR_DOUBLE((*jobs)); for(i=0; i<(*machs); i++) { for(j=0; j<*(jobs); j++) { fscanf(data,"%10d", &temp_data ); pt[i][j] = temp_data; } fscanf(data,"\n"); } Anexo 52 52 for(j=0; j<(*jobs); j++){ fscanf(data,"%10d", &temp_data ); W[j]=temp_data; } fscanf(data,"\n"); fscanf(data,"%d\n", &temp_data); *(epsilon) = temp_data; fclose(data); if(print_flag == YES) { printf("Instance %s - n: %d m: %d\n",filename, *(jobs), *(machs)); print_int_matrix(pt, *(machs), *(jobs) ); print_double_vector(W,*(jobs)); printf("EPSILON = %f\n", *(epsilon)); } return W; } 7.2 Código de generación de instancias #include <schedule.h> #include <stdio.h> #include <stdlib.h> #include <time.h> double FObjConjuntoB (int N, int M, VECTOR_INT Wj, VECTOR_INT orden, VECTOR_INT Ctime); int *completiontime(int N, VECTOR_INT orden, MAT_INT PT); int main(int argc, char *argv[]) { int j, i, k; int n; int m=2; 53 53 Metaheurísticas aplicadas al problema de Flowshop de permutación con dos conjuntos de trabajo n=atoi(argv[1]); char *salida = argv[2]; int n_a = n/2; srand(time(NULL)); MAT_INT tiempos_proceso = DIM_MAT_INT(m,n); VECTOR_INT w = DIM_VECTOR_INT(n); for(j=0; j<n; j++) { for(i=0;i<m;i++){ tiempos_proceso[i][j] = rand()%100+1; } } for(j=0; j<n; j++) { w[j] = rand()%100+1; } //WSPT VECTOR_DOUBLE suma_p =DIM_VECTOR_DOUBLE(n); for(j=0; j<n; j++) { suma_p[j]=0; for(i=0; i<m; i++) { suma_p[j]+=tiempos_proceso[i][j]; } } VECTOR_DOUBLE v = DIM_VECTOR_DOUBLE(n); VECTOR_DOUBLE v_a = DIM_VECTOR_DOUBLE(n_a); VECTOR_DOUBLE v_b = DIM_VECTOR_DOUBLE(n_a);