自动排课分析

自动排课

每个学期对本校教学任务进行合理安排是教务科重要任务。其中排课是最为关键的环节。排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题。目前由于学校扩招，学生和课程数量比以往大大增加，教室资源明显不足，在这种情况下排课人员很难在同时兼顾多重条件限制的情况下用人工方式排出令教师和学生都满意的课表。

排课问题很早以前就成为众多科研人员和软件公司的研究课题，但是真正投入使用的排课软件却很少。原因是多方面的，其中算法的选择是最·关键的一个问题，S.Even等人在1975年的研究中证明了排课问题是一个NP-Complete问题，即若是用“穷举法”之外的算法找出最佳解是不可能的。然而由于穷举法成本太高，时间太长，根本无法在计算机上实现。因为假设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制的情况下，能够推出的可能组合就有n种，如此高的复杂度是目前计算机所无法承受的。因此众多研究者提出了多种其他排课算法，如模拟退火,列表寻优搜索,约束满意等。 通俗来讲

排课，即是课程编排，是指学校为了正常进行教学工作，对班级、教师、课程及学校教学资源合理安排，制定各种各样课程表的行为，自动排课是指将排课过程交给计算机去自动计算，省去人工排课的过程。

排课问题的核心为多维资源的冲突与抢占，对其研究对类似的问题（特别是与时间表有关的问题：如考试排考场问题、电影院排座问题、航空航线问题）也是个参考。

1.流程：

①输入学校教师、班级、开设课程等资料 ②分配课程 ③设定条件 ④编排、调整课程 ⑤打印及输出各式课程表

排课因素：

1.课程 （课程包含学时，总学时、上课周数、周学时）

2.任课老师 （同一门课存在多名任课教师，也可能同一教学班由不同任课教师上课） 2.教室 （地点、座位数是考虑因素之一，教室所在的教学楼所在的校区也是考虑因素之一） 3.学生 （上课人数是考虑因素之一） 4.时间

时间、教室（地点）、任课教师、学生 都有相应的 预留设置，排课的时候根据预留的情况将预先设置的情况剔除。

教学班：教学班是按所选课程分的班,行政班里有一个班主任,教学班没有,一个行政班里学生所

[1]

m*k

选课程可以不一样,而一门课程的教学班里所选的是同一门课程，简单的讲就是课程+学生+老师（老师可选）+教室的综合体。

排课的过程就是将某个教学班安排在某一具体时间、安排在某一具体教师内的行为。

基本原则 ：

1) 同一学生在同一时间(某些特定的选修课时间除外) 不能安排两门课程 2) 同一教师在同一时间不能安排两门课程 3) 同一教室在同一时间不能安排两门课程

4) 同一时间安排的课程总数不能大于所能提供的教室总数 5) 某一课程参加学习的总人数不应大于所安排教室的座位数 6) 所提供教室的属性与课程所需教室的属性一致

如果不能安排下，尽可能的先安排下课程，再进行总学时校验。

最重要：可以随时中断，中断后保存中断过结果，可以锁定已经排完成的结果继续操作。

尽量满足：

1) 要尽量为所排课程安排上该类课效果最好的时间

2) 体育课男女分班、艺术类男女分班（如舞蹈）

3) 课程在一周上多次时, 要有一定的间隔性（比如一周上三节语文，最好是一三五分别上一次）

4) 公共课等涉及面广、学时多的课程应优先处理（公共课涉及到使用公共的资源，有限处理较好）

5) 对同一教师, 同一上课对象应尽量选择相对固定的几个教室（这样尽量避免老师上课要找教室，相对比较属性）

6) 对同一个教学班的课程应选择相对固定的教室

7) 连着的课的教室选择不应相隔太远 （比如上节课是语文，这节课是数学，应该安排在同一教室或者安排在相邻的教室内）

7）同一天有几门课时尽量把课分散（一天上两节课语文，那最好上午一节课、下午一节课） 8) 优先满足一些特殊要求（比如有些教室喜欢上上午的课，可以优先满足）

9) 尽量避免会出现某一老师某一天 没有课的情况（这样不会出现某些老师一周只需要上几天课，剩下的时间都没课的情况 ）

10) 课程教室容量利用率（教室座位利用率，作用是避免小班占用大教室的现象）

11) 课程周节次段分布均匀度（课程时间分布均匀度，作用是使每个时间段所安排的课程的数目相对均匀，避免出现某个时间段的课程过于集中，某个时间段没有课的现象）

12) 课程节次段利用率(课程节次段利用率，作用是避免出现如2课时占用3节次的时间段的现象)

13) 课程日组合优度(课程的日组合优度，是衡量每周上课次数大于1的课程的多次上课的日组合优度好坏的标志）

14) 行政班平均日课时均匀度(行政班平均日课时均匀度，作用是避免出现某个行政班某天课很多，某天没课的现象)

15) 课程节次段优度(课程节次段优度，根据预设的上课节次段的优度值、课程节次段要求计算的某一课程安排时间节次段的优略程度）

16) 教室时间利用分布均匀度（教室时间利用分布均匀度，作用是避免出现对某一部分教室过度集中使用，防止因其他用途这些集中使用的教室资源出现饥饿现象）

17) 老师一天内非跨校区上课率（老师一天内非跨校区上课率，避免老师出现同一天跨校区上课，采用该指标来衡量课表合理性）

18) 体育课后不排非体育课率(育课后不排非体育课率，作用是避免出现同一行政班同一天同一午别体育课后面排非体育课程,因为体育课后的课效果很差)

19) 同一教学班同一教室上课率（同一教学班同一教室上课率，同一教学班尽量安排在一个教室上课）

尽量满足的内容可以让用户自由设置权重，根据权重去判断尽量满足哪个，排课不可能完全100%达到最优。

中职 坐班制（类似中小学） 坐班制虽然没有跑班制，但是教学班依旧存在。所以大部分中职学校并不在排课的时候安排教室。因为教室固定。 高职 跑班制 本科 跑班制

Faq:很多中职学校并不存在

贪心算法

当一个问题具有最优子结构性质时，我们会想到用动态规划法去解它，但有时会有更简单、更有效的算法，即贪心算法。顾名思义，贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不是整体最优上加以考虑，他所作出的选择只是在某种意义上的局部最优的选择。虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解，如图的算法中单源最短路径问题，最小支撑树问题等。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。

在贪心算法中较为有名的算法是Dijkstra算法。它作为路由算法用来寻求两个节点间的最短路径。Dijkstra算法的思想是：假若G有n个顶点，于是我们总共需要求出n-1条最短路径，求解的方法是：初试，写出V0(始顶点)到各顶点(终顶点)的路径长度，或有路径，则令路径的长度为边上的权值；或无路经，则令为∞。再按长度的递增顺序生成每条最短路径。事实上生成最短路径的过程就是不断地在始顶点V何终顶点W间加入中间点的过程，因为在每生成了一条最短路径后，就有一个该路径的终顶点U，那么那些还未生成最短路径的路径就会由于经过U而比原来的路径短，于是就让它经过U。 回溯法

回溯法有“通用的解题法”之称。用它可以求出问题的所有解或任一解。概括地说，回溯法是一个既带有系统性又带有跳跃性的搜索法。它在包含问题所有解的一颗状态空间树上，按照深度优先的策略，从根出发进行搜索。搜索每到达状态空间树的一个节点，总是先判断以该节点为根的子树是否肯定不包含问题的解。如果肯定不包含，则跳过对该子树的系统搜索，一层一层地向它的祖先节点继续搜索，直到遇到一个还有未被搜索过的儿子的节点，才转向该节点的一个未曾搜索过的儿子节点继续搜索；否则，进入子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根的所有儿子都已被搜索过才结束；而在用来求问题的任一解时，只要搜索到问题的一个解就可结束。

遗传算法

遗传算法是一种通过模拟自然界生物进化过程求解极值的自适应人工智能技术，是由美国芝加哥大学Holland教授于1962年首先提出的。遗传算法借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制来提高各个个体的适应性，体现了自然界中“物竞天择、适者生存”的进化过程。遗传算法也因此吸引了一大批的研究者，并广泛应用于函数优化、组合优化、生产调度、机器学习、图像处理、模式识别等多个领域。

本文来源：https://www.bwwdw.com/article/8q32.html