Enfoque multihebrado del algoritmo de resolución del problema de bi-mezcla

Abstract

Los algoritmos de dise˜no de mezclas tienen como objetivo determinar las mezclas de ingredientes que se ajustan a las restricciones de dise˜no impuestas para el producto en cuesti´on. Estas restricciones pueden ser lineales y/o cuadr´aticas. Se quiere minimizar el coste y el n´umero de ingredientes utilizados, n´otese que con m´as ingredientes se puede obtener menor coste. Los fabricantes elaboran una serie de productos a partir de un conjunto dado de materias primas. La escasez en la disponibilidad de estas materias primas introduce restricciones de disponibilidad que alteran la soluci´on Pareto-´optima. Los autores han desarrollado algoritmos de Ramificaci´on y Acotaci´on para resolver problemas de mezcla en donde la complejidad computacional se incrementa con el n´umero de posibles ingredientes para elaborar el producto. Debido a esta complejidad, se abordar´a el problema de mezcla para la obtenci´on de s´olo dos productos. El dise˜no de mezclas para dos productos es m´as dif´ıcil que para un ´unico producto porque adem´as de que el dise˜no de cada producto est´a sometido a unas restricciones, el frente de Pareto as´ı como la disponibilidad de materias primas pasan a ser comunes a ambos productos. Se debe realizar una combinaci´on final entre todas las soluciones encontradas del primer y el segundo producto para eliminar las combinaciones de mezclas que no satisfacen los criterios impuestos. El conjunto resultante puede ser usado como dato de entrada del mismo algoritmo cuando se requieran resultados m´as precisos. El coste computacional de la fase de combinaci´on depender´a del n´umero de elementos del conjunto final de cada producto. Aqu´ı, estudiaremos el coste computacional de las diferentes fases del algoritmo de mezcla para dos productos y proporcionaremos dos versiones hebradas para la fase m´as costosa. Los experimentos se han realizado en una m´aquina de ocho n´ucleos con memoria compartida, usando un problema de tama˜no medio para evitar largos tiempos de ejecuci´on. Los experimentos muestran que la computaci´on paralela es una herramienta necesaria para hacer una b´usqueda exhaustiva en problemas de grandes dimensiones y de m´as de un producto.