У меня есть задачи с известной целой длиной их продолжительности. Задачи также имеют зависимости между ними. У меня также есть произвольное количество рабочих, на которых я могу запланировать эти задачи.
Я хотел бы найти оптимальное расписание для них таким образом, чтобы я, во-первых, минимизировал общую продолжительность выполнения всех задач, а во-вторых, я хотел бы запланировать задачу на работнике, в котором было выполнено большинство предыдущих зависимостей. прежде, и в-третьих, я хотел бы свести к минимуму количество работников, необходимых.
Так что, если задача имеет зависимости A, B и C, и worker1 запускает A и B, worker2 запускает C, то я бы предпочел, чтобы новая задача была добавлена в worker1.
Я делаю визуализацию для потока выполнения программы, и задачи на самом деле являются вызовами функций (с известным числом операций), а зависимости являются зависимостями данных. Вместо одного длинного линейного представления я хотел бы визуализировать независимые вызовы параллельно. Я рассматриваю эту проблему как аналог задачи планирования задач, описанной выше.
В моем первом простом подходе мне удалось оптимизировать длину всего выполнения, но если задачи не имеют предшествующей зависимости, они добавляют их к своим работникам. Даже если в существующих рабочих есть неиспользуемые дыры. Поэтому я не уверен, как оптимизировать как длину, так и количество работников. Прежде чем тратить на это больше времени, мне было интересно, есть ли какой-нибудь известный алгоритм для решения этой проблемы, даже библиотека, которую я мог бы просто использовать.
Этот вопрос не является дубликатом этого , потому что:
- Задачи не имеют срока выполнения, но есть зависимости.
- Я хотел бы запланировать задачи на том же работнике, на котором были запланированы предыдущие зависимости.
- Возможны несколько дополнительных работников, а не только один.