排课表问题的毕业论文.doc

1、一 问题重述每学期的开学初，总有许多老师对课程安排进行抱怨，还有许多老师要求调课，教务处对这一问题很是头疼。假设你是一名刚刚毕业的大学生，被分配到了教务处，领导安排你负责排出课表，请你们根据实际情况，用数学建模的方法解决这一问题，既要让老师满意，又要让同学和学校满意。让老师满意，就是要让每位老师在一周内前往上课的乘车次数内尽可能少，同时还要使每位老师在逗留的时间尽可能少，比如安排尽量少出现像同一天同一位老师上1-2节，7-8节；让同学们满意，可从以下几方面考虑，比如，同一专业同一门课程，至少应间隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段；让学校满意，就是要节约支出，每周车次

2、尽可能的少。请你们从实际情况出发(自己收集相关数据)，用数学建模的方法解决以下问题：1)建立排课表的数学模型，并研制出排课表的软件包；2)利用你的模型及软件对本学期校区的课表进行重排，并与现有的课表进行比较；3)给出评价指标评价你的模型，特别要指出你的模型的优点与不足之处；4)对学校教务处排课表问题给出你的建议。二基本假设1、课程对于教室的要求都一样，不存在特定课程对应特定教室的现象;2、老师与工作人员的满意度与到校区的次数有关，与课程安排的教室位置无关;3、教室足够多,不存在教室不够用的情况；4、周一至周五每天上四节课；5、对于任一专业，某门课程一周内的授课时间数（节数）是固定的， 即不考虑

3、单双周情况；6、教室足够大，相同专业在一起上课，共用一个课表；7、每辆校车最多乘坐50人；8、校车每天开四次，即每次上完课都有校车发车；9、校车在规定时间到达乘车点后，所有人员应在该点上车的乘客均上车,校车为满员状态，不考虑校车单独去接个别人员的情况。三.符号约定X时间集合Xa第a个时间段每周上课时间Y老师集合Yb第b位老师老师总数Z专业集合Zc第c个专业专业总数R教室集合R第间教室L课程集合L第门课程DepCost(j)j班相同课程的时间间隔度量值之和PriCost(j)j班课程重要度度量值之和ReqCost(j)j班上课老师的要求与课程安排符合程度度f(x)适应度函数x决策向量y目标向量e

4、（x）约束条件Xi（i=1,2,320）每周内第i节课Pc交叉概率Pm变异概率num随机整数F效用函数g（a）校车数量函数G一周内学校派往的校车总数四问题分析1、让老师满意 让老师满意，就是要让每位老师在一周内前往上课的乘车次数内尽可能少，同时还要使每位老师在教学时间尽可能的集中，比如安排尽量少出现同一天同一位老师上1-2节，7-8节。 首先对老师满意度进行定义，用符号Req表示老师满意度，其值越高，老师对所排课表越满意。若某课程的上课时间完全符合老师要求，如老师希望将课程安排在上午第一节，课表情况亦如此，则Req=10；如果课表安排与老师要求不符合，但同为上午或下午，则Req=5；其他情况，

5、Req=0。2、让学生满意 让同学们满意，可从以下几方面考虑，比如，同一专业同一门课程，至少应间隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段。关于同一门课的排课满意度，为某班相同课程两次课之间的时间间隔赋权值，权值越大，满意度越高。如表1所示。间隔权值同一天0相邻两天，间隔时间段两节课4相邻两天，间隔时间段两节课6间隔一天10间隔一天以上6表1 某班同一门课程时间间隔权值根据上课时间的不同为重要度赋权值。如表2所示。周一周二周三周四周五第一节9.59.99.79.49.2第二节8.58.98.78.48.2第三节6.56.96.76.16.2第四节5.55.95.75.15.

6、2表2 一周内每节课的权值对于比较难学的课，排课表时优先排，以保证能尽量安排在最好时间段。3.让学校满意让学校满意，就是要节约支出，每周派往的车次尽可能的少。相比于让老师满意和让学生满意，让学校满意问题中出现了最低成本，即校车数量最少，这样多目标调度问题就变成了模型优化问题。在“满意度”和“最低成本”这两个变量中建立相关关系，共同评定，求出最优解。考虑到以上三方面问题，采用遗传算法，得出最优个体，然后考虑让学校满意，对问题进行优化。基本思路如图1考虑成本N班级、课程、老师、时间随机初始种群适应度评估是否符合最优化解输出最佳个体选择交叉变异新种群车辆数平均满载率效用函数Y 图1：基本思路五.模型

7、建立、算法及求解问题的本质是将课程、老师和学生在合适的时间段内分配到合适的教室中，是一个多因素的整体优化问题。模型的主要任务是将专业、教室、课程、老师安排在一周内且不发生时间冲突。并且尽量做到人性化，最大可能的使学生、老师、学校满意。为此，我们采用遗传算法对学生和老师做排列，输出满意度较高的个体，然后考虑进校车数量等经济性因素，建立效能函数，对目标进行最终优化。5.1 遗传算法遗传算法采用类似基因演化的循环过程，其演算过程如下：1）随机产生一定数目的初始种群；2）对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第三步；3）依据适应度选择再

8、生个体；4）按照一定的交叉概率和交叉方法生成新的个体；5）按照一定的变异概率和变异方法生成新的个体；6）由交叉和变异产生新一代的种群，然后返回第2步。如图2所示：图2：遗传算法示意图5.2 模型建立以下分析是在不考虑学校满意度的基础上进行的5.2.1 约束条件排课的硬约束条件在时间和空间上根据不同的约束条件进行排列组合,以使教学正常进行。一张课表是有效的,则它至少应该满足以下硬约束条件:1) 教师不能冲突,同一教师在同一时间不能教授两门课程；2) 教室不能冲突,同一教室在同一时间不能安排两门课程；3) 专业不能冲突,同一专业在同一时间不能安排两门课程。排课的软约束条件为了尽可能的提高老师、学生

9、、学校的满意度，模型还应考虑以下软约束条件:1)专业课表在星期上分布尽量均匀；2)对于同一老师，每天上课时间应该相对集中，尽量避免同一天上下午均上课的情况；3)同一专业同一门课程，至少应间隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段；4)同一课程的多个课时段要保持一定的时间间隔；5)学校每周派往校区的班车尽可能少，即平均满载率尽可能高。可以认为，在符合约束条件的情况下，能最大限度满足要求的课表安排方案是优良的。5.2.2 建立一般模型对排课问题建立以下模型：其中，这里的x表示决策向量即时间、专业、老师因素, y表示目标向量即个体适应度, X表示决策向量x 形成的决策空间, Y

10、表示目标向量y 形成的目标空间,约束条件e(x) 确定决策向量可行的取值范围。方案一：采用三维编码的方式如图所示三维坐标系，X轴为时间轴，每个时间坐标对应一个时间间隔。如X1、X2分别代表周一上午第一、二节课。以一周五个工作日、每个工作日四个时间段计，共有20 个坐标值（X1X20）。Y 轴每一轴代表一位老师。Z 轴每一间隔代表一个专业。三维坐标可以确定一个小方块。其值定义如下：假设每个老师只教一门课，则Y轴同时也表示课程。同时，为了保证解的可行性，做以下约束e (xi)：约束一：如果Y 坐标和Z 坐标确定，则 应与Y老师在一周内给Z 班上课次数相同。约束二：如果Y 坐标和X 坐标确定，则约束

11、三：如果X坐标和Z坐标确定，则 采用遗传算法，并定义个体适应度为：选择算子：为各个个体的新适应度，用赌盘选择法随即确定下一代群体中还未确定的个体。交叉算子：交叉概率Pc取0.40.99。如下图，以垂直Z轴的面将个体切割，交换两个个体的阴影部分。这样一来就能保证新个体满足编码约束一的要求，而且每个班的适应值不变但个体适应值改变，算法容易收敛变异算子：变异概率Pm取0.00010.1。变异算子实现如下：第一步：产生01 之间随机数num1，判断是否需要变异。如果num1pm，执行第二步，否则，保留该个体。第二步：产生120之间随机整数num2、num3（num2num3）交换X坐标分别为num2和

12、num3，而Y 、Z 坐标相同的基因块值。很明显，经过这样变异的个体不会冲突，但个体适应值有所变化。由于个体的编码和适应值可以变化，从而提高了局部搜索能力。另外，每条染色体用以代表每位教师的课表，其结构表示如下：（教师ID，专业ID，课程ID，教室编号，上课时间）在算法设计时，染色体采用十进制数编码，例如：某一老师ID为0011，要教授课程编号为0001 的“高等数学”这门课，周学时为4，专业为2101，随机产生上课时间和教室，则可生成染色体如下：“0011，2101，0001，01102，3251”其中01102代表教室编号，3251中32代表上课时间星期三第二个教学单元（即上午3-4节），

13、51代表星期五第一个教学单元（即上午1-2节）。案例：基于以上算法，对一个学院进行模拟算例数据：Z专业集合01,02,03,04,05,06,07Y老师集合01,02,03,04,05,06,07,08,09,10,11,12,13,14,1516,17,18,19,20,21,22,23, 24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40L课程集合01,02,03,04,05,06,07,08,09,10,11,12,13,14,15，16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33

14、,34,35,36,37,38,39,40,41,42,43运行参数：M，T，Pc，Pm=645，8000，0.5，0.05运行结果：下图为某一次进化过程中，最高适应值和平均适应值的变化曲线。可见，收敛性较好。如下为部分课表信息： “01，01，01，12301，34” “02，01，02，01201，14”“03，01，03，14102，33” “04，01，04，11306，54”“05，01，05，14203，41” “06，01，06，11110，44”“07，01，07，14204，2324” “08，01，08，14103，1231”“09，01，09，01204，11”“10，0

15、1，10，04303，2132”“11，01，11，11203，53”“12，02，12，01301，3221”“13，02，13，01105，44”“02，02，01406,21”“14，02，13，01506，5123”“36，07，18，11102，5433”“37，07，37，01507，34”“38，07，38，13202，14”“39，07，39，11402，2142”“40，07，40，11307，1432”专业一课表如下：老师专业课程教室每周有课节次周一周二周三周四周五010101X23014020102M12014030103X41023040104X13064050105X

16、42031060106X11024070107X42043、4080108X410321090109M12041100110X430312110111X12033考虑学校满意度：问题转变成在满意度与成本之间的优化建立模型：F=0.6f(x) +4g(x)/G该函数表明，g（x）越大即同一时间段来学校的老师越多，所排课程越好，也从侧面说明了对于比较好的时间段，学校要尽可能多的安排 老师来上课，从而保证了学生的满意度。G越小每周所派校车数目最少，说明平均满载率越高，保证了学校的满意度。F最大时即为最优解，所排课程最好。如下为部分课表信息：“01，01，01，12301，34”“02，01，02，0

17、1201，13”“03，01，03，14102，33”“04，01，04，11306，52”“05，01，05，14203，41”“06，01，06，11102，44”“07，01，07，14204，2342”“08，01，08，14103， 1231”“09，01，09，01204，11”“10，01，10，14303，2132”“11，01，11，11203，22”“12，02，12，01302，1332”“13，02，13，14101，32”“02，02，02，11204，23”“14，02，14，01403，1442” “36，07，36，11303，2241”“37，07，37，01

18、504，43”“38，07，38，14304，33”“39，07，39，03202，52”“40，07，40，13304，3251”专业一的课程经过优化如下：老师专业课程教室每周有课节次周一周二周三周四周五010101X23014020102M12013030103X41023040104X13062050105X42031060106X11024070107X420432080108X410321090109M12041100110X430312110111X12032最终我们排好的实际课表如下：和学校现行的课表：相比之下我们的算法排出来的课表1 时间主要相对集中在周一到周四，安排在周五的课

19、只有一节，这样同学就可以享受一个相对较为宽松的周末。好好地休整。2 一日之计在于晨，在周一到周四早上全部安排的是满课。可以有效地利用时间，提高学习效率。3 相对重要的专业基础课。安排的时间间隔都为一天，可以保证同学在充分消化的的基础上又不至于遗忘的太多。达到有效学习。但是不足之处在于：1. 没有考虑到单双周的安排，课时安排相对较集中，前期学习任务繁重，使得任务不均。2. 我们所排的课表在教室地点的选择上是随机的，地点较为分散，不方便同学下课后及时的到达下一个教室，容易造成上课迟到的现象，影响教学秩序。这个问题有待解决。方案二排课问题还可以用分支界定发进行解决，建立模型如下：但是，经过我们对一个

20、专业5 个班、12 门课、12 个教师,5 个条件的情况进行了测试。结果整个排课时间达到几分钟。可以进一步推测，若是应用到整个学校几百个班的排课情况，排课时间将会很久，是不可取的。六.模型的优缺点及进一步分析6.1 优点1、遗传算法是一种全局优化策略,能避免陷入局部最优.2、基于三维编码的遗传算法求解课表安排问题，避免了适应值可能为负值、个体之间适应值相差过大，不利于算法收敛的缺陷，具有良好的收敛性。3、通过模型检验，所求模型较为稳定。4、为了平衡满意度与成本，我们综合考虑了满意度、车辆数、平均满载率三个指标。对于较优的课表，车辆数的减少会带来平均满载率的提高，所以又可将问题转化为满意度与车辆

21、数的双目标规划问题，以权重的形式反映了这些因素对效用函数的影响。6.2 缺点1、为了简化问题，没有考虑到教室资源的不足问题；2、为了简化问题，没有考虑单双周所上课程不同的问题；3、采用随机方式来初始化种群,这就造成了运算量变大和复杂度增加等情况,从而影响了算法的性能。需要较长的程序运行时间。七、参考文献1、张春梅. 用自适应的遗传算法求解大学课程表安排问题J . 内蒙古大学学报:自然科学版,2002 ,33 (4) :459 - 464.2、金炳尧,蔚承建,何振亚. 进化算法PBIL 在时间表问题中的应用J . 系统工程理论与实践,2000 ,20 (5) :104 - 108.3、胡献华,陈

22、江,陈启华. 基于遗传算法的排课问题求解A . 自动化理论、技术与应用中国自动化学会第19 届青年学术会议论文集C . 山东大学出版社,2004. 347.4、郭东伟. 遗传算法运行机理的研究D . 长春:吉林大学,2002. 829.5、何军华. 课表编排系统的算法研究与实现J . 湖北师范学院学报(自然科学版) ,2003 ,23 (1) :84287.6、陈行平,陈江,陈启华. 基于遗传算法的高校排课系统设计J . 绍兴文理学院学报,2004 (10) :26227.附录：关键算法程序遗传算法伪代码：BEGIN :I = 0 ;Initialize P( I) ;Fitness P( I

23、) ;While (not Terminate2Condition)I + + ;GA2Operation P( I) ;Fitness P( I) ;END.2.适合度求解算法：for i=1:50 for j=1:50 if j=i for h=1:50 if h=j&h=i sum=0; for k=1:50 summ=RS2(k,i); if (RS2(k,j)summ)&(RS2(k,j)RS2(k,h) summ=RS2(k,j); end if (RS2(k,h)summ)&(RS2(k,h)endans(i,j,h) minmin=endans(i,j,h); k=i; m=j

24、; l=h; end end end end endendminmin3、根据适合度得到教室：int number=get_number(priority7); BOOL fail While iCount20 do: Begin: fail=Get_Time_Pieces(2,&number,po); if(!fail) then do begin: iCount2-; cp-append_list(po); end begin else break; End Begin While iCount30 do: Begin: fail=Get_Time_Pieces(3,&number,po); if(!fail) then do: begin: ICount3-; Cp-append_list(po); End begin Else Break; End Begin18