algorithm - 选择能够执行给定任务集的工作集的最佳组合

Question

我有一组工人 W1、W2... Wn，每个人都有不同的能力/技能。我有一组任务 T1，T2...Tn。

• T1 可以由 W1 和 W2 执行
• T2可由W1执行
• T3可由W1、W2、W3执行
• T4可由W2执行

任务 T1、T2、T3 和 T4 必须按顺序完成，如果一些工人空闲也可以。在这种情况下，能够执行所有任务的最佳工作集组合是 {W1 和 W2}。有没有一种算法可以识别出这种最合适的组合？

我调查了Set Cover Problem。通过将问题表示为 2D 矩阵，其中 Tasks 为行，Workers 为列：

1 1 1 0
1 0 1 1
0 0 1 0

识别最小行数以便这些子集的并集就是一切，即所有列都被表示是一个 NP 难题。我的问题是它是否真的是一个 Set Cover 问题，还是我看错了方向？是否有其他算法可以帮助找到这些问题的近乎最佳解决方案？

标签： algorithmoptimizationmathematical-optimizationnp-hard