Un estudio sobre la paralelización del método de ramificación y acotación

Abstract

En el presente trabajo se propone un esquema paralelo para dicho método cuando la regla de búsqueda es del tipo primero el de mejor cota. En síntesis el trabajo esta organizado de la siguiente forma: 1) exposición y comentarios de las arquitecturas paralelas y técnicas de diseño de programas para las mismas. 2) revisión de los métodos ya propuestos y sus ventajas e inconvenientes. 3) propuesta de un método paralelo basado en la participación de la lista de nodos vivos en tatas listas como procesadores incorporando funciones de distribución de nodos. 4) estudio de los nodos críticos y su importancia en la evaluación de los algoritmos de ramificación y acotación paralelos. 5) análisis de los requerimientos de comunicación de las dos funciones de distribución propuestas con objeto de prorratear la distribución de los nodos críticos entre todas las listas. 6) estudio de la eficiencia del método propuesto en relación con el de lista única mediante la simulación de la resolución por ambos métodos de problemas generados aleatoriamente.