高校排课系统的设计与实现_基于ＵＭＬ的排课系统的设计与实现

　　摘要:本文采用可视化建模工具UML对排课系统进行了分析与设计，提出使用二部图来解决排课中的选课问题，并给出了具体的实现方法。 　　关键词:统一建模语言；选课；二部图
　　
　　近几年来，随着高校扩招，高校在校学生人数急剧增加，而相应的教育资源增长缓慢，教务管理自动化是亟待解决的问题。而教务工作中比较难处理的一项就是每学期的课表排定工作。由于教师、教室和设备相对紧张，如何合理地安排和分配，从而充分利用教学资源是要研究的问题。利用信息化来改造传统的教学管理模式,这是一个重要途径。
　　课程表问题,是典型的组合优化和不确定性调度问题,是解决对时间和空间资源争夺而引起的冲突。20 世纪50 年代末, 国外有人开始研究课表编排问题;1962 年, Gotlieb 曾提出一个课表问题的数学模型, 并用匈牙利算法解决了三维线性运输问题; 20 世纪70年代中期, 美国人S.Even 等论证了课表问题是NP 完全问题。进入20 世纪90 年代后, 国外对课表问题的研究仍然十分活跃, 比较有代表性的有印度Vastapur大学管理学院的Arabinda Tripathy, 加拿大Montreal大学的Jean Aubin 和Jacques Ferland 等。
　　1 UML和二部图
　　
　　1.1 UML简介
　　统一建模语言UML(Unified modeling language)从1997年11月正式诞生以来，凭借定义良好、易于表达、功能强大和普遍适用等优点迅速取代Booch、OMT、Fusion等面向对象分析和设计的强有力的可视化建模工具。它由9种图表组成。UML的2.0版在不久前被OMG批准为新的标准。常用的支持UML的建模工具有RationalROSE、Visio 2002。UML进行需求分析时主要使用3类模型。①功能模型:从用户角度描述系统的功能，即系统应该“做什么”，用用例图来表示。②静态模型:描述系统的静态结构，即在功能模型中描述的功能“由谁来完成”，主要描述类(或对象)之间的关系属性和操作，用类图和对象图表示。③动态模型:描述问题的暂时的、行为的控制特征，即描述上述定义的功能“如何完成”，“什么时间完成”，包括对象的事件序列、状态和操作，主要用顺序图、合作图、状态图和活动图来表示。其中功能(用例)模型是系统的核心，它驱动着其他模型的开发。
　　1.2 二部图
　　二部图是较特殊的无向图。若无向图G 的顶点集V 可划分成两个子集V 1 和V 2 (满足V 1∪V 2= V 且V 1∩V 2= 5 ) , 使图中每一条边的一个端点在V 1 中, 另一个在V 2 中, 则称G为二部图。实际应用中, 点集V 1 和V 2 可视为具有分工或分配等性质的对象, 边集可视为对象间的关系或联系。
　　2 排课系统地分析与设计
　　作为一个排课系统，主要有两种用户：教师和管理人员。对于教师来说，可以选课和查看课程安排；对于管理人员来说，管理课程信息，管理教师信息以及进行排课。系统的用例描述如图1所示：
　　给每一门课程选择适合的老师是排课系统中最为重要的问题，那么如何做才能使得所有的老师的满意度最大？这个问题是选课系统中必须解决的问题。众所周知，在排课的过程中必须遵守很多的规则，例如：每位老师的工作量应控制在一个范围内；每一个老师的专业课应控制在1~2门；对于不同专业的统一门课程应该指定不同的老师等，正是由于诸如此类的众多规则才使得排课问题变得更加复杂，因此，如何更好地解决这样的问题是每一个管理人员都应该思考的问题，因为排好课是提高教学质量最为重要的一环，也是促进教师不断提升自我的重要因素。本文使用二部图来解决选课问题。具体的方法如下：
　　1) 列出所有的上课老师及课程。选课问题主要涉及到两个方面：教师和课程；列出排课需要满足条件，例如：对于名称相同而专业不同的课程规定要有不同的老师来上；那么这门课程在排课时应作为两门课；或者由于同一专业的同一门课程工作量太大需要两名老师来上，那么这门课在进行排课时也应看作是两门。按照指定的规则对课程进行相关的处理并列出处理后的课程及要上课的老师。
　　2)老师按照自己的喜好在所列出的课程中选择一到二门专业课，并给出所选课程的权值w1；
　　3)管理人员根据以前的课程安排及老师的专业特点，给上这门课的老师一个权值w2；
　　4)构造二部图；根据老师的选课进行连线，并给定一个权值W=w1*w2
　　5)在该二部图中进行搜索，找出最优匹配。最优的匹配就是所有老师的满意度最大或所有的可成都找到了最合适的老师。在此，选用所有的课程都找到合适的老师作为最优匹配的标准，因此，最优匹配即为所有课程的权值之和最大，由于图中的最大权值算法是一个NP问题，所以本文采用贪心算法来求近似解。那么所有课程的权值之和最大即为每一门课程的权值最大，所以将权值最大的老师作为该门课程的授课教师。当然在这个问题中还存在如果有一门课没有人选问题，对于这些课程，按照管理人员指定的老师进行连线，并且权值为w2，这样就可以保证没有所有的课程度有合适的老师。然后对所有的老师所要授的课进行统计，对于超过或不足工作量的老师及课程进行筛选，然后进行协调。
　　3 结论
　　本文采用UML队排课系统进行了分析和设计，并且提出了用二部图来解决排课中的选课问题，该方法在作者所在学院的选课过程中取得了良好的效果。
　　
　　参考文献
　　[1] 张力昂，屈婉玲译.算法设计.清华大学出版社[M].2007，177~196
　　[2] 梁立，肖飞.免疫排课算法.计算机科学[J] .2006（33）：205~205
　　[3] 王晓东.计算机算法设计与分析（第3版）[M].电子工业出版社.2007
　　[4] 潘金贵，顾铁成等译.算法导论（第2版）. 机械工业出版社[M]，2006，97~102