基于C/S模式自动排课系统的算法分析

张志顺，周 铭，张晴雯，肖海荣

1.嘉应学院医学院，广东梅州 514031

2.梅县气象局，广东梅州 514700

基于C/S模式自动排课系统的算法分析

张志顺1，周 铭1，张晴雯2，肖海荣1

1.嘉应学院医学院，广东梅州 514031

2.梅县气象局，广东梅州 514700

本文根据嘉应学院医学院教学排课工作的实际需求，从排课问题入手，分析了教室信息数据结构及课程信息数据结构，对排课算法流程进行详细描述和说明，给出了排课算法流程图，实现了排课、调课、查询、统计、打印等基本功能，可大大减少教学排课的手工劳动。

排课；C/S；数据结构；算法

1 排课问题描述

随着高校教学改革工作的深化进行，教学排课工作的灵活性日益增强，如何对教室、教师、学生以及时间等几部份资源进行最优组合，是保证整个教学计划正常进行关键。排课是将教师与学生在时间和空间上根据不同的约束条件进行排列组合，在满足全部约束条件的基础上，实现教室、教师、学生、时间等资源的最优组合[1]。这里的约束条件主要是：同一时间对同一名教师安排了两门不同的课程，对于该教师来说课程的安排是冲突的；对于学生也是如此，同一时间给同一教室安排两门不同的课程，则对于这两门课程来说，安排的教室是冲突的。

2 数据结构定义

2.1 教室信息数据结构

2.2 课程信息数据结构

3 算法流程描述

第一步：清空上次排课的结果；

第二步：根据条件查询数据库得到教室使用信息与待排课程信息，初始化roomlist（教室信息链表）和courselist（课程信息链表）；

第三步：进行自动排课。自动排课分为：有上课时间的排课与没有上课时间的排课两种情况；

第四步：保存排课结果。

对第一步操作的说明：

1）清除数据库中T_jxTeachImplement表的所有有关的排课信息，包括课程的时间和地点，以及教室的fArranged字段（课室是否被安排）的内容都设为NULL。

2）清除数据库T_ksClassroomUseInfo表中fArrangeTableId的内容，清除时把fArrangeTableId字段设为NULL。

对第二步操作的说明：

1）从数据库中查找教室信息与课程信息。教室信息的来源是：根据查询条件从T_jxClassroomList表中查找出教室信息。课程信息的来源是：根据查询条件从T_jxTeachImplement表中查找出可供自动排考的课程信息。

2）根据教室信息取得教室的“座位数”、“课室功能代码”、“序号”作为roomlist的roomkey值，再根据jxClassroomList（教室信息表）中的“序号”从T_ksClassroomUseInfo表中找到“安排项目ID”、“可用周数”、“可用节次”作为roomlist的roomvalue值。

3）根据课程信息找到“总共人数”、“课室功能代码”、“序号”作为courselist的coursekey值，这里的总共人数是指最大的上限人数据，其中新生的总人数是按照学籍班人数计算，而老生的人数是按照注册人数来计算[2]。

4）如果每周上课的次数大于1，则生成2个课程链节点。对有上课时间的，可根据上课时间找出对应的上课地点，对无上课时间的，则上课时间与上课地点都为空。

对第三步操作的说明：

1）取出courselist中的一个元素，以教室的容纳人数来安排课程。如果一门课程无法找到合适的教室，就把它的序号（fId)插入UnarrangeableSet集合中，这可用来统计无法排课的课程。

2）为有上课时间但无上课地点且上课人数大于0的课程安排该门课程的上课时间与上课地点。

3）课程链节点值与教室链节点值满足以下条件：课室安排项目相等、课室功能相等、上课时间是否处于教室可用日期、符合单双周的要求、节次是合适。如果条件成立，则课程结点获得上课地点。

4）对无上课时间且无上课地点的课程安排该门课程的上课时间与上课地点。

5）对面授周数和上课人数都大于0的课程安排，课程链节点值与教室链节点值满足以下条件：课室安排项目相等、课室功能相等、教室的可用周数大于等于课程班所需要的面授周数。如果条件成立，生成安排时间和分裂教室结点。

对第四步操作的说明：

1）把排课中占用的教室时间写入T_ksClassroomUseInfo表中。

2）把排课结果写入到（教学计划实施表）T_jxTeachImplement表中。

4 算法流程图

4.1 排课系统数据流图

图4-1 排课系统数据流图

4.2 排课算法流图

图4-2 排课算法流图

5 结论

本文所设计的基于c/s（Client／Server，客户/服务器）模式的教学排课系统，由客户应用程序Client、服务器管理程序Server和中间件Middleware3个部件组成[3]，以Windows Server 2000/XP为网络操作系统，以Borland公司的C++ Builder语言开发客户端软件，以SQL Server 2000为后台数据库，具有交互性强，可靠性高，事务数据处理能力强的特点。教学排课系统全面支持广域网络办公模式，实现了排课、调课、查询、统计、打印等基本功能，可大大减少教学排课的手工劳动。

[1] 王璐，邱玉辉.基于协商的智能排课系统的研究[J].计算机科学，2006，33(6)：214-217.

[2] 潘以锋.高校智能排课系统的算法[J].上海师范大学学报：自然科学版，2006，35(5)：31-37.

[3] 部建华，纪玉玲.基于三层c/s结构教务管理系统的开发[J].佳木斯大学学报:自然科学版，2004，22(3)：27-30.

TP393

A

1674-6708（2010）18-0122-02

张志顺，讲师，工作单位：嘉应学院医学院，从事计算机技术研究与软件开发

周铭，职务：教务科长，工作单位：嘉应学院医学院

张晴雯，助理工程师，工作单位：梅县气象局，从事计算机技术研究

肖海荣，高级讲师，工作单位：嘉应学院医学院，从事软件开发