我们在一所大学的理学硕士课程中遇到了一个实际问题,在该大学中,学生必须被分配到实验室。所涉及的数字并不是很大,所以我不是在寻找一个快速的解决方案,而是一个易于理解的解决方案,以便为学生和小组负责人提供所提议配对的理由。让学生与实验室配对
鉴于2列表
S1 Li,Lj,Lk
S2 Lu,Lv,Lw
.
Sn
这里每个学生s已上市的前3个实验室中的优先顺序。所以学生S1理想情况下会喜欢在实验室我。如果该实验室不需要他,那么他会想要进入Lab j等等。
和
L1 Si,Sj,Sk
L2 Su,Sv,Sw,Sx,Sy
.
Lm
其中每个实验室列出的学生,他们希望在实验室。因此,如果实验室1选择了本实验室(他的前三个选择之一),那么实验室1会首先要求学生i。请注意,实验室可以挑选尽可能多的学生。
约束条件是每个学生只能在一个实验室中,但每个实验室可能有0,1或更多的学生。
的目标是生产中,所有学生被分配到实验室匹配(SI,LJ)和配对导致最大满意。
的满意分数被定义为
Z=sum_{i=1..n}(sum_{j=1...m} (abs(i-j))
直观这个尝试配对的许多学生和实验室用他们最好的选择。
所以我寻求其目的的解决方案是最小化Z.
一种可能的部分解决方案该优化算法的算法如下:
定义的阵列称为分配的长度L的和初始化它全是假的
首先,匹配的第一选择和放弃这些学生
for each s in {S1,..,Sn}:
Assigned[s]=False
Assigned[s]=j
repeat until all(Assigned)==True:
for each s in S:
if RANK(Lj,s)==1:
Assigned[s]=j # i.e. pair student s with lab Lj
del(S,s) # delete s from the list S
函数RANK( Lj,s)返回实验室j中首选学生列表中的位置。如果学生不在实验室j中想要的学生名单中,则返回无穷大。
我不知道应该怎么还是这种方法可以减少分数Z.
任何帮助将非常感激进行。