Минимизировать максимальную сумму элементов матрицы

Дано М команд и N задач. Для каждой команды i известно время t_i,j, за которое будет выполнена задача j (то есть задачу можно представить в виде матрицы M*N с элементами t_i,j).
Каждую задачу может выполнять только одна команда, но у одной команды может быть несколько задач. Нужно распределить задачи по командам таким образом, чтобы минимизировать время выполнения всех задач, то есть предельно уменьшить время работы самой загруженной команды.

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

0

Сообщение от Executus Подскажите решение этой задачи или хотя бы метод

У вас нет исходных данных, поэтому нет "этой задачи". Именно метод решения "подобных задач". Вручную всё делается, сейчас пробую автоматизировать, насколько это возможно.

0

Сообщение от jogano У вас нет исходных данных, поэтому нет "этой задачи". Именно метод решения "подобных задач". Вручную всё делается, сейчас пробую автоматизировать, насколько это возможно.

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

0

Хочу уточнить критерий оптимальности для окончания процесса:
- если нужно минимизировать сумму всех времён выполнения всех заданий, то есть общие затраты времени всех команд, это одно. И это легко сделать сразу.
- если нужно минимизировать время самой загруженной команды, то есть найти такое минимальное время Tmin, чтобы для каждой команды выполнялось Ti<=Tmin, это другое. Тогда суммарное время для всех команд не будет минимальным. Вот это требует нескольких итераций.
Например, для такой задачи (рис) нужно 4 итерации, чтобы найти оптимум по второму критерию. А красным выделены клетки (команда;задача), удовлетворяющие первому критерию - просто минимум каждого столбца.

Миниатюры

 

0

Сообщение от jogano Например, для такой задачи

Генетический алгоритм EXCEL находит решение (22) - только не очень быстро

Вложения

Оптимизация командной работы.xlsx (9.5 Кб, 4 просмотров)

0

Да, нужна именно минимизация времени самой загруженной команды.

0

После трёх дней вывод такой: стратегия постепенного улучшения базисного решения путём замены в одном столбце какой-то строки на другую не позволяет придти к оптимальному решению - можно постепенно улучшать решение, но доходится не до лучшего решения. Т.е. может быть так, что путём перестановки строк в одном столбце решение сначала ухудшается (т.е. максимум суммы строк становится больше, чем на последнем шаге), а на следующем шаге (при перестановке в другом столбце) оно становится лучше первого. Поэтому - программа перебора, к сожалению. Хотя может есть ручные методы, но мне они не известны.
Если перебирать тупо, то макрос в VBA находит решение того примера, который в посте 4, примерно за 3 минуты и выписывает на листе несколько постепенно улучшающихся стратегий (в последнем прогоне написал 16 максимумом сумм строк от 70 до 22). Если стратегий с лучшим максимумом строк (22) несколько, то выписываются они все.
Можно оптимизировать процесс перебора, если отсеивать стратегии, содержащие клетки с ценой (т.е. с затратами времени (команда;задача) ) больше чем последний лучший результат. Например, последняя лучшая стратегия дала максимум суммы строк 30. Значит, стратегии, в которых задействованы ячейки с ценой >30, можно сразу отсеивать и не проверять, какой у них выходит максимум сумм строк - понятно, что не меньше, чем самая большая цена в задействованных ячейках. Но я так не делал - написал по-простому для начала.

0