Алгоритмы планирования, используемые в сетке
Я пытаюсь симулировать планирование в сетке. Я не знаю, какие алгоритмы использовать. Я рассматриваю алгоритм планирования работы магазина http://en.wikipedia.org/wiki/Job_shop_scheduling но не знаю, используется ли он в сетках. Какие алгоритмы обычно используются в сеточных средах для планирования входящих заданий на ресурсы? Любая помощь приветствуется. Благодарю.
3 ответа
Существует много алгоритмов планирования работы, которые можно распараллелить. Вы должны начать с обзора литературы или хорошего справочника, такого как "Алгоритмы планирования" Брукера. Особенности вашего домена могут позволить или запретить различные псевдополиномиальные подходы времени.
Флойд-Варшалл для двудольных графов и алгоритм Блоссома Эдмонда для двудольных графов.
Планирование работы магазина не является алгоритмом, это проблема, насколько я знаю.
Если у вас есть 3 или более машин, это NP завершена. Существует множество алгоритмов, которые могут справиться с задачами NP, такими как поиск по Tabu, генетические алгоритмы, имитация отжига,... Некоторые из них могут быть многопоточными (другие сложными). Но выигрыш от многопоточности относительно невелик по сравнению с улучшением алгоритма. Смотрите этот слайд, чтобы узнать, как улучшить VS / многопоточность VS, улучшив алгоритм на одном из примеров Drools Planner.