@tnick1502

Как решить задачу оптимального распределения задач по времени среди определенного количества исполнителей?

Есть некоторое количество приборов (входной параметр, может быть разным). Также есть некоторое число опытов, каждый из которых имеет свое время выполнения (также набор входных параметров). Суть задачи состоит в том, чтобы распределить эти опыты по приборам так, чтобы общее время выполнения всех опытов было минимальным.
Если кто-то сталкивался с подобным, покидайте литературу по теме, также ссылки на похожие задачи с решением.
  • Вопрос задан
  • 68 просмотров
Решения вопроса 4
@dmshar
В общем виде задача называется "Оптимальное распределение ресурсов".
Изучается обычно в рамках курсах "Методы математической оптимизации", "Исследование операций", "Линейное и динамическое программирование" и т.д.

Учебников масса - начиная с классики:
Вентцель Е. С. Исследование операций: задачи, принципы, методология.
Ответ написан
Adamos
@Adamos
Именно эту задачу необязательно решать в общем виде, если "приборы" и "опыты" одинаковы, то есть не имеют дополнительных условий.
Достаточно отсортировать опыты от длинных к коротким и распределить их в цикле, выбирая под каждый следующий тот прибор, у которого минимальна сумма времени уже назначенных опытов.
Disclamer: Алгоритм может выдавать не самое оптимальное решение из возможных. Зато он будет делать это значительно быстрее любых переборов.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Это сложная задача - тут нет простого и быстрого алгоритма.

Можно свести ее к integer linear programming и решать какой-то из множества существующих библиотек/солверов. Если числа маленькие, то можно или полный перебор или какую-то динамику, типа решения задачи о рюкзаке сделать (тут надо будет набранные суммы во всех приборах взять в параметры).

Если нужно не обязательно оптимальное решение - а что-то не слишком ужасное, то можно делать жадность, как Adamos предложил.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Такая (многомерная) "упаковка" делается только рекурсивным эволюционным алгоритмом, и быстрее и точнее - больше никак.
Сложность (максимум): (n*log(n))^n.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы