【作者】 黄静；

【导师】 许勇；

【作者基本信息】 华南理工大学 ， 计算机应用技术， 2009， 硕士

【摘要】 排课问题是每个高校都必需面临的问题,也是计算机学科中的一个经典问题。排课问题是典型的多重约束和组合优化问题,并且早在70年代已经被证明是一个NP完全问题。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的自适应随机搜索算法。它具有良好的并行性、通用性、稳定性,是一种非常有效的解决NP完全问题的方法。本论文主要基于遗传算法,结合排课系统的一些具体需求,研究并实现一个排课系统。本文将遗传算法应用于求解排课问题,主要进行了以下几个方面工作:首先,研究了经典遗传算法,从遗传算法的构成要素到基因染色体的三个最重要的操作,分析了遗传算法解决排课问题的优势。其次,系统分析了排课问题的各要素及多重约束条件,提出了排课问题的求解难点和优化目标,并完整设计了排课问题的数学模型。再次,全面设计了包含排课各元素的染色体编码方案,设计了时间安排算法和教室安排算法,设计了衡量全局课表的适应度函数,并且设计了染色体的种群操作。然后,以Visual C++6.0为主要开发工具,根据排课系统算法设计并实现了基于遗传算法的自动排课系统。最后,以实际排课数据测试了本论文设计的排课系统在实际排课问题中的应用,并对测试结果从时间复杂度和排课结果两方面进行了性能分析,效果令人满意。更多还原

【Abstract】 Curriculum scheduling problem is the issue that colleges and universities must face, and it also is a classic problem on computer science. Curriculum scheduling problem is a typical problem about multi-restraints and combination optimization, and has been proved to be a Nondeterministic Polynomial Completed (NPC) problem in the 1970’s.The Genetic Algorithm (GA), based on the biological mechanism of natural selection & heredity, is an adaptive and stochastic search algorithm. It can be highly implemented in parallel. For the stability and generality of GA, GA is often used to solve complicated NPC Problem. This paper is mainly based on genetic algorithm, combined with some of the specific needs of Course Scheduling System, a Course Scheduling System has been studied and implemented.In this paper Genetic Algorithm (GA) is applied to solve curriculum scheduling for a university. The main works as follows:Firstly, I do research on the classic GA, from constituent elements of the GA to three most important gene operations of Genes Chromosomes, analysis the advantages of the GA to solve the problem of arranging schedule. Secondly, all kinds of potential factors, multi-restrictions of curriculum scheduling problem are discussed. What’s more, the difficulties to resolve the curriculum scheduling problem and the optimal object are represented, and the mathematic model about curriculum scheduling problem is designed. This paper is mainly based on genetic algorithms, combined with some of the specific needs of Course Scheduling System to study and implement a Course Scheduling System. Thirdly, a Chromosome coding scheme which contained all of the course arrangement elements is designed, as well as the Scheduling algorithm and classroom scheduling algorithm. Meanwhile overall fitness function to measure the timetable and the operation of chromosome populations are designed. And then, an automatic curriculum scheduling system based on the Design of Scheduling System Algorithm is realized on the windows platform using Visual C++6.0.Finally, real course data is used to test this design on the Scheduling System Algorithm in the application of real curriculum scheduling problem, and the result is satisfying in the way of the time complexity and curriculum scheduling result.更多还原