Алгоритмы планирования, используемые в сетке

Question

Я пытаюсь имитировать планирование в сетке. Я не знаю, какие алгоритмы использовать. Я рассматриваю алгоритм планирования рабочих магазинов http://en.wikipedia.org/wiki/job_shop_scheduling Но не знаю, если он используется в сетках. Какие алгоритмы обычно используются в сетчатых средах для планирования входящих рабочих мест для ресурсов? Любая помощь приветствуется. Спасибо.

Answer 1

Есть много Алгоритмы планирования работ-магазина, которые могут быть параллелизированы. Вы должны начать с обзора литературы или хорошей ссылки, например, «алгоритмы планирования Брэкера». Подробности вашего домена, вероятно, позволят или запретить различные псевдополиномиальные подходы времени.

Answer 2

Расписание магазинов Насколько я знаю, не алгоритм, это проблема.

Если у вас 3 или более машин, это Np завершен. Анкет Есть куча алгоритмов, которые могут решать полные проблемы NP, такие как Поиск табу, Генетические алгоритмы, Имитация отжига, ... некоторые из которых могут быть легко прочитаны (другие жестко). Но прирост многопоточного чтения относительно невелик по сравнению с усилением улучшения алгоритма. Видеть это слайд Для эффекта улучшения процессора/многопоточного по сравнению с улучшением алгоритма с одним из примеров Слюни планируют.

Answer 3

Floyd-Warshall для двухпартийных графиков и алгоритма Blossom Edmond для не-двухпартийного графика.