信息系统毕业论文--学分制体系下排课系统模型的研究.doc

装订线安徽工业大学管理科学与工程学院 学分制体系下排课系统模型的研究安徽工业大学毕业设计(论文)任务书课题名称学分制体系下课程编排模型研究学 院 管理科学与工程学院专业班级工051班姓 名学 号课题工作内容及基本要求:1课题目的：通过对学分制下课程安排分析，研究其相关因子及流程，建立学分制体系下课程编排模型，以达到专业综合训练的目的； 2应用文献资料：学习课题相关的编程技术和专业知识，查阅不少于10篇的参考文献，其中外文资料不少于2篇； 3方案论证(综述)：通过对教务处实际课程编排情况调查，收集资料，拟订一份切实可行的研究方案； 4方法手段：综合应用运筹学、C/S及数据库技术，设计相关的库、表，完成算法设计及代码编写、系统测试； 5毕业论文：严格遵照“毕业设计（论文）说明书的撰写内容和规范”的规定，采用A4打印纸，完成正文不少于2.5万字的毕业论文1份，中文摘要（500字以内）及相应的英文摘要，完成3张A3CAD图纸； 6外语要求：将一篇不少于20000外文字符的资料翻译成汉语； 7计算机要求：熟悉VB等C/S开发工具及SQL SEREVR数据库。起止时间：2009年2月16日至2009年6月14日共17周指 导 教 师签 字系 主 任签 字院 长签 字中文摘要排课的问题是指针对于每一课程给予一个时段和教室，它是涉及班级、教师、教室等因素的决策优化问题，也是组合规划中的典型问题。本文借鉴以往的基于贪心算法和优先级算法的成功排课经验研究的系统，对学期课表的教师、教室、学生三大冲突进行了全面的分析，运用冲突搜索及冲突判断方案获得冲突的数据，然后给出了一个学期课表编排中出现的冲突数据分析及改进方案，最后，给任务书手动调整课表中冲突。冲突检测需满足一下需求：检测“一师多课”冲突情况，即一位教师在同一时间内排了一门以上的课；“一室多课”冲突情况，即一个教室在同一时间内排了一门以上的课；“一班多课”冲突情况，即一个班级在同一时间内排了一门以上的课。关键字：排课；学分制；冲突判断；数据分析ABSTRACT Timetable of the problem is that indicators for each course and the classroom to give a period, which is involved in classes, teachers, classrooms and other factors to optimize the decision-making, but also a typical portfolio planning issues. This article from the past and priority-based greedy algorithm algorithm-level empirical studies of successful systems Timetable for semester schedule of teachers, classrooms, the students to conduct a comprehensive conflict analysis, the use of conflict and conflict search program to determine the data conflict, and then given one semester in the school timetable scheduling conflicts and improve data analysis program, finally, to schedule tasks manually adjust the book in the conflict. Detection of conflict need to satisfy the demand: solve the one more class division in conflict situations, that is, a teacher at the same time more than one row of the class. One more class room in conflict situations, that is, a classroom at the same time more than one row of the class. A group of multi-class in conflict situations, that is, a class at the same time more than one row of the class.Keywords: Timetable; Credit System; conflicts judge; data analysis目录1.绪论11.1学分制排课问题的提出11.2学分制排课问题分析11.3课题的现状31.4课题算法及比较41.5课题开发工具52需求分析62.1课题研究目的62.2系统功能要求63系统分析83.1 课题开发环境与开发模式83.2 可行性分析与调查83.3管理流程分析93.4 数据流程分析113.4.1数据流程图123.4.2数据组织分析154模型建立164.1排课模型研究164.2模型中相关因素分析164.3基于优先级的排课184.3.1排课的预处理184.3.2排课处理194.4排课系统中冲突问题的分析和研究194.5冲突的搜索判断和预处理204.5.1合理确定课程的编排顺序204.5.2时间模式与教室的选择原则214.5.3时间与学分的分配原则224.5.4排课中的冲突解决策略235.系统总体设计245.1排课系统中冲突检测相关数据分析245.2 排课系统中冲突的检测255.3排课结果及分析295.4冲突检测对排课的意义及改进316.系统的进一步研究与思考346.1系统的不足346.2系统的展望34结束语36致谢37主要参考文献381.绪论1.1学分制排课问题的提出学分制是我国高校近年来已普遍实行的一种教学管理制度，它的推行可以明显的提高教学质量，它能够利用高校自身所拥有的办学优势和教学资源条件实施因材施教，大大增强了高校办学的活力，同时学分制的推行它能够尊重学生的个体差异，可以实现学生的自主学习、科学化学习，是培养高素质、具有创新精神和自学实践能力的高素质大学生的有力保障。选课制是学分制的核心制度，选课制允许学生在学校规定的范围内自主选择，包括选择课程、选择教师、选择上课时间，在一定条件下可以选择专业；自主安排学习进程；还可以通过辅修另一专业，跨学院跨专业辅修课程来完善自己的知识结构1。随着我国高校招生规模的扩大，学科种类、学校专业数、学生人数也都逐年增加，但教学资源（教师、教室、上课时间段）还是相对的紧张，手工排课已难以完成高校课表的编排。另外，由于随着教学改革的进行，学生的自由选课以成为高校实行学分制教学的一个重要的方面，这就对教学资源提出了更高的要求。其次，在学分制下，高校的教学过程已逐步演化为一个供需求过程，高校教学部门，常以教务处、各学院为主，将各系和授课部门的课程申请进行汇总，他们为学生提供所需的课程，而学生主要根据自己的发展需要选择所需要学习的课程。传统的学年制排课及以“班级”为单位的排课方式已经不能适应学分制下的以课程为中心的教学模式，这不仅限制了学生的选课自由，还不能充分利用学校的优质教学资源，传统的排课由各学院教研室根据当年的学期培养计划安排相应的教师任教，老师被分配到班级上课，有可能造成师生都不满意的情况。另外结合安徽工业大学的教学课程开课安排，编排规模大、涉及因素多、结构复杂等因素，人工的对课程进行时间和空间的组合会耗用大量的时间和精力，成为一个繁重的让人头痛的教学管理工作，因此我们必须研究和开发能有效的学分制下高校的计算机排课系统。1.2学分制排课问题分析学分制下的排课问题有如下特点1：课程授课对象可以是一个专业，也可以是不同专业的组合，同一个教师可以讲授多门不同的课程，每次授课节次为连续的2节，学生上课的教室不固定。排课是将教师与学生在上课时间和上课地点上根据不同的约束条件进行排列组合和统筹规划,简化数学模型可概括为一个资源分配的模型，排课过程最基本的要求是避免冲突现象的发生包括学生冲突、教师冲突、教室冲突，结合我校的实际情况还存在着跨校区的冲突。在课表中,上课时间、上课地点以及授课教师是主要变量,其中授课教师是确定型的变量而上课时间、上课地点则是我们求解的对象。对其进行仔细分析，其简化数学模型均可概括为一个资源分配模型，即将某种定量资源分配给不同的需求个体，并同时满足一定的约束条件，是属于运筹学范畴。下面讨论该数学模型的几个要素:1.需求集 由于资源总量是有限的，故需求集合中包含的元素个数也应是有限的。每个元素具有一系列特征。正是这些特征使不同的需求个体相互区别。对于具体的排课问题而言，需求集合中的元素就是需要安排时间与地点的课程，其特征有课程名称，上课人数，授课教师等等。2.资源集 资源的总数是有限的。其不同资源也是可以互相区分的。排课的问题就是要求在避免冲突的情况下，能实现课表的优化组合。一般来说，排课要满足一下的条件：（1）必须满足的硬约束条件 教师不冲突，同一位教师在同一时间只能带一门课程； 学生不冲突，同一个学生不能在同一个时间安排两门课程； 教室不冲突，同一个时间不能安排两门或两门以上的课程； 同一时间安排的课程总数不能大于所提供的教室总数； 资源限制，教师可用时段有限，教室资源有限； 学时要求，每门课必须达到规定的学时 (学分)要求，不同的学分每周排的次数不同； 具备“相同课程排在相同的时间”的特点；合班课程不冲突，合班的专业必须同时能参加合班课程；某一课程参加学习的总人数不应大于所安排教室的座位数。（2）尽量予以满足的软约束条件，使课表更为人性化： 时段要求：根据课程特点和学时要求，不同课程的时段要求不同。例如 =5学分的课程尽量排上午，选修课尽量排下午；体育课须安排在上午3、4节课或下午3、4节课； 教师课表的连续性要求：大多数教师希望集中、连续授课，因此每天每个教师授课节次应尽量紧凑,中间无空课时； 班级课表的分散性要求：考虑到学生的接受度，学生的课表应尽量平均分散在每周的五天；班级上课地点尽可能相邻较近，尽量在同一校区。（3）根据排课经验和我们学校的实际情况，我们对排课问题做以下假设和简化 教室资源足够，可用教室资源通常远远大于教师和可用时段，在排课算法设计中暂不考虑教室资源； 将每天的13节课分为 5个时段，周学时大于4的课程尽量不排在相邻两天； 不考虑学生课表的分散度要求。由于选课制度的实行，学生可以一定程度上自主调节学习计划和课表，因此，学生每周的课时数大致是均匀分散的；对于一门课程，尤其是专业课程来说，并不是所有的班级都会选修，而只是由同一专业或相关专业的班级来选修。即使是同一专业的学生，也不会四个年级同时选修同一门课程。所以，针对课程设置的这种特点，将每一学期的所有课程按照年级进行等价类的划分，将凡是有共同参与者的课程划分在同一等价类中。这样，在每个等价类中的课程之间只存在地点上的冲突，而没有时间上的冲突。根据以上分析，我们要解决的课表问题可以描述为：将课程号、教师、专业、学分、计划开课人数、时间段和教室按照上述的约束条件安排上课时间和上课教室。1.3课题的现状近几年，国内外一直就有人开始研究课表编排问题。1962年，Gotlieb曾提出了一个课表问题的数学模型，并利用匈牙利算法解决了三维线性运输问题。次后，人们对课表问题的算法、解的存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是Gotlieb的数学模型的简化或补充，而至今还没有一个可行的算法来解决课表问题。近40年来，人们对课表问题的计算机解法做了许多尝试。其中，课表编排的整数规划模型将问题归结为求一组0-1变量的解，但是其计算量非常大。解决0-1线性优化问题的分支一定界技术却只适用也规模较小的课表编排，Mihoc和Balas（1965）将课表公式化为一个优化问题，Krawczk则提出一种线性编程的方法。Junginger将课表问题简化为三维运输问题，而Tripathy则把课表问题视作整数线性编程问题并提出了大学课表的数学模型。此外，有些文献试图从图论的角度来求解排课表的问题，但是图的染色问题也是NP完全问题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题，这样的数学模型与实际相差太远，所以对于大多数学校的课表编排问题来说没有实用价值。进入九十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度的Vastapur大学管理学院的ArabindaTripathy、加拿大Montreal大学的Jean Aubin和Jacques Ferland等。目前，解决课表方法的问题有：模拟手工排课法，图论方法，拉格朗日法，二次分配型法等多种方法。由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈增大，这已经成为应用数学编程解决课表问题的巨大障碍。国外的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有希望得到成功的办法。在国内，对课表问题的研究开始于80年代初期、具有代表性的有：南京工学院的UTSS（A University Timetable Scheduling System）系统，清华大学的TISER（Timetable SchedulER）系统，大连理工大学的智能教学组织管理与课程调度等，这些系统大多数都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。但是这些系统课表编排系统往往比较依赖于各个学校的教学体制，不宜进行大量推广。从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人意。一方面原因是作为一个很复杂的系统，排课要想面面俱到是一件很困难的事；另一方面每个学校由于其各自的特殊性，自动排课软件很难普遍实用，特别是在调度的过程中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大变动，在实际的应用中这是很难实现的事。1.4课题算法及比较编排课表是每所高校在新学期开始之前必须进行的工作其实质就是为包括开课教师以及各年级各专业学生的各个教学活动安排一组适当的教学时间与空间，从而使整个教学活动能够有计划有秩序地运行。大学课表的编排规模大、涉及因素多结构复杂，历来要耗费大量的时间和精力，是一项繁重的教务管理工作。在相当长的时间里，排课工作不得不由人工进行，一般是由富有经验的排课专家集中数周的时间进行编排，协调出现的各种矛盾，并反复检查修订，直到符合要求为止。但人工排课虽然思维清晰但很难做到整体优化。采用计算机模拟人工排课的关键也是难点的是能够模拟人工排课的思维对整个课表进行优化处理，要让计算机懂得人的思维，必须通过数学语言程序化赋予计算机，但排课问题是一个NP完全性问题1，目前还没有一个更好的算法能够解决。现在常用的方法有：分组优化决策算法、遗传算法、回溯算法、动态规划法等相对比较好解决这个问题的算法。遗传算法2是根据生物染色体自然进化的模型，它仿照染色体的基因在进化的过程中进行选择、交叉、变异生成下一代种群。计算开始时对种群进行初始化，并计算每一个个体的适应度函数，生成第一代。如果生成的种群不满足优化条件，则按照适应度选择个体，父代进行交叉或变异生成子代。然后子代取代父代，再生成下一个子代。这一过程循环执行，直到满足优化准则为止。回溯是一种优选搜索法3。它按选优条件向前搜索，以达到目标，但当搜索到某一步时，发现原先的选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态点称之为回溯点。具体到计算机智能排课系统中，选优条件即为排课数学模型中的约束条件群。换而言之，若不满足约束条件群，该选择即为不优或达不到目标。当遍历该步骤的所有可能仍未满足约束条件群，则该状态满足了回溯条件，该状态点即为回溯点。分组优化算法决策1按照难易等级进行逐批排课，在待排的课程集合中选择排课难度大的课程组进行优先排。在对此课程组进行排课时，先搜索本课程组的课程在当前的约束条件下依据优化方法决策出其上课时间和上课地点。优化决策过程遵循的原则是这种搜索出的时间和地点对与本课程组相关的课程在后续排课时不产生影响或产生的影响最小。选课制下排课，我们可以探索以课程_专业数的大小顺序替代难易等级进行分组优化决策排课。利用计算机程序的反复验算功能（验算式的确定很重要，因为它可以作为优化过程结束的边界条件），不断地对整体课表进行优化。动态规划法4是将求解的问题一层一层地分解成一级一级、规模逐步缩小的子问题，直到可以直接求出其解的子问题为止。分解成的所有子问题按层次关系构成一颗子问题树。树根是原问题。原问题的解依赖于子问题树中所有子问题的解。动态规划算法通常用于求一个问题在某种意义下的最优解。设计一个动态规划算法，通常可按以下几个步骤进行：1.分析最优解的性质，并规划其结构特征。2.递归的定义最优解。3.以自底向上的方式计算出最优解。4.根据计算最优解时得到的信息，构造一个最优解。步骤14是动态规划算法的基本步骤。在只需要求出最优解的情形，步骤4可以省去。若需要求出问题的一个最优解，则必须执行步骤4。此时，在步骤3中计算最优解时，通常需记录更多的信息，以便在步骤4中，根据所记录的信息，快速地构造出一个最优解。1.5课题开发工具排课系统主要分成自动排课、冲突检测、手工调整三个部分，自动排课系统采用客户机/服务器（C/S）模式，运用了基于Visual Basic语言，以SQLServer数据库作为后台数据库。冲突检测是基于存取排好的选课课程表的Microsoft Excel的中的VBA语言进行程序编写的检测。而自动排课后的手工调整系统采用浏览器/服务器（B/S）模式，运用了基于ASP语言中的VBScript技术，以SQLServer数据库作为后台数据库，使用Dreamweaver开发前台页面，实现了排课系统，提高了排课系统的效率，优化了页面。基于以上的分析，安徽工业大学排课系统采用的开发工具及运行环境是：1.Visual Basic开发语言；2.集成应用程序共享一种通用的自动化语言VBA语言；3.采用Microsoft Excel作为运行界面的基础；4.以Windows 2000或Windows XP为平台；5.客户端运行环境采用Windows系列操作系统2需求分析2.1课题研究目的学分制选课的根本出发点就是提供给学生更多的选择空间，从排课上讲就是提供给学生更加灵活多样化的课表，让学生能够合理安排自己的上课时间和生活节奏。从数学上分析，排课过程可以看作是：在给定的约束条件下，求优化解的过程。约束条件越多，解的范围就越小，学生选课的自由度就受到限制。学分制排课就要求系统能够结合学校的实际情况，按照排课的一般原则，根据教学计划、教师、教室和学生等资源，通过解决他们之间的种种冲突，根据教师信息、学校的各专业的开课信息、教室等具体资源，由计算机自动生成一套适应学校、教师、学生等各个方面要求的排课结果信息，省却了以往教务人员排课的繁琐、费时、不科学的种种弊端，以实现教学资源（教师、教室、教学设备等）的充分合理运用。为了使排课系统更加完善，通过对自动排课后的课程进行手工调整改动，以解决自动排课中不能满足一些特殊课程，例如体育课等不需要占用教室，增加课程、删除课程和修改课程时，就需要运用手工调整进行修改。随着校园数字网的发展，和学校的人数增加，在客观上要求提高管理水平，提高工作效率，注重学生素质修养、加强通识教育、优化课程体系,培养复合型人才等特点,扩大学生学习自主权,实行因材施教,激发教学工作的活力,深化教学改革,提高人才培养质量。该系统实现的目标有：1.信息在各部门之间实现完全共享，减少重复劳动，提高工作效率；2.操作员的工作变得快速并且准确；3.操作简单，界面友好；4.能够快速的了解课程排课现状；5.系统维护方便，有一定的安全性；6.能够突出显示冲突。2.2系统功能要求熟悉排课系统的设计思路、实现过程和实现方法，对系统所需的资源：部门、课程、教室有着充分的调研，部门分类：学校里包含的多个系，每个系又分为多个专业；课程的分类：包括基础课、专业基础课、专业课和公共课、选修课；教室分类：普通教室、阶梯教室。再从系统面向的用户考虑，了解不同用户的需求，从而分析出系统应具备的功能。排课系统的需求及排课设计中需要做到以下几个方面：1.预排课功能 由于存在公共基础课以及选修课，应该预先设置。2.自动排课功能 根据输入的基本信息，进行自动排课，生成课表。在自动排课完成后，将排课异常信息给予反馈。3.手动调节功能 完全依赖自动排课排出的课表不能完全符合客观需求，同时我们在算法及优先级确定的精确度方面的水平也有限，因此，应该增加手动调节功能，以进一步确保合理性。4.冲突检测 主要是针对手动预排课和手动调节功能可能出现的冲突情况，完善手动排课。5.友好性 排课系统与使用者应具有交互性，可以增加排课向导提示用户的使用满足系统的要求应主要有以下模块更能：排课系统系统管理排课管理基本信息管理图2.1排课系统功能模块开课任务书属于教师教师课表课程属于系别机构专业教学楼属于教室周课时分布属于年级图2.2排课系统ER图3系统分析3.1 课题开发环境与开发模式排课系统主要分成自动排课和手工调整两个部分，自动排课系统采用浏览器/服务器（B/S）模式，运用了基于Visual Basic语言，以SQLServer数据库作为后台数据库。而自动排课后的手工调整系统采用客户机/服务器（C/S）模式，运用了基于ASP语言中的VBScript技术，以SQLServer数据库作为后台数据库，使用Dreamweaver开发前台页面，实现了排课系统，提高了排课系统的效率，优化了页面。Visual Basic For Application(VBA)5,可以认为VBA是非常流行的应用程序开发语言VASUAL BASIC 的子集.实际上VBA是寄生于VB应用程序的版本.VBA和VB的区别包括如下几个方面: 1.VB是设计用于创建标准的应用程序，而VBA是使已有的应用程序(EXCEL等)自动化； 2VB具有自己的开发环境，而VBA必须寄生于已有的应用程序； 3要运行VB开发的应用程序，用户不必安装VB，因为VB开发出的应用程序是可执行文件(*.EXE)，而VBA开发的程序必须依赖于它的父应用程序，例如EXCEL，VBA它是一种自动化语言,它可以使常用的程序自动化,可以创建自定义的解决方案。对于Excel VBA应用程序开发有着以下的5个明显的步骤5：1总结操作步骤 记录和总结操作步骤和规律2录制宏 分步骤总结出来的操作，同时用录制宏的方法得到和这些操作步骤相对应的Excel VBA代码3改造代码 对代码的改造需明确3个目标：变量化、简明化、高级化4试验和改进代码 程序编制完成以后，立即运行试验是否能够达到预期的效果。如果成功，紧接着运行第二次5档案化 程序中的一些重要变量和重要语句应用注释语句加以说明SQL Server6数据库技术：SQL Server 2000是Microsoft公司推出的基于Client/Server模式的新一代大型关系数据库管理系统。它功能强大、操作简便，广泛应用于数据库后台系统。SQL Server 2000代表着下一代Microsoft.NET Enterprise Servers（企业分布式服务器）数据库的发展趋势。它在电子商务、数据仓库和数据库解决方案等应用中起着重要的核心作用。 SQL Server 2000无论是从规模上还是从功能上都更优于ACCESS，更适合于做投入实际运营的较大规模的网站的后台数据库。3.2 可行性分析与调查系统分析7是在总体规划的指导下，对系统进行深入详细的调查研究，确定新系统的逻辑模型的过程。系统分析的主要任务是定义或制定新系统应该“做什么”的问题。 1.了解用户需求 详细了解每个业务过程和业务活动的工作流程及信息处理流程，理解用户对信息系统的需求，包括对系统功能、性能方面的需求，对硬件配置、开发周期、开发方式等方面的意向及打算。对这部分工作要求用户配合系统分析人员完成，先由用户提出初步的要求，经系统分析人员对系统的详细调查，进一步完善系统的功能、性能要求，最终以需求说明书的形式将系统需求定义一下来。这部分工作是系统分析的核心、确定系统逻辑模型，形成系统分析报告。 在详细调查的基础上，运用各类系统开发的理论、开发方法和开发技术，确定系统应具有的逻辑功能，再用适当的方法表示出来，形成系统的逻辑模型。新系统的逻辑模型有一系列图表和文字组成，在逻辑上描述新系统的目标和具有的各种功能和性能，且以系统分析报告的形式表达出来，为下一步系统设计提供依据。2.现行系统的调查 现行系统的详细调查7是集中一段时间和人力，通过各种途径做全面、充分和详细的调查，弄清现行系统的边界、组织机构、人员分工、业务流程、各种计划、单据和报表的格式、种类及处理过程、企业资源及约束情况等，为系统开发做好原始资料的准备工作。 详细调查的原则：真实性、全面性、规范性、启发性。 （1）详细调查的内容： 系统的定性调查：定性调查主要是对现有系统的功能进行总结，包括组织结构的调查、管理功能的调查、工作流程的调查、处理特点的调查与系统运行的调查等。 系统的定量调查：定量调查的目的是弄清数据流量的大小、时间分布、发生频率，掌握系统的信息特征，据此确定系统规模，估计系统建设工作量，为下一阶段的系统设计提供科学依据。（2）详细调查的方法： 问卷调查法 召开调查会 调查人员直接参加业务实践 查阅企业的有关资料 由用户的管理人员向开发者介绍情况 其他还有专家调查等方法，可以根据系统调查的具体需要确定调查方法。总的原则是，以了解清楚现状为最终目标。3.3管理流程分析业务流程调查主要任务7是调查系统中各环节的业务活动，掌握业务的内容、作用、及信息的输入、输出、数据存储和信息的处理方法及过程等。它是掌握现行系统状况，确立系统逻辑模型不可缺少的环节。组织结构6，指的是一个组织（部门、科室等）的组成以及这些组成部分之间的隶属关系或管理与被管理的关系。排课模型组织结构图通常可用以下的组织结构图3.1来表示图3.1 排课系统管理组织结构图系统调查过程中，业务流程调查的工作量非常大，需要耐心细致工作，系统开发人员与用户之间联系非常密切，需要彼此间进行良好的沟通，调查中，既要完成好自身工作任务，又要考虑所调查业务与其他业务彼此间的联系。在详细调查的基础上，用一定的图表和文字对现行排课系统进行描述。开发一个新系统应该看作对组织的一种有目的的改造过程，详细了解各级组织的职能和有关人员的工作职责、决策内容对新系统的要求。业务流程的分析应当顺着原系统信息流动的过程逐步进行，通过业务流程图详细描述各环节的处理业务及信息的来龙去脉。业务流程图（transaction flow diagram，简称TFD) 7，就是用一些规定的符号及连线来表示某个具体业务处理过程。业务流程图的绘制基本上按照业务的实际处理步骤和过程绘制，换句话说，就是“文本”用图形 方式来反映实际业务处理过程的“流水账”。分析的内容中排课系统涉及到：1现有的排课系统不合理的业务流程有哪些？ 2不合理的业务流程产生的历史原因是什么？ 3改进措施有哪些？以及改进会涉及到哪些方面知识（包括技术支持）？ 4改进前后对组织的目标的影响有多大？带这些“5W1H”疑问去做流程从而使的排课系统更加完善更加简洁，确定新的排课系统业务流程。画出系统的业务流程图为图3.2图3.2 排课系统业务流程图排课系统的业务流程特点：1全过程完成排课工作，对全校排课工作的质量控制很有帮助。2系统柔性大。只要稍加修改系统的数据库结构就可适合很多高校使用。3系统自动排课与人工调整结合，使得排课工作柔性大。自动排课可保证达到几个基本的最优目标，即保证获得近优解，又可考虑人工的需求，使排课工作更具人性化，可使排课更加优化。4无须人工处理数据，数据处理全部有计算机完成。计算机处理相关数据，相对用户，这些处理是透明的，处理的结果是提供有条理的信息给用户或写入到数据库存放。5查询功能强大。从选课表信息、教室占用信息到教师授课通知书等功能都可以实现。3.4 数据流程分析1确定每门课程的排课顺序，按照排课顺序由高到低依次选取各门课程；2根据课程周学时搜索可安排的上课时间模式，并进行优选，确定各课程的上课时间；3进行教室搜索，确定课程中各课程的上课教室，形成“时间教室”对；4对发生冲突的课程运用冲突解决策略解决冲突；5对无法解决的冲突课程写入冲突课程表，在自动排课后进行手工编排。3.4.1数据流程图数据流程分析7就是把数据在组织或原系统内部的流动情况抽象的独立出来，舍去具体组织机构、信息载体、处理工作、物资、材料等，仅从数据流动过程考察实际的数据处理模式。主要包括对信息的流动、传递、处理与存储的分析、数据、数据流程调查。教师课程表 班级课程表 系院课程表 教室课程表教师要求定义排课规则定义微机自动排课教学场地定义教师课程定义教学计划定义系统编码定义教学计划教师情况教室情况排课规则教师要求系统编码排课明细图3.3系统的逻辑模型数据流图7是组织中信息运动的抽象，是系统逻辑模型的主要形式。数据流图是一种能全面地描述信息系统逻辑模型的主要工具，它可以用少数几种符号综合地反映出信息在系统中的流动、处理和存储情况。数据流图是在对系统调研阶段绘制的业务流程图进行分析的基础上，从系统的科学性、管理的合理性、实际运行的可行性角度出发，将信息处理功能和彼此之间的联系自顶向下逐层分解，从逻辑上精确地描述新系统应具有的数据加工功能、数据输入、数据输出、数据存储及数据来源和去向。通过对系统总体模型的研究及功能模块的研究分析、抽象化，对排课系统的总体情况的分析，我们可以看到数据的来源有从教务处管理员和各学院教学干事输入的数据，也有系统从排课模型数据库中读取的教师信息、教室信息；对于系统数据的输出有输出显示给用户和系统的管理员。由此我们可以将排课的数据流程图显示如下：图3.4排课的数据流程图排课系统第二层数据流程图图3.5排课系统第二层数据流程图排课涉及的数据有教师信息、学生信息、教室(含实验室和场馆)信息、课程信息、学校作息情况。专业、课程、教室三者之间的对应关系在同一时间内与不同时间内的相互关系可用ER图表示图3.6同一时间的E-R图图3.7不同时间内ER图排课涉及的数据有教师信息、学生信息、教室(含实验室和场馆)信息、课程信息、学校作息情况。对于排课中所涉及到的实体关系及相关的联系图可以进行如下表示1教师（教师号，教师姓名，课程名）2课程（课程号，课程名，学分，上课时间，上课地点）3授课对象（系别，学院，年级）4学生上课（课程名，上课时间，上课地点）5教师授课（课程名，授课对象，上课时间，上课地点）课表中的关系模型实例表如下：课程编号课程名称类型学分学时起周末周授课对象容量教师教师号上课时间上课地点校区01014001物理化学D1必修232112冶0875王海川0574三5-6东教一南206(起周:1)东区05324009AutoCAD基础必修2.540110艺0850张海娟2769二1-2 四3-4东教一北309(起周:1)东区图3.8 一个课表实例3.4.2数据组织分析排课系统中，数据库由许多数据表组成，例如:教师表、教室表、班组表、课程表、课组表，这些表并不是孤立的，它们之间有很多的联系，每一门课程对应着一个教师，一门课程可能有很多班级同时上一个课组包括几门课程等。因此对于排课系统的数据，影响排课质量的并有可能产生数据冲突的数据源就包括：教师表、教师表、时间段、课组表。对于数据的冲突数据检测就主要考虑：教师、教室、上课时间、上课教室、课程。教室数据库描述了有关教室号、教室名、教室位置、容纳人数及功能等有关信息,其中教室号由教学楼及编号组成。教师数据库描述了教师号(由教研室,所在系院和序号组成)、教师姓名、职称、学历、学位、年龄、工作时间、专业及授课等信息。课程库信息由课程号、课程名、学时数、学分等组成，因此从数学上讲,排课问题是一个在时间、教师、学生和教室四维空间,以教学计划和各种特殊要求为约束条件的组合规划。为了进行合理的排课我们对课表中的相关数据进行一些规范化的预处理。1授课对象分类在这里我们将具有共同听课对象的任务划分在同一等价类中,在每个等价类之间只存在地点上的冲突,而没有时间上的冲突.然后按照的大小,从大到小进行处理，等价类的划分可以先按年级分,然后再按系别分。2教室分类为了合理使用教室,我们采用了教室分类的办法,以便尽可能在课程编排过程中避免上课人数少的课程盲目强占容量大的教室现象。根据教室的容量再分别对每个教室等价类进行划分:如分为030人、3060人、6090人、90120人、120180人等若干种。依此而决定是否可以根据课程对其进行分班、合班教学。4模型建立4.1排课模型研究排课是将教师与学生在上课时间和上课地点上根据不同的约束条件进行排列组合和统筹规划,简化数学模型可概括为一个资源分配的模型，即将某种定量资源分配给不同的需求个体，且同时满足一定的约束条件。学分制选课的制约因素主要是教学资源数量及配置的制约。教学资源主要包括教师、教学场地、教学设备甚至于排课时间等。教学资源的制约是影响选课制推行的关键。排课过程最基本的要求是避免冲突现象的发生包括学生冲突、教师冲突、教室冲突、和时间冲突，对我校来说还存在着跨校区冲突。在避免冲突的情况下，要实现课表的优化组合。排课问题是典型的组合优化和不确定调度问题，早在70年代就被证明为一个NP完全性问题即此算法的计算时间是呈指数增长的。目前大家对NP 完全问题研究的主要思想是如何降低其计算复杂度，即利用一个近似算法来代替，力争使得解决问题的时间从指数增长化简到多项式增长。结合到课表问题就是建立一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这是解决排课问题一个很多的思路。数学是解决实际问题的有效工具和手段，它是架于数学理论与实际问题之间的桥梁。我们可以用集合论的方法建立课表编排问题的数学模型：设有：T=t1,t2,.,t!表示时间集合；R=r1,r2,.,r表示教室集合；N=(t1,r1),(t1,r2),.,(t1,r),(t2,r1),(t2,r2),.,(t2,r),., t!,r1),(t!,r2),.,(t!,r)=TR表示时间与教室的笛卡尔积，N中的元素称为时间教室对；M=m1,m2,.,m表示课程集合；这样，排课问题就是求课程M到时间教室对N的幂集。结合安徽工业大学的教学管理模式，我校的学分制排课的实施首先是根据专业教学计划生成以“班级课程学时”为表现形式得开课任务表及专业教学培养计划，它把一个专业的学生抽象为一位学生进行排课处理，因此排课时比较容易避免所授课程、上课学生、授课教师在时间、地点上的冲突。4.2模型中相关因素分析从数学上分析，排课过程可以看作是:在给定的约束条件下，求优化解的过程。约束条件越多，解的范围就越小，学生选课的自由度就受到限制。在课表中，上课时间、上课地点以及授课教师是主要变量，其中授课教师是确定型的变量而上课时间、上课地点则是我们求解的对象。一般情况下，教室资源和教师资源是给定的，然后根据教师承担的教学任务来安排任课教师的上课时间及上课地点。如果教室资源相对充足，则主要的是上课时间的确定。为了排出满足学生要求的选课课表，不仅在选择授课教师，而且在选择授课时间上也应该有很大的自由度，因此，时间资源理论上讲越多越好。总体来说排课问题就是针对教学对象，安排所需上课的时间与地点所面临的问题。从管理者的观点而言，目标是希望所有课程都能排到适当的时段和教室，并且尽可能的满足越多的条件限制越好。从教师的观点而言，目标是希望所排课的时间都在自己所喜好的时段中。从学生的观点而言，目标是希望所有的课程都能排在自己所喜欢的时段，并且越少冲堂越好才能更弹性的选课。所以根据对教师、学生的需求了解后，收集了可能影响排课问题的限制式并结合安徽工业大学的教学资源，可以对排课因素进行一下考虑：1. 教室资源 为了满足课程能够有教室资源，在排课中教室的资源的供求应大于课程开课总数，以使每个课程能够有教室开课。2教学计划人数由于学分制下的教学计划人数差异性很大，所以用人数区间来表示。为了使教学计划人数更加直观化，所以把教学计划人数、教室容量和时间安排因素等联系起来，才能表示清楚，在这里暂不考虑。3教师课程安排好了，教师就是课程授课的主要资源。对于教师我们应考虑一些教师的在课表中的属性（教师号、所属学院、） 4时间段安排因素在实际排课过程中，以某一等长的时间段为课表的时间安排单位，称之为时间单元7在考虑排课的时候，必然要排上课时间，那么不可避免的要考虑时间段因素，这也是系统排课中最重要的一个元素，因此如何安排时间段就显的尤其重要了，在一星期中可用的时间段有：一1-2，一3-4，一5-6，一7-8，一9-11二1-2，二3-4，二5-6，二7-8，二9-11三1-2，三3-4，三5-6，三7-8，三9-11四1-2，四3-4，四5-6，四7-8，四9-11五1-2，五3-4，五5-6，五7-8，五9-11六1-2，六3-4，六5-6，六7-8，六9-11日1-2，日3-4，日5-6，日7-8，日9-115课程号因素由于课程存在很大的差异性，由于有些课程存在很大的差异。例如：体育课不需要安排教室，而且上课时间最好安排在周一到周五的上午3-4节课或者下午的7-8节课。例如课程设计课程、实验课程等上课时间虚设，有些课程的教室都是虚设。总之，像这些特殊的课程在安排时间和上课地点时可不在自动排课中考虑可在手工调整中考虑。4.3基于优先级的排课从数学上讲, 排课问题是一个在时间、教师、学生和教室四维空间, 以教学计划和各种特殊要求为约束条件的组合规划问题。其实质就是解决各因素之间的冲突。在设计算法时, 为了降低课程调度的算法复杂性, 我们主要采用了化整为零的思想及优先级算法4.3.1排课的预处理1.等价类的划分将具有共同听课对象的任务划分在同一等价类中, 在每个等价类之间只存在地点上的冲突, 而没有时间上的冲突。 然后按照的大小, 从大到小进行处理。 等价类的划分可以先按年级分, 然后再按系别分。针对我院管理科学与工程系的听课对象等价类的划分：2005级(N1)工业工程(M1)物流工程(M2)信息管理于信息系统(M3)2006级(N2)工业工程(M1)物流工程(M2)信息管理于信息系统(M3)2007级(N3)工业工程(M1)物流工程(M2)信息管理于信息系统(M3)2008级(N4)工业工程(M1)物流工程(M2)信息管理于信息系统(M3)先按年级分为四个类: 2005级(N 1) , 2006级(N 2) ,2007 级(N 3) ,2008 级(N 4) , 而对每一个等价类N 1、N 2、N 3、N 4 又可以按专业分为若干个子类, 然后对每个子类分别进行排课处理,由于高年级专业课具有学院唯一性我们可以优先考虑排课，这样做就可以大大降低算法的复杂性。2教室分类为了合理使用教室, 我们采用了教室分类的办法, 以便尽可能在课程编排过程中避免上课人数少的课程盲目强占容量大的教室现象。首先将教室按照其类型分为若干个等价类, 如下所示,然后, 根据教室的容量再分别对每个教室等价类进行划分: 如分为0 30 人、30 60 人、6090 人、90 120 人、120 200 人等若干种。3.时间分类时间模式是根据教务人员的经验, 为各种周学时数不同的课程学分指定的一种时间组合方式（1）对于学分=5的课程我们安排的如下的上课时间段一1-2 三3-4 五1-2；一3-4 三1-2 五3-4二1-2四3-4 五5-6；二3-4四1-2 五3-4一1-2 二3-4四1-2；一3-4二1-2四3-4；二1-2四3-4五1-2（2）对于5学分2.5的课程我们可以安排如下的上课时间段一1-2 三3-4；一3-4 三5-6；一3-4三1-2；