1  引言

        .1  开发背景

        近几年来，随着各高校办公自动化工作的推进，教务管理自动化也被摆上了日程。在教务工作中占有很大比重的一项就是每学期的课程表排定工作。由于教工、教室和设备的相对紧张，如何进行合理地安排和分配，从而充分利用教学资源是我们不得不面对的问题。而人工进行排课不仅任务重，效率低，而且易出错，难于维护，想要排出一张各方面都满意的课表非常困难。并且随着高校规模的扩大手工排课的难度和工作量呈几何级数增长。

        随着信息技术的飞速发展，各个行业的信息化势在必行。科技的进步大大地提高了生产率。作为高校，如何才能提高办学效率，更好地完成教学任务，跟上社会发展步伐，这是一个摆在教学工作者面前的一个迫切的问题。应用信息化来改造传统的教学管理模式是一个重要途径  。

        在实际的应用中，很多研究者都提出了各种解决排课问题的方法，由于排课问题的复杂性，还没有找到有效的算法能获得NP完全问题的最优解。因此，如何运用近似算法和新的软件技术来降低排课问题的计算复杂度，仍然是颇具挑战性的研究方向  。

        传统的人工排课使用手工操作存在许多弊端，如重复劳动严重、效率低下、且不能达到资源的最优化配置等，将产生大量的文件和数据，这对于查找、更新和维护都带来了不少的困难。最令人担心的问题就是——出现教室资源冲突或教师资源冲突的情况，而且工作繁琐，工作量巨大,尤其是在给大学校园进行排课时出现的问题更多。当前高校教务管理所涉及到的信息资料数量大、类型多，还可能带有大量的统计输出，同时学校规模的不断扩大和招生人数的逐年攀升导致传统的排棵手段已无法满足现代化管理的要求  。

        排课管理系统是利用数据库管理系统开发的一种应用系统,其开发主要包括数据库的建立，充分满足正常的题库管理的前提下，提供了多角度的题库信息查询和题库信息分析报表，使学校管理人员可以随时掌握学校的排课情况，进一步指导学校的教学。真正实现了业务一体化，为学校全方位的信息化管理奠定了基础。

        在教学计划的不断完善和各高校校园网建立的大背景下，设计满足高校教务要

        求的排课系统显得十分必要。而据了解，排课管理是高校教务处重复性比较强且急需得到解决的工作， 且排课系统有安全性要求高、交互性强、处理数据量大等人工难以实现的特点。

        因此设计一个基于校园网络的人工智能化且操作简便的排课系统是高校教务管理信息系统实现的首要条件，同时也是一大难点，因为排课管理要求综合考虑教师、课程、班级、教室、时间等诸方面的因素，统筹兼顾，使课表既符合教学规律，又能够充分利用现有资源使其最大限度地发挥作用  。

        .2  国内外研究现状

        在国内，在20世纪80年代初期，国内学者开始用从模拟手工排课，也有人工智能构建的专家系统等等，具有代表性的有：南京工学院的UTSS(A University Timetable Seheduling System)系统，大连理工大学的智能教学组织管理与课程调度系统等。这些系统大都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。但是这些课表编排系统往往依赖于各个学校的教学体制，不宜于进行大量推广  。

        早在20世纪50年代末，国外就有人开始研究课表编排问题。1963年，Gotlieb曾提出一个课表问题的数学模型，但由于排课问题易受实际问题的影响，求解结果也不理想。20世纪70年代，美国人S.Even等就证明了排课问题是一个NP完全问题，其算法的时间复杂度呈指数增长。S.Even的论证正式确立了排课问题的学术地位，把人们对排课问题的认识提高到了理论高度  。此外，有些文献试图从图论的角度来求解课表问题，但是图的染色体问题也是NP完全问题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题。

        .1  JSP简介

        应用程序不同于其他语言开发的单一性程序。使用Jsp编程时，必须首先确定应用程序如何与用户交互，如鼠标单击，用户必须编写代码控制这些事件的响应方法。

        使用JSP开发数据库应用程序的一般步骤如下所示：

        （1） 建立数据库

        （2） 建立用户界面

        （3） 编写代码

        （4） 调试运行

        （5） 编译应用程序

        （6） 发布应用程序

        应用程序的结构：

        由于JSP应用程序是基于对象的，所以应用程序的代码结构就是该程序在屏幕上物理表示的模型。根据定义，对象包含数据和代码。在屏幕上看到的窗体代表属性，这些属性定义了窗体的外观和内在特性。

        界面设计

        （1） 控件的位置

        （2） 界面元素的一致性

        （3） 保持界面的简明

        （4） 使用颜色和图像：增加视觉的感染力

        （5） 图像和图标：增加应用程序的视觉上的趣味

        （6） 选取字体

        .2  SQL Server 2000简介

        本系统所用SQL Server 2000 的特性包括： 1.Internet 集成；2.企业级数据库功能；3.易于安装、部署和使用。同时本系统使用SQL Server 2000 个人版; 其特性为：

        (1)支持对称多处理器结构、存储过程、ODBC，并具有自主的SQL语言。SQL Server以其内置的数据复制功能、强大的管理工具、与Internet的紧密集成和开放的系统结构为广大的用户、开发人员和系统集成商提供了一个出众的数据库平台。

        (2)高性能设计，可充分利用Windows NT的优势。

        (3)强壮的事务处理功能，采用各种方法保证数据的完整性。

        (4)系统管理先进，支持Windows图形化管理工具，支持本地和远程的系统管理和配置。

        .3  Tomcat简介

        很受广大程序员的喜欢，因为它运行时占用的系统资源小，扩展性好，支持负载平衡与邮件服务等开发应用系统常用的功能；而且它还在不断的

        是一个小型的轻量级应用服务器，在本系统中当在一台机器上配置好Apache 服务器，可利用它响应对HTML 页面的访问请求。实际上Tomcat 部分是Apache 服务器的扩展，但它是独立运行的，所以当你运行tomcat 时，它实际上作为一个与Apache 独立的进程单独运行的。

        当配置正确时，Apache 为HTML页面服务，而Tomcat 实际上运行JSP 页面和Servlet。另外，Tomcat具有处理HTML页面的功能，同时它还是一个Servlet和JSP容器，独立的Servlet容器是Tomcat的默认模式。

        需求分析

        1 帮助系统维护可以实现：操作日志、重新登录、打印设置（包括统计各种报表及打印等）、退出等操作。

        2 系统的主要功能

        3掌握学校所有的课程和教师的信息。包括每门课程的时间、班级以及任课老师的姓名等。

        4可以对一个或多个班级进入课程管理与排课表管理，可以不限次的生成该班级课程表。

        5针对不同的人员授予不同的权限。提供灵活的浏览、查询功能。可以查看某个系、某个班级所有课程的信息。

        可以对课程进行变动管理。既可以手工排课，又可以实现自动排序功能。 

        提供一种或多种课程表输出功能，并使用活动的模板输出功能，输出样式可以由用户自定义。

        实现功能全面化，由于每个学校或班级的每天课程数目或时间都不太一样，实现智能计算总课程数目和管理对应的时间段，并且根据每门课程的独立分布式来进行排列（例如：大学语文自动排列的分布方式可以是周一至周六，那么系统就会自动将其平均分布在周一至周六这些天里）。

        1用户管理：设置两个级别用户：管理员和普通用户，管理员有权限操作系统中的所有数据，普通用户只能以执行查询，输出之类的功能，无法对系统进行实质性的操作，用户使用本系统之前必须先通过身份认证（用户级别、用户名和密码，密码输入有次数限制，连续三次输入错误密码则锁定该用户）。

        .2 系统所需硬件环境

        （1）处理器：建议使用酷睿 2

        （2）内存：1G以上

        .3  排课的约束条件

        在我的排课系统，主要对不同类型课程进行等级划分，排列出课程的排课优先级别，通过优先次序对不同类型的课程使用不同的算法进行排课，能够非常方便地处理各种排课约束条件的限制。

        例如教师和教室冲突、班级冲突、教师上课时间和地点选择、分层次教学、单双周排课、一课多教师教学和课程连上等各种各样的约束。同时该系统还能够非常迅速地得到排课结果，例如排一千门课只需几分钟时间等一系列问题。

        .4  系统所需软件平台

        （1）操作系统：Windows XP

        （2）数据库：Access 2003

        （3）Web 服务器 ：IIS 6.0

        （4）浏览器：IE 7.0，推荐使用360安全浏览器

        系统总体设计

        4.1  设计思想

        本系统采用各班级独立划分管理，所有教师均可为任何班级服务，各班级根据每天课程数目来进行自动排序，同时各教师允许教学多门课程，因此为了每名教师配置了时间占用表，只要与班级对应的时间空间表未被占用，都可以参与排课，并根据用户定义的要求排出课程。

        数据管理类：由于班级，时间，教师，课程等信息都需要一个活动的管理过程，因为在节省资源的情况下，将各数据所需要的代码合并在一起进行编写和使用。

        4.2  系统功能模块划分

        教务排课系统在功能上分四个模块，如图4.2：

        4.3  数据库结构的设计

        利用SQL Server2000来管理排课资源、排课约束条件等信息，利用数据库技术来实现设置排课优先级、课时和时间段的匹配以及处理排课资源的冲突，从而实现自动排课的目的。

        主要包含的数据实体有：专业、课程、教师、教室、课程表等。实体的具体属性如下：

        （1）专业信息包括：专业代码、专业名称；

        （2）课程信息包括：课程代码、课程名称、课程类型、总学时、每周课时、任课教师、开课院系、授课班级（专业）、上课人数、约束条件等信息；

        （3）教师信息包括：教师代码、教师名称、所属院系、约束条件等；

        （4）教室信息包括：教室代码、教室名称、教室类型、教室地址、容纳人数等；

        （5）课程表信息包括：课程代码、专业代码、教师代码、教室代码、上课时间等。

        系统详细设计

        .2  主界面及课表生成设计

        .2.1  班级管理设计

        模块设计说明：班级的操作部分是排课程序正常执行的重要部分，班级的添加不允许有同名的班级出现，而修改也不能做到修改班级名，班级名称将作为不可修改的数据部分，而删除部分，在删除之前必须保证该班级的课表是否已经生成，如果是，则需要注销课程表，这样做是让该班级生成的课表占用教师空间的部分全部返回，这样不会使教师的空间被反复占用，而最终导致错误发生。

        .1  登录系统设计

        设计说明:进入主界面后,等待操作用户输入用户名和密码,在输入之后按确定进入,验证用户名和密码,实现流程:

        (1) 检测数据库中有无管理员账号，如果有,则等待用户输入用户名和密码,否则按程序本身自动执行插入命令,新建一个管理员用户,并等待用户输入.

        (2) 验证用户名和密码是否正确,错误次数不能超过三次,超过三次则退出系统登陆界面

        (3) 当验证通过后,检测该登陆用户的管理权限,并设置变量传值给主窗体

        .2.3  课表生成部分设计

        图5.4 排课循环流程图 模块设计说明：此处将执行的数据分成很多小部分来执行，这样做可以在测试中便如发现问题，因为排课系统的要求非常高，所以在程序实现方面是以由简到繁的过程。

        (1)排课中要求的每周课程数相加不能超出定义的课表范围，否则也将会出现死循环。

        (2)列出对应课程教师的未被占用的排课列表和班级的课程占用表。

        (3)穷举法列出以上两者之间的共通点，可用点。

        (4)最后通过循环随机选择来实现课程的定位与排列。

        (5)课程定位中不允许每天有相同的课程重复，并按规定来执行按什么样的格式来排列，例如两节连排，也就是说可以把该课程在同一天排在一起，可以实现两节课连上，这是大学课表里最常用的一个功能。

        5.2.2  班级课程处理设计

        模块设计说明：课程数据的添加，修改或删除都会影响到已生成课程表的返回，因为在操作之前必要保证课程表属于未生成状态，如果当前为生成状态，则需要注销课程表，这样才可以继续操作。

        注：已生成课程表的返回：由于课程表排列好后，对应的课程后教师的排课占用表都会有标记标明，如果这时修改了某此数据后，这教师的占用表并没有恢复到未生成状态，这样就会导致不可预知的错误发生。

        5.2.4  报表输出功能设计

        模块设计说明：此处采用了两种输出方式，第一种是普通的报表方式输出，可以实现一般的打印预览等功能，第二种则是采用模板功能，用户可以自由修改模板，前提是不可以更改数据位，其它的部分无论如何修改都没有关系。

        .3  数据表设计

        在使用SQL server创建“排课管理系统”数据库系统中需要建立的数据表如下所示:

        课程信息

        表5.1 课程信息表

        2 用户登录

        3 课程名

        5 课程占用表

        系统日志

        7 系统设定

        5.4  其它模块设计

        此处几个模块是经过资源优化将其与班级管理整合在一起的，此处工作流程基本上与班级管理的流程相同。

        6  系统的实现

        .1  调课功能的实现及设计说明

        由系统自动排课生成的并不一定能完全达到用户所想需要的效果,虽然在程序中解决了系统冲突的出现,但是因为某些原因而出现临时的原因都需要进行调课,因此排课系统中除了自动生成课表还必须有很灵活的调课功能才能让系统更完整,也方便使用。

        此处调课是事先获取系统有用资源空间,并在图表中进行背景色变色显示,提示用户该门课程可以调动至变色显示的地方,主要是通过班级的课程占用与该教师的排课占用情况进行对比,寻找有利和适用的位置,并等待用户进行调课操作。

        执行调课:在进行以上操作后,计算机自动等待用户选择系统列出的调课点,在选择某调课点后,系统自动清除数据库的中该课程的教师与当前班级该处资源占用情况,并同时清除图表中的资料,将其重新放置到新位置,并修改新地点的资源占用情况,最后将图表的可调位置背景色还原回正常状态。