基于Java Web的高校排课系统的设计与实现

PAGE\*ROMANPAGE\*ROMANII摘要基于JavaWeb排课系统的设计与实现摘 要排课问题是一个NP完全问题,是一个多约束的、多目标的组合优化问题。而是现在高校教务管理的迫切需求。JavaWeb平台下的排课系统的WebB/SJSPModel2MVC关键词：排课系统；MVC；JSPModel2；JavaWebAbstractCourseArrangementSystemDesignImplementationBasedonWebAbstractCoursetimetablingproblemisaNPcompleteproblem,andisacombinatorialoptimizationproblemwithavarietyofconstraintsandamultiobjectiveoptimization.thetraditionalmanualmethod,isnotonlytediousanderror-prone,andcannotfullytakethereasonableuseoftheteachingresourcesintoconsideration.Therefore,designingacoursearrangementsystemthatcanarrangethecoursearrangementautomaticallyaccordingtotheconstraintsistheurgentdemandofuniversityeducationaladministrationmanagementnow.Throughtheanalysisofthecurriculumarrangementsystem,thispaperexpoundsthewebsolutionsofcurriculumarrangementsystembasedonJavaWebplatform.ThissystemadoptsB/Sstructure,andusingtheMVCdesignpatternbasedonModel2,greatlysimplifyingthedifficultiesofsystemdevelopment.Thispaperusegeneticalgorithmtosolvethecoursetimetablingproblem,andexpoundsthebasicprincipleofgeneticalgorithm,thealgorithmflow,andtheconcreteimplementationintheproblem.Keyword:CourseArrangementSystem；MVC；JSPModel2；JavaWebIIIIII目录目录摘要 IAbstract II第一章绪论 1课题背景与意义 1国内外发展现状 1本文的研究目标 2第二章相关开发技术 3网络结构 3JSP技术 3MVC模式介绍 5本章小结 6第三章排课系统分析与设计 7排课系统需求分析 7排课系统功能架构分析 9数据库设计 12第四章排课系统算法设计 18遗传算法介绍 18排课系统算法设计 194.3本章小结 26第五章排课系统实现与测试 27登录模块实现与测试 27基本信息管理模块实现与测试 28手动排课模块实现与测试 29自动排课模块实现与测试 30课表查询模块实现实现与测试 30本章小结 31第六章总结与展望 326.1总结 326.2展望 32参考文献 33致谢 35绪论绪论PAGEPAGE2第一章绪论课题背景与意义随着我国在校大学生人数快速增长，教学资源相对紧缺，合理安排课程变为了适应当前高校教务管理逐步趋向高效化、快捷化、方便化、人性化的管理风格，为了方便用户管理信息，查询信息，以及信息的及时反馈与沟通，本文采用了基于Web的应用体系结构。国内外发展现状（TimeTableProblems,TTS1963GotliebTheConstructionofClass-TeacherTime-Tables》中，他首次提出了排课问题的数学模型，但并未找出一个有效的算法。1976年，SEven用数学方法证明了排课问题NP[24]。我国对于排课问题的研究相对较晚。相对较早的排课问题的研究成果是，1984年林漳希和林尧瑞发表的《人工智能技术在课表编排中的应用UTSSTISER系统、浙江大学的正方现代教学管理信息系统等[20]。本文的研究目标本文主要的研究目标是：剖析排课问题，研究排课时需要考虑的问题，并提出解决方法。利用遗传算法解决排课问题。Web开发过程，掌握相关理论与技术。相关开发技术相关开发技术PAGEPAGE6第二章相关开发技术网络结构本系统采用了B/S结构，以下是对B/S结构的简介。B/S结构B/SBrowser/Server(浏览器/服务器)的。B/S结构分为三个部分：客户端、服务器端、数据服务器。在开发过程中，现在把B/S模式分为三个层次：表示层、业务逻辑层、和数据访问层，分别对应B/S结构中的三个部分(如图2.1所示)。客户端客户端表示层：用于处理用户输入，以及请求处理结果的输出。WEB服务器WEB服务器业务逻辑层：执行业务逻辑，向数据库发送请求。数据服务器数据存储层：运行SQL语句。图2.1B/S结构简图B/SURL地址，浏览器通过域名解析到IP地址，并向WebHTTPWebWeb服务器。WebHTTP响应，浏览器接受并显示响应结果。B/S结构的优缺点优点：对客户端硬件要求低。易于维护与升级。缺点：响应速度相对较慢。安全性相对弱。服务器负荷重。JSP技术目前流行的三种动态页面技术有AS（ActiveServerPageJSP(JavaPages)，PHP(HypertextPreprocessor)等。本文采用JSP来开发排课系统。JSP是由SUN公司倡导、许多公司参与一起建立的一种动态网页编程技术标准[15]。它基于Java技术，支持跨平台、跨服务器技术，拥有JavaBean与扩展标记库技术，是Servlet技术的扩展。早期的JavaWeb层体系结构中只有ServletHTMLServletServlet中不能像PHP等一样嵌入HTML代码，所以利用Servlet来输出HTML非常困难。为了克服Servlet的这些弱点，Sun公司推出了JSP技术。JSP包含很多技术，包括JavaBean，自定义标签，EL表达式，JSTL标准标签类库等[15]。JSP页面的执行过程：Web容器服务器端2.向服务器发送浏览请求1.URL地址3.调用某个JavaBean组件4.JavaBean返回的数据用户客户端浏览器7.显示HTML 6.返回HTML页面做出响应JavaBean(Java组件)5.读取数据库或者Web容器服务器端2.向服务器发送浏览请求1.URL地址3.调用某个JavaBean组件4.JavaBean返回的数据用户客户端浏览器7.显示HTML 6.返回HTML页面做出响应JavaBean(Java组件)5.读取数据库或者文件DBJSP的优点：

图2.2JSP页面访问过程图跨平台,一处编写随处运行；实现了内容生成与显示的分离；JDBC连接数据库；可复用性好，支持可重用的基于组件的设计；安全性好；支持分布式处理；JSP的缺点：1．开发周期长；2．开发成本高；MVC模式介绍MVC模式简介MVC模式中，应用程序被划分成模型Mode、视图Vie）和控制器（Controller）三个组件[14]，如图2.3所示。各个组件的定义与作用如下：Model(模型)：该组件是应用程序最核心的部分，包含了应用程序的业务数据和业务处理逻辑。View(视图)：该组件代表用户看到并与之交互的界面。视图的功能就是向用户显示数据，向用户提供输入数据的接口。Controller(控制器)：该组件用于处理用户的请求，对模型和视图进行匹配，协同完成用户的请求。选择视图选择视图(控制器)接受用户请求调用模型响应用户请求选择视图显示相应结果业务处理（视图）显示模型状态递给控制器用户请求状态查询通知更新数据（模型）响应状态查询处理业务流程通知视图业务状态更调用事件MVC模式的优点调用事件

图2.3MVC模式图护。模型与视图分离，提高了应用程序的重用性。功能。MVC模式的JSPModel2实现请求控制层例示WebDB模型层响应视图层（JSP）选择视图在JavaWebServlet+JSP+JavaBean的模型称为Model2MVC请求控制层例示WebDB模型层响应视图层（JSP）选择视图图2.4MVC的JSPModel2实现结构图JSPModel2的工作流程：当用户在视图层发送请求，控制层ServletJSP页面，由视图层显示给用户。本章小结JSPMVCMVCJSPModel2中的实现。排课系统分析与设计排课系统分析与设计PAGEPAGE9第三章排课系统分析与设计排课系统需求分析系统需求分析的基本任务是准确地回答“系统主要是做什么？”这个问题，即清楚、准确、具体地描述信息系统必须具有的功能、性能、运行规格的等要求[10]。3类，分别是管理员、学生和教师。对于管理员，登录后，可综上所述，本系统的主要功能有：系统登入功能：对于不同的用户，登录后产生不同的用户界面；基本信息管理：对教师、教室等基本数据信息的增、删、改、查操作课表安排并进行冲突检测；课表查询显示：根据查询条件显示并打印相应课表安排；系统用户管理：授权与撤销用户的权限，以及修改用户密码。课表建议管理：可以提出课表建议，并且查询、处理课表建议。排课系统数据流图数据流图（DataFlowDiagram,DFD）是描述软件系统结构中数据处理过程的一种有力的图形工具[10]。排课系统数据流图，如下所示：顶层数据流图系统管理员系统管理员输入基本信息排课系统打印课程表学生、教师图3.1顶层数据流图系统管理员系统管理员维护基本信息自动排课课程表手工调整打印课程表第二层数据流图

图3.2第一层数据流图基本信息表基本信息表课课程表程表表课程课程表系统管理员事务维护基本 事务信息自动排课手工调整产生课表课程表排课约束条件

图3.3第二层数据流图排课问题就是根据约束条件，对教师、班级、时间、教室、课程这5约束条件。硬性约束条件有：教师约束：同一个教师在同一时间一定不能教授多门课程；教室约束：同一教室不能同一时间安排多门课程；班级约束：同一班级不能同一时间安排多门课程；除了以上3程对应的教室类型正确；排课时，除了考虑硬性约束条件，还要考虑软性约束条件。软性约束条件，用于评价排课方案是否合理，衡量排课方案的合理性和人性化。一般考虑的软性约束条件有：匹配；同一门课一周内在节次上要均匀分布；体育课一般安排在上午3、4节或者下午；公共课一般安排在主教学楼上课；专业课一般安排在各个学院楼上课；满足诸多方面要求的原则方案。排课系统功能架构分析排课系统体系结构本排课系统采用了B/S三层体系结构，关于B/S结构的介绍，参照第二章2.1小节。WebController(Servlet)浏览器请求Model(JavaBean)JDBCSQLServer响应View(JSP)表示层业务逻辑层 数据访问另外，本排课系统以MVC与三层架构相结合的模式进行开发，大大简化了weWe的三层架构将WeWebController(Servlet)浏览器请求Model(JavaBean)JDBCSQLServer响应View(JSP)表示层业务逻辑层 数据访问图3.4排课系统架构图排课系统分析与设计排课系统功能模块学生、课程、教学计划等信息的增、删、改、查的操作；排课管理模块分为：自动排课、手工排课、查询课表、调课申请的管理,排课管理模块是排课系统的核心部分；系统用户管理模块包括授予用户权限(即为不同用户，例如管理员和普通教师，设置不同使用权限)和修改密码等；课表建议管理模块包括查看课表建议、处理课表建议以及对课表建议信息的维护。系统的主要的功能模块，如图3.5所示：

图3.5排课系统功能模块图用例图（UseCaseOiagram能的操作者。分别为以管理员、教师和学生身份登录的系统用例图：10排课系统分析与设计3.6管理员用例图1排课系统分析与设计3.7教师用例图3.8学生用例图数据库设计数据库概念设计数据库概念结构设计阶段最常用的方法是：实体-联系方法，描述工具是：E-R(Entity-Relationship)E-R方法可以形象的描述现实世界中实体直接的E-R图如下：12排课系统分析与设计数据库结构设计

图3.9E-R图本排课系统中数据库的关系模式，如下：管理员（编号，名称，密码）院系（系部编号，系部名称，所属学院代码，所属学院名称）专业（专业编号，专业名称，院系编号）班级（班级编号，班级名，专业编号，班级人数，年届）课程(课程编号，课程名称，学分，课时，上课时间，教室类别，教师编号，专业编号，开课院系,周学时)教师（教师编号，教师名字，性别，年龄，职称，院系编号，密码）教室（教室编号，教室名称，教室类型，教室容量，教室地址）学生（学生编号，学生名字，性别，年龄，班级编号，密码）排课表（编号，教室编号，班级编号，课程编号，年级范围，单双周）教室表、班级表、时间表、排课表等等，如下所示：1. 管理员表(Admin)13排课系统分析与设计排课系统分析与设计PAGEPAGE17字段名字段描述数据类型 字段大小字段名字段描述数据类型 字段大小允许空 说明Admin_id管理员编号 varchar10否主键Admin_name 管理员名称 varchar30否Password密码varchar301234562. 院系表（Deptment)3.2院系表（Deptment)字段名 字段描述 数据类型 字段大小允许空说明Dept_id 系部编号 varchar 10否主键Dept_name 系部名称 varchar 30否Academy_id 所属学院代码 char 2Academy_name 所属学院名称 varchar 303. 专业表（Profession）表3.3专业表（Profession）字段名 字段描述 数据类型 字段大小允许空说明Pro_id 专业编号 varchar 10否主键Pro_name 专业名称 varchar 30Dept_id 院系编号 varchar 104. 班级表(Class)表3.4班级表(Class)字段名 字段描述 数据类型 字段大小允许空说明Class_id 班级编号 varchar 10否主键Class_name 班级名称 varchar 30否Class_num 人数 int 4Class_year 年届 int 4Pro_id 专业编号 varchar 105. 学生表(Student)外键表3.5学生表(Student)字段名字段描述数据类型字段大小允许空说明Sid学生编号varchar10否主键Sname学生名字varchar30Ssex性别char2Sage年龄int4Class_id班级编号varchar10外键Password密码varchar30否1234566. 教师表表3.6教师表（Teacher）字段名 字段描述数据类型 字段大小允许空说明Tid 教师编号varchar 10否主键Tname 教师名字varchar 30否Tsex 性别char 2Tage 年龄int 4Ttitle 职称varchar 30Dept_id 院系编号varchar 10外键Passpword 密码varchar 30123456教室表(Room)

表3.7教室表(Room)字段名字段名字段描述数据类型字段大小 允许空 说明Room_id教室编号varchar10否主键Room_name教室名称varchar30Category教室类型int4capacity教室容量int4addr教室地址varchar500123”代表体育场课程表(Course）表3.8课程表(Course）字段名字段描述数据类型字段大小允许空说明Cid课程编号varchar10否主键Cname课程名称varchar30否Cmark学分int4Chours课时int4Cweeks上课时间varchar10Category教室类别int4Tid教师编号varchar10外键Dept_id开课院系varchar10外键WeekHours周学时int4在课程表，课程编码中第一位表示课程的性质：T表示通识课、Z表示专业课、J表示学科专业课。教学计划表(TeachPlan)表3.9教学计划表(TeachPlan)字段名字段描述数据类型字段大小允许空说明id自动编号varchar10否主键Cid课程编号varchar10Pro_id专业编号varchar10Sem_id学期号int4其中，学期号的取值范围是1-10，分别表示大学期间的各个学期。排课表(Curriculum)01012字段名字段描述数据类型字段大小允许空说明id自动编号varchar10否主键Cid课程编号varchar10Class_id班级编号varchar10Time_id时间代号int4Room_id教室编号varchar10Semester学期范围varchar20DSZ单双周int4分别来表示全周，单周和双周三种上课情况。本章小结分析与设计。排课系统算法设计排课系统算法设计PAGEPAGE21遗传算法介绍

第四章排课系统算法设计遗传算法（GeneticAlgorithm）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法[19]Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems80年代由Goldberge1997年5的TransactionEvolutionalyComputation计算和建模方法的研究日趋成熟。遗传算法的基本思想[18]。因此，遗传算法的第一步就是实现从表现型到基因型的映射开始开始产生初始种群个体评价终止条件结束选择运算交叉运算变异运算产生新群体图4.1遗传算法的流程图排课系统算法设计行合理优化安排并取得合理解的问题。通过对排课问题的数据分析、约束条进行算法设计与实现。时间片问题(44节)2个相邻的小节，不能在上、下午之间跨时段。把45T1，T2，T3……T20来表示一周中的各个时间片，则每周的4.1所示：星期一星期二4.1周时间片分布表星期三星期四星期五T1T2T3T4T5T6T7T8T9T10T11T12T13T14T15T16T17T18T19T20染色体编码形式之外，它还决定了个体从搜索空间的基因型到解空间的表现型时的解码方[19]。故对于编码的设计需要考虑到这几方面的因素。班级IDIDIDID)所有的教学课程就是一个可能[17]。结合排课问题的实际特点，本文采个班级，时间片段为T1-T20，则由T1-T20中的值就是染色体基因，其中每个基N个“个体”组成，设计的基本思路如表4.2所示：下面介绍本文采用的基因编码：表4.2染色体编码示意表下面介绍本文采用的基因编码：班级1班级2……T1T1T1T2T2T2………………TJTJTJ………………T19T19T19T20T20T20班级IT1T2……TJ……T19T20……T1T2……TJ……T19T20班级M-1T1T2……TJ……T19T20班级MT1T2……TJ……T19T20因编码由原来三元素，转变为了二元素（课程，教室因编码由原来三元素，转变为了二元素（课程，教室。但是考虑到排课过程中的冲突检测，需要将教师编号、教室类型和教室编号进行编码。的冲突检测，需要将教师编号、教室类型和教室编号进行编码。由于遗传算法要求的编码原则是：一、有意义的积木块原则；二、最小字符由于遗传算法要求的编码原则是：一、有意义的积木块原则；二、最小字符集编码原则集编码原则[19]。所以对于基因的编码采用了与数据库数据编码相同的符号编码方法。同时，这样也有利用从基因型到表现型的解码操作。方法。同时，这样也有利用从基因型到表现型的解码操作。综上所述，本文采用的基因编码规则：教师编号综上所述，本文采用的基因编码规则：教师编号(10)+课程编号(8)+教室编号（（6）+所需教室类型（1）是否为单双周（1，编码长度为10+8+1+6+1=26个字符。字符。以及单双周编码已在数据库设计阶段已给出，此处不再赘述。以及单双周编码已在数据库设计阶段已给出，此处不再赘述。例如，基因编码：6101000003Z610100361A10200，放在二维数组中第i行第j列，则表示教师编号为6101000003的教师，在第j个时间段给第i个班级，在编号为61A102的教室上编号为Z6101003的课程，该课程占用普通教室，其是全周上课。产生初始种群1—20个数，如然后，按种群规模的大小，产生一定数量的个体，这样就组成了一个初始种群。另外，本人设计了教师时间类和教室时间类1表示未1610构造适应度函数本文的适应度函数，是由软约束条件转化而来。以下是本文考虑的软约束条排课系统算法设计排课系统算法设计22件；P1:匹配；P2:同一门课一周内在节次上要均匀分布；P3:体育课一般安排在上午3、4节或者下午；P4:公共课一般安排在主教学楼上课；P5:专业课一般安排在各个学院楼上课；育课的安排时间。（一）体育课时间期望（一）体育课时间期望在教室类型中，在教室类型中，3表示体育课，所以只要检测编码中的教室类型为3的课程，就是体育课。就是体育课。具体方法：遍历二维数组，查找每个班级中体育课的位置（即时间片具体方法：遍历二维数组，查找每个班级中体育课的位置（即时间片，计算出对应的期望值，并将期望值累加。算出对应的期望值，并将期望值累加。定义体育课时间期望值函数为：定义体育课时间期望值函数为：FP1iF(i)，其中i=(1,2,3……18,19)。P1时间1,5,9,3,172,6,10,14,183,7,11,15,194,8,12,16,20期望值051015表4.3体育课时间期望表表4.3体育课时间期望表（二）课程离散程度期望课程离散度期望值。课程离散度期望值。定义课程表离散度期望值函数为：F F(i)F F(i)，其中P2 P2 P2 P2i ii=(1,2,3i=(1,2,3……18,19)。表表4.4课程离散程度期望表课程时间差1,18,192,16,173，13，14,154，9，10，5,6,7,8期望值02411，126 8排课系统算法设计排课系统算法设计PAGEPAGE26（三）教室利用率期望（三）教室利用率期望具体方法：遍历二维数组，计算每个教室的利用率，其中教室利用率具体方法：遍历二维数组，计算每个教室的利用率，其中教室利用率=班级人数人数/教室容量，得出每个教室的利用率期望值，并累加。定义教室利用率期望值函数为：FP3rF(r)，其中r表示教室利用率。P3表表4.5教室利用率期望表教室利用率不小于80%不小于60%不小于40%小于40%期望值10850（四）计算适应度函数FitnessFitnessw*

w*

w*

，其中w1,w2,w3,分1

P

P3别为w1,w2,w3的取值分别是：1，8，4。选择操作选择操作就是用于确定父代群体中按某种方法选取哪些个体遗传到下一代利用此方法可以很好地避免基因缺失、提高全局收敛性和计算效率[17]。其具体操作过程是：计算个体适应度；计算选择概率；计算累计选择概率；随机产生0-1体被选中。交叉操作交叉操作是产生新个体的重要操作,它决定了遗传算法的全局搜索能力。在runstheriskofcreatingageneticalgorithmthatspendsmostofitstimeevaluatingillegal（即二维数组PC，随机产生一个浮点数P（0-1，当P小于PC时，执行交叉操作，否则不执行。由于交叉操作，可能会产生“教室冲其具体操作过程是：假设种群个体为M，且为偶数。将种群中的个体一一配对，本文采用的是1号个体-2号个体,3号个体-4个体，……，M-1号个体-M号个体；随机产生一个浮点数0-P小于PC行；要交换的行，交换该行的数据；冲突检测和消除。变异操作[19]。针对排课问题，由于在排课时极易产生冲突，不能使用一般的PM，随机产生一个随机浮点数（0-P小于P设置控制参数M、交叉率PC、变异率PMT种群大小M种群大小M表示种群中的个体总数。当MM取值过大时，会降低算法运行速度。一般M的取值范围是20-100，本文M取值为40。交叉率PC交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率一般较大[19]。但交叉率过大，会破坏群体中的优势个体，影响运算性能；取值过小，产生新个体的速度又慢。一般取值范围为0.4-0.99，经过测试，本文取值为0.4。变异率PM变异操作主要是为了抑制早熟和改善遗传算法的局部搜索能力，若取值过取值范围为0.0001-0.1。经过测试，本文取值为0.03。终止代数T终止代数T是表示运行结束条件的一个参数。当遗传算法运行到指定进化代数，则终止，输出当前群体中的最优个体做为最优解。一般建议取值范围是100-500[19]。本文取值为200。冲突的检测与消除教室类型冲突、教室大小冲突。虽然在编码过程中已经解决了个体初始化时可能产生的以上列举的各种冲在种群初始化时，本文采用了教师时间类（TeacherTime）和教室时间类（RoomTime）这两个类来记录教室和教师资源的利用情况。而且这两个类也是（一）交叉过程中冲突检测和消除取出第二个个体的交叉行的课程表的基因列表，填入第一个个体的交叉0-20至在该时间片，未分配课程，且教师和教室均可用，则填充该时间片。继续填充，重复2，直至基因列表全部填入第一个个体的交叉行中。利用相同的方法，交换第二个个体中这个班级的课程表。（二）变异过程中冲突检测和消除0-20的时间片，继续检测，直至不会发生冲突，则交换。（三）一般的冲突检测首先读取二维数组（课程表）第一行第一列的基因编码；2测。开始读取二维数组第一行第二列的基因编码，重复2、3一般的冲突检测，主要运用在手工排课的过程中。4.3本章小结决排课问题。排课系统实现与测试第五章排课系统实现与测试登录模块实现与测试本系统主要有三种用户，分别为：系统管理员、教师、和学生。登录子系统的主要功能是根据不同的用户类型登录到不同的用户界面中去，并记录用户的登录状态。JSPModel2login.jsp时，输入表单，并将表单提交给一个专门处理登录信息的Servlet—LoginServlet面；若用户提交的用户名和密码不正确，则返回到登录界面。测试结果，如图所示：图5.1系统登录界面图5.2管理员登录后系统首页27排课系统实现与测试图5.3教师/学生登录后系统首页基本信息管理模块实现与测试5.4所示：查询结果分页显示

图5.4院系信息图显示。本系统中主要使用的自定义标签有：DeptPageTagProPageTag、28排课系统实现与测试需在JSP页面中插入自定义标签，即可输出内容，例如：<taglib:deptPagepageSize="10"></taglib:deptPage>。手动排课模块实现与测试产生冲突。基本处理流程是：用户通过表单提交需要插入的课表记录，提交给一个ServletServlet调用业务逻辑层的方法，从数据库中读取课程表，构造课程表若没有发生冲突，则插入该课程记录。测试结果,如图5.5、图5.6、图5.7、图5.8所示：图5.5选择班级界面截图图5.6插入班级课程表界面截图29排课系统实现与测试图5.7插入课程记录界面截图图5.8 插入结果界面截图自动排课模块实现与测试以在第四章详尽介绍过，此处不再赘述。自动排课界面，如图5.9所示：图5.9自动排课界面中。然后，跳转到课表查询界面。课表查询模块实现实现与测试由于本系统的用户为三类：系统管理员、教师、和学