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

Question

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

Answer 1

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

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

Answer 2

Флойд-Варшалл для двудольных графов и алгоритм Эдмонса Блоссома для двудольных графов.

Answer 3

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