排课问题的算法研究

《排课问题的算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、？？？分类号：密缴：硕±研究生学位论文排课问题的算法研究专业：应用数学研究方向：最优化理论与算法研究生：李茜指导教师：赵天玉教授＜论文起止日期１４年９月至２０１６年４月：２０分类号：：密级麥向乂蓉硕击研究生学位论文排课问题的算法研究专业：应用数学研究方向：最优化理论与算法研究生：李茜指导教师：赵天玉教授论文起止日期１４年９月至２０１６年４月：２０＼ｆＡｌｏｒｉｔｈｍＲｅｓｅａｒｃｈＯｎＣｏｕｒｓｅＳｃｈｅｄｕｌｉｎＰｒｏｂｌｅｍｇｇＭａｏｒ：

2、ＡｌｉｅｄＭａｔｈｅｍａｔｉｃｓｊｐｐＤｉｒｅｃｔｉｏｎｏｆＳｔｕｄ：ＯｔｉｍｉｚａｔｉｏｎＴｈｅｏｒａｎｄＡｌｏｒｉｔｈｍｙｐｙｇＧｒａｄｕａｔｅＳｔｕｄｅｎｔ：ＬｉｉａｎＱＳｕｅｒｖｉｓｏｒ：ＴｉａｎｕＺｈａｏｐｙＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＭａｔｈｅｍａｔｉｃｓＹａｎｔｚｅＵｎｉｖｅｎｉｔｇｙＳｅｐｔｅｍｂｅｒ２０１４化Ａｒｉｌ，２０１６，ｐ摘要近年来，学校的教学管理工作因高校招生人数和课程种类的逐渐増多而增加了很大难度。教学管理工作是十分复杂的工作，排课问

3、题是其中难度最大、复杂性最高的问题。排课问题是Ｓ．Ｅｖｅｎ在１９７５年证明了的ＮＰ难问题，在排课过程中需要综合考虑很多要素，比如年级、课程种类、教室容量、教师类型、上课时间、教师等等，。Ｗ实现教学资源的合理规划因此，如何对高校课程进行优化排列，提高学校教师、教室Ｗ及配套教学资源的利用率是各个学校追求的目标。排课问题涉及到教学资源的配置问题，更关系到各学校教学目标能否实现，己经成为国内外众多学者关注的焦点。利用计算机自动排课系统排课，可合理高效地处理复杂、多变的多种资源，在满足各学校教务活动需要的同时，还能提高各学校教学资源

4、的利用率，在确保教学任务能够顺利实施的同时，使教学成本得到最大程度的控制，这不仅对于学校发展有实际意义，对我国整个教育业，乃至其他行业的发展同样具有促进作用。高校排课问题属于时间表问题，该问题的解决不仅可Ｗ有效处理高校扩招、学分制推行等改革过程中遇到的资源紧缺问题，还能对其他时间表类问题给予一定的借鉴意义，如教育系统的考试安排问题、行政或商业部ｎ的会议安排问题、交通部口的车辆时刻安排问题等。课程表是编排课程的表。科学的课程安排才能调度全校师生的教学活动，使学校的教学工作有序进行。所Ｗ，富校相关机构和人员需要对课程进行合理编排。

5、早先，，还，高校是通过人工的方式进行课程编排不仅浪费了大量的人力和精力可能会由于某种情况考虑不周出现排课冲突，。后来国内外众多学者对排课问题，在排课问题中融入遗传算法进行了广泛研巧、模巧退火算法、蚁群算法、分支定界算法等智能算法，极大的提高了排课效率和合理性，但在编排的科学性上还有欠缺。较为常见的算法原理及其应用情况如下所示：应用遗传算法时需要确定信息要素的编码方案，适应值函数１＾＞１及遗传算子，然后利用迭代过程中的新信息进行，适应能力较大的可继续往下计算组织搜索。遗传算法具有简单、独立性强的优点，但它约束能力方面不够

6、强。禁忌搜索算法是构造禁忌表，将禁忌表中的移动列入禁止，防止陷入循环。该法有较强的爬山和记忆能力，可跳出局部最优解。模拟退火算法巧制算法进程是通过冷却进度表的参数，，虽然过程较为复杂但是该算法能在多项式时间里得到近似最优解，适合求解大规模非线性规划问题。蚁一群算法利用正反馈原理，它是种可并行实现的算，通过信息加强加快进化过程法，不同妈蚁之间不断进行信息素的交流和传递，通过相互协作更容易发现较好解。分支定界法的基本思想是搜索有限解空间中所有带有约束条件的最优化问题的可行解，，。该算法通过不断把全部可行的解空间分割为越来越小的

7、子集即分支Ｉ并计算每个子集内的解值的下界或上界，即定界。每次分支是不会再继续分支界限己超出己知可行解值的子集的。这样，就可Ｗ不用考虑解的许多子集，即搜索一树上的相应结点，从而缩小了搜索范围。这过程直到找到可行解才结束，且该可行解的值不超过任何子集的界限。，，在解决高校排课问题上由Ｗ上分析可知不同的智能算法有其各自的特点，一一各具利弊，单算法难，［实现预期的目标将不同算法融为体，构筑更为先进，的算法成为必然。遗传算法具有很强的适应能力，但后期的收敛性较差蚁群算法收敛性较好，但对运算数据的要求较高，若将两个算法融合，把遗传算法

8、的结果作为蚁群算法的初始值，即能解决遗传算法后期收敛慢的问题，又能解决蚁群