Алгоритм для преобразования рабочего процесса DAG в параллельное распределение ресурсов?

Скажите, что у меня есть график, где узлы являются рабочими нагрузками различных видов, и края являются зависимостями между рабочими нагрузками. (Это - DAG, так как циклические зависимости не должны существовать.)

У меня также есть ряд нескольких агентов, кто может выполнить работу.

Некоторые варианты рабочей нагрузки могут быть даны любому агенту, другие должны быть склонны к определенному агенту, и другие должны быть склонны к одному агенту среди конкретной группы агентов.

Как делают я присваиваю рабочие нагрузки, таким образом что:

• Никакая рабочая нагрузка не дана агенту, пока все его рабочие нагрузки блокирования не завершаются

• Самое короткое время требуется, чтобы завершать общий график рабочей нагрузки. (Обратите внимание, что уменьшение времени простоя агента обычно хорошо, но не фундаментальное требование - могут быть сценарии, согласно которым один конкретный агент бездействует для дольше, но общее время для завершения всех заданий через все агенты как минимум.)

Рабочие нагрузки имеют оценки продолжительности, но предполагают для пользы простоты, что каждая рабочая нагрузка занимает время для вычислений. (Просто разломайте каждую рабочую нагрузку на несколько, последовательно зависимые рабочие нагрузки, пока каждая рабочая нагрузка не будет эффективно постоянно-разовой операцией.)

Я знаю, что топологический DAG сортирует, но это производит единственное, последовательное упорядочивание узлов. У меня есть несколько агентов, работающих параллельно, и отношения таковы, что потенциально большая оптимизация синхронизации может быть сделана неочевидным переупорядочением задач.

Результат этого был бы представлен лучше всего как Диаграмма Гантта минимальной полной продолжительности. На самом деле при размышлении о проблеме как о выделении уведомлений об ошибках в этап инженерам в команде, с целью получения этапа сделанный ASAP, затем Вы получаете идею. (Не... не говорите мне импортировать свой график в Проект MS и затем экспортировать его :) - что я интересуюсь алгоритмом позади него!)

Указатели на известные алгоритмы, библиотеки программного обеспечения, или общие вопросы и принципы очень ценятся!