教务管理中的排课排考算法设计

摘要

随着计算机的高速发展，各种教务软件系统已在高校中普及，不少排课排考算法也被相继提出。但是由于课表问题属于NP完全类问题，它的复杂度极大程度地限制了算法的发展；另外各高校教务管理的现状和要求各有不同，目前开发的软件针对性都较强，所以一直以来都没有一种算法能做到真正的通用有效。 近年来，越来越多的学者致力于课表问题的算法研究，提出了不少革新思想。对一些已有的算法也做了修正和补充，比如将几种优化算法结合，互补缺陷，或者在一种优化算法的基础上加入其他的优化思想，扩大其可行域、提高其有效性。本文分别对排课、排考问题提出了优化算法。算法基于对现况的分析，从需求出发，并且结合了若干优化思想，使用较短的机时搜索最优解，力求通用有效。 全文共分五章。第一章介绍了课表问题的研究背景和发展现状，并分析了课表问题的复杂度。第二章阐述了目前教务管理的现状及趋势，由此进行了排课排考的数据分析，为下文进行算法设计作了准备。第三章使用遗传算法搜索时间强要求的排课问题的最优解，结合了优化初始染色体、提高较差基因的操作概率、回溯、添加软约束等优化思想，设计了一套详细的算法流程，并给出了简单示例和用实际数据测试的有效结果。第四章结合了贪婪算法、分段匹配、相邻原则、最短路径法等优化思想，对空间强要求的排考问题进行分析，给出一套详细的算法流程。在第四章末尾还介绍了根据该算法编写的一款排考软件，以及其实际应用中取得的良好效果。最后第五章对全文总体思想作了总结，并对将来排课排考优化算法的发展作了展望。

目录

文摘

英文文摘

第一章引论

一、课表问题的研究背景及现状

二、N P(Nondeterministic polynomial)完全类问题

三、排课排考的算法复杂度

第二章排课排考问题的一些理论与实际分析

一、教务管理的现状及趋势

二、排课排考问题的数据分析

第三章排课问题的算法设计

一、时间强要求的排课问题与遗传算法

二、排课问题的软硬约束条件

三、核心算法步骤

四、算法在实际中的应用

第四章排考问题的算法设计

一、空间强要求的排考问题

二、排考问题的软硬约束条件

三、核心算法步骤

四、算法在实际中的应用

第五章总结与展望

参考文献

作者攻读硕士学位期间发表的论文

致谢

附录