蚁群算法在求解一类时间表问题中的应用的研究

《蚁群算法在求解一类时间表问题中的应用的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、摘要排考问题是一类典型的时间表问题，是对考生、考场、时间、考试科目和监考人员等因素进行配置的决策性问题。由于排考问题的普遍性和复杂性，众多科研机构和研究者已投入大量研究力量寻找其解决方案，因此本文的研究具有实际意义。论文在对西安电子科技大学网络教育学院考务流程及考务系统功能进行分析后，构建排考问题数学模型，研究模型求解过程中需要的关键算法，并提出具体的求解方案。首先基于图着色算法的理论，对考试科目进行分组预处理，并根据分组数确定具体考试时间；其次使用蚁群算法寻找考试科目分组与时间的最优化组合，对考试时间安排进行优化：然后

2、基于贪心算法的思想安排考场；最后构造监考适合度函数合理安排监考人员。实验表明，该方案在优化考试时间、尽量满足约束条件、资源节约利用等方面，均能够产生良好的效果，具有较强的可行性和适用性。关键词：时间表问题考试安排组合优化蚁群算法Abs仃act一_———————————————————————————————————————————————————一AbstraCtEx锄．time切blingproblemisat)，picaltime诅bliIlgproblem，whichisanoptimizationaI】【ddec

3、ision-makingprobleminVolVingthefactorssuchaSstudents，examcoursesajldinVigilationteachers，etc．ForitsuIliversal时andcompleXi咄greatefronshaVebeenputbymanyresearchersandscie埘ficresearchinstimtiOnsinfindingasolution．Therefore，theresearchinthispaperhaspracticalsi鲥ficaul

4、ce．Thispaperconstmctstllemathematicalmodelofexam-tim魄lblingproblemafjceranalyzingtheex锄inationpmcessandex锄inationsystemfUnction，menresearchesthekeyalgorithmsinsolvingmodelandproposesa90ncretelmplementatlonscneme·Firstly，intheviewofgraphcoloringalgorithminpreproce

5、ssing，theex锄taSksaredividedintoseveralgroupswhichdete珊inesthespecificex锄time．Secondly’byusingantcolonyalgorithm，theex锄scheduleisoptimizedandcombinationsbetweenex锄course留oupsandtimeslots甜efoulld．7I、11irdly，accordingtothegreedyalgorltllm，claSsroomsareaHanged．LaStbu

6、tnotleast，inVi舀lationteachersarearrangedbyconstructinginvigilationteacherfitness^mction．ExperimentresultsshowmatthesolutioninthispapernotoIllyproducesgoode丘’ectinoptimizingex锄timewlththec叽Straints，but2LlsopossessesstrongfeaSibil时auldserviceabil咄Keywords：TimetabUn

7、gProblemExam—timetabIingProblemCombinatorialoptimizationAntColonyAlgorithm第一章绪论1．1研究背景时间表问题(兀P)是一类应用非常广泛的研究课题【l】，它可以描述为在资源有限制的条件下，将某些事件合理安排到给定的时间内，并且保证不发生冲突或发生冲突的可能性最小。时间表问题在工厂作业调度、汽车铁路时刻表、中小学时间表及大学时间表等领域有着广泛的应用。比较典型的时间表问题是大学时间表问题，大学时间表问题可以分为大学课程时间表问题和大学考试时间表问题，即

8、排课问题和排考问题。排考问题可以描述为在考务人员制定的考试周期内，根据学生的选课情况，利用现有的考场资源和监考人员资源，在尽量满足各种约束的条件下，无冲突的进行合理的考试安排。在考试安排过程中，既要保证避免因考试时间或考试资源等产生的冲突，又需要考虑考生考试时间安排的合理性、监考人员特殊要求等情况，从而使考试安排达到