算法基于技能相当将任务分配给工人 [英] Algorithm for fairly assigning tasks to workers based on skills

问题描述

（之前有人问，这是不是功课。）

(Before anyone asks, this is not homework.)

我有一组工人的利益，即：

I have a set of workers with interests, i.e.:

• 鲍勃：Java中，XML，红宝石

• Bob: Java, XML, Ruby

苏珊：爪哇，HTML，Python的

Susan: Java, HTML, Python

弗雷德：Python和Ruby

Fred: Python, Ruby

山姆：Java中，红宝石

Sam: Java, Ruby

等等。

（实际上有介于10-25利益为每个工人的范围，我有大约40-50工人）

(There are actually somewhere in the range of 10-25 "interests" for each worker, and I have around 40-50 workers)

与此同时，我有一个非常大的组需要在劳动者之间分配任务。每个任务都有被分配到的至少的3工人，工人必须在任务的利益，至少有一个匹配：

At the same time, I have a very large set of tasks that need to be distributed among the workers. Each task has to be assigned to at least 3 workers, and the workers must match at least one of the tasks' interests:

任务1：红宝石，XML 任务2：XHTML，Python的

Task 1: Ruby, XML Task 2: XHTML, Python

等。所以鲍勃，弗雷德，或山姆可以得到任务1;苏珊和弗雷德可​​以得到任务2。

and so on. So Bob, Fred, or Sam could get Task 1; Susan or Fred could get Task 2.

这是所有存储在数据库中正是如此：

This is all stored in a database thusly:

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个工人其列为一个利息）较为少见，有些利益是比较常见的（即一半工人一一列举了）。

Each worker has a maximum number of assignments they will do, around 10. Some interests are more rare than others (i.e. only 1 or 2 workers have listed them as a interest), some interests are more common (i.e. half of the workers list them).

该算法的必须的：

• 分配的各项任务，以3工人（这是 假定至少3的 工人有兴趣之一 任务的利益）。
• 分配每个工人1个或多个任务

• Assign every task to 3 workers (it is assumed that at least 3 of the workers are interested in one of the interests of the task).
• Assign every worker 1 or more tasks

理想地，该算法将：

• 分配每个工人的任务数成正比它们的最大分配的任务的总数。例如，如果苏珊说，她会做20个任务，大多数人只会做10个任务，有50名工人和300的任务，她应该被分配12个任务（20/10 *（五十分之三百））。
• 分配各种任务，每个工人的，所以如果苏珊列出了4利益，她得到的任务，其中包括4利益（而不是让10个任务都具有相同的利率）

最困难的方面至今一直在处理论文的问题：

The most difficult aspect so far has been dealing with theses issues:

• 在具有数相应工人权益的任务
• 谁很少有兴趣的工人，特别是
• 谁有一些利益，因为其中有相对较少的工作人员

推荐答案

试试你的任务映射到稳定的婚姻问题的。任务成为未来的妻子'，和你的员工成为追求者。

Try mapping your task to the stable marriage problem. Tasks become prospective wives `, and your staff become suitors.

您可能要添加一些额外的算法来分配每个任务的preferences工作人员介绍，反之亦然 - 你可以指定一些理想的水平neccessary每个任务的组件，然后让你的员工排名每个任务。你可以指定一个熟练的每个组件的每个工作人员posses，并用它来获取每个任务preference的工作人员。

You might want to add some extra algorithm for assigning preferences of each task to the staff, and vice-versa - you could assign some ideal proficiency neccessary for the components of each task, and then allow your staff to rank each task. You could assign a proficiency for each component that each staff member posses and use that to get each tasks preference in staff members.

一旦你拥有了preferences然后运行算法后的结果，然后让人们在对适用于您交换任务 - 毕竟这是一个人的问题，人更好地工作，当他们有一定程度的控制。

Once you have the preferences then run the algorithm, post the results, then allow people to apply in pairs to you to swap assignments - after all this is a people problem and people work better when they have a degree of control.

这篇关于算法基于技能相当将任务分配给工人的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！