Проблема с расписанием задач / заданий

У меня есть проблема с планированием задач / заданий, и я хотел бы найти наиболее эффективные алгоритмы для ее решения.

Допустим, есть рабочие. Каждый работник может выполнять свой набор задач / заданий. Следующий пример может прояснить это:

  Worker A (can do): T2, T3
  Worker B         : T1, T3, T4
  Worker C         : T3, T5

Теперь у нас есть список задач, которые необходимо выполнить. Например, список выглядит примерно так: T1, T3, T5.

Есть некоторые ограничения:

  1. Каждое задание должен выполнять один рабочий.
  2. Одновременно можно выполнять несколько задач
  3. Но работник может одновременно выполнять только одну задачу. (Он / она недоступен, пока не завершит задание)

В приведенном выше примере у нас может быть такое расписание:

  T1 --> Worker B
  T3 --> Worker C   T5 --> Worker C

Как вы могли заметить, приведенный выше график не является оптимальным. Потому что T5 должен ждать, пока работник C закончит T3. Лучше следующее решение:

  T1 --> Worker B
  T3 --> Worker A
  T5 --> Worker C

Потому что ждать нельзя.

Теперь предположим, что я знаю матрицу рабочих задач (какой работник какие задачи может выполнять). Задачи будут приходить одна за другой, но я не знаю, что это будет. Меня просят разработать планировщик, который автоматически находит простаивающего работника для каждой предстоящей задачи. А когда, наконец, все задачи выполнены, время ожидания минимальное.

Итак, мне нужен алгоритм для этого планировщика. Я не хочу изобретать велосипед, если идеальное колесо уже существует. Кто-нибудь может помочь?

Спасибо.


person yanjiang qian    schedule 15.04.2011    source источник
comment
Если вы не можете заглянуть в будущее, я бы предположил, что отправка задач по мере их поступления работнику с наименьшим способностями оставит наибольшее количество возможностей для будущего. Являются ли рабочие людьми, которые в конце концов надеются получить работу? Или рабочие - компьютеры, и им все равно, получат они работу или нет?   -  person sarnold    schedule 15.04.2011
comment
Для меня это звучит так, как будто автоматический поиск незанятого рабочего для каждой предстоящей задачи, не знаю, что это будет, и минимальное время ожидания - все это противоречит друг другу. Если вы не можете планировать, вы не можете оптимизировать.   -  person Lasse V. Karlsen    schedule 15.04.2011
comment
Что делать, если нет простаивающих рабочих, как вы собираетесь с этим бороться? Просто поставьте их в очередь?   -  person Lasse V. Karlsen    schedule 15.04.2011
comment
Кроме того, все ли рабочие одинаково подходят для всех задач? Другими словами, может ли быть, что Worker A лучше подходит для задач типа T1, чем другие рабочие?   -  person Lasse V. Karlsen    schedule 15.04.2011
comment
@Lasse: это тоже была моя первая мысль, вместо того, чтобы использовать логическое условие, лучшее моделирование связывало бы скорость выполнения с заданным типом задачи для каждого рабочего.   -  person Matthieu M.    schedule 15.04.2011


Ответы (2)



Похоже, вы ищете алгоритм "Bin Packing" -

http://en.wikipedia.org/wiki/Bin_packing

Общая проблема упаковки бункеров, очень похожая на то, что вы сформулировали, является NP-сложной, поэтому вы можете забыть об оптимальном решении, если ваш входной размер более чем тривиален.

Вы можете найти решение, которое гарантированно не будет слишком далеко от оптимального решения, обычно это мой фактор. Эта статья в Википедии - хорошее место для начала.

person shoosh    schedule 15.04.2011
comment
На самом деле это не упаковка контейнеров, это проблема планирования работы магазина: en.wikipedia.org/wiki/ Job_Shop_Scheduling - person Christian Severin; 10.12.2014