一种排课算法

摘要

本发明涉及一种排课算法，它包括排时间模型的建立和排教室算法；排时间模型包括约束条件和目标函数两个部分，然后采用分枝定界算法求解排时间模型得到一组解，该组解即为D条排时间结果；排教室算法则是针对D条排时间结果进行，最后输出对排时间结果的排教室结果即课表。该排课算法先排时间后排教室的方法，排课过程不但简单，而且高效，从而使该方法更具普遍性，更重要的是该排课算法还定义了多个软性约束，通过这些软性约束的设定，可以满足更多高校对课表的特定要求，从而使该方法更具多样性，便于推广。

主权项

一种排课算法，其特征在于，包括如下步骤：S1：排时间模型的建立:排时间模型包括约束条件和目标函数两个部分；设排时间模型的决策变量矩阵为X_n×m，x_ij是X_n×m的元素，x_ij的含义是：S1a：约束条件包括：1)周次数约束：设d_i为第i个教学任务的周次数，则有：$\underset{j=1}{\overset{m}{\Sigma }}{x}_{\mathrm{ij}}=d_i,i=\mathrm{1,2},...n---\left(2\right);$其中m表示一周内时间片的总数，n表示教学任务的数目；m＝t×s   (3)；其中t表示一周可排课的天数，s表示每天可用排课的时间片数；设M为时间片矩阵，m_qp表示星期q的第p个时间片，q＝1,2，…7，将星期一至星期七的时间片依次排列得到一维时间片矩阵M，该时间片矩阵M中共有m个时间片；2)时间片限制约束：设时间片限制约束矩阵为B_n×m，b_ij是B_n×m的元素，b_ij的含义是：则时间片限制约束表达为：x_ij+b_ij≤1,i＝1,2,…,n,j＝1,2,…m   (5)；3)教学任务冲突约束：设教学任务冲突矩阵为C_n×n，c_ik是C_n×n的元素，c_ik的含义是：则教学任务冲突约束表达为：x_ij+x_kj≤1,j＝1,2,…,m,如果c_ik＝1   (7)；4)时间片分配平衡约束：如果d_i≤3，则如下：$\underset{j=(h-1)·s+1}{\overset{(h-1)·s+1+2s}{\Sigma }}{x}_{\mathrm{ij}}\le 1,h=\mathrm{1,2},...,t-1,i=\mathrm{1,2},...,n---\left(8\right);$如果d_i≥4且d_i≤t，则如下：$\underset{j=(h-1)·s+1}{\overset{(h-1)·s+1+s}{\Sigma }}{x}_{\mathrm{ij}}\le 1,h=\mathrm{1,2},...,t,i=\mathrm{1,2},...,n---\left(9\right);$S1b：目标函数如下：设时间片效益矩阵为W_n×m，w_ij是W_n×m的元素，w_ij的含义是第i个教学任务在第j个时间片上的效益；则目标函数为：$w_{\mathrm{ij}}=\max \underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{m}{\Sigma }}{t}_{\mathrm{ij}}{x}_{\mathrm{ij}}---\left(10\right);$S1c：采用分枝定界算法求解上述排时间模型得到一组解，该组解为D条排时间结果；S2：排教室算法：S2a：输入D条排时间结果；S2b：设d＝1；S2c：获取第d条排时间结果所需的教室类型；S2d：获取属于步骤S2c中教室类型的所有教室；S2e：将步骤S2d获取的教室进行初过滤：对步骤S2d获取所有教室进行搜索，去掉被占用的教室，留下没有被占用的教室；如果留下的教室不为0，则进入S2h；如果留下的教室为0，则输出对排时间结果的排教室失败，并进入下一步；S2f：令d＝d+1；S2g：当d≤D时，返回步骤S2c，否则输出对排时间结果的排教室结果，算法结束；S2h：对初过滤后留下的教室进行再过滤，判断教室的容量与学生数量是否匹配：当教室的容量是第d条排课结果中教学任务对应的学生数量的C倍时，认为教室的容量与学生数量匹配，否则不匹配；去掉教室的容量与学生数量不匹配的教室，留下教室的容量与学生数量匹配的教室；S2i：判断留下的教室是否为0：如果留下的教室不为0，则进入S2k；如果留下的教室为0，则增加C的值并进入下一步；S2j：当C＜C_max时，返回步骤S2h；否则，输出对排时间结果的排教室失败，并返回步骤S2f；S2k：判断留下的教室是否大于1：如果留下的教室大于1，则选择容量最小的教室，并返回步骤S2f；否则选择留下的教室，并返回步骤S2f。