我的一个老师朋友让我编一个程序来帮助他们给学生分配课堂上的工作。有23个孩子和12个不同的工作类型,其中一些工作需要多个孩子,总共有23个可用职位。每周他们都想随机地给孩子们分配新的工作,在那里,没有一个孩子在尽可能长的时间内做同样的工作。
我的思维过程是按照这个规则生成所有可能的分配给工作的孩子,然后一个接一个地完成结果。但我很难想出一种实用的算法来生成这些赋值组合。
如果有人对解决方案有任何想法,或者能让我知道我在追求一个不可能的解决方案,我会很感激的!
我已经把所有的工作都贴上了,下面每个工作都需要多少个孩子,以防万一会有帮助。
“出席情况”:1,
“餐桌船长”:4,
“助教”:2、
“委员会橡皮擦”:2,
“光开关”:1,
“图书馆员”:
“午餐助手”:1,
“设备经理”:
“垃圾监视器”:2,
“技术专家”:
“纸面通行证”:
“铅笔磨刀”:1
发布于 2019-10-01 21:42:54
这是一个琐碎的调度问题。你有23名学生,占23个名额;你最大的等效组是4个(表队长)。把他们排成一排,分配工作。每周,把孩子们转移到4个点以上。23和4是相对最优的,所以这种模式在23周内不会重复。
让我们用十个数字和两个特殊字符来指定工作类型;学生可以是字母。
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
日程安排:
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的倍数分隔。
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
发布于 2019-10-01 16:36:25
这里有一个简单的贪婪算法,没有任何保证:
创建一个二部图,其中学生是一个集合中的节点,任务槽是另一个集合中的节点。
现在,我们为那些可行的作业在学生和节点之间创建边缘。最初,这些都是。一旦我们得到了这个图,我们就可以计算出一个随机的完美匹配。为此,从随机边缘开始。查看两个事件节点中是否没有任何一个节点有赋值,并修复该分配。如果其中一个节点有任务分配,则转到下一个随机边缘。
这会给你一个随机的任务。让我们看看下周会发生什么:
我们需要修改图形以排除那些会导致任务重复的边。一旦我们删除了这些边缘,我们可以再次做同样的事情,并计算一个随机的完美匹配。
最终,您将到达无法完成匹配的配置。这可能有两个原因:要么是以糟糕的方式选择边缘,要么是图形不允许完美匹配。要纠正第一个原因,您可以使用不同的随机选择多次运行相同的方法(例如,10次)。它不能给你确定性,但它减少了错误选择的可能性。第二个原因是有点棘手。这将发生在几个星期后,因为我们的任务用完了,所以必须重复。要做到这一点,我们可以添加一些边缘。要添加哪些边是非常可变的,并且取决于系统的期望行为。首先,我会添加所有的边缘任务,需要最多的人。其中,从重复次数最少的人的边缘开始。一旦你添加了这些边缘,尝试找到完美的匹配再次。如果你仍然不成功,添加一些边缘,再试一次,等等。
发布于 2019-10-01 16:36:43
首先,让我们为可能的答案找到一些常识的界限:
a
、b
、c
、d
)和3个任务(x
、y
、z
),其中x需要2人,y
和z
只需要1人,那么在某人被迫重复工作之前,只有2个有效的任务分配,而不是3:x:a&b, y:c, z:d
和x:c&d, y:a, z:b
(或等效的x:c&d, y:b, z:a
)。因此,最大的有效连续作业数的一个更严格的限制是ceil(|P| / Tm)
,其中Tm
是工作人员最密集的任务所需的人数,而P
是总人数。M任务的有效分配的上限只有在所有任务都是1人的情况下才能实现。现在,对于一个简单的算法:
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中实现上述算法提供了一个有效的(根据上面的观察,最大)调度:
// 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(", ")));
https://stackoverflow.com/questions/58185271
复制相似问题