Algoritmos de programación utilizados en una grilla: algoritmo, grilla, programación de recursos

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

Respuestas

Existen muchos Algoritmos de programación de trabajo que pueden serparalelizado Debe comenzar con una revisión de la literatura o una buena referencia, como los "algoritmos de programación" de Brucker. "Los detalles de su dominio probablemente permitan o no varios enfoques de tiempo pseudo-polinomiales.

Programación de la tienda de trabajo 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 tratar con problemas completos de NP, como Búsqueda tabú, Algoritmos genéticos, Recocido Simulado, ... Algunos de los cuales pueden ser multiproceso fácilmente (otros duros). Pero la ganancia de los subprocesos múltiples es relativamente pequeña en comparación con la ganancia de mejorar el algoritmo. Ver esta diapositiva para el efecto de mejorar la CPU / multi-threading VS mejorar el algoritmo con uno de los ejemplos de Drools Planner.

Floyd-Warshall para gráficos bipartitos y el algoritmo Blossom de Edmond para gráficos no bipartitos.