Algoritmi di pianificazione utilizzati in una griglia
-
27-10-2019 - |
Domanda
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.
Soluzione
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.
Altri suggerimenti
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.
Floyd-Warshall per grafici bipartiti e algoritmo Blossom di Edmond per grafico non bipartito.