排考场问题的算法设计与软件实现

摘要

考试安排是校园信息管理中重要环节，又是相当复杂的管理工作之一，是为学校所设置的课程安排时间、地点、监考人员，同时要尽量避免冲突的产生。 本论文首先对考试安排问题做了介绍，介绍了考试安排问题的内容、要求和面对的问题。研究了问题中班级、学生、课程、时段、监考人员及考场等实体信息和它们之间的联系，在此基础上进行数据库表的设计。在计算方法上，首先对图论中着色问题的传统解决方法回溯法作了介绍，然后加上团的信息提出解决考试安排问题的解决方法并分析了复杂性。 本系统采用Excel记录原始数据库和计算结果，首先在“考试安排.xls”文档中建立“学生情况表”、“班级情况表”、“课程情况表”、“时段情况表”、“考场情况表”、“监考教师情况表”6个工作表用于记录各个实体的原始数据，“班级-课程”和“学生-课程”记录选课关系。最后建立两表“考试安排表”和“考生安排表”记录最终得到的考试安排方案。 在实现算法时，利用Excel附带的开发工具VBA实现。在处理数据表信息时，采用定义结构化数据的方式。首先定义六个结构类型，分别用于记录班级、学生、课程、时段、考场和监考教师情况表中的数据。定义第七个结构，称为安排类型，记录一个由时段和考场共同确定的安排单位。这样将同一个个体的所有相关信息记录在一个结构化的变量中。通过在结构中嵌入集合型变量的方式解决了表表之间存在的多多对应关系。 在安排考试时段时，为了避免可能会产生的冲突，程序中首先定义了三个函数，用于判定一个时段是否可用，并对可用时段集合进行取模运算生成一个考试时段安排的方案。通过变换取模时的参数得到多个方案，再通过定义和计算这些方案产生的冲突情况对它们进行评价比较，从而得到一个可以接受的最优方案。 从计算的结果可以看出，本系统通过对班级、学生、课程、考场、时段及监考教师等实体关系的分析，以图论中的着色问题为理论基础，利用Visual Basic中集合类型的自定义变量的方式解决了上述实体之间复杂的联系关系，使得它们在程序中合理地表达出来，简化了它们之间的运算关系。为处理类似的多多对应关系提供了一种高效的表达方式。根据运算结果，可以看出这种方式是行之有效的。在系统的设计中提出了一种对可行时段集合的取模方法，这样在处理类似的问题时，使得利用一个初始的种子值就可以得到一个复杂系统的可行方案。在本系统中还通过使用自定义的冲突函数和冲突系数的方法，有效地避免了冲突的产生，并可作为评定一个方案优劣的参数，以此得到的最终方案中，各个班级、学生所参加的考试都有一定的时间间隔。

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权的声明

第一章前言

第二章考场安排相关的技术基础

第三章系统设计

第四章系统开发中的难点问题及解决

第五章算法的设计与分析及程序

第六章运行结果与结论

参考文献

致谢

攻读学位期间发表的学术论文情况