单位文秘网 2021-07-20 08:13:01 点击: 次
思想,用增广路径求二分图最大匹配的算法,算法的核心是寻找增广路径,也可用于指派问题的求解[2]。
针对多人执行多项工作的指派问题,张云华采用匈牙利算法的基本思想和步骤进行了研究[3]。目标分配问题作为指派问题的一种类型,谷稳综合匈牙利算法及其进化算法的特点,对机器人足球的目标分配问题进行了研究[4]。为避免匈牙利算法多次试分配导致处理速度慢的不足,周莉等人对寻找独立零的次序进行改进,得到匈牙利算法求解指派问题的一次性分配算法[5]。李延鹏等人提出利用虚拟工作代替并联环境,将具有并联环节的人员指派问题转化为典型的指派问题,提高了匈牙利算法的适用性[6]。谢博耶夫采用反圈法和对称差,对匈牙利算法进行了推广[7]。对于“人少任务多”型指派问题的解决,与“加边补零”法、“加边补最小值”法等传统解法不同,马晓娜通过差额法对匈牙利算法进行了改进[8]。
3 基于匈牙利算法的任务指派优化模型
问题描述 教学课程的指派优化问题,需要综合考虑教师教学特长、学生满意度、课程内容等多因素,追求教学质量、满意度和教师教学精力等多目标的优化决策问题,任何一个参数的改变都可能影响最终的指派结果。该类问题可描述为:
假设有n名不同教研室的教师,N={N1,N2,...,Nn},所有教师可以讲授课程共m门,M={M1,M2,...,Mm}。已知n名教师对m门课程的擅长程度矩阵G、n名教师的课时上限序列U和学员对教师满意度序列S,如何安排n名教師教授的课程,使得总体教学质量、教师精力和学生满意度最优化?
指派优化模型 由于该问题涉及因素较多,因此,采用解析方法或传统的匈牙利算法难以给出合适结果。总体最优化的前提是教师擅长课程、精力和学生满意度满足基本要求,本文采用比值的方式求解三种因素的综合表现。矩阵G元素值为百分比,Gij值越高,表明第i名教师对第j门课程的擅长程度越好。序列U和S经过归一化处理后,也可表现为百分比形式,Ui值越高,表明第i名教师的教学任务越饱满;Si值越高,表明学生对第i名教师的满意度越高。以Tij表现三种因素综合影响下第i名教师教授第j门课程的情况。Tij值与Gij、Si呈现正相关关系,而与Ui呈现负相关关系,计算得到:
末位淘汰制是当前高校教师竞争较为常用的制度[9],对所有教师求解Tij,对Tij按值由高到低排序PT,根据T进行课程指派前的初始末位淘汰。因此,模型的目标方程为:
约束条件如下:
1)n为能够完成教学任务的教师数量,m为需要完成的教学课程数量,i表示教师,j表示教学课程;
2)教师擅长教学课程的程度矩阵G,其值由教学专
家、往届学生成绩和教师自身资历确定,其值越高,表明越擅长;
3)教学课时饱满程度序列U,由教师所承担的教学任务、科研任务、外出授课学习和自身情况确定,其值越高,表明教师课程任务越重;
4)学生满意度序列S,由往届学生评价、本届学生评价综合确定,其值越高,表明教师讲授课程的受欢迎程度越高;
5)矩阵为修正后的擅长矩阵,依据G、U和S求解T,采用末位淘汰制修正G后成为。
模型求解
1)构建平衡的矩阵G。求解平衡问题是匈牙利算法的特长,当教师数量和教学课程数量不相等时,需要增添虚拟的教师或课程,重新构建平衡的矩阵G。具体方法如下:
①若n>m,一门教学课程可能由多个教师讲授,属于不平衡状态下择优录用问题,可虚拟n-m门课程,構建新的平衡矩阵G={Gn×m∣Gn×(n-m)}。
②若n ③若n=m,属于平衡状态下的标准指派问题,直接由匈牙利算法求解。 构建结束后,由求解最大值转为求解最小值,将目标函数转为标准的目标函数。即求,令 ,则与有相同的最优解。 2)处理擅长矩阵、饱满序列和满意度序列。如果某教师Ni无法讲授某项课程Mj,则将擅长矩阵G对应元素Gij的值设定为0。对满意度序列S进行归一化处理: 对课程饱满程度序列U进行归一化处理: 3)修正擅长矩阵G。根据处理后的擅长矩阵、饱满序列和满意度序列,求解T进行末位淘汰。将所有Tij值按由高到低的顺序进行排序,设定合理的淘汰比例p,对于排名低于p的,取消该教师讲授相应课程的安排,即当PT(Tij)≤p时,Gij=0,修正形成矩阵G′。 4 实例分析 某高校计划开设创客空间,需要开展的教学任务有焊接、车工、钳铣磨工、数控、3D打印、切割。现有8名教师可承担相关课程教学,教师对教学课程的擅长矩阵G见表1。根据教师自身安排、专家组打分和课时等分析,得到教师教学任务的饱满程度序列U,见表2。通过问卷调查、往届课程成绩、学生座谈等形式,得到学生对教师的满意度序列S,见表3。根据学校本学期末位淘汰安排,执行p=15%的末位淘汰率。计算T并进行排序,如表4所示,得到综合排名靠后的教师课程为(A2-车工)、(A2-钳铣磨工)、 (A3-数控)、(A4-车工)、(A6-3D打印)和(A7-焊接),将其执行末位淘汰改进矩阵G′。 随后采用匈牙利算法进行最优化指派,使用MATLAB进行编程求解,得到教师A2和A7不参与该项教学任务,其他的如表5所示。 5 结论 在传统教学任务指派中,需考虑教师擅长度和教学任务饱满程度、学生满意度等诸多问题,采用一般经验进行定性的任务指派费时、费力、效率低。而采用定量分析和计算机辅助解决实际问题,使得结论客观而可靠。本文从实际教学出发,以教学任务指派问题建立模型,应用匈牙利算法实现总满意度最高的求解,使得任务分配更加客观和明确,具备可操作性和可重复性,为教育任务分配提供科学依据。 参考文献 [1]胡运权,郭耀煌.运筹学教程[M].4版.北京:清华大学出版社,2012. [2]傅家良.运筹学方法与模型[M].上海:复旦大学出版社,2006. [3]张云华.论匈牙利算法在指派问题管理工作中的应用[J].价值工程,2016(25):214-215. [4]谷稳.基于进化匈牙利算法的目标分配问题研究及应用[D].西安:西安电子科技大学,2013. [5]周莉,张维华,徐射雕.求解指派问题的一次性分配算法[J].计算机工程与应用,2011(18):135-138,152. [6]李廷鹏,钱彦岭,李岳.基于改进匈牙利算法的多技能人员调度方法[J].国防科技大学学报,2016(2):144-149. [7]谢博耶夫.匈牙利算法及其推广[D].上海:华东师范大学,2016. [8]马晓娜.“人少任务多”型指派问题的一种新算法[J].重庆工商大学学报:自然科学版,2014(12):68-71,75. [9]姚维.如何看待高校实行“末位淘汰制”[J].亚太教育, 2016(22):201,189.
地址:https://www.kgf8887.com/show-142-67648-1.html
上一篇:论管理学技术至上观的现实遭遇
下一篇:建筑设计方法及创新发展研究
版权声明:
本站由单位文秘网原创策划制作,欢迎订阅或转载,但请注明出处。违者必究。单位文秘网独家运营 版权所有 未经许可不得转载使用