湖北经济学院本科毕业生毕业论文(毕业设计) 开题报告书

1、湖北经济学院本科毕业生毕业论文（毕业设计）开 题 报 告 书题目 自动排课系统的研究与实现 指导教师姓名及职称 讲师 学生姓名 李红卫 所属院系 计算机技学与技术学院 专业名称 软件工程 班级名称 软件Q0341 开题时间 年 月 日 湖北经济学院本科毕业生毕业论文（毕业设计）开题报告书姓 名李红卫专业和班级软件Q0341开题时间题 目自动排课系统的研究与实现一、题目来源及研究的理论与实际意义课程的安排是学校教学系统中的一个重要环节,是维护学校教学秩序正常进行的重要保证。随着在校学生的增多,课程类别的多样化,学生选课的自由度增加,使得课程的安排工作日益复杂和繁琐,所以学校课程安排的合理与否直接

2、体现了教务部门的工作效率和学校的教学质量。目前使用计算机进行自动排课,可以使教务管理人员迅速掌握全校教学情况,提高教务管理工作的效率,加快其现代化进程,可以看出加强学校的课程安排工作对学校教务管理工作具有非常重要的意义。传统的人工进行排课，最令人担心的问题就是出现教室资源冲突或教师资源冲突的情况，而且工作繁琐，工作量巨大,尤其是在给大学校园进行排课时出现的问题更多。计算机软件技术应用于学校的课程安排是发展的必然。充分发挥计算机的优势，将大量复杂的判断与运算交给计算机来做，是真正意义上的人脑的“减负”。 教师设置好学校基本情况及排课要求，让计算机排出课程表，适度调课后的课表就能满意地应用于新的学

3、期。虽然当前已经出现了许多采用不同算法设计的自动排课系统，但它们普遍存在着不足：或因适用范围太广而导致操作复杂，需手工输入排课信息太多；或因适用范围窄而导致排完课后仍需人工调整，既耗时且排课质量差。市场流行的排课系统很多，比如：相似排课CIS，plsn智能排课系统，正信华课程安排管理系统，排课博士，排课高手,水晶排课等等。这些排课软件在解决排课问题时大多数采用的算法都是回溯算法，排课的效果也都很好。利用回溯算法解决问题的思路是先选择某一可能的线索进行试探，每一步试探都有多种方式，将每一方式都一一试探，如有问题就返回纠正，反复进行这种试探再返回纠正，直到得出全部符合条件的答案或是问题无解为止。这

4、种解决问题的方法就是回溯法。回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。二、国内外相关研究成果及研究动态综述排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。对于NP完全问题目前在数学上没有一个通用的算法能够很好地解决，然而很多NP完全问题具有很重要的实际意义。目前大家对NP完全问题研究的主要思想是如何降低其计算复杂度，即利用一个近似算法来代替，力争使得解决问题的时间从指数增长化简到多项式增长。结合到课表问题就是

5、建立一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这是解决排课问题一个主要的思路。进入九十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度 V a s t a p u r 大学管理学院的ArabindaTripathy、加拿大Montreal大学的JeanAubin和JacquesFerland等。目前，解决课表方法的问题有:模拟手工排课法、图论方法、拉格朗日法、二次分配型法等多种方法。由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈增大，这已经成为应用数学编程解决课表问题的巨大障碍。国外的研究表明，解决大规模课表编排问题单纯靠数学方法是

6、行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有希望获得成功的办法。在国内，对课表问题的研究开始于80年代初期，具有代表性的有:南京工学院的UTS（SAUniversityTimetableSchedulingSystem）系统，清华大学的TISER（TimetableSchedulER）系统，大连理工大学的智能教学组织管理与课程调度等，这些系统大多数都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。但是这些课表编排系统往往比较依赖于各个学校的教学体制，不宜进行大量推广。从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人意。一方面是作为一个很复杂

7、的系统，排课要想面面俱到是一件很困难的事；另一方面每个学校由于其各自的特殊性，自动排课软件很难普遍使用，特别是在调度过程中一个很小的变动，要会引起全部课程的大调整，也就意味着全校课程大变动，在实际的应用中这是很难实现的事。排课是每一所学校都会面临的繁重作业,且通常是校务计算机化中最难解决的一环。如何将排课的资源与其限制进行妥善而令人满意的调度安排,是排课作业的基本要求与目标。迄今为止,对课程表的研究工作已经进行了长达40多年之久,取得了丰硕的成果。但是,仍然存在许多困难,例如规模大、约束条件复杂以及规律不断变化等,因此课程表问题至今仍未完全解决。比较常用的算法有: 贪心算法, 回溯算法, 动态

8、规划法。比较流行的算法有: 基于优先级的排课算法和遗传算法。近年来, 遗传算法用于排课成为热门, 许多国内外的学者进入了这个领域。三、主要研究内容1分析现有排课算法, 总结出其优缺点。2在现在算法的基础上, 设计出自己的排课算法,。3实现该排课算法, 并加以图形化的实现。四、本研究的关键创新点、研究方法、研究进度计划和完成时间1研究的关键创新点: 采用回溯算法和碰撞检测的思想, 将排课问题转为排列问题, 为约束建立碰撞检测函数, 便于系统的扩充。2研究方法: 查阅文献资料, 在了解现在流行的排课算法的基础上设计出自己的排课算法。写出算法的伪代码, 并写出排课关键代码, 并测试,。 待通过后选择图形化开发工具, 参看别人做好的排课系统界面, 取长补短, 设计出自己的界面, 然后添加实现代码。3研究进度计划和完成时间 五、主要参考文献1黄玉波 基于空间的合理排课算法分析J. 科技广场,2007,(1). 2殷荣庆 高校排课算法的分析与设计J. 安徽教育学院学报,2006,(6). 3陈强 通用高校排课算法研究J. 科技广场,2006,(7). 4田岭 大学自动排课算法设计与实现J. 教育信息化,2006,(13). 5张慧兰,罗家国,张甜 基于校院两级任务的计算机排课算法研究J. 南方冶金学院学报,2006,(1). 6