2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 задача, похожая на задачу о назначениях
Сообщение17.08.2013, 23:12 
Здравствуйте!

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

 
 
 
 Re: задача, похожая на задачу о назначениях
Сообщение18.08.2013, 02:36 
Michaelx в сообщении #755665 писал(а):
у каждого сотрудника своя скорость - V1..Vn
то есть скорость выполнения любой работы для данного сотрудника одинакова? Какие у вас, однако, универсальные специалисты. Если при этом еще и любую работу могут выполнять одновременно несколько человек (красить газон или подметать ломами плац), то никакого распределения не надо - есть одна большая работа суммарного объема и пусть каждый делает что хочет.

 
 
 
 Re: задача, похожая на задачу о назначениях
Сообщение18.08.2013, 09:38 
Цитата:
то есть скорость выполнения любой работы для данного сотрудника одинакова?

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

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

-- 18.08.2013, 09:57 --

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

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

 
 
 
 Re: задача, похожая на задачу о назначениях
Сообщение17.09.2013, 17:35 
Аватара пользователя
См. https://en.wikipedia.org/wiki/Notation_ ... g_problems и далее по ссылкам.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group