Распараллеливание алгоритма статического планирования является естественным способом уменьшения временной сложности поиска наилучших планов для больших графов задач. Такое распараллеливание особенно полезно для кластеров, потому что функция планирования м. б. внедрена в микропрограммные средства, поддерживающих единое изображение системы путем интеграции с другими системными функциями, такими как управление контрольными точками и миграция потоков. Новый метод, называемый поиском на базе кластеров (CBS), позволяет параллельно планировать большие графы задач на гетерогенном кластере рабочих станций, связанных посредством высокоскоростной сети (напр., с использованием АТМ переключателя при ОС-3 скорости). CBS алгоритм использует параллельный случайный поиск в окрестности, который осуществляется путем одновременного уточнения множества различных начальных планов с использованием различных рабочих станций.