algorithm - 建立基于技能的团队

Question

我正在尝试实现一个团队选择算法 - 假设我们有 n 个人，每个人都有根据他们的表现排序的技能：P1 {ruby，python，java} 意味着他比 java 更精通 ruby​​，类似的 P2.. 等等。我的项目 Proj1 需要人们具备一些技能 {比如 ruby​​、python 等}、Proj2 等。我如何在项目之间分配人员以实现公平分配（假设一个人只能从事一个项目）？

Answer 1

这里可以应用线性规划。您需要根据可以最大化或最小化的目标来定义公平分配。然后根据项目添加约束。您可以使用任何 LP 求解器来解决这个问题，例如lpsolve。从维基百科引用 LP 的历史

Dantzig 最初的示例是找到 70 人对 70 个工作的最佳分配。

希望这可以帮助。

Answer 2

这是我的建议，其中包含我的假设的问题定义空白。这类似于 Ankush 的回答中的线性规划方法

您为程序员拥有的每项技能分配权重：

P1{java,ruby,python} -- P1{1, 0.5, 0.25}
P2{ruby,python} -- P2{1, 0.5}
P3{python,ruby,java} -- P3{1, 0.5, 0.25}

现在您的项目要求是：

项目{java,python}

因此，您将每个程序员的权重乘以 1（需要技能）或 0（不需要技能）：

P1_suitability = 1*1 + 0.5*0 + 0.25*1 = 1.25
P2_suitability = 1*0 + 0.5*1 = 1
P3_suitability = 1*1 + 0.5*0 + 0.25*1 = 1.25

您为项目选择 P1 和 P3

另一个项目需要：

项目{ruby,python}

计算适用性：

P1_suitability = 1*0 + 0.5*1 + 0.25*1 = 0.75
P2_suitability = 1*1 + 0.5*1 = 1.5
P3_suitability = 1*1 + 0.5*1 + 0.25*0 = 1.5

您为其他项目征集 P2 和 P3

同样，这是非常投机的解决方案，因为问题定义不完整。无论如何，这不是一个糟糕的练习..

Answer 3

Here is another linear programming approach, based on the theory that nobody notices if you finish early, but you're in big trouble if you finish late.

For each project, estimate the number of standard programmer hours of each skill required.

For each programmer and each skill, estimate how long (because of their particular skill level) they have to work to produce one standard programmer-hour's worth.

You then need to solve a linear program where most of the unknowns are of the form Pijk, where Pijk is the number of elapsed hours programmer i spends working on skill j of project k.

You immediately have the constraint that SUM_j,k Pijk <= Qi, where Qi is the total amount of time programmer i has to spare, on all projects.

The total amount of work done on skill j of project k is SUM_i Pijk*Eij, where Eij depends on how good programmer i is at skill j. The amount of slack for a particular activity, given the Pijk, is Sjk = SUM_i Pijk * Eij - Wjk, where Wjk is the total amount of work to do for that skill and project. If the minimum amount of slack on any skill of any project is S, then we have the constraint that S <= Sjk.

Because missing deadlines is expensive, I claim that a good objective function is to maximise S, the minimum amount of slack on any skill of any project. All this is given as a set of linear inequalities, so you should be able to find the Pijk that lead to a maximum possible S as a linear programming problem.