论文部分内容阅读
摘要：课程表排课安排和管理是每个学校教务活动中非常重要的工作，它依靠计算机来完成复杂的排课部分，避免了手工排课产生的老师上课时间冲突和教室冲突。该文运用遗传算法的全局寻优对自动排课系统的设计构思和实现过程进行了研究，并利用遗传算法对问题进行求解。在演化过程中采用一种新的遗传策略，加速了群体的收敛速度。并得到了一个解决适合学校要求的课程表模型的好的算法。
关键词：排课；遗传算法；全局寻优；自动排课
中图分类号：TP301.6文献标识码：A 文章编号：1009-3044(2008)33-1463-03
A Kind of Based on Genetic Algorithm the Application in Layout Course Table
QIAO An-hong
(Jiaxing University, Jiaxing 314001,China)
Abstract: Course table row lesson arrangement and management are every school campaign work of educational administration with frequently important Central Africa, it relies on computer to complete complex row lesson part, have avoided the teacher that handwork row lesson produces to attend class time conflict and classroom conflict. It is studied that this paper utilizes the overall situation of genetic algorithm to seek the good design conception for the system of automatic row lesson and the course of realizing and has gone on , and beg to untie using genetic algorithm for problem. In evolution course have accelerated group with a kind of new hereditary strategy show restraint speed. And have gotten a good algorithm of the course table model that solves to suit school requirement.
Key words: queue up lesson; genetic algorithm; overall situation seek good; queue up lesson voluntarily
1 引言
学校课程表排课安排和管理是每个学校教务活动中非常重要的工作，它涉及面广、限制条件多，而计算机自动排课系统设计就是根据教学计划的内容以及一些限制条件自动生成课程表，从而减轻排课的工作量、提高排课的效率和科学性，其功能是可根据用户需求进行如下的排课生成：设置上午、下午、晚上的上课节数，全校每天不排课的限制、上课周数。专业配课、年级配课、班级配课。课程信息设置，包含任课老师，性质、课时等。教室信息设置，包括性质、隶属。教师的信息配置，包括教授的课程、特殊情况等自动排课生成各类课表手动编排。
目前最具科学性的方法：使用计算机软件技术配合手工排课。就是将人脑和电脑的优势结合在一起发挥作用——即具有“人工排课”的灵活、合理性，又具有“智能排课软件”的便捷性。（也就是“计算机辅助排课”）使用计算机辅助排课系统的自动教师资源、教室资源和时间资源组成的效率与质量完全取决于时间表算法的设计。遗传算法以其自适应寻优及良好的智能搜索技术，受到了广泛的运用。Potts J C等人基于变异和人工选择的遗传算法对最优群体规模进行了论述；Hamilton M A等结合遗传算法把其运用到神经网络中，并取得了良好的效果；也有众多的学者对保留最佳状态的遗传算法的收敛速度做了讨论。通过理论推导和事实运用，发现遗传算法在寻优和收敛性方面都是非常有效的、确实可行的一种解决方法。
2 问题描述
传统的人工排课，最令人担心的问题就是——出现教室资源冲突或教师资源冲突的情况。而且工作繁琐，工作量巨大。况且我发现目前的排课软件普遍存在——排课条件设置复杂，难以做到课程的合理分布（例如：数学、英语等主课多数要安排在上午上课）、出错概率高、难以操作等缺点。计算机自动排课系统实际上是时间表的优化问题。如何根据班级的课程设置、课程的周内次数、现有教室资源、以及现有教师资源进行科学的合理安排，提供给学校的教务部门一个自动排课系统，在实际工作中具有一定的应用价值。
在进行计算机自动排课系统设计过程中，我考虑了三类资源：一类是教师资源，一类是教室资源，一类是时间资源。教师资源包括在编教师和每个教师历年所上过的课程、以及所上过课程的评价值。同一课程可能有多名教师能开课，在资源分配允许的情况下，自然选择评价值高的教师上这门课。多数情况下，在进行教学任务安排时，已经人为考虑了教师和课程之间的固定联系。教室资源是指现有可用教室。时间资源是指允许可用的时间段。此外，按每学期教学大纲，本学期每个班(专业)所上课程和每门课的周学时数(次数)是预定的。同时，我还需要考虑不同时间段的上课效果。排课问题是根据现有教师资源、教室资源和时间资源，如何使排课结果最佳。适当定义相应的一些评价系数后，排课问题变成了一个时间表的优化问题。
而排课数据结构模型的产生和实现是计算机排课系统自动化或半自动化操作的核心目标之一，而如何保证生成的课程表能最大程度的满足用户的不同需要,并具有随机性、科学性、合理性，这是实现中的一个难点。尤其在交互式环境下用户对于生成课表速度要求较高，而一个理论上较完美的算法可能会以牺牲时间作为代价，往往不能达到预期的效果。因此，选择一个高效、科学、合理的算法是自动排课的关键。
以往计算机排课系统算法的实现，大多采用随机选取法和回溯试探法。两种算法各有其优缺点，在限制条件状态空间的控制下，随机选取法有时能够获取一组令用户满意的课表。只不过由于它随机选取时间表的的范围太大，无法确定目前条件下哪些区域能够抽取合适的时间表，反而可能在那些已经证明是无法抽取在合适课表的区域内反复选取，进行大量的无效操作进入死循环，最终导致课表生成失败。回溯试探法用于课表生成的成功率较高，但它是以牺牲大量的搜索时间为代价的，已不适合应用要求。因此,必须结合以上两种方法寻找一种新的改进算法，这种算法要具有全局寻优和收敛速度快的特点。遗传算法以其具有自适应全局寻优和智能搜索技术，并且以收敛性好的特性很好的满足课表自动生成的需求算法。
3 遗传算法描述
3.1 遗传算法基本思想
遗传算法（Genetic Algorithm，缩写为GA）是一种有效的解决最优化问题的方法。它是基于人类社会的进化过程，遗传算法首先利用随机方式产生一切始群体（祖先），群体中的每个个体称为染色体，它对应着优化问题的一个可能解，染色体的最小组成元素应称为基因，它对应可能解的某一特征，即设计变量。染色体的评价函数值反映可能解的优劣，按照优胜劣汰原则对染色体进行选择，相对“好”的个体繁殖，相对“差”的个体将死亡，因此群体整体的性能，通过选择、杂交、突变等过程将趋于改善，经过若干代繁衍进化就可使群体性能趋于最佳。其实质就是一种把自然界有机体的优胜劣汰的自然选择、适者生存的进化机制与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。
3.2 遗传算法的基本步骤
1) 定义一个目标函数;2) 将可行解群体在一定的约束条件下初始化,每一个可行解用一个向量X来编码，称染色体，向里的分量代表基因，它对应可行解的某一决策变量；3) 计算群体中每条染色体Xi（i=1,2,……,n）所对应的目标函数值，并以此计算机适应值Fi，按Fi的大小来评价该可行解的好坏；4) 以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的好坏，按概率随机选择，进行繁殖，形成新的群体；5) 通过杂交和变异的操作，产生子代。杂交是随机选择两条染色体（双亲），将某一点或多点的基因互换而产生两个新个体，普通异是基因中的某一点或多点发生突变；6) 对子代群体重复步骤3）-5）的操作，进行新一轮遗传进化过程，直到迭代收敛（适应值趋稳定）即找到了最优解或准最优解。
4 遗传算法进行求解并优化应用
当我们对遗传算法的基本原理有了一定的实践和认识，利用其各种遗传操作算子就可建立和产生课程表排课系统的结构模型，并进行求解和优化描述应用如下：
4.1 解的表示
表单元：一个班级的课程表为一个表单元。每周按7天计、每天按6个时间段计。如果周末和某些时间段不能排课，可以在初始约束时用一个布尔变量关闭。
时间段填充：单元中的时间段上用2元组（课程号，教室号）进行填充，当课程有重复次数时，固定课程号做重复填充。
原子码：班级码 课程码 星期码 时段码 教室码。
其中，班级码和课程码之间的关系是固定的。
表单元码：相同班级码的原子码集合。
个体码：假设有n个班，n个表单元码构成的序形成一个个体码。
可行解：满足协调条件的个体码。
4.2 选择初始群体
1) 根据给定的班级、该班级本学期所要上的课程集合、以及每门课的重复次数。随机产生星期码、时段码、教室码。与班级码和课程码构成一个原子码。
2) 由原子码生成表单元码。
3) 由表单元码生成个体码。
4) 根据初始群体大小，生成由个体组成的初始群体。
4.3 确定评价函数
评价函数在遗传过程中起着环境的作用，根据评价函数产生每个个体的适应值。这里，我将时间段效率、时间间距约束、教室利用率等因素结合起来定义评价函数。时间段效率和时间间距约束涉及到上课的效果，教室利用率涉及到资源的利用问题。因此，应该优先考虑时间段效率和时间间距约束，在保证这两者的前提下，再考虑教室利用率。在评价函数中，前两者所占的比重相对较高。在每个个体中，每个三元组(星期码，时段码，教室码)对应着时间段效率和教室利用率。对于每个班的重复课程，对应着一个时间间距约束问题。将这三个因素按比例进行累加，就可以得到每个个体的适应值。
4.4 遗传策略
通常，我在遗传过程中采用三种算子：复制、杂交、变异，三者概率分别为Pr，Pc，Pm。
1）复制算子(reproduction): 复制算子从群体中按照某一概率选择个体，某个体si被选择的概率Pi与其适应值成正比。通常，我用轮盘赌(roulette wheel)方法进行实现。轮盘赌方法的实现如下：设群体S：s1,s2,……,sn,每个个体的适应值分别为f(s1),f(s2),……,f(sn),令sum＝f(s1) f(s2) …… f(sn),某个体所si被选择的概率Pi＝f(si)/sum (i=1,2,……,n),在0与sum之间产生一个随机数A，令B＝0，依概率p1,p2,……,pn在1到n之间随机产生一个个体编号m，将f(sm)累加进B中，直到B>A,将此sm作为被选个体。
2）杂交算子(Crossover): 杂交算子将被选中的两个个体的基因链按概率Pc进行杂交，即在某一确定段上，对等交换代码，生成两个新的个体，杂交位置是随机的。
3）变异算子(Mutation): 变异算子将新个体的基因链的各位按概率Pm进行变异，对二进制基因链来说就是对某些随机选取的位置取反。
这样，对每一代群体，我首先用协调条件进行一次筛选，剔除不满足协调条件的个体。然后才对个体进行演化计算产生下一代，从而加快了进化速度。
结合上述三种算子，采取了一种新的遗传策略。在得到群体中每个个体的适应值后，首先用轮盘赌方法将群体选择到交配池中，然后从交配池中每次取两个个体依概率进行杂交或变异产生临时新群体，此时，临时新群体数目与父代群体数目相同。接着，再将临时新群体中每个个体依概率选择或直接复制到下一代，或与上一代对应个体进行竞争(即若其适应值比上一代对应个体差，则将上一代个体保留下来，否则将其保留至下一代)。另外，将每一代中最优个体进行保存，每次产生新群体后，判断新群体中是否有比现有最优个体的适应值更好的，若有，则用其替换当前最优个体。通过父代和子代竞争，可以提高解的收敛速度。
4.5 停机准则
我可以采用多种方法来结束算法的执行，这里，我采用两种方式相结合对停机加以控制：
1) 设定最大遗传代数M，当遗传进行到第M代时，让其停机。
2) 预先定义评价函数的一个指标数，当某一代最优个体的适应值达到或超过该指标数时，让其停机。
4.6 输出结果
遗传算法结束后，可以得到适应值（即综合效率函数值）最好的个体。根据这个结果，我将对个体码进行如下分解：
1) 分解个体码成为表单元码。
2) 分解每一个表单元码成为：班级码、课程码、星期码、时段码、教室码。
由分解后的班级码、课程码、星期码、时段码、教室码分别生成如下表格：
1) 班级课程表。
2) 根据教师与课程的固定关系，生成教师工作表。
3) 每个教室的时间占用表。
4) 教学单位的课程总表。
5 结束语
本文基于遗传算法建立和描述了排课的数学模型，实际上是对一个时间任务表的优化问题，研究了对问题的求解。利用遗传算法的全局寻优和收敛速度快的特点，结合随机选取法和回溯试探法的优点，设计了一种用于课表自动生成的好的算法，在排课的成功率和速度都得到了明显的提高。实验表明：本排课模型算法的构成结果能得到较满意的课程表安排方案。然而要使课表自动生成的误差精度和收敛速度进一步得到改进，还需要做出更深的研究。
参考文献：
[1] Peter Brucker.Scheduling Algorithm. Berlin etc: Springer, 1998.
[2] J．H．Holland ，Adaptation in natural and artificial systems[M]，Ann arbor: University of Michigen press,1975.
[3] Hamilton M A. Java and the Shift to Net-centric Computing. IEEE Computer, 29(8),1996.
[4] 刘勇，康立山，陈毓屏.非数值并行算法（第二册）－遗传算法[M].北京：科学出版社，1998.
[5] 余建桥，预测模型获取的遗传算法研究[J].计算机科学,1998,25(2):12-14.
[6] 王小平，曹立明.遗传算法－理论、应用与软件实现[M].西安：西安交通大学出版社，2002.
[7] 张宗华，张伟，赵霖.利用遗传算法实现交通信号灯的控制[J].计算机科学，2002.29(9. 增刊): 178-181.
[8] 田奕,刘涛,李国杰.求解可满足性问题的一种高效遗传算法[J].模式识别与人工智能,1996.9:209-212.
关键词：排课；遗传算法；全局寻优；自动排课
中图分类号：TP301.6文献标识码：A 文章编号：1009-3044(2008)33-1463-03
A Kind of Based on Genetic Algorithm the Application in Layout Course Table
QIAO An-hong
(Jiaxing University, Jiaxing 314001,China)
Abstract: Course table row lesson arrangement and management are every school campaign work of educational administration with frequently important Central Africa, it relies on computer to complete complex row lesson part, have avoided the teacher that handwork row lesson produces to attend class time conflict and classroom conflict. It is studied that this paper utilizes the overall situation of genetic algorithm to seek the good design conception for the system of automatic row lesson and the course of realizing and has gone on , and beg to untie using genetic algorithm for problem. In evolution course have accelerated group with a kind of new hereditary strategy show restraint speed. And have gotten a good algorithm of the course table model that solves to suit school requirement.
Key words: queue up lesson; genetic algorithm; overall situation seek good; queue up lesson voluntarily
1 引言
学校课程表排课安排和管理是每个学校教务活动中非常重要的工作，它涉及面广、限制条件多，而计算机自动排课系统设计就是根据教学计划的内容以及一些限制条件自动生成课程表，从而减轻排课的工作量、提高排课的效率和科学性，其功能是可根据用户需求进行如下的排课生成：设置上午、下午、晚上的上课节数，全校每天不排课的限制、上课周数。专业配课、年级配课、班级配课。课程信息设置，包含任课老师，性质、课时等。教室信息设置，包括性质、隶属。教师的信息配置，包括教授的课程、特殊情况等自动排课生成各类课表手动编排。
目前最具科学性的方法：使用计算机软件技术配合手工排课。就是将人脑和电脑的优势结合在一起发挥作用——即具有“人工排课”的灵活、合理性，又具有“智能排课软件”的便捷性。（也就是“计算机辅助排课”）使用计算机辅助排课系统的自动教师资源、教室资源和时间资源组成的效率与质量完全取决于时间表算法的设计。遗传算法以其自适应寻优及良好的智能搜索技术，受到了广泛的运用。Potts J C等人基于变异和人工选择的遗传算法对最优群体规模进行了论述；Hamilton M A等结合遗传算法把其运用到神经网络中，并取得了良好的效果；也有众多的学者对保留最佳状态的遗传算法的收敛速度做了讨论。通过理论推导和事实运用，发现遗传算法在寻优和收敛性方面都是非常有效的、确实可行的一种解决方法。
2 问题描述
传统的人工排课，最令人担心的问题就是——出现教室资源冲突或教师资源冲突的情况。而且工作繁琐，工作量巨大。况且我发现目前的排课软件普遍存在——排课条件设置复杂，难以做到课程的合理分布（例如：数学、英语等主课多数要安排在上午上课）、出错概率高、难以操作等缺点。计算机自动排课系统实际上是时间表的优化问题。如何根据班级的课程设置、课程的周内次数、现有教室资源、以及现有教师资源进行科学的合理安排，提供给学校的教务部门一个自动排课系统，在实际工作中具有一定的应用价值。
在进行计算机自动排课系统设计过程中，我考虑了三类资源：一类是教师资源，一类是教室资源，一类是时间资源。教师资源包括在编教师和每个教师历年所上过的课程、以及所上过课程的评价值。同一课程可能有多名教师能开课，在资源分配允许的情况下，自然选择评价值高的教师上这门课。多数情况下，在进行教学任务安排时，已经人为考虑了教师和课程之间的固定联系。教室资源是指现有可用教室。时间资源是指允许可用的时间段。此外，按每学期教学大纲，本学期每个班(专业)所上课程和每门课的周学时数(次数)是预定的。同时，我还需要考虑不同时间段的上课效果。排课问题是根据现有教师资源、教室资源和时间资源，如何使排课结果最佳。适当定义相应的一些评价系数后，排课问题变成了一个时间表的优化问题。
而排课数据结构模型的产生和实现是计算机排课系统自动化或半自动化操作的核心目标之一，而如何保证生成的课程表能最大程度的满足用户的不同需要,并具有随机性、科学性、合理性，这是实现中的一个难点。尤其在交互式环境下用户对于生成课表速度要求较高，而一个理论上较完美的算法可能会以牺牲时间作为代价，往往不能达到预期的效果。因此，选择一个高效、科学、合理的算法是自动排课的关键。
以往计算机排课系统算法的实现，大多采用随机选取法和回溯试探法。两种算法各有其优缺点，在限制条件状态空间的控制下，随机选取法有时能够获取一组令用户满意的课表。只不过由于它随机选取时间表的的范围太大，无法确定目前条件下哪些区域能够抽取合适的时间表，反而可能在那些已经证明是无法抽取在合适课表的区域内反复选取，进行大量的无效操作进入死循环，最终导致课表生成失败。回溯试探法用于课表生成的成功率较高，但它是以牺牲大量的搜索时间为代价的，已不适合应用要求。因此,必须结合以上两种方法寻找一种新的改进算法，这种算法要具有全局寻优和收敛速度快的特点。遗传算法以其具有自适应全局寻优和智能搜索技术，并且以收敛性好的特性很好的满足课表自动生成的需求算法。
3 遗传算法描述
3.1 遗传算法基本思想
遗传算法（Genetic Algorithm，缩写为GA）是一种有效的解决最优化问题的方法。它是基于人类社会的进化过程，遗传算法首先利用随机方式产生一切始群体（祖先），群体中的每个个体称为染色体，它对应着优化问题的一个可能解，染色体的最小组成元素应称为基因，它对应可能解的某一特征，即设计变量。染色体的评价函数值反映可能解的优劣，按照优胜劣汰原则对染色体进行选择，相对“好”的个体繁殖，相对“差”的个体将死亡，因此群体整体的性能，通过选择、杂交、突变等过程将趋于改善，经过若干代繁衍进化就可使群体性能趋于最佳。其实质就是一种把自然界有机体的优胜劣汰的自然选择、适者生存的进化机制与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。
3.2 遗传算法的基本步骤
1) 定义一个目标函数;2) 将可行解群体在一定的约束条件下初始化,每一个可行解用一个向量X来编码，称染色体，向里的分量代表基因，它对应可行解的某一决策变量；3) 计算群体中每条染色体Xi（i=1,2,……,n）所对应的目标函数值，并以此计算机适应值Fi，按Fi的大小来评价该可行解的好坏；4) 以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的好坏，按概率随机选择，进行繁殖，形成新的群体；5) 通过杂交和变异的操作，产生子代。杂交是随机选择两条染色体（双亲），将某一点或多点的基因互换而产生两个新个体，普通异是基因中的某一点或多点发生突变；6) 对子代群体重复步骤3）-5）的操作，进行新一轮遗传进化过程，直到迭代收敛（适应值趋稳定）即找到了最优解或准最优解。
4 遗传算法进行求解并优化应用
当我们对遗传算法的基本原理有了一定的实践和认识，利用其各种遗传操作算子就可建立和产生课程表排课系统的结构模型，并进行求解和优化描述应用如下：
4.1 解的表示
表单元：一个班级的课程表为一个表单元。每周按7天计、每天按6个时间段计。如果周末和某些时间段不能排课，可以在初始约束时用一个布尔变量关闭。
时间段填充：单元中的时间段上用2元组（课程号，教室号）进行填充，当课程有重复次数时，固定课程号做重复填充。
原子码：班级码 课程码 星期码 时段码 教室码。
其中，班级码和课程码之间的关系是固定的。
表单元码：相同班级码的原子码集合。
个体码：假设有n个班，n个表单元码构成的序形成一个个体码。
可行解：满足协调条件的个体码。
4.2 选择初始群体
1) 根据给定的班级、该班级本学期所要上的课程集合、以及每门课的重复次数。随机产生星期码、时段码、教室码。与班级码和课程码构成一个原子码。
2) 由原子码生成表单元码。
3) 由表单元码生成个体码。
4) 根据初始群体大小，生成由个体组成的初始群体。
4.3 确定评价函数
评价函数在遗传过程中起着环境的作用，根据评价函数产生每个个体的适应值。这里，我将时间段效率、时间间距约束、教室利用率等因素结合起来定义评价函数。时间段效率和时间间距约束涉及到上课的效果，教室利用率涉及到资源的利用问题。因此，应该优先考虑时间段效率和时间间距约束，在保证这两者的前提下，再考虑教室利用率。在评价函数中，前两者所占的比重相对较高。在每个个体中，每个三元组(星期码，时段码，教室码)对应着时间段效率和教室利用率。对于每个班的重复课程，对应着一个时间间距约束问题。将这三个因素按比例进行累加，就可以得到每个个体的适应值。
4.4 遗传策略
通常，我在遗传过程中采用三种算子：复制、杂交、变异，三者概率分别为Pr，Pc，Pm。
1）复制算子(reproduction): 复制算子从群体中按照某一概率选择个体，某个体si被选择的概率Pi与其适应值成正比。通常，我用轮盘赌(roulette wheel)方法进行实现。轮盘赌方法的实现如下：设群体S：s1,s2,……,sn,每个个体的适应值分别为f(s1),f(s2),……,f(sn),令sum＝f(s1) f(s2) …… f(sn),某个体所si被选择的概率Pi＝f(si)/sum (i=1,2,……,n),在0与sum之间产生一个随机数A，令B＝0，依概率p1,p2,……,pn在1到n之间随机产生一个个体编号m，将f(sm)累加进B中，直到B>A,将此sm作为被选个体。
2）杂交算子(Crossover): 杂交算子将被选中的两个个体的基因链按概率Pc进行杂交，即在某一确定段上，对等交换代码，生成两个新的个体，杂交位置是随机的。
3）变异算子(Mutation): 变异算子将新个体的基因链的各位按概率Pm进行变异，对二进制基因链来说就是对某些随机选取的位置取反。
这样，对每一代群体，我首先用协调条件进行一次筛选，剔除不满足协调条件的个体。然后才对个体进行演化计算产生下一代，从而加快了进化速度。
结合上述三种算子，采取了一种新的遗传策略。在得到群体中每个个体的适应值后，首先用轮盘赌方法将群体选择到交配池中，然后从交配池中每次取两个个体依概率进行杂交或变异产生临时新群体，此时，临时新群体数目与父代群体数目相同。接着，再将临时新群体中每个个体依概率选择或直接复制到下一代，或与上一代对应个体进行竞争(即若其适应值比上一代对应个体差，则将上一代个体保留下来，否则将其保留至下一代)。另外，将每一代中最优个体进行保存，每次产生新群体后，判断新群体中是否有比现有最优个体的适应值更好的，若有，则用其替换当前最优个体。通过父代和子代竞争，可以提高解的收敛速度。
4.5 停机准则
我可以采用多种方法来结束算法的执行，这里，我采用两种方式相结合对停机加以控制：
1) 设定最大遗传代数M，当遗传进行到第M代时，让其停机。
2) 预先定义评价函数的一个指标数，当某一代最优个体的适应值达到或超过该指标数时，让其停机。
4.6 输出结果
遗传算法结束后，可以得到适应值（即综合效率函数值）最好的个体。根据这个结果，我将对个体码进行如下分解：
1) 分解个体码成为表单元码。
2) 分解每一个表单元码成为：班级码、课程码、星期码、时段码、教室码。
由分解后的班级码、课程码、星期码、时段码、教室码分别生成如下表格：
1) 班级课程表。
2) 根据教师与课程的固定关系，生成教师工作表。
3) 每个教室的时间占用表。
4) 教学单位的课程总表。
5 结束语
本文基于遗传算法建立和描述了排课的数学模型，实际上是对一个时间任务表的优化问题，研究了对问题的求解。利用遗传算法的全局寻优和收敛速度快的特点，结合随机选取法和回溯试探法的优点，设计了一种用于课表自动生成的好的算法，在排课的成功率和速度都得到了明显的提高。实验表明：本排课模型算法的构成结果能得到较满意的课程表安排方案。然而要使课表自动生成的误差精度和收敛速度进一步得到改进，还需要做出更深的研究。
参考文献：
[1] Peter Brucker.Scheduling Algorithm. Berlin etc: Springer, 1998.
[2] J．H．Holland ，Adaptation in natural and artificial systems[M]，Ann arbor: University of Michigen press,1975.
[3] Hamilton M A. Java and the Shift to Net-centric Computing. IEEE Computer, 29(8),1996.
[4] 刘勇，康立山，陈毓屏.非数值并行算法（第二册）－遗传算法[M].北京：科学出版社，1998.
[5] 余建桥，预测模型获取的遗传算法研究[J].计算机科学,1998,25(2):12-14.
[6] 王小平，曹立明.遗传算法－理论、应用与软件实现[M].西安：西安交通大学出版社，2002.
[7] 张宗华，张伟，赵霖.利用遗传算法实现交通信号灯的控制[J].计算机科学，2002.29(9. 增刊): 178-181.
[8] 田奕,刘涛,李国杰.求解可满足性问题的一种高效遗传算法[J].模式识别与人工智能,1996.9:209-212.