2006085011.txt

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

把管理提高到一个新的水平。本文作者紧跟整个项目的每一个环节，参与并负责
了其中需求分析、设计和实施等大量实际工作，笔者是这个项目的项目经理和技
术骨干，是整个项目的总负责人和系统总的设计者。
    鉴于深圳大学成人教育学院排课需求方面的特殊性，如课室资源严重不足，
全日制与夜大混全排课等，原先的排课系统不再适用。为了解决此问题，开始了
广东工业大学工学硕士学位论文
对排课模块的重新研究和实现。
    作者和项目成员首先对项目的需求进行分析，从排课工作人员方面详细了解
排课的业务流程以及需要考虑的各种因素，再基于对大量排课算法文献进行研究
的基础上进行算法研究和设计，然后进行系统设计和数据库的分析设计，最后编
码和系统的现场实施运行。由于排课算法设计和实施的难度较大，笔者是排课系
统直接的具体负责人。
    然而，排课由于其牵涉到的不同资源如上课的校区、大楼、教室、课程、教
师、班级、学生及上课器材等，再加上学校本身的其他相关行政规定所构成的排
课规定，可以看出要进行能同时满足这些因素和限制条件的排课业务是非常复杂
和困难的。
    问题主要集中在两个方面:一方面深圳大学成人教育学院地处繁华地段，课
室资源严重不足，全日制与夜大混合排课，按原来的排课算法优化原则可能导致
排出的课表不理想。另一方面当前排课算法达到较优解的收敛速度比较慢，用户
修改相关资源条件后要等很久才能有结果，有时甚至不能收敛。本文紧密结合该
项目的实际设计和运行情况，结合贪婪算法，根据原来系统的设计和运行时的不
足之处，提出了基于贪婪算法的排课系统，以资源匹配为基础，用内存动态分区
分配的最佳适应法为依托，不采用回溯，并不一味追求结果的最优化，而以实用
为目标，解决该项目排课系统实现的难题。
1 .2排课系统发展现状
    计算机排课系统的研究是当前各大高校数字化教学改革中面临的一个比较
突出的问题。排课是各个大学的教学管理部门的常务性工作。每个学期都是教学
管理工作人员最头痛的事情〔5]。现在的排课几乎都是采用人工排课，而人工排课
存在效率低、容易产生疏忽、排课结果难以避免冲突、调课难度大等弊端。
    在国外，上个世纪50年代末就有人研究课表的编排问题，如1963年
Gotlieb曾提出一个课表问题的数学模型c5」之后课表问题的研究一直都比较活跃，
目前主要提出的研究方法有:模拟手工排课法、图论方法、拉格朗日法、二次分
配型法等多种方法。国外的研究表明，解决大规模的排课问题单纯依靠数学方
法是行不通的。从上个世纪80年代以来，国内的教学管理者和计算机工作者在
第一章绪论
课表编排方面做了大量的工作，研究了许多实用算法，也取得了一些学术成果[hl
fgl。具有代表性的计算机排课系统有:南京工学院的UTSS (A University
Timetable Scheduling System)系统、清华大学的TISER(Timetable SchedulER)
系统、大连理工大学的智能教学组织管理及课程调度系统等。但这些系统都模拟
它们各自的手工排课，以“班”为单位，依赖于各个大学的传统学年制教学体制，
不宜于进行大量推广以及适应现行学分制教学改革的要求[(9l0
1.3本论文排课系统的解决方案
    学分制改革是近年来我国高等学校教育教学改革的一项重要举措。推行学分
制，体现了注重素质修养、加强通识教育、优化课程体系，培养复合型人才等
特点，对扩大学生学习自主权，实行因材施教，激发教学工作的活力，深化
教学改革，提高人才培养质量起着重要的作用。学分制的核心是选课制，选课
制的实施使学生变被动学习为主动学习，为学生在选择所修课程、学习方式和方
法、授课教师、授课时间及地点等诸多方面提供了广阔空间与自由。这种以人为
本、因材施教的教学管理机制有助于调动学生学习的积极性和主动性。选课制的
实现前提是与之相适应的合理排课。在高校的教学管理工作中，课表的编排是一
项十分复杂、棘手的工作。
    本论文为适应学分制的要求，在流程方面采取以下方案:教学计划实施任
务一一预排课一一选课一一最终排课。
    预排课:对严格按教学计划时间安排进行学习的班级学生(大部分学生都是
这样的)进行安排，每门课程的上课人数默认为班级注册人数。这里最关心的是
上课时间。
    选课:根据预排课的课表结果，学生上网进行选课，避免自身的上课时间冲
突。这时学生除可以选自己教学计划那部分的课程，也可以根据自己的学习能力
选择其他课程。
    最终排课:根据选课的情况确定课程的上课人数然后进行安排，与预排课不
同的是，此时课程已经有上课时间的要求，需要根据课程的选课人数适当调整课
室，结果包括上课时间和上课地点都要保存到数据库。
    如果此时为了达到最终排课结果的优化，采用一般的排课算法，则可能要求
广东工业大学工学硕士学位论文
对上课时间重新安排，这可能与在网上学生选课的时间安排存在冲突，会引起教
学秩序的混乱。因此在算法方面本文采取以下方案:
    (1)融合Se lim[''[ Z"3'和Loo['] ['〕的思路，在对课程科目进行处理时，先对已经
指定时间的科目进行安排，然后再对没有指定时间的科目进行处理。
    (2)为了提高排课速度，并不一味追求结果的最优化，而是基于贪婪算法，
以资源匹配为基础，用内存动态分区分配的最佳适应法为依托，把教室的可用资
源(综合教室可容纳人数以及可用的时间)按照从大到小排成一条链，把申请教
室的课程班按照班级人数从多到少排成另一条链。而后取出课程班去申请教室资
源，这样可形成大班优先排课的机制，保证大班一定有教室可上课。
.4课题研究内容与意义
.4.1课题研究内容
    本课题的背景是广东工业大学计算机工程研发中心与深圳大学成人教育学
院合作研发的教学管理系统，在教学管理系统项目研发和运行的过程中，发现排
课问题是比较复杂的。
    在开发和运行实践中，存在的问题主要表现在:
    一是排课涉及到教室、教师、班级、课程、时间及其他人为要求等多个约
束条件，排课方案的可能数目随问题规模的缓慢增长将急速上升，出现“组合爆
炸”。
    二是当前排课算法达到较优解的收敛速度比较慢，用户修改相关资源条件
后要等很久才能有结果，有时甚至不能收敛。
    三是深圳大学成人教育学院课室资源严重不足，全日制与夜大混合排课，
按原来的排课算法优化原则可能导致排出的课表不理想。
    在论文阶段，作者完成的工作是按照导师项目课题组的要求，完成排课系
统的系统分析、算法研究和设计、实现和测试，主要内容包括:
    1.在参照了排课算法的大量文献上，根据项目中排课的实际需求，设计基
于贪婪算法的排课方案、数据结构、主要算法步骤等。
    2.根据排课的需求，依据排课时的实际考虑因素，确定贪婪算法中的贪婪
第一章绪论
准则。
    3.采用三层体系结构，将基于贪婪算法的排课核心程序写成线程的形式成
为中间层，由排课主界面程序调用后在后台开辟线程进行运行，不影响其他功能
的继续操作。
    4.为了提高排课速度，将数据库中的数据读取到内存中进行处理，算法应
用了C++ STL(标准模板库)中的multimap关联容器建立两条链表，一条是教
室信息链，另一条是课程班信息链，然后进行基于资源匹配的贪婪准则的排课算
法的运行。
    5.采用面向对象方法分析设计整个排课系统，用C十+Builder6.0工具开发实
现该排课系统，并在实践中验证。
4.2课题研究意义
    课表是教学管理工作开展的基础，排课是教学管理中复杂、庞大、工作量较
大的工作任务，而排课问题是一个NP完全问题，研究开发一个实用的排课系统
具有非常重要的意义:
    1.排课系统得出的课表更加合理，资源得到更充分的利用;
    2.排课系统的运行可以减轻工作人员的排课工作量，提高效率;
    3.排课方案改动时，容易马上产生一个新的课表。
.4.3特色之处
    本论文的目的是要实现一个实用的排课系统，让用户能够根据资源情况比
较快地排课。具有以下特色:
    1、利用贪婪算法有效抑制排课中的“组合爆炸”现象。
    2、通过资源匹配方法实现贪婪策略，符合排课实际要求。
    3、提高了排课速度。并不一味追求结果的最优化，而是以资源匹配为基础，
用内存动态分区分配的最佳适应贪婪算法为依托，不采用回溯，所以排课速度得
到提高。
广东工业大学工学硕士学位论文
1.5论文内容组织
    贪婪算法是一个应用得比较广泛的算法，本文根据排课系统的实现和现在
的运行情况上的不足，提出基于贪婪算法的排课系统，并初步实现。
    本文的组织如下:
    第一章绪论首先阐述了课题的来源，接着分别阐述排课系统的发展现状
和本论文排课系统的解决方案，最后指出了课题研究的内容、意义和研究成果。
    第二章教学管理系统介绍，介绍了论文的项目情况，包括项目的项目需求、
网络拓扑，体系结构，模块功能，数据库设计和排课的概述，并指出排课系统存
在的不足，从而引出本文的论题，为文章后续部分引出基于贪婪算法的排课系统
研究和实现的描述作了一定的铺垫。。
    第三章排课系统的相关技术，综述了排课问题的求解技术，介绍项目中
用到的multimap关联容器技术，最后介绍了贪婪算法，包括主要思想、求解步
骤、求解问题的性质和求解例子等。
    第四章基于贪婪算法的排课系统的研究与设计。首先阐述了本排课系统采
用贪婪算法的原因，接着对排课的情况进行分析，然后对整个排课系统进行分析
设计，包括用例图、体系结构、类、数据库和主要功能等。根据项目的实际情况
定出排课中用到的贪婪准则，然后详细地描述排课算法中用到教室和课程班的数
据结构，给出了主要的算法。。
    第五章基于贪婪算法的排课系统实现。对各部分功能，包括预排课、最终
排课、手动排课、合并班级、删除排课结果和保存排课结果给出详细的实现，还
将总控程序、排课、信息结点初始化、分裂教室结点的关键代码都给出来了。
    第六章运行情况分析及展望。介绍了运行情况和分析，以及展望和进一步
的工作。
    最后是论文的结论部分，总结完成的工作，并指出不足和进一步的研究。
第二章教学管理系统介绍
第二章教学管理系统介绍
2. 1项目需求
    随着中国教育、科研计算机网络和各校校园网的建设和发展，大部分学校都
具备较好的网络通讯环境，网上MIS建设已成为各校当务之急。10多年的经验
证明，MIS建设工作的开展，促进了高校管理体制的改革，管理观念的更新。建立
教学管理系统是为了更充分利用学校的人、财、物和信息资源，达到信息集成、
高效管理的目标，提高学校的教学质量。各大高校为了提高整个学校的教学管理
水平，纷纷提出教学管理系统的研发需求。
    为此广东工业大学计算机研发中心已经为多家高校开发了教学管理系统，通
过网络的构建，系统的开发，优化了业务流程，将教学管理网络化、规划化，实