У меня есть набор рабочих W1, W2 ... Wn, каждый с различными возможностями / наборами навыков. У меня есть набор заданий T1, T2 ... Tn.
- T1 может выполняться W1 и W2
- T2 может выполняться W1
- T3 может выполняться W1, W2, W3
- T4 может быть выполнена W2
Задачи T1, T2, T3 и T4 должны выполняться последовательно, и хорошо, если некоторые работники находятся в состоянии ожидания. В этом случае лучшая комбинация рабочего набора, которая способна выполнить все задачи, - это {W1 и W2}. Есть ли алгоритм, который может идентифицировать такую комбинацию наилучшего соответствия?
Я рассмотрел Задача покрытия обложки . Представив задачу в виде двумерной матрицы с заданиями в виде строк и работниками в виде столбцов:
1 1 1 0
1 0 1 1
0 0 1 0
Определение минимального количество строк, так что объединение этих подмножеств - это все, т. е. представление всех столбцов - трудная задача NP У меня вопрос: действительно ли это проблема Set Cover или я смотрю на это в неправильном направлении? Существуют ли другие алгоритмы, помогающие найти почти оптимальные решения этих проблем?