Задача / задача планирования работы

Question

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

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

  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

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

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

Поскольку ожидания нет.

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

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

Спасибо.

Answer 1

Алгоритмы, работающие на входе, который не известен заранее, но вводится «по ходу», называются онлайновыми алгоритмами .Естественно, они только неоптимальны.Они измеряются тем, что они хуже, чем оптимальный алгоритм, не более, чем постоянным фактором (например, если лучшее решение (которое не является онлайн, то есть имеет весь входной аванс), делает X шагов, то ваше онлайн решение должно быть нечем больше k * X шагов, тем меньше k, тем лучше).

В вашем случае требование не ясно - «минимальное время ожидания» по сравнению с чем?

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

Answer 2

Звучит так, как будто вы ищете алгоритм "Bin Packing" -

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

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

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