大学课程表问题中的算法研究与应用
摘要
课程表问题(UTP)是一个应用广泛的、典型的组合优化和不确定性调度问题，并且已经被证明是NP完全问题。随着高校规模的不断扩大，和教学管理信息化的不断深入，传统的手工排课和计算机辅助排课已经越来越难以适应现实的需求，而自动化排课系统，因其固有的高难度和复杂性，它的研究与实现成为完善中南大学网络教学管理系统十分重要的一环。本文从实际应用出发，基于动态规划的思想，提出了一种解决大学课程表问题的混合算法，并基于此算法设计并实现了自动化排课系统。
本文首先介绍了UTP问题的研究现状、涉及的因素、各种约束条件，及其数学模型，然后详细阐述了将课程表问题划分为时间片安排和场地安排两个阶段，分别采用智能算法和最佳适应算法逐段求解，并最终求得全局较优解的混合算法。然后，对混合算法与经典遗传算法进行了对比实验分析，结果表明这种分阶段决策的算法在保证课表质量的同时，能够有效的减小遗传算法在求解UTP问题中的复杂度，提高程序的运行速度，也有利于工程应用中对多目标优化的进一步扩
展。
随后，本文基于混合算法，根据项目的实际需求，并考虑到和网络教学管理系统中其它子系统的集成，设计了排课系统的数据库表和各个功能模块，结合图表和文字说明，给出了详细的系统实现过程，并对系统实现过程中的关键技术进行了说明。
最后，总结了本文所做的工作，分析了当前工作的不足及需进一步研究的工作。
ABSTRACT
University Timetable Problem (UTP) is a tyhttps://p.9136.com/28bination optimization problem and uncertain management problem, which is applied widely. UTP has been proved a NP-completion problem. With the enlargement of the university and the deepening of the teaching management information, the tranditional way, arranging course by hand,and the way by using computer assistant could hardly meet the current requirement. The antomatic course arranging system, for its inherent high difficulty and complicacy, its research and realization are very important for the whole network teaching management system. In this paper, with the thought of dynamic programming, a mixed algorithm is proposed to solve this problem. And an automatic course arranging system is designed and realized by using this algorithm in the following.
This paper introduces the development, main factors, constraints and mathematic model of university timetable problem first. Then it expounds a mixed algorithm which divides the course timetabling problem into two
phases, arranging time by intelligent algorithm and arranging classroom by best fit algorithm, and gets the whole solution by resolving each phase of the problem. In the following, compared the mixed algorithm with classical genetic algorithm, it shows the mixed algorithm at the same time of ensuring the quality of result, reduces the complicacy, have a better performance and expansibility.
After that, the database table and sub modules are designed based on the mixed algorithm and requirement, the intergration with other sub system of teaching management system is also considered. The detailed realization and the key technique are then explained by using the combination of text and diagram.
Finally, it summarizes the research work, also analyzes the present problems and the work in future.KEY WORDS university timetable problem, dynamic programming,genetic algorithm, arranging of curriculum schedule。
目录
摘要..................................................................................................... I
ABSTRACT.......................................................................................................II
目录....................................................................................................... III
第一章绪论................................................................................................. 1
I.1课题来源及应用背景........................................................1
1.2国内外研究动态............................:.......................................................... 1
1.3课题的研究内容及意义............................................................................ 2
1.4论文的内容安排和组织结构............................................................... 3
第二章课程表问题...............................................5
2.1时间表问题概述.............................................................................. 5
2.1.1时间表问题及其分类................................................................. 5
2.1.2 School Timetabling问题............................................................5
2.1.3 Course Timetabling问题............................................................7
2.2课程表问题的因素及约束条件........................................................ g
2.3课程表的编排原则............................................................8
第三章基于动态规划思想的混合算法.............................................................. 11
3.1最优化原理和动态规划......................:.......................................................11
3.1.1多阶段决策最优化问题......................................................... .11
3.1.2最优化原理...............................................................................11
3.1.3动态规划理论··……12
3.2混合算法设计……13
3.2.1算法的总体设计思想.................................13
3.2.2算法描述....................................................14
3.3基于遗传算法分配时间..............................................................................15
3.3.1遗传算法概述....................................................15
3.3.2基因编码设计....................................................17
3.3.3初始化种群....................................................18
3.3.4遗传算子操作设计....................................................19
3.3.5冲突检测与消除....................................................22
3.4基于最佳适应算法分配场地................................................................22
3.5对比实验分析.................................................................................... 24
3.5.1算法比较..........................................................24
3.5.2实验设计....................................................25
3.5.3实验结果及分析................................................................25
第四章基于混合算法的排课系统.................................................... 27
4.1系统需求分析..................................................27
4.2系统总体设计.................................................................28
4.2.1与其它子系统的集成..............................................28
4.2.2系统架构设计.....................28
4.2.3系统网络体系结构.........................30
4.2.4系统功能模块划分...................................31
4.3数据库设计.....................................33
4.3.1数据库设计方案.......................................33
4.3.2表的'设计..........................................34
4.4系统实现..................................................37
4,4.1表示层的实现............................................37
4.4.2服务层的实现.......................................................38
4.4.3业务逻辑层的实现..............................41
4.4.4数据访问层的实现.............................. 43
4.5关键技术研究.........................................44
4.5.1系统性能优化...............................................44
4.5.2数据库安全机制...............................................47
第五章回顾与展望.................................... 49
5.1全文总结和工作回顾........................................................49
5.2后续工作与展望...............................................49
参考文献..................................51
致谢..........................................55
攻读学位期间主要的研究成果..................................... 56
5.1全文总结和工作回顾
高校招生规模逐年的扩大及计算机在教学工作中的普及应用，用自动化的智能排课系统代替劳动强度大、工作效率低的手工排课，或是人工介入很大的计算机辅助排课，越来越成为教学管理之中迫切需要解决的研究课题之一。
本文从大学课程表问题的研究与应用出发，设计了基于动态规划思想的混合算法，并基于此算法，结合整个教学管理系统的实际需求，实现了适应中南大学需求的排课系统。具体说来，本人的工作可以归纳如下:
【大学课程表问题中的算法研究与应用】相关文章：
浅谈经济问题中的数学建模应用10-12
人力资源会计的应用与研究论文10-13
行动学习的实践应用与优化策略研究09-23
浅谈填充型导电材料的研究与应用10-27
低碳设计理念与应用研究10-01
管理会计在我国的应用与发展研究08-13
浅谈管理会计理论的研究与应用论文10-13
舞蹈教学语言原则与应用研究的论文07-18