RS Paralelo para Máquinas paralelas no relacionadas PDF Imprimir E-mail

El problema general de secuenciado de n trabajos sobre m Máquinas Paralelas no Relacionadas sin interrupciones es clasificado como un problema de tipo NP-Completo [A.M. Garey and D.S. Jonnson,1979].

Investigadores se han enfocado en este tipo de problemas debido a la dureza que el problema representa cuando se busca la solución óptima.

Muchas investigaciones se han hecho en la búsqueda de algoritmos que resuelvan el problema. Por ello, hemos enfocado nuestros esfuerzos en el diseño de algoritmos meta-heurísticos de aproximación eficiente y eficaz. Que muestren un buen desempeño para encontrar soluciones de buena calidad en tiempos de respuesta factibles.

Recocido Simulado paralelizado con memoria distribuida es aplicado sobre un cluster de alto rendimiento. El problema es modelado como un problema de Emparejamiento Bipartita Ponderado.

El estudio de Máquinas Paralelas no Relacionadas es de interés debido a su amplia aplicación en la industria manufacturera. La solución eficiente y eficaz a los modelos teóricos hace un planteamiento más sencillo para el estudio de modelos reales que permitan a la industria para aumentar su grado de competitividad.

Este trabajo presenta una solución al PMPR (acrónimo de Problema de Máquinas Paralelas no Relacionadas) usando un algoritmo de Recocido Simulado para resolver el problema como un problema de Emparejamiento Bipartita Ponderado.

 


Modelo de Programación Lineal Entera Ponderado.

El problema Rm || ΣkCj [1], es un modelo de tipo NP-complete.

 Puede ser formulado como un problema de programación lineal entera (PLE) con una estructura especial que hace posible resolver el problema en tiempo polinomial usando un algoritmo determinista. Este modelo PLE modela el problema como un conjunto de máquinas que deben procesar un conjunto de trabajos, cada trabajo requiere una operación para terminar. Cada máquina puede procesar cualquier trabajo uno a la vez. El tiempo de procesamiento de un trabajo depende de la máquina en la cual se procese.

El problema PLE presentado en [3] es formulado como sigue: La contribución a la función objetivo en (1) de cada trabajo j, depende de la máquina i donde el trabajo j es procesado, así como de la posición k donde el trabajo es procesado en la máquina i, el conjunto de trabajos que se procesan en la máquina i es ordenado. El trabajo j contribuye en kpij al valor de la función objetivo. La función objetivo optimiza el tiempo total de termino ponderado (ΣkCj). En este modelo, la restricción en (4) indica que las variables x toman solo el valor de 0 ó 1. Si xikj = 1, entonces el trabajo j es asignado a la máquina i en la k-th posición. Si xikj= 0, en caso contrario. Las restricciones en (2) aseguran que cada trabajo es asignado a una solo posición k. Las restricciones en (3) aseguran que cada posición k para cada máquina i es tomado por al menos un trabajo j. Este modelo puede ser mapeado para problemas de transporte [4] si las restricciones del conjunto (4) son reemplazadas por un conjunto de restricciones de valores no negativos, esto es, xikj >= 0. Esto es importante debido a que con este modelo relajado se obtendrían límites con algoritmos exactos para problemas NP-Completos como el modelo Rm|| Cj. En el caso del modelo con la presente estructura, la formulación relajada tiene resultados de 0 o 1 para las variables x. De esta manera, es posible usar un algoritmo exacto como el SIMPLEX en el sentido de tener una solución para el modelo sin necesidad de relajar las restricciones en (4).

Modelo de Grafos Bipartita.

Un caso especial del problema de transporte es el PEBP (acrónimo de Problema de Emparejamiento Bipartita Ponderado). El modelo Rm || kCj para la estructura definida en la PLE en la sección 2 puede ser representado como PEBP [3].

La figura 1 presenta una instancia de 3 trabajos y 2 máquinas para el problema Rm || kCj usando un grafo bipartita. El grafo esta compuesto de n trabajos y mn posiciones donde cada máquina puede procesar a lo más n trabajos. El trabajo j que es asignado a la posición ik presenta un costo kpij. El objetivo es determinar la asignación ik para cada trabajo j en el grafo bipartita que tenga el mínimo costo de tiempo total.

La interpretación se da sobre la base de la figura 1 como sigue: Para la máquina i=1 el trabajo j=1 puede ser procesado en primer lugar (p11), segundo lugar (2p11) o en tercer lugar (3p11). El trabajo j=2 puede ser procesado en primer lugar (p12), segundo lugar (2p12) o en tercer lugar (3p12). El trabajo j=3 puede ser procesado en primer lugar (p13), segundo lugar (2p13) o en tercer lugar (3p13).

Metodología de Solución.

Para solucionar el problema Rm || kCj usando programación paralela con memoria distribuida, la siguiente metodología es propuesta basado en el grafo bipartita (Figura 1) y consiste en los siguientes pasos:

  1. Representación simbólica del grafo bipartita.
  2. Determinar la estructura de vecindad que obtenga soluciones factibles.
  3. Sintonizar los parámetros de RS. T, r, MCS y FROZEN.
  4. Aplicar la meta-heurística de RS secuencial y paralelizado.
  5. Aplicar mecanismo generador de soluciones.
  6. Aplicar mecanismo para recolectar soluciones en el cluster. 

Mecanismo para recolectar soluciones en el cluster.

Se desarrolló una modificación al algoritmo de RS para permitir su ejecución en paralelo. Esta modificación consiste en agregar funciones para el pase de mensajes entre el proceso de control (llamado proceso maestro) y los diferentes procesos de los nodos del cluster (llamados procesos esclavos). El número de procesos que se ejecutan en cada nodo es igual al número de procesadores que tenga cada nodo en particular, esto es, a cada proceso le corresponde un solo procesador. Conocido como MPI (Interfase de Pase de Mensajes) este estándar permite agregar paralelismo a las aplicaciones con memoria distribuida.

El algoritmo de RS paralelo maestro recolecta las soluciones obtenidas por los procesos de RS esclavos. Esto significa que cada proceso de RS esclavo envía el óptimo encontrado al proceso maestro. De esta manera el óptimo global de los RS esclavos puede ser obtenido por el RS maestro. Cuando se encuentran más de un óptimo Global igual se toma el que tiene menos tiempo de procesamiento. En la figura 9a los p procesos esclavos de los n nodos del cluster ejecutan el RS cada uno con su propia solución inicial, en cada ciclo MCS los p procesos esclavos generan soluciones aleatorias y al término descienden la temperatura. Este proceso se repite hasta llegar al punto de congelación FROZEN.

Finalmente los p procesadores esclavos envían el resultado final encontrado al nodo maestro. Entonces el nodo maestro escoge la mejor solución (figura 9b). En caso de encontrar resultados iguales en más de un procesador, se toma el que tenga un tiempo menor de búsqueda.

 

Patrocinadores


CIICAp
Maestrías y Doctorados en: Tecnología Eléctrica, Tecnología Química, Tecnología de Materiales y Tecnología Mecánica.




 

 

Links Relacionados

Mapa de visitas de esta página

Springer
Revista Programación Matemática

Springer

Artículo Mini Grid Morelos
Artículo Mini Grid Morelos

Contador de visitas

mod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_counter
mod_vvisit_counterHoy121
mod_vvisit_counterAyer53
mod_vvisit_counterEsta semana121
mod_vvisit_counterÚltima semana318
mod_vvisit_counterEste més329
mod_vvisit_counterUltimo més1980
mod_vvisit_countertodos los dìas431928