2006085011.txt

收集打包的一个有关《基于遗传算法的排课系统》的论文和设计及遗传算法介绍的文件！

广东工业大学工学硕士学位论文
基于贪婪算法的排课系统的研究与实现
聂小东
-oo六年四月
分类号:
UDC:
学校代号:
学号:
11911
2110305216
广东工业大学学位论文
基于贪婪算法的排课系统的研究与实现
聂小东
指导教师:
学科门类:
专业名称:
申请学位级别:
论文提交日期:
论文答辩日期:
学位授予单位:
The Research and Implementation
of arranging course system based
on greedy arithmetic
    Author: Nie xiaoDong
Supervisor: Prof. LI ZhenKun
      A Thesis Submitted for the Master Degree
Institute of Computer Science GuangDong University of
                    Technology
        GuangZhou, GuangDong, P R.China
                    April, 2006
                                            摘要
旦旦旦旦里旦里鱼里旦鱼鱼旦旦旦旦旦旦旦巨旦旦旦旦旦旦鱼旦里鱼鱼，绝旦典旦旦旦旦旦旦旦巨鱼旦鱼鱼鱼鱼坦坦旦旦旦，巨
摘要
    目前，随着计算机的广泛应用和互联网技术的高速发展，在全国高校中许多
教学管理系统相继投入使用。然而，在实际项目的研发中，由于排课问题是一个
NP完全问题，开发出符合要求的排课系统是一件难事。
    针对排课系统研发和运行中存在的问题，尝试使用贪婪算法去研究和解决问
题。贪婪算法是从问题的某一个初始解出发，通过一系列的贪婪选择—当前状
态下的最优选择，逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算
法中的某一步不能再继续前进时，算法停止。在贪婪算法(greedy method)中采
用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策(在一定
的标准下)。
      基于此，以广东工业大学计算机工程研发中心与深圳大学成人教育学院合
作研发的排课系统为背景，在参照了排课算法的大量文献上，结合本系统的实现
和现在的运行情况上的不足，根据项目中客户排课的实际需求，基于贪婪算法，
以资源匹配为基础，用内存动态分区分配的最佳适应法为依托进行研发，最后设
计和实现该排课系统，在实际运行测试中表明，该排课系统的响应时间和排课结
果较满意，可以将此推广到其他教学管理系统的开发和实施上。
    论文最后对论文本身做了总结，阐述了论文的工作，并指出进一步研究的方
向。
关键词贪婪算法;教学管理;排课
广东工业大学工学硕士学位论文
ABSTRACT
    Nowadays,
of Internet,
with widely use of the computer and the quick development
many teaching management systems have being used in
succession in domestic universities. However, in the actual researching
project, arranging course is a NP proplem. It is difficult to develop a
good arranging course system for user.
    Aimed at the problem of reseaching and running of arranging course
system, I try to use greedy arithmetic to research and solve the problem.
Greedy arithmetic gets going from an initial solution to problem, through
a series of greeding chosen which is best chosen at currently status, and
it gets the aim step by step, hope to get the better solution as possible
as it can. When it reaches a step can not resumption, the arithmetic will
stop. Greedy arithmetic want to get the best solution step by step, at
every step, it will make a decision that seem to best.
    Based that theory, aimed at arranging course system that developed
by the center of computer engineering research and development in
GuangDong university of technology, refer to the arranging course
algorithmic of literature and the actual requirement of user, based the
greedy arithmetic and resource matching method, use dynamic memory
distributing best adapting method to develop. At last, we had desiged and
implement the arranging course system. At the test of running, the
response time and the result of system had reached satisfaction, it can
spead to development and implement of other teaching management system.
    At last, the thesis does the summary to itself, elaborate the work
of the thesis, and point out the direction of further research.
Keywords:Greedy arithmetic;Teaching Management;Arranging Course
11
目录
目录
要
摘
ABSTRACT..............................”二”.................................................................................................II
目录.............................................................................................................................................. III
CONTENTS.........................................................................”二”.““““.....……””.””“:.“一”......... VII
第一章绪论””.，…‘.“，.…”.，二，.…，”.，。二，……‘……，，.”，.”，..…，二‘“..……”.”.“…‘.“.....……”.““..…“二，二”......1
  1.1课题的来源.............................................................................................................................1
  1.2排课系统发展现状....……。......................................................................................................2
  1 .3本论文排课系统的解决方案.................................................................................................. 3
  1.4课题研究内容与意义.……，............……、、、...……，…、........................................................4
    1.4.1课题研究内容.，............................................................................................................... 4
    1.4.2课题研究意义.................................................................................................................. 5
    1.4.3特色之处........................................................................................................................... 5
  1.5论文内容组织......................................................................................................................... 6
第二章教学管理系统介绍.”““二””““..””..“二“..............................................................................7
  2.1项目需求................................................................................................................................. 7
  2.2网络拓扑............................................……，............................................................................ 8
  2.3教学管理系统的体系结构....................................................................................................10
  2.4系统功能模块.....................................……，......................................................................……11
  2.5数据库设计...........................……，.....……。..............................……，...................……，.......……13
  2.6排课概述.................................................................................……，.................................……14
  2.7系统的运行情况和问题及论文研究对象的导出..................................................................17
  2.8本章小结.....................................................................……，............................................……19
第三章排课系统的相关技术..…”.…”.“”.”.“.”””“…””.…””.…”““二”.……”“二”.”.“…”““二”......... 20
  3.1排课问题的求解技术综述................................................................................................... 20
广东工业大学工学硕士学位论文
3. 2 MULTIMAP关联容器....................……，...............................................................................……22
3.3贪婪算法介绍.…。..…。.......................................................……。…，......................................... 26
  3.3.1贪婪算法主要思想......................................................................................................... 26
  3.3.2贪婪算法的求解步骤..................................................................................................... 26
  3.3.3贪婪算法求解问题性质................................................................................................. 26
  3.3.4贪婪算法的求解例子..................................................................................................... 27
3.4本章小结.............................................................................................................................. 27
第四章基于贪婪算法的排课系统的研究与设计””…“”二”............................................................ 28
  4.1本排课系统采用贪婪算法的原因......................................................................................... 28
  4.2排课情况分析....................................................................................................................... 29
    4.2.1排课的要素.................................................................................................................... 29
    4.2.2排课过程的约束条件..................................................................................................... 29
    4.2.3排课目标........................................................................................................................ 31
  4.3排课系统分析..................................................................................................................... 32
    4.3.1排课系统用例图............................................................................................................. 32
    4.3.2排课系统用例说明，..…，..…，.，，.…，，，，...……，..................……。.....····...···························一33
  4.4系统的体系结构。............................................................……。.，...............·......···············一34
  4.5类和数据库的设计................................................................................................................ 36
    4.4.1类设计..................................................……，....................................................……，.……36
    4.4.2数据库设计.。............................................................……。，.................................·........... 37
  4.6系统主要功能....................................................................................................................... 40
    4.6.1预排课............................................................................................................................ 40
    4.6.2最终排课..…。................……，.......................................................................................... 41
    4.6.3手动排课.......................................................................................................................42
    4.6.4合并班级........................................................................................................................ 45
    4.6.5删除排课结果................................................................................................................ 46
  4.7排课系统中的贪婪准则........................................................................................................ 47
    4.7.1为有上课时间要求的课程安排教室的贪婪准则............................................................47
    4.7.2为无上课时间要求的课程安排教室的贪婪准则............................................................ 47
                                                  目录
~.........，.....
  4.8数据结构............................................................................................................................... 48
    4.8.1教室信息数据结构及函数、链表...................................................……，.......................48
    4.8.2课程班信息数据结构及函数、链表............................................................................... 50
  4.9排课主要算法.................................……，...................................……，......……，....................... 51
    4.9.1排课主算法(<0层图)..…，............................................................................................ 51
    4.9.2信息结点初始化(加工1子图)................................................................................... 53
    4.9.3安排教室(加工2子图)........……，.............................................................................. 53
    4.9.4分裂教室结点(加工3子图)...................................................................................... 55
  4.10本章小结............................................................................................................................. 55
第五章基于贪婪算法的排课系统实现.””“二”.............................................................................. 56
  5.1预排课................................................................................................................................... 56
  5.2最终排课.........................................……。...........……，...........................................……。....……57
  5.3手动排课............................................................................................................……，....……58