高校排课问题的图论模型及算法
- 格式：pdf
- 大小：152.92 KB
- 文档页数：3
（2）图的边集 E 由顶点集的两个部之间的连线组成。若 T 中某一个老师教授 C 中的某一节课程，则将这两个顶点以实 线相连。以这种方式抽象排课问题得到了一个偶图。由于大学 里某一班级的同一课程基本上都是由一位老师担任教授，所以 偶图中第二顶点集（课程）的顶点度数都为 1。由于选择某一门 课程的学生也可能选择另外一门课程，因此这两门课不能安排 在同一时间段。如高数 1 班的某一学生也可能选择属于英语 2 班，因此在这两个班级课程之间用一条虚线相连，表示这两节 课不能同时上。
3 算法的设计
根据教学大纲，利用上述方法构造出图 G。假设图中共有 n 条实线边，根据课程的重要程度为每条实线边 e 设置权重为 we；图中顶点的最大度为△；有 L 个教室可以利用，则要求每个 颜色集内包含的边集至多为 L 个。
（1）构造 G=（C，E），其中 E=准 表示已着色的实线边集合， E 用来表示还没有着色的实线边集合。任意取一个整数 m（m≥ △），并构造数组 K=（k1，k2，…，km）代表 m 种颜色；令|ki|为着 ki 颜色的边的个数，初始值为 0；{{k1}，{k2}，…，{km}}分别为着这些 颜色的实线边的集合，初始值为 准。数组（K1，K2，…，Km）表示每 种颜色已着色边的权值之和，初始值为 0。根据实际所要达到 的课程的均匀程度及教室的数目适当选取参数 X，其中 X≤L。
作者简介：王凤（1980-），博士生，研究方向：决策支持系统、决策模型；林杰（1967-），教授，研究方向：决策支持系统、分布式仿真等。 收稿日期：2008-05-21 修回日期：2009-03-25
王 凤，林 杰：高校排课问题的图论模型及算法
2009，45（27） 241
11、高数 12、高数 13 区分成不同课程，类似的有高数 21、高数 22、高数 23，则全校所有班级的所有课程都可以正确区分了， 把这样的课程抽象成结点作为图顶点集的另外一个部分，依次 记为{C1，C2，C3，…，Cm}表示共有 m 次课程。
T1
T2
T3
T4
T5
C1
C2
C3 C4
C5 C6
C7 C8 C9 C10 C11
图 1 排课图
用边着色理论分配授课时间段：如果一个图可以用 K 种 颜色实现正常边着色，就说明，从每一个顶点发出的相邻边可 有不同的颜色。把一种颜色对应一个授课时间段，就可以保证 在一张有 K 个时间段的课表内，某个老师代的各班的课不在 一个时间段，同样，每个班级上的不同老师的课也不在同一个 时间段。这素不会发生冲突。在上述建立的模型中，运用边着色理 论，为图中每一条实线着色，且要求其顶点有虚线相连的实线 边着不同颜色。由此可以得到一组颜色集，每个颜色集就代表 了一次授课分配时间段，由此保证了老师学生的课程不发生冲 突。如图 1 所示：教师 T1 教高数 1 班的每周 3 节高数课 C1、C2、 C3。T2 教高数 2 班的每周 3 节课 C4、C5、C6。T3 教英语 1 班的每 周 2 节英语课 C7、C8。T4 教英语 2 班的每周 3 节课 C9、C10。T5 教 授全体学生每周 1 节的哲学课 C11。为每条实线边着色便可得 到一组颜色集，即一种授课时间分配方式。
的情况。对于单双周课或合班课可以进行“虚排”，然后再人工 减删，所空出的课时和教室留以待用或作其他安排。
（2）在每种课的编排时按先排时间课程表，再根据所排时 间课程情况配备以教室的排法。而为了保证在同一课时，教室 的资源的利用尽可能均衡，即在为图进行边着色时，为每个颜 色 ki 设置一个参数|ki|，记录其所包含边数的个数，并为它们设 置上限 X，通过对 X 的调整，使得每个颜色集的元素数量尽量 均衡。另外，若某两节课程要用相同的教室资源（如实验室）也 可将课程顶点集中对应的课程用虚线相连，以保证它们不被安 排在同一时间段。
基金项目：国 家 863/ CIMS 主 题 资 助 项 目（Projects supported by the National High - Tech.R&D Program for CIMS ，China under Grant No. 2007AA04Z151）；新 世 纪 优 秀 人 才 支 持 计 划 资 助（Program for New Century Excellent Talents in University，China under Grant No.NCET-06-0377）；上海市重点学科建设项目（Shanghai Leading Academic Discipline Project，No.B310）。
2.1 基于图论理论的简单模型
根据大学课表的特点，以周为单位，按下列方式抽象成图 G（V，E）：
（1）图的顶点集 V 由两部分组成，其一用 T={T1，T2，T3，…， Tn}表示有 n 个不同的教师，另一用 C={C1，C2，C3，…，Cm}表示所 有班级的所有课程集合，如高等数学有两个班级，高数 1 班、高 数 2 班，则用高数 1、高数 2 区分成不同课程；若每周课时多于 一次的课程，如高数 1 班在 1 周内需要排课 3 次，则用高数
240 2009，45（27）
Computer Engineering and Applications 计算机工程与应用
高校排课问题的图论模型及算法
王 凤 1，林 杰 1，2 WANG Feng1，LIN Jie1，2
1.同济大学 经济与管理学院，上海 200092 2.同济大学 电子商务与电子政务研究所，上海 200092 1.School of Economics and Management，Tongji University，Shanghai 200092，China 2.The Laboratory of E-commerce and E-government，Tongji University，Shanghai 200092，China E-mail：morning1231@
摘 要：针对排课系统的缺陷，提出了尊重学生学习规律，按照课程的重要程度和重要课程分配的时间间隔，利用图论的边着色理 论，对排课资源进行建模，并给出了有效的多项式时间算法，使得排课问题的解决更加合理与人性化。 关键词：高校排课；边着色；图论模型 DOI：10.3778/j.issn.1002-8331.2009.27.072 文章编号：1002－8331（2009）27-0240-03 文献标识码：A 中图分类号：TP39；O157.6
1 问题的提出
近二十年来，已经有许多学者针对不同应用环境的高校排 课问题给出不同的解决方案。通过图论的方式来研究排课问题 是一个比较典型的方法，但多数情况下对排课的数学抽象都过 于简单而且有些并不能符合实际情况。
例如：有些模型将教师和班级分别作为二部图的两个顶点 集，若某一教师教授某一班级的课程则将图中这两个顶点连 线，用求偶图对集的方式来为不同的班级安排授课时间。这种 模型忽略了大学教学中班级不固定的特点，导致了班级划分不 唯一。还有些模型将不同课程的所有班级一一列出，又会出现 英语一班的某个同学也同时属于高数一班，而按照模型的设置 并没有显示这两门课程不可以排在同一时间，进而引起冲突。 有些模型违背人类学习掌握知识的渐进式生理特点，将一门课 程的两次课（每次 2～3 学时）安排在一天之中，导致学生在两次 课之间根本没有时间去消化知识和完成作业；还比如，在班级 课表中，同样明显存在一周中的某一天课特别多，而有的天课 又特别少的情况。其次，在对待不同门类的课程方面，也经常出 现不合理的上课安排。比如，在同一个班中，将专业主干课排在 了非黄金时间（下午 3～4 节或晚上），而将较次要的选修课则排 在了黄金时间，等等。
（3）为保证重要课程安排在黄金时间，为每条实线边设置 一个权数，在着色的时候尽量使得所连权重相似的边着相同的 颜色。这样可以将重要的课程同时安排在课程的重要时间，避 免出现将重要程度相差很大的课程安排在同一颜色集中，导致 分配时间段时必须有所牺牲的情况。课程教学按照每周 5 天， 每天安排 4 个时间段：即上午 12 节、34 节和下午 56 节、78 节 的方式进行。上午 12 节课是黄金时段，一般安排重要的课程。3 节的课程一般安排在下午 567 节。在为模型的边着色过程中， 由于同一课程的一周内不同的课次是相邻的，因此它们被分配 了不同的颜色，即安排了不同的时间段。根据文献[1]：相同课程 不同课次的安排应该是交叉安排比较合理，如高数课程一周 3 次，安排在星期一 12 节，星期三 34 节，星期五 12 节；或星期一 34 节，星期三 12 节，星期五 34 节。在分配好颜色集后，由于颜 色集的数目不会很大（一般每周为 15~20 个时间段），将所有颜 色集按权数总和进行排序，根据权数大小进行交叉安排，使得 权数大的课程尽量优先安排。将相同课程的不同课次不安排在 同一天，以保证学生有时间去消化知识和完成作业。
2.2 排课模型的进一步完善
（1）大学课程的安排一般分为公共课，必修课和选修课。公 共课主要指像英语、计算机基础、高等数学、哲学等课程，它们 涉及全校较大范围的师生；必修课主要指专业必修课，这些课 一般只涉及各个系内师生；公共课和专业必修课都是以班级为 单位、由学校进行设置的课程，而选修课主要指以学生个人为 单位、由学生本人在某一范围内进行选择的课程。实际中的课 程经过处理都转化为上面三类，以便简化问题。排课中，对课程 采取公共课优先、必修课次之、选修课最后的排法。由于文献[1] 中对大学选修课排法做了详细深入地分析，指出：即使每位学 生最多选两门课程，问题仍然是难解的，这样得到在实际选课 过程中，优先将公共课与必修课安排好，再对选修课适当排列， 使得学生根据必修课的情况选择自己时间上允许的选修课。这 种方式保证了选课的不冲突性，而且将问题进行了分割以逐步 求解。避免了所有课程同时安排而出现没有足够的时间段分配
上述问题的出现，主要是模型的设计不当造成的，仅仅注 重排课资源中时间和教室问题，对人性化设计的要求重视不 够，即在算法设计中对老师、学生及课程情况考虑较少，对教与 学的规律尊重不够。因此，该文针对上述问题，构造出相对人性 化的排课模型，以期一定程度上改善该问题。
3 算法的设计
根据教学大纲，利用上述方法构造出图 G。假设图中共有 n 条实线边，根据课程的重要程度为每条实线边 e 设置权重为 we；图中顶点的最大度为△；有 L 个教室可以利用，则要求每个 颜色集内包含的边集至多为 L 个。
（1）构造 G=（C，E），其中 E=准 表示已着色的实线边集合， E 用来表示还没有着色的实线边集合。任意取一个整数 m（m≥ △），并构造数组 K=（k1，k2，…，km）代表 m 种颜色；令|ki|为着 ki 颜色的边的个数，初始值为 0；{{k1}，{k2}，…，{km}}分别为着这些 颜色的实线边的集合，初始值为 准。数组（K1，K2，…，Km）表示每 种颜色已着色边的权值之和，初始值为 0。根据实际所要达到 的课程的均匀程度及教室的数目适当选取参数 X，其中 X≤L。
作者简介：王凤（1980-），博士生，研究方向：决策支持系统、决策模型；林杰（1967-），教授，研究方向：决策支持系统、分布式仿真等。 收稿日期：2008-05-21 修回日期：2009-03-25
王 凤，林 杰：高校排课问题的图论模型及算法
2009，45（27） 241
11、高数 12、高数 13 区分成不同课程，类似的有高数 21、高数 22、高数 23，则全校所有班级的所有课程都可以正确区分了， 把这样的课程抽象成结点作为图顶点集的另外一个部分，依次 记为{C1，C2，C3，…，Cm}表示共有 m 次课程。
T1
T2
T3
T4
T5
C1
C2
C3 C4
C5 C6
C7 C8 C9 C10 C11
图 1 排课图
用边着色理论分配授课时间段：如果一个图可以用 K 种 颜色实现正常边着色，就说明，从每一个顶点发出的相邻边可 有不同的颜色。把一种颜色对应一个授课时间段，就可以保证 在一张有 K 个时间段的课表内，某个老师代的各班的课不在 一个时间段，同样，每个班级上的不同老师的课也不在同一个 时间段。这素不会发生冲突。在上述建立的模型中，运用边着色理 论，为图中每一条实线着色，且要求其顶点有虚线相连的实线 边着不同颜色。由此可以得到一组颜色集，每个颜色集就代表 了一次授课分配时间段，由此保证了老师学生的课程不发生冲 突。如图 1 所示：教师 T1 教高数 1 班的每周 3 节高数课 C1、C2、 C3。T2 教高数 2 班的每周 3 节课 C4、C5、C6。T3 教英语 1 班的每 周 2 节英语课 C7、C8。T4 教英语 2 班的每周 3 节课 C9、C10。T5 教 授全体学生每周 1 节的哲学课 C11。为每条实线边着色便可得 到一组颜色集，即一种授课时间分配方式。
的情况。对于单双周课或合班课可以进行“虚排”，然后再人工 减删，所空出的课时和教室留以待用或作其他安排。
（2）在每种课的编排时按先排时间课程表，再根据所排时 间课程情况配备以教室的排法。而为了保证在同一课时，教室 的资源的利用尽可能均衡，即在为图进行边着色时，为每个颜 色 ki 设置一个参数|ki|，记录其所包含边数的个数，并为它们设 置上限 X，通过对 X 的调整，使得每个颜色集的元素数量尽量 均衡。另外，若某两节课程要用相同的教室资源（如实验室）也 可将课程顶点集中对应的课程用虚线相连，以保证它们不被安 排在同一时间段。
基金项目：国 家 863/ CIMS 主 题 资 助 项 目（Projects supported by the National High - Tech.R&D Program for CIMS ，China under Grant No. 2007AA04Z151）；新 世 纪 优 秀 人 才 支 持 计 划 资 助（Program for New Century Excellent Talents in University，China under Grant No.NCET-06-0377）；上海市重点学科建设项目（Shanghai Leading Academic Discipline Project，No.B310）。
2.1 基于图论理论的简单模型
根据大学课表的特点，以周为单位，按下列方式抽象成图 G（V，E）：
（1）图的顶点集 V 由两部分组成，其一用 T={T1，T2，T3，…， Tn}表示有 n 个不同的教师，另一用 C={C1，C2，C3，…，Cm}表示所 有班级的所有课程集合，如高等数学有两个班级，高数 1 班、高 数 2 班，则用高数 1、高数 2 区分成不同课程；若每周课时多于 一次的课程，如高数 1 班在 1 周内需要排课 3 次，则用高数
240 2009，45（27）
Computer Engineering and Applications 计算机工程与应用
高校排课问题的图论模型及算法
王 凤 1，林 杰 1，2 WANG Feng1，LIN Jie1，2
1.同济大学 经济与管理学院，上海 200092 2.同济大学 电子商务与电子政务研究所，上海 200092 1.School of Economics and Management，Tongji University，Shanghai 200092，China 2.The Laboratory of E-commerce and E-government，Tongji University，Shanghai 200092，China E-mail：morning1231@
摘 要：针对排课系统的缺陷，提出了尊重学生学习规律，按照课程的重要程度和重要课程分配的时间间隔，利用图论的边着色理 论，对排课资源进行建模，并给出了有效的多项式时间算法，使得排课问题的解决更加合理与人性化。 关键词：高校排课；边着色；图论模型 DOI：10.3778/j.issn.1002-8331.2009.27.072 文章编号：1002－8331（2009）27-0240-03 文献标识码：A 中图分类号：TP39；O157.6
1 问题的提出
近二十年来，已经有许多学者针对不同应用环境的高校排 课问题给出不同的解决方案。通过图论的方式来研究排课问题 是一个比较典型的方法，但多数情况下对排课的数学抽象都过 于简单而且有些并不能符合实际情况。
例如：有些模型将教师和班级分别作为二部图的两个顶点 集，若某一教师教授某一班级的课程则将图中这两个顶点连 线，用求偶图对集的方式来为不同的班级安排授课时间。这种 模型忽略了大学教学中班级不固定的特点，导致了班级划分不 唯一。还有些模型将不同课程的所有班级一一列出，又会出现 英语一班的某个同学也同时属于高数一班，而按照模型的设置 并没有显示这两门课程不可以排在同一时间，进而引起冲突。 有些模型违背人类学习掌握知识的渐进式生理特点，将一门课 程的两次课（每次 2～3 学时）安排在一天之中，导致学生在两次 课之间根本没有时间去消化知识和完成作业；还比如，在班级 课表中，同样明显存在一周中的某一天课特别多，而有的天课 又特别少的情况。其次，在对待不同门类的课程方面，也经常出 现不合理的上课安排。比如，在同一个班中，将专业主干课排在 了非黄金时间（下午 3～4 节或晚上），而将较次要的选修课则排 在了黄金时间，等等。
（3）为保证重要课程安排在黄金时间，为每条实线边设置 一个权数，在着色的时候尽量使得所连权重相似的边着相同的 颜色。这样可以将重要的课程同时安排在课程的重要时间，避 免出现将重要程度相差很大的课程安排在同一颜色集中，导致 分配时间段时必须有所牺牲的情况。课程教学按照每周 5 天， 每天安排 4 个时间段：即上午 12 节、34 节和下午 56 节、78 节 的方式进行。上午 12 节课是黄金时段，一般安排重要的课程。3 节的课程一般安排在下午 567 节。在为模型的边着色过程中， 由于同一课程的一周内不同的课次是相邻的，因此它们被分配 了不同的颜色，即安排了不同的时间段。根据文献[1]：相同课程 不同课次的安排应该是交叉安排比较合理，如高数课程一周 3 次，安排在星期一 12 节，星期三 34 节，星期五 12 节；或星期一 34 节，星期三 12 节，星期五 34 节。在分配好颜色集后，由于颜 色集的数目不会很大（一般每周为 15~20 个时间段），将所有颜 色集按权数总和进行排序，根据权数大小进行交叉安排，使得 权数大的课程尽量优先安排。将相同课程的不同课次不安排在 同一天，以保证学生有时间去消化知识和完成作业。
2.2 排课模型的进一步完善
（1）大学课程的安排一般分为公共课，必修课和选修课。公 共课主要指像英语、计算机基础、高等数学、哲学等课程，它们 涉及全校较大范围的师生；必修课主要指专业必修课，这些课 一般只涉及各个系内师生；公共课和专业必修课都是以班级为 单位、由学校进行设置的课程，而选修课主要指以学生个人为 单位、由学生本人在某一范围内进行选择的课程。实际中的课 程经过处理都转化为上面三类，以便简化问题。排课中，对课程 采取公共课优先、必修课次之、选修课最后的排法。由于文献[1] 中对大学选修课排法做了详细深入地分析，指出：即使每位学 生最多选两门课程，问题仍然是难解的，这样得到在实际选课 过程中，优先将公共课与必修课安排好，再对选修课适当排列， 使得学生根据必修课的情况选择自己时间上允许的选修课。这 种方式保证了选课的不冲突性，而且将问题进行了分割以逐步 求解。避免了所有课程同时安排而出现没有足够的时间段分配
上述问题的出现，主要是模型的设计不当造成的，仅仅注 重排课资源中时间和教室问题，对人性化设计的要求重视不 够，即在算法设计中对老师、学生及课程情况考虑较少，对教与 学的规律尊重不够。因此，该文针对上述问题，构造出相对人性 化的排课模型，以期一定程度上改善该问题。
