基于遗传算法的排课管理平台的设计与实现

黄新叶　蒋高峰

摘要：本文意在编写一套适用于江苏信息学院的自动排课系统，通过校园网构建一个交流平台来连接教师、学生和教学管理部门。利用并结合J2EE技术、Struts技术、MVC结构设计、SOA技术实现B/S结构的数据信息管理目标；通过对排课算法进行算法分析与算法设计，建立基于遗传算法的排课数学模型。同时利用算法中的各项约束条件和混合编码方法简化排课过程中存在的问题。

关键词：排课；排课管理；遗传算法

中图分类号：G647 文献标志码：A 文章编号：1674-9324（2016）15-0011-02

一、国内外研究动态

（一）背景与意义

排课管理作为教育教学中的重要环节，其目的是为教师、学生安排合适的教学地点与时间。排课管理是教学管理中一项复杂的工作，只有合理安排好了课程时间与地点，才能保障教学工作的有序进行[1]。关于教学排课管理研究已经有近四十多年之久，在理论以及实际应用中都取得了丰硕的成果。然而，现有教学排课管理在面对复杂教学排课环境及大规模教学排课管理时存在的问题至今尚未完全解决，特别是随着各大高校学生的大力扩招，给教学排课管理带来了巨大的压力。在国内，目前教学排课管理采用系统自动排课与人工排课的方式[2]，系统首先进行自动排课，然后找出存在冲突的课程进行人工调整，并根据经验判断将课程安排到合理的位置。由于人工调整缺乏理论指导与数据模型，使教学排课管理具有一定的盲目性，因此需要利用计算机技术与合适的排课算法解决人工干预的问题，这对于推动教学的发展也起到了非常重要的作用[3]。排课管理通过将各个年级开设的课程汇总，然后根据学校全年教学计划任务和教学资源定制各个年级课程表，从而达到优化教学资源的目的，通过设计一个有效的智能排课系统，减轻教学管理工作者的劳动强度，提高教学工作效率，为规范教学管理工作流程提供技术支持，从而保障学校的正常教学秩序。排课管理是非常复杂而烦琐的管理过程，在学校规模大、约束（条件）复杂以及规律不断变化的环境下，目前许多排课软件与排课算法无法满足实际需求，为满足学校排课需求及师生对教学资源利用的要求，规避资源限制等约束条件，本研究对江苏信息学院排课管理进行了研究分析以滿足学院实际排课需求。

（二）国内外研究现状和发展态势

排课问题是教育界非常关心的问题，对于排课问题研究主要集中在理论、启发式搜索技术应用求解、系统求解设计、遗传算法应用求解上。在国外，排课算法起源于20世纪50年代，1963年Gotlieb提出“排课算法数学模型”这一概念，标志着排课算法研究进入了科学的殿堂。自此以后，许多学者也参与到了排课算法研究中，早期的大多数求解都存在诸多问题，无法完全应用于实际生活中，如Ferland、吴金荣等人将排课问题化成整数规划来求解，但这种方法计算量巨大，只能应用到小数据量环境中，无法适用于实际应用中。而何永太和胡顺仁等人则采用图论中的染色问题进行排课研究，由于图论的染色问题本身也是NP完全问题，其计算比较复杂，也只能应用于特殊条件中，因此至今没有一个切实可行的算法。到了20世纪90年代，国外对于排课算法研究非常活跃，提出了一种新的课表编排方法，它以“人”为单位，利用格朗日松弛法及分支定界技术进行排课算法研究。而在我国，对于排课算法的研究却要始于20世纪80年代，从模拟手工排课到运用人工智能，逐步发展，取得了一定的成绩。随着人工智能的发展，开始在排课算法中引入了生物界进化思想和遗传算法，依靠其超强的并行搜索能力和在解决优化问题中表现出来的优势，已经被广泛使用。特别是生物进化思想和遗传思想的出现，出现了基于遗传算法来求解排课问题。本课题就是利用了基于遗传算法进行排课算法设计，并结合J2EE技术、Struts技术、MVC结构设计、SOA技术实现系统开发设计。

二、理论意义及实用价值

随着社会经济的发展，高校规模的扩大增加了教学管理的难度及造成了教学资源的相对紧张，但显然这些学校的师资、教学设备和其他教学资源都不能及时有效地进行补充，所以无法适应教学发展的需求，这其中排课问题就尤为突出。不仅在普通高校出现了以上问题，在高职院校也出现同样的问题。江苏信息职业技术学院经过六十多年的艰苦创业，现有全日制在籍学生共一万多人，学校形成了中高职衔接、职成教一体的办学体系。目前采用的是2004年引进学院的教务排课系统，经过十年的运营，技术已经落后，不能很好地满足日常教学工作的需要。本文也是基于这个原因，意在编写一套适用于江苏信息学院的自动排课系统。

三、目标、研究内容和研究方法

（一）工作目标与任务

结合江苏信息学院的现实，再造教务教学管理的管理流程，使它更加科学化、规范化。据此建立一套教学制管理制度，不但要适合江苏信息学院的现实，还要完成选课排课的信息化与自动化。最后设计一个排课系统，与现有运行的排课系统相比，该系统支持全学分制，这是它最明显的优点。它不仅能够减少各级教学管理人员的工作量，方便检索查询与管理，还能够形成先进的教学理念和管理制度。

（二）研究内容和研究方法

本文主要包括以下工作：重点分析、设计及研究排课管理系统。（1）对目前许多高校的教务管理流程进行重点分析，找出手工排课的主要问题和编制课表的基本原则，分析排课需求。组织学生评价教师及他们所授的课程，最优组合教师和课程，充分做好排课的相关准备工作；（2）从多方面分析系统需求，主要包括系统开发背景、可行性论证、主要业务流程分析、系统功能需求分析、数据模型分析等，确定江苏信息学院排课管理系统实现的必要性及可行性；（3）全面设计系统实现的各个功能模块，确定本排课系统的主要内容：其中包含系统管理、原始数据、教室管理、教学任务管理、排课管理、和课表管理等六大模块。同时，详细设计各个功能模块；（4）利用J2EE技术、Struts技术、MVC结构设计、SOA等技术进行具体的程序开发。同时，在后台数据库方面，选择SQL Server 2008作为管理系统；（5）关于算法研究方面，本排课系统完整讨论了排课问题的主要影响要素、约束条件、以及排课系统中遗传算法的设计及核心算法等问题。

四、关键技术问题

（一）创新之处

首先，对于排课问题的影响要素、主要约束条件、求解目标和难点，本系统进行了完整的讨论，提出了排课问题求解方法的总体框架和技术路线；其次，根据江苏信息学院的实际情况，从排课系统的需求分析开始，建立排课系统的数据模型及其体系结构。给出排课系统中遗传算法的设计，核心算法的实现方法和步骤；最后，说明本排课系统的总体设计方案、各模块的功能结构及相应的实现方法。

（二）拟解决的关键问题

影响排课的因素很多，总结起来分为以下两大类：一是参与教学活动的主体。主要是指教师、班级、课程，教学等主体对象因素，这些因素在每个学期都是可能变动的，是动态的。它们是需要给予分配资源的对象。而在排课过程中，这些主体对象必须在空间和时间上都保证独立，而不是冲突的。在排课过程中，最主要的问题就是解决这些主体对象因素在空间和时间上的冲突；二是教学资源对象因素。主要指被分配的资源，如教室、教学时间等因素，这些资源往往都是有限的。并且教学资源都是分种类的，如教室有大教室、小教室之分，类型有多媒体教室、普通教室、语音室、实验室之分。其他因素还包括教学计划的不同、教师个人的选择喜好等。

五、可行性论证

（一）目标可行性论证

通过校园网构建一个交流平台来连接教师、学生和教学管理部门，利用并结合J2EE技术、Struts技术、MVC结构设计、SOA技术实现B/S结构的数据信息管理目标。

（二）技术可行性论证

软件方面，本系统结合了物联网技术，采用目前最常用的J2EE技术与SQL相结合的模式进行开发，数据库服务器选用Microsoft的SQL Server 2008作为数据库，此数据库能够处理大量的数据，不仅能够保持数据的完整性，而且还能够提供多项高级管理功能。由此可见，系统的软件开发平台条件已经满足。在硬件方面，江苏信息学院计算机容量越来越大，可靠性越来越高，硬件平台完全能够满足系统开发和系统运行的需要。

（三）成本可行性论证

本系统只需花费少量的经费，广大教务管理人员就能从繁重的手工排课工作中解脱出来，他们可以把更多的精力投入到其他教学管理工作中，提高工作效率；同时也可以使广大师生通过校园网查询到相关的个人教学信息，此方式成本低，既方便又经济。

（四）社会可行性论证

目前，江苏信息学院校园网络已经覆盖了整个教学区和学生区，学院各个教学部门、行政部门和广大学生的上网需求都可以满足。尤其是本学院已经通过光纤接入的方式与Internet连接，能够很好地实现校内用户之间以及校内用户与校外用户之间的联系。

综上所述，面对江苏信息学院教务信息处理需求的日益增长，开发一个教务排课管理系统来应对这种需求，为学生和教学管理人员提供快捷方便的双向选择服务，提高排课管理工作的效率，是非常有必要的。

参考文献：

[1]刘真.基于URP的地方高校数字校园建设应用研究[D].山东大学硕士学位论文，2008.

[2]王慧.基于URP的校园信息公建设的研究[D].河海大学硕士学位论文，2006.

[3]钱晨.高校数字化校园统一身份认证平台设计[D].复旦大学硕士学位论文，2010.