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

Question

[tnick1502]

Есть некоторое количество приборов (входной параметр, может быть разным). Также есть некоторое число опытов, каждый из которых имеет свое время выполнения (также набор входных параметров). Суть задачи состоит в том, чтобы распределить эти опыты по приборам так, чтобы общее время выполнения всех опытов было минимальным.
Если кто-то сталкивался с подобным, покидайте литературу по теме, также ссылки на похожие задачи с решением.

Answer 1

[dmshar]

В общем виде задача называется "Оптимальное распределение ресурсов".
Изучается обычно в рамках курсах "Методы математической оптимизации", "Исследование операций", "Линейное и динамическое программирование" и т.д.

Учебников масса - начиная с классики:
Вентцель Е. С. Исследование операций: задачи, принципы, методология.

Comments

[BorLaze]

Она же - задача о раскрое.

Тысячи их.

[tnick1502]

Большое спасибо за ответы!

Answer 2

[Adamos]

Именно эту задачу необязательно решать в общем виде, если "приборы" и "опыты" одинаковы, то есть не имеют дополнительных условий.
Достаточно отсортировать опыты от длинных к коротким и распределить их в цикле, выбирая под каждый следующий тот прибор, у которого минимальна сумма времени уже назначенных опытов.
Disclamer: Алгоритм может выдавать не самое оптимальное решение из возможных. Зато он будет делать это значительно быстрее любых переборов.

Comments

[Wataru]

Этот жадный алгоритм не работает. Тут вообще нет жадности.

вот пример 2 станка, 5 работ {10,9,3,2,2} - ваш алгоритм вернет {{10,2},{9,3,2}}. максимум 14. Хотя можно 3 положить не к 9, а к 10, и получить {{10,3},{9,2,2}} - максимум 13.

[Adamos]

Илья Николаевский, спасибо за пример!
Да, идеальное решение не гарантируется, этот вариант - скорее для ситуации, когда "работы" добавляются динамически и не могут быть просчитаны заранее.

[tnick1502]

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

[Adamos]

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

[Wataru]

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

Answer 3

[Wataru]

Это сложная задача - тут нет простого и быстрого алгоритма.

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

Если нужно не обязательно оптимальное решение - а что-то не слишком ужасное, то можно делать жадность, как Adamos предложил.

Answer 4

[xmoonlight]

Такая (многомерная) "упаковка" делается только рекурсивным эволюционным алгоритмом, и быстрее и точнее - больше никак.
Сложность (максимум): (n*log(n))^n.

Comments

[tnick1502]

Спасибо за ответ