基于TOPSIS算法优化高校实验排课系统研究与实现

谢旭 李艳玲 吴仁寿

摘 要：目前各高校、普通高校等教育机构在教学排课上普遍采用回溯算法、贪心算法以及遗产算法等进行课程编排，这种编排方式在编排数量大，约束复杂的情况下是无法得到人性化的排课效果，比如：学生上课在时间上过于拥挤，上课地点空间跨度太大，以上算法在计算机上执行来完成排课工作还是会存在各种各样的缺陷。目前所存在的排课算法研究也是相当多的，但是在实际执行结果上并不能完全适应学生以及教师便捷地授课和上课的实际的需求。因而本文在已有研究基础上提出基于TOPSIS算法来优化高校实验排课设计以解决在课程安排紧凑，实验课室有限情况下的排课困难的问题。

关键词：课程编排 TOPSIS算法 排课系统

中图分类号：TP311.5 文献标识码：A 文章编号：1672-3791（2018）04（a）-0006-04

Abstract：At present colleges and universities， such as regular institutions of higher education institutions of backtracking algorithm is widely used in teaching process， a greedy algorithm and inheritance algorithm and so on carries on the curriculum arrangement， the layout in the choreography is big enough， constraint complex situations cannot be arranging the effect of human nature， such as students to class on time is too crowded， venue space span is too large， the above algorithm to perform on the computer to complete the course arrangement will exist all kinds of defects.At present， there are quite a lot of research on scheduling algorithms， but the actual implementation results cannot fully adapt to the students and the practical needs of teachers' convenient teaching and teaching.Therefore， based on the existing research， this paper proposes a TOPSIS algorithm to optimize the design of experimental courses in colleges and universities in order to solve the problem of difficulty in arranging courses under the tight schedule and limited experimental classrooms.

Key Words：Curriculum arrangement； TOPSIS algorithm； Course arranging sustem

排课一直是高校或者普通高中学校教学管理中一项重要且复杂的工作，特别是当授课所需的设备设施稀缺或者教师课程安排紧凑时，都会造成学生、教师之间时间冲突以及课程错乱的矛盾。所以，编排科学并且可行性高的教学课表是教学开展的核心所在。编排课程表实质上是在教学计划己经被制定好的基础上，按照也理学和教育学原理，由教务科根据不同的约束条件以表格的形式合理、有效地安排教学计划的过程[1]。在实际排课应用中，由于个人时间安排、不同上课班级之间课程编排、实验教学设施资源有限等因素，排课算法在实际应用中兼容性和通适性较差，无法保证所编排的课程都适应所有人。因此，在算法设计方面，我们也力求约束条件之间能满足大范围学生的需求特点，优化课程编排，以优化在授课资源稀缺下，学校排课困难的问题。

1 目前国内所存在的排课算法现状

排课问题从数学上讲，是一个在时间、教师、学生和教室四維空间，以培养方案和各种特殊要求为约束条件的组合规划问题，其实质就间，以培养方案和各种特殊要求为约束条件的组合规划问题，其实质就是解决各因素之间的冲突[2]。因此在设计与投入使用方面都有一定研究限制和难度，就研究范围而已，目前国内存在着多种多样的排课算法，在实际应用方面也算法的时间效率和耗费的资源也不尽相同，常见使用的算法有遗传算法、贪心算法、动态规划和回溯算法等。

例如：贪婪算法，贪婪算法的设计思想是分阶段工作，在每一个阶段选择局部最优，而不考虑将来后果。对最终的解不追求最优解，能够得到某种意义下的近似解的分级处理方法。贪婪算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况[3]。

又如回溯算法是一个既带有系统性又带有跳跃性的搜索算法，它在包含问题所有解的一颗状态空间树上，按优先条件向前搜索，以达到目标。算法搜索至状态空间树上的任一结点时，总是先判断该结点是否肯定不包含问题的解。若肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。这种走不通就退回的技术为回溯法，而满足回溯条件的某个状态点称之为回溯点。回溯算法在用来求解问题的所有解时，要回溯到根且要搜索过根结点的所有子树才可以结束，而在用来求解问题的任一解时，只要搜索到问题的一个解就可以结束[4]。

在实际应用中，贪婪算法在求解排课问题上会出现同一班级上课时间集中或者太过于分散或者相连的不用科目上课的教师距离太过于远。这和他排序的算法有关，由于算法在排序时选择的是局部最优，也就意味着在不用约束条件中不能综合考虑不同情况下的班级排课和上课时间之间相互协调。采用回溯算法，通过搜索节点的方式来确定排课的时间地点，相比贪婪算法，回溯算法在排课过程更为细腻，在排课质量上，有更高的契合度和满意度，使用情况良好。

就目前实验所使用的算法使用情况来看，排课算法之间优劣都有差异，在研究了几个常用算法的基础上，提出使用TOPSIS算法来进行排课设计，已解决对于任意一个班级排课难，排课不科学的问题，已提高排课的效率。

2 支持方便实用的互动式实用式的系统设计

针对目前国内主流的教学排课系统的兼容性和实用性入手，本系统以建议安装的桌面应用程序入手，方便教师与学生的使用。旨在打造一个易于使用的灵活性教学排课平台，并且便捷的将排课结果导出供学生使用。

2.1 系统功能框图

按照本系统的实际需求分析，以软件工程理论为基础和指导思想，初步确定本系统地功能结构，如图1所示。

2.1.1 初始设置

（1）历史排课信息管理功能：对以前排课信息包含教师信息、教室信息以及班级信息进行管理，为今后排课提供相关决策信息。

（2）清除系统数据功能：给重新编排的初值清零，避免系统混乱。

（3）设置系统值功能：为各使用单位提供便利。例如：设置学校名称、学院名称。

（4）排课初值设置功能：此功能与教学机制密切相关，用户根据实际情况设置学期的教学周数以及每周的上课天数、每天开设的节次数等。

2.1.2 基本信息管理

基于本系统兼容性方面的考虑，诸如教师基本信息、教室基本信息、班级基本信息以及课程信息等可以借助人事管理系统、学籍管理系统直接导入，同时，导入的基本信息可去除冗余，并增加新的可用字段，并且各部分信息管理具有输入、查询、浏览、修改、删除及打印各式报表的功能。

教学计划管理是整个排课系统的根基，教学计划管理规范可以说是整个排课工作进行的先决条件，因为教学计划和专业紧密联系，教学计划的完备与否直接影响着专业开课计划，所以它同样具有输入、查询、浏览、修改、删除及打印报表的功能。最后，还有教学日历管理，它主要是准确提供每个教学周所对应的教学时间。

2.1.3 排课管理

理论课程的预安排是正式排课之前必须经过的步骤，它目的是为了检测教学任务是否安排合理、教学资源是否够用、约束条件是否能够满足。

（1）遵循资源规划实践类教学环节进程。

（2）理论教学任务根据进程是否一致、人数多少、特殊要求来确定教室类型，并分教室类型统计教学总量，从而判断教室是否满足需求。

（3）满足条件则提示预安排成功。

（4）若小教室不够使用可安排大教室或合班，若大教室不够则需要拆班。

（5）若特殊需求不能满足则需要增添设备，经调整继续执行直到满足。

教学任务的管理就是指已经编排好的教师的实际班级开课计划，根据课程特点以及教师实际要求对教学任务表增加或删除约束条件并添加输入、查询、浏览、修改、删除及打印报表的功能。

自动周次规划管理就是指自动排课之前对教师、教室以及班级所做的一种周次时间规划，并为其提供可以安排理论教学的周数；然后，规划出课程的周学时数。本系统中为教师、教室以及班级分别建立了一个规划表专门用于对排课周次的控制，将不能用于理论课编排的时间全部锁定。

最后，自动排课管理按照完全整理好的排课数据用确定好的算法完成自动编排。手工排课管理主要是增加本系统的灵活性，针对某些约束条件特殊或临时调课的情况利用手工排课来解决冲突问题，达到成功排课的目的。

2.1.4 课表管理

教师任务书、教室课表、班级课表以及时间课表管理均能提供多样化打印。

课表查询功能可以随时提供教师、教室、班级以及时间来查询课表，同时，还可以进行组合查询为调课提供准确可靠的信息。

2.1.5 工作量管理

此功能主要是加强学校对于教师工作量的管理，规范工作量计算办法，其中计算機公式是计算工作量的政策依据，不同学校标准并不一致，而且计算办法也在不断更新，为了保证系统具有一定的通用性，计算公式的管理可以对计算公式进行随时调整以适应不同需要。

2.1.6 系统设置

为了增强系统可靠性和安全性，专门在系统设置中添加数据备份和数据恢复功能，便于今后对数据更新和维护，其中用户管理是对用户名、密码、权限的修改的设置；代码维护是指完成对系统中所用到的所有代码更新和维护。

2.2 TOPSIS排课算法设计

TOPSIS法是C.L.Hwang和K.Yoon于1981年首次提出，TOPSIS法根据有限个评价对象与理想化目标的接近程度进行排序的方法，是在现有的对象中进行相对优劣的评价。TOPSIS法是多目标决策中常用方法之一，通过监测评价对象中最优解与最劣解的距离来进行排序，当评价对象最靠近最优秀解的同时又远离最劣解，则是最理想的决策，反之，则为不理想决策。即在课程编排过程，通过计算不同等待排课班级在所指定时间段内，选中具体班级使用实验可使整个排课过程在排课方案中最接近最优解的同时又远离最劣解。

2.3 TOPSIS算法原理简述

首先对n个评价单元选择p个评价指标进行综合评价 （如果p个指标中有逆向指标或适度指标，则将其正向化），原始数据矩阵如下：

依照相对贴近度的大小对目标进行排序，形成决策依据。

在同一时间段，对有上课的教室所能上课的班级进行排课的选择，就转变为计算需要上课班级选择所需要课室的属性值，并进行决策排序。

相比论文在上文所提到的各类算法在使用过程的排课过程中的基本原理，使用TOPSIS算法进行排课在排课过程能够有效地减少类似其他排课算法容易出现的课程拥挤、几何空间跨度大、课室分配不合理等现象。通过正理想值与负理想值所计算出来的最优解与最劣解來衡量对比排课过程所出现的可能性选择，并且选择最有的可能性排课。这样的排课算法，显然有一下几个优点。

（1）保证学生所有课程在上课期间分布均匀。

（2）保证学生在同一上课时间段所经过的空间距离不会太远。

（3）保证教师在授课和教室之间的时间安排分布均匀.

（4）保证学校所有的教学资源充分地利用。

在计算机编程方面，将复杂的编排情况转化为可计算的矩阵以及可量化的指标来时间结果的输出，实现科学的编程过程，使整个系统在开发过程更加快捷，且算法实现难度适中，便于实现。

2.4 系统的架构与部署

在算法设计以及为了更加便于实现以投入使用，在系统设计上，采用C/S结构，通过服务器端的管理控制以及数据保存，服务器端以一个软件包的形式简易安装我Windows平台上，方便教师在教学管理和课程安排，并且极大的节省了排课时间。

系统采用Visual Studio 2015作为开发工具，采用SqlServer 2008数据库来存储数据，使系统在Windows上更加兼容。并且，系统开发也采用三层架构来进行开发，分清界面层（User Interface layer）、业务逻辑层（Business Logic Layer）、数据访问层（Data access layer），使系统结构更加的明确，可以降低层与层之间的依赖，并且在后期维护的时候，极大地降低了维护成本和维护时间[5]。

在安装部署上，将数据与编排任务合理分配到Client端和Server端，降低了系统的通讯开销，在使用本排课系统时需要安装客户端才可进行管理操作。客户端和服务器端的程序不同，用户的程序主要在客户端，服务器端主要提供数据管理、数据共享、数据及系统维护和并发控制等，客户端程序主要完成用户的具体的业务。当教师需要进行排课时，只需要在Windows平台安装软件安装包，即可使用并且再次使用不用重复安装。

2.5 TOPSIS算法在排课上的实现

开发后的系统可以在导入班级信息后选择班级所需要进行的实验，并且实现可选课程来进行排课，结果显示如图3所示。

不仅学生所需进行的实验可选，上课时间也可以进行选择，确保教师在教学安排上更具灵活性，并且加此约束进行排课。

在本系统中，排课的最终结果将以excel表格形式导出，方便师生在教学过程使用。

3 结语

高校排课一直是作为实用型研究项目的研究对象，其算法在设计上也有较高的复杂性和时间复杂度，因而在实际应用中也会存在各种特殊情况与不合理的编排，通过对比多种排课算法设计在设计与实际执行的情况，本论文提出利用TOPSIS算法来优化高校实验课程的编排，尽最大的努力来使排课更加人性化与具有更高的现实可执行性。

参考文献

[1] 李双成.中职学校排课系统的设计与实现[D].华南理工大学，2014

[2] 杨绪华.佳木斯大学排课系统的分析与设计[D].北京邮电大学，2016

[3] 高明芳，赵敏.高校自动排课系统排课算法的研究与设计[J].电脑知识与技术，2010，6（29）：8229-8230，8233.

[4] 张华.智能排课算法的研究及实现[D].山东大学，2010.

[5] 孟亚辉.基于校园网的多协议节约资源型离线下载系统设计[J].广东石油化工学院学报，2016（4）：32-36.