Algoritmi di pianificazione utilizzati in una griglia

Question

Sto cercando di simulare la pianificazione in un ambiente a griglia. Non so quali algoritmi usare. Sto prendendo in considerazione l'algoritmo di programmazione http://en.wikipedia.org/wiki/job_shop_scheduling Ma non so se viene utilizzato nelle griglie. Quali algoritmi vengono generalmente utilizzati in ambienti di griglia per pianificare i lavori in arrivo alle risorse?. Qualsiasi aiuto sarebbe molto apprezzato. Grazie.

Answer 1

Ci sono molti Algoritmi di pianificazione del lavoro che possono essere parallelizzati. Dovresti iniziare con una recensione della letteratura o un buon riferimento, come gli "algoritmi di pianificazione" di Brucker. È probabile che i dettagli del tuo dominio consentano o vietino vari approcci di tempo pseudo-polinomiale.

Answer 2

Pianificazione del negozio di lavoro Non è un algoritmo, è un problema per quanto ne so.

Se hai 3 o più macchine, lo è NP completo. Ci sono un sacco di algoritmi che possono affrontare i problemi completi di NP, come Ricerca tabu, Algoritmi genetici, Ricottura simulata, ... alcuni dei quali possono essere facilmente multi-thread (altri difficili). Ma il guadagno del multi-threading è relativamente piccolo rispetto al guadagno di miglioramento dell'algoritmo. Vedere questa diapositiva per l'effetto di migliorare la CPU/multi-threading vs miglioramento dell'algoritmo con uno degli esempi di Pianificatore sbava.

Answer 3

Floyd-Warshall per grafici bipartiti e algoritmo Blossom di Edmond per grafico non bipartito.