Algoritmos para la programación de la producción en un entorno de flujo regular distribuido de permutación

Abstract

Este proyecto implica la documentación, estudio y posterior implementación de un Algoritmo de Optimización basado en la Biogeografía para un tipo Flow-Shop de permutación distribuido. Estos tipos de problemas consta de dos etapas: producción y montaje (en este documento nos centramos en la etapa de producción), en la que los productos se producen de forma secuencial. Éstos se elaboran por partes en distintas fábricas para que en el caso de que fallase alguna, la producción no se detenga. Para ello, habrá que tener claro en qué se fundamenta la optimización basada en la biogeorafía y como funciona el Algoritmo. Después de hacer la correspondiente implementación se transcurrirá a la comparación de resultados entre los distintos algoritmos que existen para resolver este problema: algoritmo HBBO y la Heurística basada en la inserción (HBI) de Hatami (2013). Antes de describir el problema es necesario tener unos conocimientos previos, como por ejemplo qué es un Flow-Shop, qué tipos de entornos existen en la programación de operaciones, los tipos de restricciones que se pueden dar y qué tipo de objetivos se plantean en las fábricas. Todas estas explicaciones están elaboradas en el capítulo 2 del documento. En la descripción de los algoritmos que se ha realizado en el apartado 3 se han incorporado la explicación de las funciones más importantes utilizadas, además de alguna suposición que se ha tomado debido a qué no se han tenido los datos suficientes para abordarlo o se han detectado errores en el documento Jian y Shuai (2016). En la implementación se ha utilizado un progama llamado Code::Blocks (comentado en el objeto del problema) que se utiiza para codificar en C, junto con la librería <schedule_lib.h>, para hacer más sencilla la imlementación, ya que esta libería posee una serie de funciones que son utilizadas en la elaboración del documento y facilita la inicialización de elementos como vectores o matrices. Para la comparación de estos dos métodos de programación, se han utilizado una serie de datos que han sido recopilados del documento Jian y Shuai (2016) y que se expresan en el capítulo 4 del proyecto. Los datos a emplear son el número de trabajos (n), el número de máquinas (m), el número de fábricas (F), la cantidad de instancias (smax) y el número de iteraciones máximas a realizar en cada experimento (Itermax). Estos datos tienen dos bloques diferenciados: instancias de pequeño tamaño e instancias de gran tamaño. Los experimentos a elaborar consistirán en la combinación del número de trabajo, máquinas y fábricas (n x m x F) teniendo en cuenta que para cada tamaño de instancias se usa una cantidad de hábitats y número de iteraciones diferentes. Para cada experimento se obtendrá las soluciones que serán comparadas con el fin de comprobar la eficacia del algoritmo. Todos los resultados que se han obtenido se pueden apreciar en el apartado 4 de la memoria, que con la ayuda del Excel para crear tablas y gráficas se han podido realizar la comparación entre ambos métodos y sacar una conclusión. La conclusión final que se puede deducir es que para pequeñas instancias (número de trabajos, máquinas y fábricas pequeños) el algoritmo HBBO es más eficiente que el algoritmo HBI, pero para instancias de gran tamaño (número de trabajos, máquinas y fábricas más grandes) el algoritmo HBBO da peores resultados que el algoritmo HBI. En conclusión, si se trabaja con instancias de pequeño tamaño es más adecuado la utilización del algoritmo HBBO para obtener la mejor solución, pero para instancias de gran tamaño, el uso de algoritmo HBBO resulta ineficiente y el tiempo de obtención de los resultados es mucho mayor, siendo así la utilización del algoritmo HBI una mejor opción.