Филимоненков Виктор (fiviol) wrote,
Филимоненков Виктор
fiviol

Categories:

Задача о загрузке исполнителей

Поставилась задача, вроде бы совершенно базовая, так что должна быть куча литературы. Буду благодарен, если дадите ссылку на хороший текст с разработанными алгоритмами решения, можно на учебник. А если кто захочет помочь мне придумать алгоритм самому, так будет и вообще прекрасно!

Имеется n операций, которые необходимо выполнить, и m исполнителей. Каждую операцию выполняет один исполнитель, каждый исполнитель одновременно не может выполнять более одной операции. Задана матрица А (размера m*n), a(i;j) = "время, которое тратит i-тый исполнитель на j-тую операцию".
Для каждой операции i требуется указать номер ее исполнителя k(i), так, чтобы наибольшая сумма времен операций, выполняемых одним исполнителем, была минимальной.

Далее, разумеется, есть куча обобщений, самое нужное из которых:
учесть, что некоторые операции упорядочены по времени выполнения (одна операция не может начаться, пока не закончена другая). В этом случае кроме k(i) нужно еще указать С(i) - время начала i-той операции, так, чтобы все указанные ограничения были выполнены, а время на выполнение всех операций было минимальным.
Tags: Задачи, Математика
Subscribe

  • Одноклассники

    Какая-то вязкая, вялотекущая в последнее время жизнь была встряхнута неожиданным и приятным событием. Благодаря инициативе и стараниям моих…

  • Отпуск, июнь 2020, Улан-Удэ

    Первую часть отпуска на в этом году мы взяли на июнь, исходя из того, что в конце мая Олег должен был вернуться домой, отслужив свой год в Бурятии.…

  • Серебряная свадьба

    20 августа 1994 года: 20 августа 2019 года: Как говорится, найдите 25 отличий. :)

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 38 comments

  • Одноклассники

    Какая-то вязкая, вялотекущая в последнее время жизнь была встряхнута неожиданным и приятным событием. Благодаря инициативе и стараниям моих…

  • Отпуск, июнь 2020, Улан-Удэ

    Первую часть отпуска на в этом году мы взяли на июнь, исходя из того, что в конце мая Олег должен был вернуться домой, отслужив свой год в Бурятии.…

  • Серебряная свадьба

    20 августа 1994 года: 20 августа 2019 года: Как говорится, найдите 25 отличий. :)