基于技能公平地为工人分配任务的算法

Question

(在任何人问之前,这不是功课.)

我有一组有兴趣的工人,即:

• Bob:Java,XML,Ruby

• 苏珊:Java,HTML,Python

• 弗雷德:Python,Ruby

• 山姆:Java,Ruby

• 等等

(对于每个工人,实际上在10-25"兴趣"的范围内,我有大约40-50名工人)

与此同时,我需要在工人之间分配大量的任务.每项任务必须分配给至少 3名工人,工人必须至少符合其中一项任务的利益:

任务1:Ruby,XML任务2:XHTML,Python

等等.所以鲍勃,弗雷德或萨姆可以得到任务1; 苏珊或弗雷德可以得到任务2.

这一切都存储在数据库中:

Task
    id integer primary key
    name varchar

TaskInterests
    task_id integer
    interest_id integer

Workers
    id integer primary key
    name varchar
    max_assignments integer

WorkerInterests
    worker_id
    interest_id

Assignments
    task_id
    worker_id
    date_assigned

每个工人的工作任务数量最多,大约为10个.有些利益比其他人更少见(即只有1或2个工人将其列为利息),有些利益更为普遍(即一半的工人列出他们的利益) ).

算法必须:

• 将每个任务分配给3名工作人员(假设至少有3名工人对该任务的一项兴趣感兴趣).
• 为每个工人分配1个或多个任务

理想情况下,算法将:

• 为每个工作人员分配与其最大分配和任务总数成比例的多个任务.例如,如果苏珊说她将完成20项任务,大多数人只完成10项任务,有50名工人和300项任务,则应分配12项任务(20/10*(300/50)).
• 为每个工作人员分配各种任务,因此如果Susan列出了4个兴趣,那么她将获得包含4个兴趣的任务(而不是获得10个具有相同兴趣的任务)

迄今为止最困难的方面是处理这些问题:

• 与少数相应工人有兴趣的任务
• 特别是兴趣不大的工人
• 有兴趣的工人,任务相对较少

Answer 1

此问题可以建模为 最大流量问题.

在最大流问题中,您有一个带有两个特殊节点的有向图,即源和接收器.图中的边缘具有容量,您的目标是通过图形从源到接收器分配流量,而不会超出任何边缘容量.

通过(非常)精心设计的图表,我们可以找到满足您最大流量要求的任务.

让我对要求进行编号.

需要:

1. Workers are assigned no more than their maximum assignments.
2. Tasks can only be assigned to workers that match one of the task's interests.
3. Every task must be assigned to 3 workers.
4. Every worker must be assigned to at least 1 task.

可选的:

5. Each worker should be assigned a number of tasks proportional to that worker's maximum assignments
6. Each worker should be assigned a variety of tasks.

我将假设使用Edmonds-Karp算法找到最大流量 .

让我们首先找到符合要求1-3的图表.

将图形描绘为4列节点,其中边缘仅从列中的节点到右侧的相邻列中的节点.

在第一列中,我们有源节点.在下一栏中,我们将为每个工作人员提供节点.从源头来看,每个工人都有一个优势,其能力等于工人的最大分配.这将强制执行要求1.

在第三列中,每个任务都有一个节点.对于第二列中的每个工作人员,该工作人员感兴趣的每个任务都有一个优势,容量为1(如果工作者的兴趣交叉点非空,则工作人员对任务感兴趣).这将强制执行要求2.容量为1将确保每个工作人员只为每个任务占用3个插槽中的1个.

在第四列,我们有水槽.每个任务都有一个边缘,容量为3,这将强制执行要求3.

现在,我们使用Edmonds-Karp算法在此图中找到最大流量.如果此最大流量小于此值3 * (# of tasks),则没有符合要求1-3的分配.如果没有,就有这样的任务,我们可以通过检查最终的增强图来找到它.在增强图中,如果从任务到具有容量1的工作线程的边缘,则将该工作线程分配给该任务.

现在,我们将修改我们的图形和算法以满足其余要求.

首先,让我们满足要求4.这将需要对算法进行少量更改.最初,将源中的所有容量设置为1到1.在此图中查找最大流量.如果流量不等于工人数量,则没有分配会议要求4.现在,在最终残差图表中,对于每个工人,从源到该工人的边缘具有容量0并且反向边缘具有容量1将这些分别更改为that worker's maximum assignments - 1和0.现在像以前一样继续Edmonds-Karp算法.基本上我们所做的是首先找到一个赋值,使每个worker只分配给一个任务.然后从该任务中删除反向边缘,以便始终将工作人员分配给至少一个任务(尽管它可能不是第一次传递中分配给的任务).

现在让我们满足要求5.严格地说,这个要求只是意味着我们将每个工人的最大分配除以sum of all worker's maximum assignments / number of tasks.这很可能没有令人满意的任务.但那没关系.使用这些新的最大分配初始化我们的图表.运行Edmonds-Karp.如果它找到一条使任务边缘饱和的流程,那么我们就完成了.否则,我们可以在残差图中将容量从接收器增加到工作者,并继续运行Edmonds-Karp.重复,直到我们将边缘浸入水槽.不要增加容量,以至于为工作人员分配了太多任务.此外,从技术上讲,每个工人的增量应该与该工人的最大分配成比例.这些都很容易做到.

最后让我们满足要求6.这个有点棘手.首先,在工作人员和任务之间添加一个列,并删除从工作人员到任务的所有边缘.在这个新专栏中,为每个工作人员为每个工人兴趣添加一个节点.从这些新节点中的每一个中,为每个任务添加一个边缘,使其具有与容量匹配的兴趣1.将每个工作线的边缘添加到容量为1的每个感兴趣节点.现在,此图中的流将强制执行被分配给n个任务,那么这些任务的兴趣与该工人的兴趣的联合的交叉点的大小至少为n.同样,如果没有这项任务,可能会有令人满意的任务,但没有一项任务.我们可以像要求5一样处理这个问题:运行Edmonds-Karp完成,如果没有令人满意的任务,则将工作量增加到他们的兴趣节点并重复.

请注意,在此修改后的图形中,我们不再满足要求3,因为如果他们的兴趣的交集大小大于1,则可以将单个工作者分配给任务的多个/所有槽.我们可以解决这个问题.在兴趣节点和任务节点之间添加新的节点列,并删除这些节点之间的边缘.对于每个员工,在新列中为每个任务插入一个节点(因此每个员工都有自己的每个任务节点).从这些新节点到右侧相应的任务,添加容量为1的边缘.从每个工人的兴趣节点到该工作人员的任务节点,将每个兴趣的容量为1的边缘添加到匹配的每个任务.

-

编辑:让我试着澄清这一点.让我-(n)->成为一个有n容量的边缘.

以前我们worker-(1)->task为每个具有匹配兴趣的工作 - 任务对.现在我们有worker-(k)->local interest-(1)->local task-(1)->global task.现在,您可以想到一个与工人兴趣对匹配的任务.第一个优势是,对于一个工人来说,每个人的兴趣都可以与k任务相匹配.第二个优势表明,每个工人的兴趣只能与每个工作匹配一次.第三个边缘表示每个任务只能分配给每个工作人员一次.请注意,您可以将多个流从工作者推送到本地任务(等于他们感兴趣的交集的大小),但由于第三个边缘,只有1个流从工作者流向全局任务节点.

-

另请注意,我们无法将此递增与要求5的递增正确混合.但是,对于worker-> interest edge,我们可以针对每个容量{1,2,...,r}运行整个算法一次.然后我们需要一种方法来对作业进行排名.也就是说,当我们放宽要求5时,我们可以更好地满足要求6,反之亦然.但是,我更喜欢放松这些限制的另一种方法.

需求放松的更好方法 (灵感来自/取自templatetypedef)

当我们希望能够放宽多个要求(例如5和6)时,我们可以将其建模为最小成本最大流量问题.这可能比我上面描述的增量搜索更简单.

例如,对于要求5,将所有边缘成本设置为0.我们具有从源到工作者的初始边缘,其容量等于worker's maximum assignments / (sum of all worker's maximum assignments / number of tasks)并且具有成本0.然后,您可以添加另一个边缘以及该工作人员的剩余容量成本1.另一种可能性是使用某种渐进成本,这样当您向工作人员添加任务时,向该用户添加另一个任务的成本就会增加.例如,您可以将工人的剩余容量分成具有成本的单个边缘1,2,3,4,....

然后可以在工作节点和本地兴趣节点之间针对要求6进行类似的事情.需要平衡加权以反映不同要求的相对重要性.

这种方法也足以强制执行要求4.此外,要求5的成本应该使得它们与工人的最大分配成比例.然后为具有最大值100的工作人员分配1个额外任务的成本不会超过为具有最大值2的工作人员分配额外任务的成本.

复杂性分析

让n = # of employees,m = # of tasks,k = max interests for a single task/worker,l = # of interests,j = maximum of maximum assignments.

要求3意味着n = O(m).我们也假设l = O(m)和j = O(m).

在较小的图形中(在要求的变化之前),图形具有n + m + 2 = O(m)顶点和最多n + m + k*min(n, m) = O(km)边缘.

在更改之后它有2 + n + n * l + n * m + m = O(nm)顶点和n + k * n + k * m * n + n * m + m = O(kmn)边(从技术上讲,我们可能需要j * n + j * l更多的节点和边,这样从一个节点到另一个节点没有多条边,但这不会改变渐近边界).另请注意,没有边缘需要容量> j.

使用最小代价最大流配方,我们可以找到一个解决方案O(VEBlogV),其中V = # vertices,E = # edges和B = max capacity on a single edge.在我们的例子中,这给了O(kjn^2m^2log(nm)).

Answer 2

尝试将您的任务映射到稳定的婚姻问题。任务变成了准妻子`，你的员工变成了追求者。

您可能需要添加一些额外的算法来将每个任务的偏好分配给员工，反之亦然 - 您可以为每个任务的组成部分分配一些必要的理想熟练程度，然后允许您的员工对每个任务进行排名。您可以为每个员工拥有的每个组件分配一个熟练程度，并使用它来获取员工中每个任务的偏好。

一旦你有了偏好，就运行算法，发布结果，然后允许人们成对向你申请以交换任务——毕竟这是一个人的问题，当人们有一定程度的控制权时，他们会工作得更好。