适合中小学的简单排课算法

1、模型及数据库表 (1)时间模型

假设每天可以使用的授课时间为8个时间单位,则一个星期可以使用的总授课时间为40=8×5(一周上课时间为5天)。整个有效的周期时间域可以定义为集合Ω={1,2,3,4,…40},班级、教师被占用的时间是Ω的一个子集。

(2)信息对象的逻辑关系

信息对象的逻辑关系体现在以下几个数据库表中: 表1:课程—课时表 表2:班级—课程表 已知表，由表1、2、3可计算出Tij，表示课时量 表3:教师—班级—课程表

表4等价于Sij，表示时间集合 表4:教师—班级—时间分配表

结构：教师工号、班级编号、时间分配(Ω的一个子集) 表5:排课总表 结构：教师工号、班级编号、课程编号、时间分配(Ω的一个子集)

2、算法 (1)排课算法 排课算法的目的和关键是通过表1、表2、表3建立表4，然后由表4生成表5(这一步相对简单)。 根据表3我们可以得到一个教师—班级需求矩阵,矩阵的元素Tij表示教师j为班级i上的总课时量。 表4等价于这样一个矩阵,矩阵中的元素Sij表示教师j为班级i上课的时间集合,且Sij是Ω的一个子集,Sij中的元素个数等于Tij。 原则即，Sij每一行(同一个班级的课)尽量互斥，Sij每一列(同一个教师的课)尽量互斥。 步骤1：先排Sij的第一行，S11为从集合中任意取出的T11个时间单元，S12位从Ω-S11剩余的集合中任意取出的T12个时间单元，以此类推。 步骤二：排完Sij的第一行后，对Sij进行如下图初始化，目的是使每一行列的元素互斥。然后在这基础上调整。调整步骤看原文吧…

(2)调整算法 附：

原文地址：http://wenku.http://www.china-audit.com//view/4f789e0b6c85ec3a87c2c54a.html