Estudio de Modelos Teóricos de tipo NP-completos en el Laboratorio Nacional de GRIDS de Súper Cómputo, Utilizando Algoritmos Evolutivos de Optimización con Técnicas de Procesamiento Distribuido”

Alcance de la propuesta: Se trabajará con dos modelos teóricos de asignación de recursos. El primer modelo es el que representa a una cadena de suministro y el segundo es el que representa a la asignación de recursos en un taller de manufactura. Se trabajará con instancias grandes de estos modelos utilizando algoritmos evolutivos.

 

Resumen completo

A la fecha se ha realizado poco trabajo para tratar problemas de optimización de tipo NP-duro de tamaño grande utilizando grids. Generalmente este tipo de problemas de optimización se tratan en equipos que cuentan con unos cuantos CPU’s. Estos problemas por ser de gran complejidad requieren primero del diseño de algoritmos eficientes/eficaces y después de la ejecución de estos algoritmos en equipos de cómputo con gran poder de procesamiento como lo pueden ser las grids. Fujisawa, fue unos de los primeros pioneros en el estudio de problemas de tipo NP-duros en sistemas grid [Fujisawa, et al., 2004]. 

 

Reporte completo

En base a las dificultades que se tuvieron para poder acceder al Laboratorio Nacional de GRID de Súper Cómputo, debido a que éste aun no está disponible para dar servicio puesto que está en etapa de pruebas y acorde a la necesidad del proyecto de trabajar en una GRID, se decidió por parte del grupo de trabajo, implementar una MiniGRID UAEM-ITVer, de cómputo de alto rendimiento con comunicación a través de Internet 2. En esta GRID llamada Tarántula, se realizaron y aun está realizándose el estudio de dos modelos teóricos de tipo NP completos [Papadimitriou and Steiglitz, 82]. El primer modelo es el Problema de una Cadena de Suministros con Ventanas de Tiempo [Toth and Vigo, 01]. El segundo modelo es el Problema de Calendarización de Trabajos en Talleres de Manufactura [Roy and Sussman, 64]. 

 

Reporte final completo

Investigador Líder