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

Question

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

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

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

Как назначить рабочие нагрузки, такие, что:

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

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

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

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

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

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

Answer 1

Если у вас нет бесконечного количества агентов, чтобы доступный совместимый агент был доступен, как только все предшественники задачи будут выполнены, это проблема с NP-трудностью.

< бесстыдный штепсель>

Очень похожая проблема есть в моей книге "Algorithms For Interviews"

</бесстыжие плагин>

Вот проблема и решение из книги:

Нам нужно запланировать N лекций в классах M. Некоторые из этих лекций являются предпосылками для других. Как бы вы выбрали, когда и где проводить лекции, чтобы закончить все лекции как можно скорее?

Нам дается набор лекций продолжительностью N единиц и классных комнат M. Лекции могут проводиться одновременно, пока в одном классе не должно проходить две лекции одновременно, и все ограничения приоритета выполняются. Проблема планирования этих лекций, чтобы свести к минимуму время до завершения, как известно, является NP-полной. Эта проблема, естественно, смоделирована с использованием графиков. Мы моделируем лекции как вершины с ребром от вершины u до вершины v, если u является предпосылкой для v. Очевидно, что граф должен быть ацикличным для ограничений приоритета, которые должны быть выполнены. Если есть только одна комната для лекций, мы можем просто проводить лекции в топологическом порядке и заполнять N лекций в N раз (при условии, что каждая лекция имеет длительность единицы). Мы можем разработать эвристику, наблюдая следующее: в любой момент есть набор лекций, приоритеты которых были удовлетворены. Если этот набор меньше M, мы можем запланировать их все; в противном случае нам нужно выбрать подмножество для расписания. Выбор подмножества может быть основан на несколько метриках:

• лекций порядка ранга на основе длину самой длинной цепи зависимостей, что они находятся в самом начале.
• Лекции по порядку рангов, основанные на количестве лекций, для которых они являются неотъемлемыми предпосылками для.
• Лекции по порядку ранжирования, основанные на общем количестве лекций, которые являются прямыми или косвенными предпосылками для.

Мы также можем использовать комбинации этих критериев для заказа лекций, которые в настоящее время планируются. Например, для каждой вершины мы определяем ее критичность как длину самого длинного пути от нее до раковины. Мы планируем лекции, обрабатывая вершины в топологическом порядке. В любой момент нашего алгоритма у нас есть набор кандидатских лекций - это лекции, предварительные условия которых уже запланированы. Если набор кандидатов меньше размера M, мы планируем все лекции; в противном случае мы выбираем M самых важных лекций и планируем их - идея состоит в том, что их следует планировать раньше, так как они находятся в начале более длинных цепочек зависимостей. Критерий эвристический и может не привести к оптимальным расписаниям - этого можно ожидать, так как проблема NP-полная. Можно использовать другие эвристики, например, мы можем использовать количество лекций, которые зависят от лекции L, как критичность лекции L или некоторой комбинации критерия.

Answer 2

Статья в Википедии по адресу PERT может быть полезным местом для начала.