задача, похожая на задачу о назначениях

[Michaelx]

Здравствуйте!

Помогите, пожалуйста, найти алгоритм на задачу, кажущуюся крайне распространенной. Есть задача о назначениях, мой случай таков:
m работ, n работников, m>n. Каждый сотрудник может делать одновременно только 1 работу, но когда закончит, берется за следующую ( если она есть). У каждой работы свой объем - W1..Wm, у каждого сотрудника своя скорость - V1..Vn. Задача соответственно распределить (сразу) работы между сотрудниками так, чтобы минимизировать общее время работы.

[_Ivana]

Michaelx в сообщении #755665 писал(а):

у каждого сотрудника своя скорость - V1..Vn

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

[Michaelx]

Цитата:

то есть скорость выполнения любой работы для данного сотрудника одинакова?

да, одинакова, но одновременно работать над одной задачей они не могут.

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

-- 18.08.2013, 09:57 --

судя по всему, это задача относится к теории расписаний, и похожа на open-shop problem..

[пианист]

Надо полагать, "общее время работы", которое надо минимизировать, это время работы того, кто закончит работу последним?
Тогда можно так: переменные $x_{ia}\ge0$, $z$. Ищем минимум $z$ при условиях $\sum_ax_{ia}=w_i$, $z\ge\sum_i\frac{x_{ia}}{v_a}$.
Задача ЛП.

[maxal]

См. https://en.wikipedia.org/wiki/Notation_ ... g_problems и далее по ссылкам.