首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >将任务分配给人的算法,其中有些任务需要多个人,而且没有人两次执行相同的任务。

将任务分配给人的算法,其中有些任务需要多个人,而且没有人两次执行相同的任务。
EN

Stack Overflow用户
提问于 2019-10-01 12:57:19
回答 3查看 1.2K关注 0票数 2

我的一个老师朋友让我编一个程序来帮助他们给学生分配课堂上的工作。有23个孩子和12个不同的工作类型,其中一些工作需要多个孩子,总共有23个可用职位。每周他们都想随机地给孩子们分配新的工作,在那里,没有一个孩子在尽可能长的时间内做同样的工作。

我的思维过程是按照这个规则生成所有可能的分配给工作的孩子,然后一个接一个地完成结果。但我很难想出一种实用的算法来生成这些赋值组合。

如果有人对解决方案有任何想法,或者能让我知道我在追求一个不可能的解决方案,我会很感激的!

我已经把所有的工作都贴上了,下面每个工作都需要多少个孩子,以防万一会有帮助。

“出席情况”:1,

“餐桌船长”:4,

“助教”:2、

“委员会橡皮擦”:2,

“光开关”:1,

“图书馆员”:

“午餐助手”:1,

“设备经理”:

“垃圾监视器”:2,

“技术专家”:

“纸面通行证”:

“铅笔磨刀”:1

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2019-10-01 21:42:54

这是一个琐碎的调度问题。你有23名学生,占23个名额;你最大的等效组是4个(表队长)。把他们排成一排,分配工作。每周,把孩子们转移到4个点以上。23和4是相对最优的,所以这种模式在23周内不会重复。

让我们用十个数字和两个特殊字符来指定工作类型;学生可以是字母。

代码语言:javascript
运行
复制
0 "Attendance": 1,
1 "Table Captain": 4,
2 "Teacher's Helper": 2,
3 "Board Eraser": 2,
4 "Light Switcher": 1,
5 "Librarian": 2,
6 "Lunch Helper": 1,
7 "Equipment Manager": 3,
8 "Trash Monitor": 2,
9 "Tech Specialist": 1,
# "Paper Passer": 3,
$ "Pencil Sharpener": 1

日程安排:

代码语言:javascript
运行
复制
 job    0 1 1 1 1 2 2 3 3 4 5 5 6 7 7 7 8 8 9 # # # $
week 1  a b c d e f g h i j k l m n o p q r s t u v w
week 2  t u v w a b c d e f g h i j k l m n o p q r s
week 3  p q r s t u v w a b c d e f g h i j k l m n o

如果你需要把学生们混在一起,这样你就没有一对学生一周一周地分享工作,那就洗牌轮岗吧。确保作业的两个实例不被4的倍数分隔。

代码语言:javascript
运行
复制
 job    0 # 1 1 1 1 2 5 3 4 7 2 8 5 6 7 3 7 # 8 9 # $
week 1  a b c d e f g h i j k l m n o p q r s t u v w
week 2  t u v w a b c d e f g h i j k l m n o p q r s
week 3  p q r s t u v w a b c d e f g h i j k l m n o
票数 1
EN

Stack Overflow用户

发布于 2019-10-01 16:36:25

这里有一个简单的贪婪算法,没有任何保证:

创建一个二部图,其中学生是一个集合中的节点,任务槽是另一个集合中的节点。

现在,我们为那些可行的作业在学生和节点之间创建边缘。最初,这些都是。一旦我们得到了这个图,我们就可以计算出一个随机的完美匹配。为此,从随机边缘开始。查看两个事件节点中是否没有任何一个节点有赋值,并修复该分配。如果其中一个节点有任务分配,则转到下一个随机边缘。

这会给你一个随机的任务。让我们看看下周会发生什么:

我们需要修改图形以排除那些会导致任务重复的边。一旦我们删除了这些边缘,我们可以再次做同样的事情,并计算一个随机的完美匹配。

最终,您将到达无法完成匹配的配置。这可能有两个原因:要么是以糟糕的方式选择边缘,要么是图形不允许完美匹配。要纠正第一个原因,您可以使用不同的随机选择多次运行相同的方法(例如,10次)。它不能给你确定性,但它减少了错误选择的可能性。第二个原因是有点棘手。这将发生在几个星期后,因为我们的任务用完了,所以必须重复。要做到这一点,我们可以添加一些边缘。要添加哪些边是非常可变的,并且取决于系统的期望行为。首先,我会添加所有的边缘任务,需要最多的人。其中,从重复次数最少的人的边缘开始。一旦你添加了这些边缘,尝试找到完美的匹配再次。如果你仍然不成功,添加一些边缘,再试一次,等等。

票数 1
EN

Stack Overflow用户

发布于 2019-10-01 16:36:43

首先,让我们为可能的答案找到一些常识的界限:

  • 如果有M个任务,并且不允许子任务重复任务,那么就不能有比M任务更多的任务了,因为M+1th分配必须重复M个以前的分配中的一个。因此,生成M有效的、非重复的赋值是一个初始上限.
  • 初始、有效的任务分配可以通过以下方式进行:人员列表(按任何给定的顺序)、任务列表(按任何给定的顺序),然后简单地用人员填充任务,直到所有任务都满为止。请注意,给定此方法生成的有效赋值,所有其他有效分配都可以通过人员列表的排列来生成。
  • 因为有些任务需要多个人来完成,所以在没有重复的情况下,这些任务是最难完成的。例如,如果有4人(abcd)和3个任务(xyz),其中x需要2人,yz只需要1人,那么在某人被迫重复工作之前,只有2个有效的任务分配,而不是3:x:a&b, y:c, z:dx:c&d, y:a, z:b (或等效的x:c&d, y:b, z:a)。因此,最大的有效连续作业数的一个更严格的限制是ceil(|P| / Tm),其中Tm是工作人员最密集的任务所需的人数,而P是总人数。M任务的有效分配的上限只有在所有任务都是1人的情况下才能实现。

现在,对于一个简单的算法:

代码语言:javascript
运行
复制
sort all persons into a list P; random is fine       
   persons in P have an initially empty list of tasks that they have carried out
sort all tasks into a list T; random is fine
generate a valid assignment as follows:
   for each task Ti in T,
       for t = Ti (the number of people required to staff the i-th task), and t>0
           for each person Pj in P, starting from the last-assigned person,
               if Pj has never performed Ti, and has no task for the current day,
                   add Ti to Pj's tasks, and decrement t
               otherwise, skip Pj; if everybody is so skipped, then exit

在上述伪代码的末尾,每个人都将有一个任务列表,他们将在每一天连续完成这些任务。有些任务可能比其他任务多一个任务,因此生成的有效任务数是最短任务列表的长度。该算法的运行时间显然受到O(v_n_m)的限制,其中v是返回的有效连续赋值的数量,它本身位于v*n下,因此对于少量的人员和任务,这应该是相对较快的。

ceil(23 / 4) = 5,这样你的学生将不得不在5天后开始重复工作。在JavaScript中实现上述算法提供了一个有效的(根据上面的观察,最大)调度:

代码语言:javascript
运行
复制
// initialize tasks            
let tasks = new Map([
    ["Attendance", 1],
    ["Table Captain", 4],
    ["Teacher's Helper", 2],
    ["Board Eraser", 2],
    ["Light Switcher", 1],
    ["Librarian", 2],
    ["Lunch Helper", 1],
    ["Equipment Manager", 3],
    ["Trash Monitor", 2],
    ["Tech Specialist", 1],
    ["Paper Passer", 3],
    ["Pencil Sharpener", 1]
]);

// initialize people by counting total hands for all tasks
let totalPeople = 0;
for (let p of tasks.values()) totalPeople += p;
// and give each person an empty list of tasks for each assignment
let people = Array.apply(null, Array(totalPeople)).map(() => new Array());

function assign(tasks, people) {
    let moreAssignmentsMayBePossible = true;
    let assignments = 0;
    outer: while (moreAssignmentsMayBePossible) {
        let nextIndex = 0;
        for (let t of tasks) {
            let initialIndex = nextIndex;
            let [name, count] = [t[0], t[1]];
            while (count > 0) {
                if (nextIndex >= people.length) {
                    nextIndex = 0;
                }
                let candidate = people[nextIndex++];
                if (candidate.indexOf(name) == -1 && candidate.length == assignments) {
                    candidate.push(name);
                    count --;
                } else if (nextIndex == initialIndex) {
                    moreAssignmentsMayBePossible = false;
                    break outer; // no more assignments possible
                }
            }
        }
        assignments ++; // yay! finished a full assignment
    }
    // drop extra tasks from over-burdened people
    people.forEach((o) => o.length = assignments);
    return assignments;
}

assign(tasks, people);
people.forEach((o, i) => console.log(i, o.length, o.join(", ")));

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/58185271

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档