排课系统的开发和实现.docx
- 文档编号:18349744
- 上传时间:2023-08-15
- 格式:DOCX
- 页数:45
- 大小:341.74KB
排课系统的开发和实现.docx
《排课系统的开发和实现.docx》由会员分享,可在线阅读,更多相关《排课系统的开发和实现.docx(45页珍藏版)》请在冰点文库上搜索。
排课系统的开发和实现
排课系统的开发和实现
摘要
要完成一所大学或者一个学院的课程安排是一件非常复杂的问题,如果用人手工进行安排的话,需要极大的精力和时间。
而在排课的时候,需要考虑的范围,涉及到教师、课程、教室还有班级情况等等。
而在现今的大学排课过程中,整个学校需要考虑的教师,课程信息是成百上千,排课问题由此变为一个异常复杂的组合问题。
所以在现实世界的应用中,排课问题的所有排列组合对于人类来说几乎可以被认为是一个天文数字。
而一个可以被接受的排课方案是一个满足排课所有制约性要求的方案。
在此基础上,如果有人希望能通过一些启发性的设定而得到一个更为优化(更为合理,美观,更为符合人的习惯)的排课方案的话,则这个问题就会变得超乎寻常的困难。
所以迄今为止,为了能够用计算机自动完成排课任务已经进行了非常多的尝试。
排课的本质问题是将大量的课程安排进有限的上课时间和教室中,与此同时还会涉及到
任课老师和学生班级等各种因素互相制约的影响。
通常来说,排课中涉及的变量越多,则排课问题就会越复杂。
而本课题的排课研究涉及的排课环境是上海交通大学的网络学院。
网络学院的排课是排课问题中的一个全新的领域。
因为,在网络学院中,教室有了多媒体,视听等各种新的属性,而这在传统的排课问题中是没有的。
而且,网络学院的上课时间也更具多样性。
不同的专业,有的每天上午最多只能排4节课,而有的专业却可以安排5节课。
时间标准的多样性,教室属性的多样性,使得网络学院的排课问题需要考虑更多的因素,从而给排课提出了更高的要求。
本文所做的研究工作先是比较了一下当今比较流行的集中排课算法,如线性算法、遗传算法、限制逻辑(CLP)编程等等算法各自的优缺点和适用性。
并且,在此基础上,本文针对网络学院排课更为特殊的要求,提出了一个新的算法。
最终,基于本文所提出的这个算法,开发出了一个全新的排课模型,使其不但能适应普通的排课环境,还能够很好地满足网络学院更为特殊的排课要求。
关键词:
远程教育,排课,人工智能,遗传算法,限制逻辑编程
THECONSTRUCTIONOFTIMETABLESFORSCHOOLCOURSES
Abstract
Theconstructionoftimetablesforuniversitiesorschoolsisanextremelycomplexproblem,whosemanualsolutionrequiresmucheffort.Thesetofallpossiblesolutions,thatisthespaceoftheproblem,isverylarge,atleastintherealworldexamples.Anacceptablesolutionisonewhosatisfiesalltheproblemconstraints.Theproblemgoesevenmoredifficultifsomeonewantstogenerateanoptimumtimetableaccordingtosomeheuristiccriteria.Variousattemptshavebeenmadesofarontheautomaticsolvingofthetimetablingproblembyacomputer.
Thecourse-timetablingproblemessentiallyinvolvestheassignmentofweeklylecturestotimeperiodsandlecturerooms.Andgenerallyspeaking,themorevariablethetimetablinghas,themorecomplexitis.Becausetherearequitealotofversionsofthetimetablingproblem,differingfromoneschooltothenext,wefocusonconstructingcoursetimetablesatourownlong-learningschool.
ThetimetablingforournetworkschoolisabrandnewintheTTParea.Inthisproblem,theclassroomshaveattributessuchasMultimedia,Videothatweneverencounteredbefore.Someobstacleslikethatmakethetimetablingforthenetworkschoolamorecomplexproblemandbringalotofnewchallenges.
Inthispaper,somepopularTTPalgorithmssuchasLinear,geneticalgorithmshavebeenintroduced.Andaccordingtotheespeciallyhighdemandofthenetworkschool,thepaperbringsanewalgorithmandaccomplishedanewtimetablingsystem.Itnotonlymeetsthedemandofordinarytimetablingproblem,butalsosatisfiesthenetworkschool’sespeciallycomplicatedstandard.
Keywords:
Distance-Learning,timetabling,ArtificialIntelligence,geneticalgorithms,evolutionaryalgorithms,ConstraintLogicProgramming(CLP)
目录
第一章绪论5
§1.1网络教育特点和发展现状5
§1.2本课题的研究背景6
§1.3本课题的研究目标7
§1.4本课题研究应解决的主要问题7
第二章排课问题的理论介绍7
§2.1排课问题的诞生7
§2.2目前排课问题的几个普遍的算法8
§2.2.1SimulatedAnnealing9
§2.2.2ConstraintLogicProgramming10
§2.2.3GraphicColoringHeuristics11
§2.2.4GeneticAlgorithms12
§2.2.5LinearProgramming12
§2.3小结12
第三章排课问题的要求13
§3.1对本排课系统的要求13
§3.1目标13
§3.2排课的基本情况13
§3.2.1教学任务的划分13
§3.2.2不同教学任务教学时间的安排13
§3.2.3排课中按照课程重要性的划分14
§3.2.4关于排课时间的概念14
§3.2.5关于中同一门课程的持续时间的安排14
§3.3排课过程中遇到的各种条件和限制14
§3.3.1排课系统必须满足的条件(hardconstraints)15
§3.3.2排课系统会尽量争取满足的条件(softconstraints)16
§3.4小结16
第四章本课题所做排课系统的实现17
§4.1本排课系统的排课过程17
§4.2本排课系统的实现原理18
§4.2.1开发工具和前期准备18
§4.2.2排课系统的基本思路和算法18
§4.3本排课算法的小结25
第五章本排课系统的使用介绍26
§5.1信息的输入26
§5.1.1教室信息的输入26
§5.1.2班级信息的输入27
§5.1.3课程信息的输入27
§5.1.4教师信息的输入28
§5.2课表的生成29
第六章总结和展望30
§6.1本课题完成的总结30
§6.2对于排课系统的期望30
§6.2.1排课系统的架构31
§6.2.2usecase技术31
§6.2.3COM/DCOM标准对象模型31
致谢33
参考文献与附录:
34
第一章绪论
随着社会科技的不断发展,特别近20年来在信息技术上所取得的革命性进步,我们的生活方式也不可避免的不断地受信息技术影响而改变,其中就包括我们长久以来的学习方式。
有着长久历史的课堂教学模式,由于有着地域(跨地域的不可行性),时间(时间上的不灵活性)以及资源(合格的教师资源和课堂资源的短缺性)已经渐渐难以胜任现代社会日益增长的全民学习和终身学习的要求了。
而与此同时,信息技术,特别是近年来迅速发展的互联网(INTERNET)为我们带来了一个全新的教育理念——远程教育。
§1.1网络教育特点和发展现状
网络教育可以是远程教育的一种模式。
远程教育是指位于不同地点的教师和学生通过通信的方式来完成教学任务。
远程教育的先驱应该是邮件式的函授教育。
通过邮件的函授教育,存在着教育双方的延时非常严重的情况(邮件在两地来回的时间),可谓不是非常的理想。
随着社会技术的不断进步,在上个世纪的二,三十年代出现了基于收音机的广播教育。
然后在上世纪的五,六十年代随着电视的普及,又诞生了电视学校。
不过,无论是广播还是电视,教学中非常重要的交互性(教师和学生之间的及时互动)以及可回溯性(学生在任何时间想要复习一下以前所学的内容)都由于技术的原因没能很好实现。
值得庆幸的是,随着互联网的飞速发展,远程教育的最新形势,通过互联网Internet或是局域网Intranet的网络教育迅速兴起,并且提供了目前为止作为理想的远程教育方式。
目前的对于网络教育的研究差不多集中在以下两个领域:
基于Web的远程教育和实时的远程教育。
在基于Web的方式下,教学内容以课间的形式放在Web服务器上,学习者可以在任意时间任意地点独立地学习,我们称之为以学生为中心的学习模式。
而实时的远程教学则主要利用视频会议系统传输视频和音频,购建一种分布式的教室,在这种环境下,教师和学生只是在物理位置上不同,我们称之为面向教师的学习模式。
在以上两个研究领域中,基于Web的教学模式由于对系统配置无特殊要求,在Internet上应用较为容易。
而实时的远程教学模式,由于对传输视频和音频系统有较高要求,同时还要考虑到主教室和分教室之间互相配合的各种情况,运作较复杂,但是由于交互性更好一点,所以在教学的效果上更甚一筹。
所以,在目前的情况下,两种教学模式互相依存,共同发展。
比如上海交通大学的网络学院教学模式,现在就以实时的远程教学模式为主,基于Web的教学模式为辅。
§1.2本课题的研究背景
为了适应这种网络的教育模式,上海交通大学网络教育学院开发了一个非常集成度非常高的电子教务平台。
这个平台所包括的教务管理内容有
1、排课
2、注册
3、学生基本信息统计
4、成绩管理
5、毕业资格审查
6、证书制作、发放
7、归档
其中,排课的部分又细分为
1、按专业制定教学培养计划(全部课程,包括毕业设计或论文);
2、按专业制定每学期教学执行计划;
3、按开设的课程聘请(落实)上课教师;
4、根据教学执行计划、学生人数、学生选课地点、教师要求及教室等情况排课;
但是,在电子教务系统中,排课的工作目前仍就是由负责排课的教师手工编排。
当学院开设的课程越来越多以后,教师的安排,教室的安排和课程的安排,各种制约条件之间的矛盾会越来越难处理。
用手工编排,费时费力费心,还难免会有顾此失彼的情况发生,所以将排课部分由计算机来完成这一工作变的日益重要。
而纵观目前市面上说流行的各种排课系统软件,不是小学版的,就是中学版的,主要原因是中小学的上课安排规律性很强,每次上课人数由一个班级组成,不需要换教室,没有上下学期课程不同之分,每天上课都为早上4节,下午2-3节的固定时间。
没有晚上要上课的要求,白天也不会有课时空着等等情况出现。
而大学的排课问题就要复杂很多,而且各个大学的教学情况不同,导致对排课的要求也有很大的不一样。
所以,目前适合大学排课的软件市面上比较罕见。
而网络教育学院的排课比起普通的大学排课方式,更要麻烦许多。
比如,网络学院的教室就有多媒体教室,视听教室等等目前普通的大学排课中还没有遇到的问题。
而且,在网络学院的授课中,有时还会出现教师在主教室上课,而通过连线的方式,另外有一部分同学在分教室上课的情况。
至于是否能进行连线上课,除了要考虑教室的容量和学生的数目,还要考虑所授课程是否适合在不同的教室中连线授课,还要考虑教室的性质是否能符合连线上课在技术上的要求。
并且在目前网络学院的教学中,除了普通的本科生教学任务外,还有为了满足社会需求而开设的工程硕士课程,其课程又要求安排在双休日和星期一至星期五的晚上,而且其每个课时的长短,每天上课的课时数又和普通网络学院的本科生有很大不同。
所以由此产生的现实是,市面上无数种软件中没有为网络学院的排课所开发的软件。
因此,作为计算机领域的一个经典课题,本文的研究课题,“排课系统”,作为网络教育学院电子教务平台的一个补充,在这样的背景环境下被提了出来。
§1.3本课题的研究目标
排课系统的本质目标是合理安排一个学期中所有的时段,模块,教室还有教师,使之不互相冲突。
由于教室,时间,教师等资源的有限供应性(limitedavailable),由此就意味着排课系统必须有一些必须满足的制约(hardconstraints),从而才能满足特定的条件。
在满足以上排课的硬性要求要求,如教室的不冲突,教师的不冲突,课程的不冲突的目标以后,还应该尽一切可能满足一些不一定必须满足但最好满足得要求(softconstraints)
比如,将主课尽量的安排在上午等等。
最后,在完成上面这些常规排课的要求上,本课题尚需结合上海交通大学网络教育学院的实际情况,比如因为要通过网络上课,对教室有各种性质的要求,最后能够开发出能够满足本校网络教育排课这一特殊要求的排课程序出来。
§1.4本课题研究应解决的主要问题
(1)排课问题数学模型的建立。
(2)排课问题中各种限制性制约(hardconstraints)条件如何满足。
(3)排课问题中优化条件的如何完成。
(4)由于排课是一个大规模排列组合的问题,所有得可能性非常大,所以如何对搜索的规模进行一定的缩小,也是一个非常重要的问题。
第二章排课问题的理论介绍
§2.1排课问题的诞生
最近的30年来,排课(timetabling)受到了越来越大的关注。
各种关于排课的文献,理论,方法也层出不穷,并且这种趋势仍有继续下去的迹象。
各种关于排课的方法不断更新,很大一部分原因是因为近年来学校教学的方式在不断的改变(比如上海交通大学现在就有了网络教育学院),而排课的方法也必须跟着学校教学方式的改变而不断改变。
每一个学年或是学期,大学的教务管理当局都必须设计出一张全新的课程表,而随着大学教育规模的扩大和教学模式的复杂化,要排出一张理想的课程表成为了一件非常令人头疼的任务。
其中让人倍感困惑的就是在排课中有一系列共享资源(比如教室,教师)的课件(modules)引起互相之间的矛盾或说是制约(Constraints)。
以上海交通大学网络学院为例,每一个课件(modules)通常有两个学时或是三个学时构成。
在排课的时候,若干互相制约的条件必须被考虑到。
比如,不能有两门课(course)在同一时间,在同一教室上课。
或者教室的容量比上这门课的同学数量来的小。
或者,考虑的更远一点,除了这些必须满足的限制性条件外,还会有一些希望满足的优化条件,比如一些比较重要的课程,最好能安排在上午完成。
为了便于管理,同一专业的英语课程最好能安排在同一时间完成。
等等。
还有就是,在某些的固定时段,某些课程的教师会有进修的任务或是开会的任务等等,不一而足。
总之,也就是,在这些时候,这些教师不能上课,或者说,某些班级的某些课程就不能安排在一周中的这些特定时段。
由于,排课问题是一个比较经典的计算机难题,特别是大学的课程。
而我们学校网络学院,由于授课方式的更为灵活,教学手段和途径和传统的授课方式又有所不同,因此,要做这样一个排课的系统就更为困难。
所以,迄今为止,绝大多数的课程表都由人手工完成,除了比较费时费力以外,还比较有可能出现一些前后互相矛盾的地方。
为此,就算排课问题是一个比较困难的问题,针对我们学校网络学院特殊情况的排课系统还是有开发的必要。
通常来说,一张课程表的完成可以分为独立的两个步骤
(1)教学资源的分配,如上课时间,教室,课程等等信息的配置。
具体来讲,就是那个班级要上哪些课程,每个班级的人数,每门课具体的教师的安排,以及这些教师什么时候有空等。
结合到网络学院的特殊情况,还必须考虑到上课的教室有没有一些特殊要求,是否允许几个教室之间连线上课等等。
(2)一个可以接受的课程表的设计实现和完成,所谓可以接受的课程表就是必须满足先前定义各种限制性的条件,而且要比较好的满足各种非强制性的期望条件(优化条件)的课程表。
目前为止来说,由计算机能做的只能是第二个部分的工作,而第一部分的工作通常要排
课的老师输入或决定。
而且就长远来说,第一部分的工作计算机估计永远无法完全的由人来完成。
§2.2目前排课问题的几个普遍的算法
作为计算机领域的一个比较经典的问题,排课算法的研究在国内仍然不是非常普遍。
有关排课算法的相关资料,国内的材料十分的鲜见。
虽然,市面上排课的软件不少,但大多数却是为中,小学开发的,难度也相对较低。
不过,在国际上,有关排课算法的文章相对就较多,而且虽然迄今为止,没有所谓最完美,或者说是最佳的排课算法,但由于所做的研究相当多,所以已经有了较为成熟和理想的排课算法。
以下,就是目前为止,较为常见的几种排课的算法或也可以称之为技术。
§2.2.1SimulatedAnnealing
这个算法名字SimulatedAnnealing[14][20]的中文直译应该是“模拟淬火”算法,不过我没有看到过相关的中文资料,所以决定还是保留其英文的原名比较好。
SimulatedAnnealing(SA)算法被广泛应用于处理各种不同组合优化问题,特别是在学校的排课计划中。
其基本的算法描述如下图所示。
Figure2.1:
TheSimulatedAnnealingAlgorithm
SA算法相对其他的一些全局优化技术有优点也有缺点。
优点之一是非常容易实现,几乎可以应用到任意一个组合优化问题中去,能为大多数问题提供解决方案,并能与专家系统等启发式方法相结合解决一系列复杂的问题。
所以SA是一个比较可靠的技术,不过它的确仍有缺点。
为了得到一个好的结果,升级的过程以及各种可调节变量的选取变的非常重要。
而且,SA技术比较消耗时间,运行的时候速度比较慢。
最显而易见的将排课问题(TimetablingProblem)映射到SimulatedAnnealingAlgorithm的构造如下
1.state是一个包含如下集合的课表:
oP:
教师的集合
oC:
班级的集合
oS:
学生的集合
oR:
教室的集合
oI:
时间段的集合.
2.cost或是E(P,C,S,R,I)定义如下:
oE(P):
是分配超过定额
的课同一位教师所引发冲突的代价,在计划外增加一门或若干门课在教师的计划中所引起的冲突
oE(C):
是将若干门课程安排在同一时间上课引发得不可避免冲突的成本
oE(S):
是将不属于某些学生专业的课程安排的这些学生课表中去所引发的矛盾的成本
oE(R):
是将教室分配给不合适(指容量上)班级而引起冲突的成本
oE(I):
是课时分配过多或过少所引起冲突的成本
3.swap(move)是以下一个或多个班级在集合C中班级
和班级
再考虑到时间段
和
以及教室
和
所做的置换。
一般来讲,每一个步骤就是指这样的一次班级的swapping。
Figure2.2:
Mapping
§2.2.2ConstraintLogicProgramming
ConstraintLogicProgramming(CLP)[2][17]是由LogicProgramming(LP)结合限制系统中的限制操作而成。
从而产生的一种新的语言结合了LP的优点(declarativesemantics,non-determinism,relationalform)与限制解决算法(constraint-solvingalgorithms)的高效率。
由此,这一语言的优势保障用户无需关心搜索的技术,限制的声明是明白无误的而且容易修改和扩展。
在限制逻辑编程的范例中,有关限制满足的问题可以被写成一个Horn子句的形式,也就是各种限制性的条件被包含进子句中。
而当程序运行的时候,各种限制相应产生被传递到限制解决机制中去。
而这一机制应用“域独立”(DomainIndependence)限制满足技术,比如线性程序或者布尔判断等来找到一个可行的解决方案。
所以,这种方法仍旧是基于搜索的,不过可以有效的减少搜索范围。
限制逻辑编程非常适合排课问题。
因为它允许所有的公式将限制明示化。
虽然,这个方法的表现会由于排课中的一些小改动而受到极大影响。
不过经改动多的排课公式仍能很好的满足各种逻辑条件。
而且由于排课问题本质上是一个大规模的组合问题,所以有一个极为庞大的搜索范围。
因此,通过用CLP语言解决这个问题,可以将搜索的范围压缩到一个较小的基础上并能很好的控制住搜索的时间。
§2.2.3GraphicColoringHeuristics
GraphicColoringHeuristics[5]这个算法的基本思想是这样的,假设有S1-S10这是十名学生,他们所选的课程分变为e1-e6中的若干门,如表2.1所示。
Student
Lecture
S1
e1,e2,e3,e6
S2
e1,e2,e3,e5
S3
e1,e2,e3,e5
S4
e1,e2,e5
S5
e4
S6
e4,e5
S7
e2,e4
S8
e2,e4,e6
S9
e3,e4,e6
S10
e3,e4,e6
Table2.1:
ExampleofStudent-LectureData
则我们可将他们之间的这种关系映射到下图所示的关系中去。
由于,学生S1会选择e1,e2,e3和e6这四门课,所以将e1e2,e1e3,e1e6,e2e3,e2e6,e3e6连起。
凡是,同一线段的两端的两门课程就不能在同一时间开设。
Figure2.3:
Graphcoloringforasimpletimetablingproblem
不过,这个算法的用途比较广泛,但有一个比较大的缺点,就是特殊应用的限制(application-specificconstraints)不能很好的整合到这一方法中去。
§2.2.4GeneticAlgorithms
遗传算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 系统 开发 实现