排课系统的设计与实现毕业设计(论文)(编辑修改稿)

排课系统的设计与实现毕业设计(论文)(编辑修改稿)内容摘要：

另一个功能，学院在这块可以查询本学院的课表，还有学院内班级的课表。 还有对已排好的课程做一些调整操作。 自动排课模块 这一模块主要完成课程上课时间、上课地点的安排。 它的实现运用了遗传算法中的选择、交叉、变异等操作，对算法得出的结果中最好的一个个体保留，就是要求的结果，虽然不是最完美符合的，但是它的适应度值已经完全可以符合学校教学所要求的了。 然后，对这个（班级，教师，课程，时间）记录做变换，让位置表去填充它，当然是按条件填充，就可以完成整个排课的大部分工作了，从而得到课 表。 此图描述了功能模块图，如图 2示： 9 图 2 功能模块图 Chart 2 the function model chart 排课是将教师与学生在时间和空间上根据不同的约束条件进行排列组合，在此同时也要安排课程，以使教学正常进行。 在本文约束条件主要为避免冲突，所谓冲突，它所包含的内容很广泛，几乎发生在所有两个或多个排课涉及因素之间。 避免冲突也是排课问题中要解决的核心问题。 只有在满足全部约束条件和避免所有冲突的基础上，才能保证整个教学计划合理正常进行。 而对教师、教室、学 生及时间等几部分资源进行最优化组合配置，才能保证充分发挥各资源的优势和提高教学质量。 在本文中，我们把排课过程中的约束条件分为三类 :基本硬约束、硬约束和软约束。 其中基本硬约束是指教师、学生和教室在时空概念上发生了不可能发生的事情，既是时间，空间，人之间的矛盾，它是排课过程中最基本的约束条件，也是众多排课模型中都要涉及的约束条件；硬约束是根据学校的实际情况，排课时必须遵循的原则，否则将会导致排课结果无意义，所以要因地制宜；软约束是指排课过程中满足更 10 佳但不满足又无妨的约束条件，这些条件的目的就是使课表更加人性化 ，每个排课都是要突出解决软约束这个问题的，违背这些约束就与实际情况相悖。 所以，可知在三类约束条件之中，前两者是衡量排课方案是否切实可行的基本标准，软约束是衡量排课方案是否人性化的标准，通常判别一个排课方案的优劣标准有多个。 可以把排课过程常见的约束条件分类罗列如下表 22所示，这些约束条件 也比较符合排课过程的实际情况。 表 22 约束表 Table 22 constraint table 基本硬约束 B1 同一时间，同一班级不能上两门不同的课程 B2 同一时间，同一个教师不能上两门不同的课程 B3 同一个时间，同一个教室不能上两门不同的课程 硬约束 H1 课程的学时在每周要均匀化 H2 满足每门课的特定教学资源 H3 教室足够大，能够容纳学生 H4 某些课程要特定安排，如某些教师的课程要固定 H5 教师学生上课不能用于在路途上的奔波 H6 体育课尽量安排在下午 软约束 S1 课程的分布要做到离散化 S2 一周有些时段处于最佳利于学习时间 S3 尽量不让老师连着上课 S4 班级相邻上课地点尽量近些 3 自动排课系统的设计 在本课题中，遗传算法解决的 问题只是求出班级 +课程 +教师 +时间的记录集，得到比较优的一个解，然后再去按条件用教室去填充这个记录集，就形成了可行可用的课 11 表。 这块的设计在整个系统是最重要的，效率的高低，课表的优劣都由本模块确定。 整个系统的流程分为以下几个主要的过程 : (1)初始种群的产生 :首先基因的编码，根据制定的编码方案，对每条染色体进行初始化，其次一条条染色体组成一个个体，既是形成一个二维表（可称为课表，但是适应度值不高）。 (1)冲突检测和消除 :初始化种群后，先对其进行各类冲突的检测，如存在冲突则消除它，而且在每次产生下一代后都要 进行冲突检测。 (2)计算出每个个体的适应度函数值，以进行优胜劣汰。 (3)遗传操作 :包括选择算子、交叉算子和变异算子，产生子代，逐渐优化。 (4)迭代第四步，直到进化停止，就是 generation=终止代数 N。 (5)班级 +课程 +教师 +时间的记录集的产生。 图 3 遗传算法流程图 实施遗传算法的第 1 步，就是把与求解目标相关的实际参数进行基因编码，这是算法的关键与难点。 12 混合式编码 构造合适的基因结构是遗传算法能否顺利实现的关键，设定混合式的教师编码作为本系统遗传算 法的“基因”。 二进制基因构成规则为 :是否固定 *教师编号号 *课程编号 *课程性质分别对应的宽为 1+15+16+16 共 6B。 下面我们给了很清晰的解释： 图 4 编码结构图 下面我们对每个字段给予解释： 有些教师的课程是固定在某个时间段的，所以在排课过程中，判断第一位就可以得知可否移动此基因片。 这也反应了排课要人性化，毕竟有些教师有特殊的要求，例如，年龄、事物等等。 我们给了 15bit 去表示教师， 15bit 能表示 215个数，足矣满足任何一所高校的教师编号，所以，在数据库里，教师表里 教师编号的数据项要为短整型。 唯一确定一门课程， 216个数，也足以表示一个学校的课程。 为了解决“特定资源”冲突问题，可在教师编码中加上 2B表示该教师所教授的课程的性质。 每一门课程都有其各自不同的特点，比如上机课需要在机房上课，英语口语需要在语音室上课，体育课需要在操场上课，为此我们规定：把 16bits分开，前后8bits 各有不同的意思； 13 图 5 比特信息图 在此我们把课程分为专业必修课，专选科，公共课，上机实验课，专业实验课，体育课，英语语音课，前 三个属于理论课，不在此分配教室。 区分：计算机专业的实验课是和非计算机专业的上节实验课不同的，他们有自己的实验室，属于专业实验课。 前 8 位编码不同时表示不同的意思： 表 31 编码课程关联表 Table 31 the relational table of coding and course 编码值 表示课程类 10000000 专业必修课 11000000 专业选修课 11100000 公共课 11110000 上机实验课 11111000 专业实验课 11111100 体育课 11111110 语音课 后 8位编码表示当此教师固定在这个时间片上课时，所在的时间片值。 染色体的表示 对于每一门课程既可能只上一次 (规定 2 学时课占用一个时间片 )，也可能 上多次，如 4学时、 6学时等。 上 2学时课时，该教师编码只能出现 1次，上 4 学时课时该教师编码出现 2次，依次类推。 在大多数，每周上 6 学时的课程不会太多，大多数时 4 学时和 2 学时； 通过以上把课程与教师等同的处理后，原课表的五要素 (班级、教室、课程、时间、教师 )转化为四要素 (班级、课程、时间）和班级。 功能室 (实验室机房、语音室等 )已经 在编码时分配好，而理论课的那些，要等到后面再去分配。 为了更好地阐述排课遗传算法，定义排课遗传算法名词： a.“基因” —— 混合型的教师编码，即 TIT25 时间片中的值； b.“染色体” —— 班级名称与 TlT25 中的“基因”组成的串； c.“个体” —— 由 bjs（班级数）个染色体组合而成的二维数据表，即对应于一张课表。 其中 BJS 为参与课表编排的班级总数； 14 d.“种群” —— 由 ZQS 个个体构成。 其中 ZQS 为种群大小。 初始化种群 每一个“染色体”都是班级的一个课表，是开课任务书中的一个班级所有记录组成的 ，形成的是班级 +教室 +课程 +时间一条记录。 对每一个课程表可以形成一个二维数组 kcb (25,bjs)，每一列就表示一个班级的课表。 首先把固定教学时间的教师编码填入该行中，然后使用随机函数产生一个 1— 25 的数，将该班的其它教师编码填入其中。 如产生的随机数对应的时间片中己有数据，则重新产生，直到将所有教师编码无重复地填入该行中。 这样就有了一条染色体 (一个初始的班课程表 )。 如此循环 bjs 次，产生了与班级数目对等的染色体数目。 于是，一个初始个体便产生了。 按种群规模的大小 ZQS，产生一定数量的个体，每个个体都存放到 一个按序编号的表中，由这些个体组成初始种群。 很明显，由上述方式产生的个体通常含有大量的冲突。 另外，在初始化种群时，基于容器的容器使其更加简捷。 对于数据库中教学楼，教室，班级等一些数量都未知的数据进行存储，运用数组显然不能解决，会出现很多的冗余，浪费内存，并且处理繁琐。 关联容器的使用方法如图 6所 示： 图 6 容器结构图 完成种群初始化后，个体的数据结构如下图示： 15 图 7 个体结构图 4 数据库问题 数据库设计 数据库设计是建立系统数据库及其应用系统的重要环节，系统的各个部分能否紧密地结合在一起以及如何结合，关键在数据库，只有对数据库进行合理的逻辑设计和有效的物理设计才能开发出完善而高效的排课系统。 本文的数据库设计及其实现如下： 概念模型设计 因为概念结构是面向现实世界的，用户容易理解，能够参加设计讨论，提出意见，在将分析结果抽象为逻辑数据库时可以降低设计的难度。 这会将数据库的概念结构转换为逻辑结构方法简单，易于实现。 对于排课问题要进行的分析主要有 :教学计划、各学院教学任务、教室基础数据、时间模式、开 课任务、及各种课表等数据。 这些关系用 ER图表示如图 8， 9， 10: 16 图 8 院管理 ER图 图 9 校管理 ER图 图 10 总 ER图 逻辑模型设计 在逻辑模型设计中，并不是划分数据的粒度越小越精确就会越好，而是要符合设计现状要求和系统实现便捷，也就是说，范式越高也不一定越好。 具体来说创建了以下各表 : 表 41 用户表 :User Table 41 user table:User 编号 数据项 数据项别名 数据类型 数据项含义 1 用户名 username Char(12) 唯一 2 密码 passwd Char(20) 3 学院 academy Char(20) 学院名，如果空的话就 17 是代表教务处 表 42 教学计划表 :TeachPlan Table 42 teaching plan table:TeachPlan 编号 数据项 数据项别名 数据类型 数据项含义 1 班级 class Char(15) 主属性 2 班级编号 Cno Char(10) 主属性 3 课程 course Char(15) 4 课程编号 courseNo Smallint(2) 主属性 5 学院 academy Char(15) 6 人数 Pno int 7 课程属性 courseAtrr Char(15) 8 周节数 pitchNum Smallint(2) 9 周数 weekSum Smallint(2) 10 开课学期 semester Char(15) 表 43 教室表： Classroom Table 43 classroom table： Classroom 编号 数据项 数据项别名 数据类型 数据项含义 1 教学楼 Tbuilding Char(10) 主属性 2 门号 houseNo Char(10) 主属性 3 容纳人数 containSum int 4 教室属性 houseAtrr Char(10) 表 44语音课体育课上机课位置表： Y_T_S Table 44 the place table： Y_T_S 编号 数据项 数据项别名 数据类型 数据项含义 1 类别 category Char(1) 区别三类教室 2 教室名 roomname Char(15) 18 3 教室编号 roomID smallint 4 班级 class Char(15) 加上班级就可以确定班级上课的位置范围 5 学院 academy Char(15) 表 45 理论课教室表： LLKAddress Table 45 the classroom table of theory course： LLKAddress 编号 数据项 数据项别名 数据类型 数据项含义 1 学院 Academy Char(20)。