У меня есть проблема с планированием задач / заданий, и я хотел бы найти наиболее эффективные алгоритмы для ее решения.
Допустим, есть рабочие. Каждый работник может выполнять свой набор задач / заданий. Следующий пример может прояснить это:
Worker A (can do): T2, T3
Worker B : T1, T3, T4
Worker C : T3, T5
Теперь у нас есть список задач, которые необходимо выполнить. Например, список выглядит примерно так: T1, T3, T5.
Есть некоторые ограничения:
- Каждое задание должен выполнять один рабочий.
- Одновременно можно выполнять несколько задач
- Но работник может одновременно выполнять только одну задачу. (Он / она недоступен, пока не завершит задание)
В приведенном выше примере у нас может быть такое расписание:
T1 --> Worker B
T3 --> Worker C T5 --> Worker C
Как вы могли заметить, приведенный выше график не является оптимальным. Потому что T5 должен ждать, пока работник C закончит T3. Лучше следующее решение:
T1 --> Worker B
T3 --> Worker A
T5 --> Worker C
Потому что ждать нельзя.
Теперь предположим, что я знаю матрицу рабочих задач (какой работник какие задачи может выполнять). Задачи будут приходить одна за другой, но я не знаю, что это будет. Меня просят разработать планировщик, который автоматически находит простаивающего работника для каждой предстоящей задачи. А когда, наконец, все задачи выполнены, время ожидания минимальное.
Итак, мне нужен алгоритм для этого планировщика. Я не хочу изобретать велосипед, если идеальное колесо уже существует. Кто-нибудь может помочь?
Спасибо.