我正在尝试实现一个将s学生分配给g个实验室组中的l个实验室的应用。约束是:
1:每个实验室的学生应与新学生一起工作。2:所有学生必须成为实验室负责人一次。
如果不能在实验组中平均分配学生,则2是不可解决的。因此,如果“奇数”的学生从未成为实验室负责人,这是可以接受的。
我尝试了两种方法,但我还不满意。
禁忌搜索,它解决了1但有问题解决了2(我实际上首先解决了1,然后尝试解决了2,这可能是错误的方法,有任何建议)
一个简单的解决方案,我将#labs中的学生划分为数组[0..6] [7..14] [15..21],然后旋转(带有0,1,2 inc)并转置矩阵,重复#labs次,重复旋转(1,2,4)和(2,4,6)。在3个实验室中的21个学生中,实验组为7个,结果如下:
实验室负责人是实验室1的第一列,实验室2的第二列…
此解决方案效果不错,但是例如对于3个实验室中的12名学生或6个实验室中的150名学生失败。有什么建议?
2似乎可以处理相同数量的情况或组合,并且与1相比,闪电般快。也许我应该得到一个高贵的价格:-)
约束1本身通常被称为社交高尔夫球手问题。(让参数g为组数,s为每组的大小,w为周数。分组是将g * s高尔夫球手划分为g组,大小为s。确定是否可以找到w组,这样每个高尔夫球手最多可分组一次。)社会高尔夫球手问题已在组合优化文献中进行了研究,方法分为三种类型(您可以使用自己喜欢的搜索引擎查找研究文章):
本地搜索。当w远低于其最大可行值时,此方法有效。Dotú和Van Hentenryck的论文将禁忌搜索应用于社交高尔夫球手问题。
完成搜索。当w高于或略低于其最大可行值时,这是必要的,但扩展性不是很好。
代数构造。这就是解决臭名昭著的g = 8 s = 4 w = 10实例的方式。不幸的是,对于许多参数集,尚无构造信息。
要分配实验室负责人,请计算学生与实验室组之间的最大匹配度,如果该学生属于该实验室组,则该学生与实验室组之间将存在一条优势。