Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Задача распределения времени при выполнении послед


Автор: so1idsnake 21.2.2014, 10:44
Суть задачи:

Есть задачи, которые выполняются рабочими. Каждый рабочий может выполнять ограниченный набор задач. Разные рабочие выполняют одну и ту же задачу за разное время. Также для каждого рабочего известны промежутки рабочего времени. На входе набор задач, которые нужно выполнить и одновременно выполняться может только одна задача. Нужно определить оптимальное время начала выполнения каждой задачи, минимизировав при этом время простоя между выполнением задач. Порядок выполнения может быть произвольным, а может быть и нет, однако это не существенно, меня интересует вариант с произвольным порядком.

Что-то мне подсказывает, что эту задачу можно было бы свести к системе линейных уравнений и неравенств. 
Буду рад любым идеям, предложениям и источникам информации smile

Автор: Фантом 21.2.2014, 11:21
Одна из классических задач теории операций. Соответственно, можно взять любой учебник по этому предмету.

Автор: so1idsnake 21.2.2014, 11:36
Дело в том что я не совсем понимаю каким образом выразить целевую функцию и при том сделать ее линейной. Был бы чрезвычайно благодарен любой помощи в решинии данного вопроса.

Автор: Akina 21.2.2014, 11:48
А она ни разу не линейная. При формальном подходе задача переборная. И спецово прикормленные методы могут лишь оптимизировать её решение, но не изменят сути.

Автор: so1idsnake 21.2.2014, 11:50
Да, чушь спорол. Прошу прощения.

Автор: so1idsnake 21.2.2014, 12:11
А что насчет спецово прикормленных методов? Можно парочку примеров?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)