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

Categories:

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

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

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

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

  • Банальные рифмы

    Поиграем? Ниже перечислены 10 слов. В течение суток с небольшим, скажем, до 19:00 московского времени завтра, 13 июня, комментарии к посту будут…

  • Стокфиш против Стокфиша

    Желая поучиться все-таки хоть иногда делать в шахматах "правильные" ходы, включил искусственный интеллект под названием Стокфиш , который умеет…

  • Куда идет король - большой секрет

    В качестве поиска замены увядшим прежним забавам попробовал играть в шахматы, в которые лет 15 последних уже играл весьма нерегулярно. Сейчас…

  • 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

  • Банальные рифмы

    Поиграем? Ниже перечислены 10 слов. В течение суток с небольшим, скажем, до 19:00 московского времени завтра, 13 июня, комментарии к посту будут…

  • Стокфиш против Стокфиша

    Желая поучиться все-таки хоть иногда делать в шахматах "правильные" ходы, включил искусственный интеллект под названием Стокфиш , который умеет…

  • Куда идет король - большой секрет

    В качестве поиска замены увядшим прежним забавам попробовал играть в шахматы, в которые лет 15 последних уже играл весьма нерегулярно. Сейчас…