导读:本文包含了课表安排问题论文开题报告文献综述及选题提纲参考文献,主要关键词:启发式算法,压缩算法,局部搜索,邻域结构
课表安排问题论文文献综述
刘永凯,张德富[1](2009)在《一种新的课表安排问题的可行解构造算法》一文中研究指出课表安排问题实质上就是要求将学校开设的所有课程,在满足一定的约束条件下,合理地安排到有限的课时和教室资源上。课表安排问题的困难在于,必须把大量的课程安排到紧缺的资源上,同时不能违反各种苛刻的客观约束和主观约束。这些约束通常分为硬约束和软约束,并定义满足所有硬约束的课表为可行解,而违反最少软约束的可行解为最优解。本文提出了一种基于定向搜索的课表压缩算法来解决可行解的构造问题。算法已经在UCTP实例上进行测试,通过与其他高校算法相比较,验证了算法的高效性。(本文来源于《心智与计算》期刊2009年02期)
刘永凯[2](2009)在《课表安排问题的启发式算法研究》一文中研究指出课表安排问题实质上就是要求将学校开设的所有课程,在满足一定的约束条件下,合理地安排到有限的课时和教室资源上。课表安排工作是教学活动中必不可少的一个重要环节,对提高教学质量和节约教学资源起着非常关键的作用。该问题还是一个NP完全问题,用传统的精确算法求解容易导致算法复杂度的指数组合爆炸,因此设计出高效的启发式算法成为当前学者研究课表安排问题的热点之一。因此,无论是从实际应用还是从理论意义的角度考虑,课表安排问题都具有很大的研究价值。本文主要研究高中和大学的课表安排问题,目标在于设计简单、实用和高效的启发式算法。课表安排问题的困难在于,必须把大量的课程安排到紧缺的资源上,同时不能违反各种苛刻的客观约束和主观约束。这些约束通常分为硬约束和软约束,并定义满足所有硬约束的课表为可行解,而违反最少软约束的可行解为最优解。本文利用贪心和禁忌搜索的思想,提出了遍历搜索和定向搜索这两种邻域搜索策略,并在其基础上结合模拟退火,设计出了一个较为通用的二阶段课表安排算法。此算法在第一阶段构造一个可行解,而其第二阶段则在保持课表可行性的同时进行优化,尝试最大程度地去减少软约束违反的数量。高中的排课问题规模较小,难度较低,具有静态性。针对这些特征,本文提出了基于遍历搜索策略的模拟退火算法对其进行求解。为了证明算法的高效性,本文选用了HDTT和GPTT这两个高中课表安排的实例进行测试,并和当前高效的遗传算法、约束规划等算法比较。实验结果的对比分析体现了我们算法的优越性。在大学课表安排问题这个研究领域,最具代表性和影响力的是UCTP国际课表安排算法设计竞赛。针对这个竞赛提出的问题,本文设计了一个定向搜索策略,用于构造可行解。而在第二阶段,本文改进了前面提到的遍历搜索策略,使得算法能够更充分地提高可行解的质量。本文对竞赛提供的标准实例进行了测试,并采用了与竞赛一致的评价方式。评价结果表明,我们的算法优于大部分参赛的高效算法,是一个简单、实用、可拓展的算法。(本文来源于《厦门大学》期刊2009-06-30)
徐云青,陈建明[3](2005)在《大学课表安排问题的PBIL算法》一文中研究指出课程表问题是时间表问题中重要的应用内容。采用一种新的基因编码方法,可以更客观地反映大学课程安排的实际,并采用先进的PBIL算法进行实验,实验的结果表明该算法的可行性和有效性。(本文来源于《衢州市自然科学优秀论文选编(2001-2004)》期刊2005-10-01)
朱冠宇,王乘,席大春[4](2004)在《利用遗传算法求解中学课表安排问题》一文中研究指出论文采用叁维编码方式及相应的遗传算子构成的遗传算法求解中学课表安排问题,通过实例验证该方法具有良好的收敛性,可产生比较优良的排课方案。(本文来源于《计算机工程与应用》期刊2004年27期)
徐云青,陈建明[5](2004)在《大学课表安排问题的PBIL算法》一文中研究指出课程表问题是时间表问题中重要的应用内容.采用一种新的基因编码方法,可以更客观地反映大学课程安排的实际,并采用先进的PBIL算法进行实验,实验的结果表明该算法的可行性和有效性.(本文来源于《浙江师范大学学报(自然科学版)》期刊2004年03期)
张春梅,行飞[6](2002)在《用自适应的遗传算法求解大学课表安排问题》一文中研究指出课程表问题又称时间表问题 (timetable problem) ,是一个多因素的优化决策问题 ,也是组合规划中的典型问题 .本文研究的是大学课表安排问题 ,根据大学课表安排的特点并以优化时间和空间两种资源为目标 ,将课程分为 P、Q两类 .采用鲁棒性比较好的遗传算法 ,并对两类课分别给出其染色体编码和适应度函数 ,并采用了自适应的杂交和变异概率 ,最后通过实验验证该方法可产生适合需求的课表(本文来源于《内蒙古大学学报(自然科学版)》期刊2002年04期)
课表安排问题论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
课表安排问题实质上就是要求将学校开设的所有课程,在满足一定的约束条件下,合理地安排到有限的课时和教室资源上。课表安排工作是教学活动中必不可少的一个重要环节,对提高教学质量和节约教学资源起着非常关键的作用。该问题还是一个NP完全问题,用传统的精确算法求解容易导致算法复杂度的指数组合爆炸,因此设计出高效的启发式算法成为当前学者研究课表安排问题的热点之一。因此,无论是从实际应用还是从理论意义的角度考虑,课表安排问题都具有很大的研究价值。本文主要研究高中和大学的课表安排问题,目标在于设计简单、实用和高效的启发式算法。课表安排问题的困难在于,必须把大量的课程安排到紧缺的资源上,同时不能违反各种苛刻的客观约束和主观约束。这些约束通常分为硬约束和软约束,并定义满足所有硬约束的课表为可行解,而违反最少软约束的可行解为最优解。本文利用贪心和禁忌搜索的思想,提出了遍历搜索和定向搜索这两种邻域搜索策略,并在其基础上结合模拟退火,设计出了一个较为通用的二阶段课表安排算法。此算法在第一阶段构造一个可行解,而其第二阶段则在保持课表可行性的同时进行优化,尝试最大程度地去减少软约束违反的数量。高中的排课问题规模较小,难度较低,具有静态性。针对这些特征,本文提出了基于遍历搜索策略的模拟退火算法对其进行求解。为了证明算法的高效性,本文选用了HDTT和GPTT这两个高中课表安排的实例进行测试,并和当前高效的遗传算法、约束规划等算法比较。实验结果的对比分析体现了我们算法的优越性。在大学课表安排问题这个研究领域,最具代表性和影响力的是UCTP国际课表安排算法设计竞赛。针对这个竞赛提出的问题,本文设计了一个定向搜索策略,用于构造可行解。而在第二阶段,本文改进了前面提到的遍历搜索策略,使得算法能够更充分地提高可行解的质量。本文对竞赛提供的标准实例进行了测试,并采用了与竞赛一致的评价方式。评价结果表明,我们的算法优于大部分参赛的高效算法,是一个简单、实用、可拓展的算法。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
课表安排问题论文参考文献
[1].刘永凯,张德富.一种新的课表安排问题的可行解构造算法[J].心智与计算.2009
[2].刘永凯.课表安排问题的启发式算法研究[D].厦门大学.2009
[3].徐云青,陈建明.大学课表安排问题的PBIL算法[C].衢州市自然科学优秀论文选编(2001-2004).2005
[4].朱冠宇,王乘,席大春.利用遗传算法求解中学课表安排问题[J].计算机工程与应用.2004
[5].徐云青,陈建明.大学课表安排问题的PBIL算法[J].浙江师范大学学报(自然科学版).2004
[6].张春梅,行飞.用自适应的遗传算法求解大学课表安排问题[J].内蒙古大学学报(自然科学版).2002