Оптимальное планирование задач с переменным количеством работников - PullRequest
0 голосов
/ 08 июля 2019

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

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

Так что, если задача имеет зависимости A, B и C, и worker1 запускает A и B, worker2 запускает C, то я бы предпочел, чтобы новая задача была добавлена ​​в worker1.

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

В моем первом простом подходе мне удалось оптимизировать длину всего выполнения, но если задачи не имеют предшествующей зависимости, они добавляют их к своим работникам. Даже если в существующих рабочих есть неиспользуемые дыры. Поэтому я не уверен, как оптимизировать как длину, так и количество работников. Прежде чем тратить на это больше времени, мне было интересно, есть ли какой-нибудь известный алгоритм для решения этой проблемы, даже библиотека, которую я мог бы просто использовать.

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

  • Задачи не имеют срока выполнения, но есть зависимости.
  • Я хотел бы запланировать задачи на том же работнике, на котором были запланированы предыдущие зависимости.
  • Возможны несколько дополнительных работников, а не только один.

1 Ответ

1 голос
/ 19 июля 2019

Сначала создайте граф зависимостей; см. топологическую сортировку] (https://en.wikipedia.org/wiki/Topological_sorting) для возможной детализации работы.

Применить Алгоритм Дейкстры с перевернутым сравнением, которое найдет самый длинный путь. Это дает вам минимальное время выполнения и критический путь. Имея это в виду, назначьте этот критический путь одному работнику.

Теперь ищите подпути зависимостей, которые включают в себя несколько зависимостей не более, чем в зависимости, которую они заменяют. Например, если у вас есть временная шкала для задач A, B, C, которые нужны D, с суммированием B & C за меньшее время, чем A, вы начнете с этого:

crit   AAAAAADDDDD
other  BBBCC

Вы можете поменять местами дугу с заданием A, предоставив вам новое преференциальное распределение:

worker1 BBBCC-DDDDD
worker2 AAAAAA-----

Это тебя начало?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...