基于遗传算法的高校排课数学模型
- 格式：pdf
- 大小：281.42 KB
- 文档页数：5
取得 较好 的排课 效果 。
１ 排课 问题
高校 的排课 问题 就是研 究如 何将 众多 的课程 编排 到 固有 的教 室和有 限的上课 时 间单 元上 ，如 何将课 程 编排给 老师 和学生 。主 要解决 的 问题 是根 据 教 学 任务 将 教 师 、班 级 、课 程 、教 室 安排 在 某 个 不相
程。
班级 要素 ：每个 行政 班级都 设有 班级 名称 、编号 和人数 等 ，并设定 在 同一 时间 只能上 一 门课 程 。 课程 要素 ：每 门课程 都设有 课程 代码 、课程 名称 和 开课 院系 等课 程信 息 ，并 且 根 据学 分 、总 学 时 、
周学 时等 安排 授课计 划 。
时 间要素 ：在排 课过 程 中 ，通常 以周 为单位 安排 授课周 期 。一般 每周 上课 时间不 超过 ５天 ，每天 划
分 上午 、下午 和晚 上 ３个 时 间段 ，每 个时 间段都 设定 上课节 数 ，例如 上 午 ４节课 、下 午 ４节 课 、晚上 ３
节课 。一 节课 为一个 课 时 ，一 般一 门课程 的上课 时 间为两个 课 时 。
教室集合 Ｒ＝ ｛ ，： ｒ ｒ，… ，， ｒ ，…， ｝ 各教室可容纳人数为 ｛ 。 ｈ ，…， ， ， ｈ， ｈ，…， ； ｈ｝ 时 间集 合 Ｔ＝ ｛ ，ｔ，… ，ｔ ｔ ２ ，… ，ｔ｝ 。时 间与 教 室对 的笛 卡 尔 积为 ：Ｍ ＝Ｔ・ Ｒ＝ （ ，ｒ） （ ｔ 。 ， ｔ，
钟 耀 广 刘群 锋
（．东莞理工学院 １ 教务处 ，广东东莞 ５ ３０ ；２ 东莞理工学 院 ２８８ ． 计算机学 院，广东东莞 ５３ ０ ） ２ ８８
摘 要 ：排课 问题是一 个有 约束 、多 目标的组合优 化 问题 ，并且 已经被证 明是 一个 Ｎ Ｐ完全 问题 。针对 高校 排课过 程 中存在诸 多约束 因素 的问题 ，提 出将遗传算法与 约束 条件算法相 结合 的排课 算 法，由约束条件 算法 确定排课任 务的优先 次序 ，遗传算 法解决单个排课任务 时间片分配 的优 化 １题 。实验结果表 明 ，该算 法能够 － ＂ ３ 改进算洳 ｝ ，提 高排课效率 。 生能 关键词 ：遗传算 法；约束 满足 ；排课 问题 中图分 类号：０ ４ ． １ １４ 文献标识码 ：Ａ 文章编号 ：１０ ０ １ （ ０ ２ ５— ０４—０ ０ ９— ３２ ２ １ ）０ ０ ０ ５
随着 我 国高 校 的扩招 ，学生规 模 大幅增 长 ，而面 临教学 资源 配套不 上 的紧张局 面 ，使排课 成 为教务 管理 中一个 棘手且 费 神 的工 作之一 。排 课 问题实 际是一 个典 型 的多约束 、多 目标优 化组 合 问题 ，已被证 明为 Ｎ （ 项式难 度 ） 完 全 问题 。这类 问题 的求 解 只 能 找 到 较 满 意 、较合 理 的解 ，而非 一个 最 优 Ｐ 多 解 。有些研 究人 员尝试 各种 算法 来解 决 ，例如 贪 心 算 法 、模 拟退 火 算 法 和 图论 算 法 等 ］ ，取 得 了一 定
教室 要素 ：每 问教室 都设 有相应 的名称 、门牌号 和教 室类 型等 ，并 设定 在 同一 时间 内只能容 纳 一 门
课程 上课 ，而 且教 室容量应 该 大于或 等 于上课 的人数 。
收 稿 日期 ： ０ ２— ５—１ ２１ ０ １
ห้องสมุดไป่ตู้
基金项 目： 东莞理工学院教育教学改革与研究项 目 （ １６ １８ 。 Ｅ ２２ ０ ） 作者简介 ： 钟耀广 （ ９ ９ ） １７ 一 ，男 ，广东东莞人 ，讲师 ，主要从事教育管理 、运筹管理等研究 。
第 ５期
钟耀广 ，等 ：基于遗传算法的高校排课数学模型
５
假设 学校 涉及 到排课 的资源有 ｃ个行 政班 级 ， 门课 程 ，．位 教 师 ， 个 时 间段 ，Ｒ个教 室 ，其 数 ，
学 模型 描述 如下 ：
班 级集 合 Ｃ＝ ｛ ｃ，… ，ｃ，… ，ｃ ｝ ｃ， ： 。 ，每一 成 员 为 一 个 行 政 班 级 。各 行 政 班 级 人 数 分 别 ｛ ｂ， ｂ，… ， ２ ｂ，… ，ｂ ｝人 ； ｃ 课 程集 合 Ｋ＝ ｛ ｋ，… ， ｋ， ： ｋ，… ， ｝ ｋ ，每 门课 程 对应 一 位 教 师 ，各课 程 对 应 的班 级 数 为 ｛。 ｅ， ｅ，… ， ２ ｅ，… ， Ｅ ； ｅ ｝ 教 师集 合 Ｊ ｛ ， ，… ， ，… ， ，各 教师 对应 课程数 ｛ ｄ ，… ， ，… ， Ｊ ； ＝ Ｊ 。 力｝ ｄ， ： ｄ ｝
冲 突的上课 时 间单元 里 Ｊ 。可见 ，课程 的编排 不 仅 涉 及参 与 课 程 的 主体 教 师 和 学生 ，教 室和 时 间也是
课程 编排 的重要 因素 。 影 响排课 的要 素及其算 法有 以下 几种 ： 教师 要素 ：每位 教师都 设有 教 师 姓 名 、工号 和职 称 等教 师 信 息 ，并 设定 在 同一 时 间 只能 授 一 门课
第 １ ９卷第 ５期 ２ １年 １ 月 ０２ ０
Ｊ ＲＮ ＯＵ ＡＬ ＯＦ ＤＯＮ ＧＧＵ ＮＩ ＥＲ Ｉ Ｙ Ｅ ＨＮ ＯＧ ＡＮ Ｕ Ｖ Ｓ Ｔ ＯＦ Ｔ Ｃ ＯＬ Ｙ
东 莞 理 工 学 院 学 报
ＶＩ１ Ｎ ． ０ ９ ｏ５ ＿
０ｃ ． ｔ ２ １ ０２
基 于遗 传 算 法 的高 校排 课 数 学模 型
的效果 。但到 目 前为止，还没有一种算法具有绝对优势。遗传算法 （ ｅｅｃＡｇｒｈ Ｇ ｎｔ ｌ ｉ ｍ，Ｇ ）作为随机 ｉ ｏｔ Ａ
优化 与搜 索方法 ，通 过对可 行解进 行选 择 、交叉 、变异 等遗传 算 法的作 用使种 群不 断进 化 ，最后 得到 全 局最优 解 或近似 最优解 ，成 为求解 排课 问题 的主要 方法 。本 文尝试 综合 多个排 课 约束 因素 ，利用 约束满 足算法 筛选 自由度小 的排课 任务 ，再应 用遗 传算法 对所 要安排 的课 程任 务求得 最优 解或 近似 最优解 ，以
１ 排课 问题
高校 的排课 问题 就是研 究如 何将 众多 的课程 编排 到 固有 的教 室和有 限的上课 时 间单 元上 ，如 何将课 程 编排给 老师 和学生 。主 要解决 的 问题 是根 据 教 学 任务 将 教 师 、班 级 、课 程 、教 室 安排 在 某 个 不相
程。
班级 要素 ：每个 行政 班级都 设有 班级 名称 、编号 和人数 等 ，并设定 在 同一 时间 只能上 一 门课 程 。 课程 要素 ：每 门课程 都设有 课程 代码 、课程 名称 和 开课 院系 等课 程信 息 ，并 且 根 据学 分 、总 学 时 、
周学 时等 安排 授课计 划 。
时 间要素 ：在排 课过 程 中 ，通常 以周 为单位 安排 授课周 期 。一般 每周 上课 时间不 超过 ５天 ，每天 划
分 上午 、下午 和晚 上 ３个 时 间段 ，每 个时 间段都 设定 上课节 数 ，例如 上 午 ４节课 、下 午 ４节 课 、晚上 ３
节课 。一 节课 为一个 课 时 ，一 般一 门课程 的上课 时 间为两个 课 时 。
教室集合 Ｒ＝ ｛ ，： ｒ ｒ，… ，， ｒ ，…， ｝ 各教室可容纳人数为 ｛ 。 ｈ ，…， ， ， ｈ， ｈ，…， ； ｈ｝ 时 间集 合 Ｔ＝ ｛ ，ｔ，… ，ｔ ｔ ２ ，… ，ｔ｝ 。时 间与 教 室对 的笛 卡 尔 积为 ：Ｍ ＝Ｔ・ Ｒ＝ （ ，ｒ） （ ｔ 。 ， ｔ，
钟 耀 广 刘群 锋
（．东莞理工学院 １ 教务处 ，广东东莞 ５ ３０ ；２ 东莞理工学 院 ２８８ ． 计算机学 院，广东东莞 ５３ ０ ） ２ ８８
摘 要 ：排课 问题是一 个有 约束 、多 目标的组合优 化 问题 ，并且 已经被证 明是 一个 Ｎ Ｐ完全 问题 。针对 高校 排课过 程 中存在诸 多约束 因素 的问题 ，提 出将遗传算法与 约束 条件算法相 结合 的排课 算 法，由约束条件 算法 确定排课任 务的优先 次序 ，遗传算 法解决单个排课任务 时间片分配 的优 化 １题 。实验结果表 明 ，该算 法能够 － ＂ ３ 改进算洳 ｝ ，提 高排课效率 。 生能 关键词 ：遗传算 法；约束 满足 ；排课 问题 中图分 类号：０ ４ ． １ １４ 文献标识码 ：Ａ 文章编号 ：１０ ０ １ （ ０ ２ ５— ０４—０ ０ ９— ３２ ２ １ ）０ ０ ０ ５
随着 我 国高 校 的扩招 ，学生规 模 大幅增 长 ，而面 临教学 资源 配套不 上 的紧张局 面 ，使排课 成 为教务 管理 中一个 棘手且 费 神 的工 作之一 。排 课 问题实 际是一 个典 型 的多约束 、多 目标优 化组 合 问题 ，已被证 明为 Ｎ （ 项式难 度 ） 完 全 问题 。这类 问题 的求 解 只 能 找 到 较 满 意 、较合 理 的解 ，而非 一个 最 优 Ｐ 多 解 。有些研 究人 员尝试 各种 算法 来解 决 ，例如 贪 心 算 法 、模 拟退 火 算 法 和 图论 算 法 等 ］ ，取 得 了一 定
教室 要素 ：每 问教室 都设 有相应 的名称 、门牌号 和教 室类 型等 ，并 设定 在 同一 时间 内只能容 纳 一 门
课程 上课 ，而 且教 室容量应 该 大于或 等 于上课 的人数 。
收 稿 日期 ： ０ ２— ５—１ ２１ ０ １
ห้องสมุดไป่ตู้
基金项 目： 东莞理工学院教育教学改革与研究项 目 （ １６ １８ 。 Ｅ ２２ ０ ） 作者简介 ： 钟耀广 （ ９ ９ ） １７ 一 ，男 ，广东东莞人 ，讲师 ，主要从事教育管理 、运筹管理等研究 。
第 ５期
钟耀广 ，等 ：基于遗传算法的高校排课数学模型
５
假设 学校 涉及 到排课 的资源有 ｃ个行 政班 级 ， 门课 程 ，．位 教 师 ， 个 时 间段 ，Ｒ个教 室 ，其 数 ，
学 模型 描述 如下 ：
班 级集 合 Ｃ＝ ｛ ｃ，… ，ｃ，… ，ｃ ｝ ｃ， ： 。 ，每一 成 员 为 一 个 行 政 班 级 。各 行 政 班 级 人 数 分 别 ｛ ｂ， ｂ，… ， ２ ｂ，… ，ｂ ｝人 ； ｃ 课 程集 合 Ｋ＝ ｛ ｋ，… ， ｋ， ： ｋ，… ， ｝ ｋ ，每 门课 程 对应 一 位 教 师 ，各课 程 对 应 的班 级 数 为 ｛。 ｅ， ｅ，… ， ２ ｅ，… ， Ｅ ； ｅ ｝ 教 师集 合 Ｊ ｛ ， ，… ， ，… ， ，各 教师 对应 课程数 ｛ ｄ ，… ， ，… ， Ｊ ； ＝ Ｊ 。 力｝ ｄ， ： ｄ ｝
冲 突的上课 时 间单元 里 Ｊ 。可见 ，课程 的编排 不 仅 涉 及参 与 课 程 的 主体 教 师 和 学生 ，教 室和 时 间也是
课程 编排 的重要 因素 。 影 响排课 的要 素及其算 法有 以下 几种 ： 教师 要素 ：每位 教师都 设有 教 师 姓 名 、工号 和职 称 等教 师 信 息 ，并 设定 在 同一 时 间 只能 授 一 门课
第 １ ９卷第 ５期 ２ １年 １ 月 ０２ ０
Ｊ ＲＮ ＯＵ ＡＬ ＯＦ ＤＯＮ ＧＧＵ ＮＩ ＥＲ Ｉ Ｙ Ｅ ＨＮ ＯＧ ＡＮ Ｕ Ｖ Ｓ Ｔ ＯＦ Ｔ Ｃ ＯＬ Ｙ
东 莞 理 工 学 院 学 报
ＶＩ１ Ｎ ． ０ ９ ｏ５ ＿
０ｃ ． ｔ ２ １ ０２
基 于遗 传 算 法 的高 校排 课 数 学模 型
的效果 。但到 目 前为止，还没有一种算法具有绝对优势。遗传算法 （ ｅｅｃＡｇｒｈ Ｇ ｎｔ ｌ ｉ ｍ，Ｇ ）作为随机 ｉ ｏｔ Ａ
优化 与搜 索方法 ，通 过对可 行解进 行选 择 、交叉 、变异 等遗传 算 法的作 用使种 群不 断进 化 ，最后 得到 全 局最优 解 或近似 最优解 ，成 为求解 排课 问题 的主要 方法 。本 文尝试 综合 多个排 课 约束 因素 ，利用 约束满 足算法 筛选 自由度小 的排课 任务 ，再应 用遗 传算法 对所 要安排 的课 程任 务求得 最优 解或 近似 最优解 ，以
