导　　师： 张博锋

授予学位： 硕士

作　　者： ;

机构地区： 上海大学

摘　　要： 考试安排一直是高校教务管理系统中一项繁重的任务。随着现代教育事业的不断发展，实现计算机智能化管理是学校管理工作的一项重要内容。考试时间的安排属于著名的时间表问题ttp(timetabling problem)。ttp问题已经被广泛应用于学校课程和考试的时间安排(examination timetabling problem，简称etp问题)、各类大型会议、体育比赛、航班(火车、飞机、轮船等)时刻表的制定等。1975年s.eveo等人论证了时间表问题属于np完全问题，是一个难题。 对于考试时间、考场和监考教师这三部分的安排，要想同时做出一个验证方案可行性的算法，其算法复杂度就不是简单的将其相加了。经过分析，这三个部分中考试时间的安排最为复杂，算法最难。考场安排相对简单些，应用银行家算法更合理的分配教室，解决了当2个考场人数都少于规定人数一半时合并考场的问题，节约了教室资源。而根据某高校的实际情况，监考教师的安排是征求教师个人意见，自己将名字报上来的，所以程序中不做完全的自动安排，而是将监考教师姓名汇总到数据库中，由教务人员选择性安排。因此，在这种情况下，首先考虑考试时间的安排算法，在满足考试时间安排的情况下再做其他部分安排。 本文分析了考试时间安排的约束条件，基于图着色的数学模型，采用了一个二阶段式的混合算法：即先用贪心算法的思想得出一个满足所有必须要满足的约束条件的初始可行解；在此基础上再用改进的分组遗传算法的思想进一步优化结论，协调好考试周总的考试天数与学生复习时间之间的矛盾关系，使得系统能在现有的条件下尽量扩大和平均分配学生的复习时间。 本文从某高校的实际应用出发，设计并实现了一个高校考试自动安排系统。系统包括前台程序和后台程序两部分，教务人员使用后台程序实现考试时间、考场和监考教师三部分的安排；前台程序挂在校园网上，学生和教师可以登录查询和打印考试安排信息。

关 键 词： 时间表问题 图着色 遗传算法 贪心算法 银行家算法 教务管理系统 考试安排 高等学校

分 类 号： [G647.3 G434]

领　　域： [文化科学] [文化科学] [文化科学] [文化科学]