通用高校排课算法研究----3.基于时间片优先级排课算法

3   基于时间片优先级排课算法描述与分析

    排课问题实质上是时间、教师、班级、教室、课程这五维关系的冲突问题，要合理的解决这个问题首先要了解排课中的一些基本原则以及排课的一些基本要求。

3．1排课中的基本原则

在课程的编排中应遵循一定的规则, 只有按照基本规则来进行课程的编排才能够减少冲突的发生, 这些基本规则主要有以下几条:

1) 同一班级的学生在同一时间(某些特定的选修课时间除外) 不能安排两门课程

2) 同一教师在同一时间不能安排两门课程

3) 同一教室在同一时间不能安排两门课程

4) 同一时间安排的课程总数不能大于所能提供的教室总数

5) 某一课程参加学习的总人数不应大于所安排教室的座位数

6) 所提供教室的属性与课程所需教室的属性一致

在时间、教师、班级、教室、课程这五维关系中, 时间、教师、班级三者之间存在着紧密关系。相对而言, 教室与它们关系就不那么密切。

3．2排课的基本要求

课程的安排不是任意的, 为了达到最好的教学效果应遵循一定的要求。这些要求主要有:

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

2) 课程在一周上多次时, 要有一定的间隔性

3) 公共课等涉及面广、学时多的课程应优先处理

4) 对同一教师, 同一上课对象应尽量选择相对固定的几个教室

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

6) 连着的课的教室选择不应相隔太远

7）同一天有几门课时尽量把课分散

8) 优先满足一些特殊要求（比如有些教室喜欢上上午的课，可以优先满足）

3．3基于时间片优先级排课算法描述

在描述算法之前我们把一些概念先讲清楚。在这里我们把从行政角度分的班叫自然班，把在同一个教室上课的班叫做排课班。在大学里有些公共课是几个排课班通过多媒体来一起上的，我们把这个排课班的总和叫做公共班。班级、教室、教师、课程都维护着自己的一张课表。对课表的每个表元（如星期一的第一节课）在这里称做时间片。

基于时间片优先级排课算法以排课班为单位，围绕着各对像(自然班、教室、教室)的时间表选择合适的时间片。

1．算法流程图                  





2．算法的伪代码描述

           输入：教师（teacher1,teacher2,…………….teachern）

                 教室（room1,room2,…………………roomn）

                 班级（class1,class2,………………….classn）

                 课程（course1,course2,………………coursen）

                 各教师、教室、班级、课程时间片的优先级

          排课班(schudel_class1,schudel_class2………schudel_classn)

          输出：已经排好课表的教师、教室、班级

Procedure schudeling(teacher,room,class,course,schudel_class,public_class)

//初始化一张空的时间表，对该时间表的每个时间片的优//先级初始化为高级

Init Time_table

         //对排课班进行处理

   For every schudel_class do:

    If(!Check_Have_despose(schudel_class))  //假如该排课班尚未排课

       Begin:

           Time_table=Time_table & get_all_class_time_table(schudel_class)

           Time_table=Time_table & get_room(schudel_class);

           Time_table=Time_table & get_teacher(schudel_class);

            Course=get_course(schudel_class);

            //假设只有两节连堂及三节连堂那种课

            Int iCount2=0;//那门课两节连堂的次数

            Int iCount3=0;//那门课三节连堂的次数

            //得到课程每周的课时数

Int course_count=get_couse_count(Course);

//得到每周的连课情况

            Parse_couse_count(course_count,&iCount2,&iCount3);

//根据iCount2,iCount3,以及Time_table为该排课班选择N个

//(N=iCount2+iCount3)适当的时间片,保存在CPoint变量中

            CPoint po;

LList<CPoint>* cp

Int priority[7]=0;

//得到每天的优先级的总和

    Loop:I=0 until I=6 do:

         Loop: J=0 until J=6 do:

          Begin:

               Priority[I] =Priority[I]+ Time_table.time_piece[I][j]

          End Begin

        

          //得到优先级总和最大的那天，我们认为那一时间最闲

//适宜安排课程

          int number=get_number(priority[7]);

          BOOL fail

          While iCount2>0 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 iCount3>0 do:

              Begin:

                  fail=Get_Time_Pieces(3,&number,po);

                  if(!fail) then do:

                    begin:

ICount3--;

                      Cp->append_list(po);

                    End begin

                   Else

                     Break;

              End Begin



//根据*cp的数据及schudel_class的数据对schudel_class中的自然班，所得到的教室，

// 老师的课表进行回写

if(!fail) do

WriteBack(schudel_class,cp);

Else then

  RollBack(schudel_class,cp);//把先前选好的教室，老师给”擦除”掉

        End Begin

     End Schudeling

算法里面有到的一些函数解释：

BOOL check_for_dispose(schudel_class):以排课班为参数，判断该排课班是否已经排好课，排好了返回treu，否则返回false

‘&’操作:该操作是对两个课表的运算，返回一个新课表；得到的课表的时间片为所运算的课表对应时间片的较小值

CTime_table& get_all_class_time(schudel_class):以排课班为参数，得到该排课班所有自然班课表的&，返回得到的新课表

CTime_table& get_room(schudel_class):以排课班为参数，为该排课分配所有合适的教室，并把所得到的教室的课表求&，返回新课表

CTime_table& get_teacher(schudel_class):以排课班为参数，为该排课班选择一合适的教师，并返回该教师的课表

Ccourse get_course(schudel_class):以排课班为参数，得到该排课班的课程，并返回之

Int get_course_count(Ccourse):以课程为参数，得到该课程每周所需上的课时数，并返回之

Parse_course_count(int&,int&,int&):分析get_course_count所返回的数值，把该数值以2节连堂和3节连堂分开(在这里假设只有2节连堂和3节连堂两种情况)

Int GetNumber(int*):传进一整型数组，得到该整型数组中的最大值的下标，并返回之

WriteBack(schudel_class,Llist<CPoint>*):根据Llist<CPoint>* 中的时间片值，更新public_class中的教师，班级，教室的时间表信息

RollBack(schudel_class,Llist<CPoint>*):擦除前面步骤在排课班、教师、班级、教室中写下的数据

计算机排课是个复杂的过程，在数据量大，约束条件多的条件下，通过人工干涉达到合理排课是非常重要的。人工干涉包括在排课前的一些数据输入工作，人工进行些预排课，排完课后对课表进行适当的调课。

3．4算法分析

此算法属于贪心算法。每次对教师、教室资源的选取都是取当前最优的数据。此算法对按照教师、教室、班级的优先级取最优值，所以对各对象的一些特殊要求会很明显的体现出来，在教师、教室资源不紧缺的情况下，此算法能排出相对合理的课程。相对于上一章介绍的两个算法，在处理各种特殊要求的能力上有明显的优势。








               参 考 资 料

参考网站：

http://www.csdn.net

http://www.vckbase.com

http://www.codeproject.com

http://lib.hnu.net.cn

参考文献：

[1] “An Average Case Approximation Bound for Course Scheduling by Greedy Bipartite Matching” Gary Lewandowski1, Prakash Ojha2, Jennifer Rizzo1, and Abigail Walker1 Xavier University, Mathematics and Computer Science Department

[2] “ A column generation scheme for faculty time-tabling “ Paolo Sera.ni, University of Udine, Italy

[3] Timetabling using a Steady State Genetic Algorithm  Ender Ozcan, Alpay Alkan

Yeditepe University Department of Computer Engineering,

[4] 基于优先级自动排课算法PCSA 的设计与实现方案 陈　谊, 　杨　怡, 　张国龙, 　王尚忠  北京工商大学计算机学院

[5] 基于课元相关运算的高校排课算法董艳云　　钱晓群　　张宇舒  西南交通大学

[6] 《Visual C++.NET宝典》Tom Archer ,Andrew Whitechapel编著，电子工业出版社   

[7] 《Visual C++ 6.0 网络及Interner 开发指南》 李博轩 著 清华大学出版社2000

[8] 《Visual C++6.0 项目案例导航》 扬小平 著 科学出版社

[9] 《学用Visual C++6 .0》 [美]Davis Chapman  著  骆长乐 译 清华大学出版社  西蒙与舒斯特国际出版公司

[6] 《数据库系统概念》 [美] Abraham Silberschatz  Henry F.Korth 著 机械工业出版社