Algoritmos de programación utilizados en una cuadrícula

Question

Estoy tratando de simular la programación en un entorno de cuadrícula. No sé qué algoritmos usar. Estoy considerando algoritmo de programación de la tienda de empleo http://en.wikipedia.org/wiki/job_shop_scheduling Pero no sé si se usa en cuadrículas. ¿Qué algoritmos se utilizan típicamente en entornos de red para programar trabajos entrantes a recursos? Cualquier ayuda sería muy apreciada. Gracias.

Answer 1

Existen muchos Algoritmos de programación de empleo que pueden ser paralelizados. Debe comenzar con una revisión de la literatura o una buena referencia, como los "algoritmos de programación" de Brucker. Es probable que los detalles de su dominio permitan o no permitan varios enfoques de tiempo pseudopolinómico.

Answer 2

Programación de la tienda de empleo No es un algoritmo, es un problema que yo sepa.

Si tiene 3 o más máquinas, es NP completo. Hay un montón de algoritmos que pueden lidiar con problemas completos de NP, como Búsqueda tabú, Algoritmos genéticos, Recocido simulado, ... algunos de los cuales pueden ser multiprocesos fácilmente (otros duros). Pero la ganancia de múltiples subprocesos es relativamente pequeño en comparación con la ganancia de mejorar el algoritmo. Ver esta diapositiva Para el efecto de mejorar la CPU/múltiples subprocesos frente a mejorar el algoritmo con uno de los ejemplos de Planificador de babeo.

Answer 3

Floyd-Warshall para gráficos bipartitos y algoritmo Blossom de Edmond para un gráfico no bipartito.