高校学分制环境下排考问题的改进图算法

本文利用图论模型的转化,改进传统贪心算法,设计了一种新的求解高校排考问题的图算法.改进后的算法可以更好应对在现实学分制环境下,跨年级、跨专业、主辅修等复杂的选课因素.为了解决传统算法中仅靠人工优化来实现的软约束目标,改进后的图算法首先将排考图着色模型,转化为无向赋权图的分团覆盖模型,通过深度优先策略和赋权机制,求解同时满足排考硬约束条件和软约束条件的排考方案.经过数据验证,改进算法的排考效果,在排考效果上优于传统贪心算法,在时间效率上优于人工排考方式.改进后的新算法在近年我校的期末考务工作中发挥了一定作用.     

大学自动排考算法设计与实现

提出了一种应用于高等院校的自动排考算法.该算法结合了启发式算法的特点,同时建立静态冲突图来降低算法复杂程度,算法充分利用了应用领域经验和规则的优势,提高了自动排考的资源搜索能力.通过在实际工程中应用,表明该算法在解决复杂的高校排考问题时有较好的效果.     

基于人性化冲突解决算法设计模型

如何合理安排好补考学生的时间、减少监考人员的场次、最佳利用考场资源等项研究,具有很好的实用价值.事实上补考的复杂度、繁琐度不低于正式考试.文章提出一种新的基于人性化的安排补考算法.通过分析实际补考安排过程中的关键因素,对补考资源进行合理抽象,同时提出避免冲突的约束条件降低算法复杂度,建立一种基于人性化的优化排补考算法模型.     

一类考场座位安排算法的研究

针对一类多科目,大规模考试的考场座位安排特殊要求,提出一种考场安排算法,并对算法的正确性和时间及空间复杂度进行了分析。算法的职业鉴定考务系统运行表明,算法较好地满足了此类考试组织的要求。     

基于LINGO的大学自动排考设计

传统排考工作是考务人员手工完成的,随着学校规模的增大、课程复杂度的提高,手工排考工作与管理要求的矛盾越来越突出.排考问题是一类典型的时间表问题,解决该问题的过程是数学建模,并根据模型的目标和约束找到最优解的过程.借助LINGO工具可方便快捷地构建模型,有效快速地求解模型,并给出分析报告.实践证明,该方法求解的排考结果与手工排考相比准确性更高、优化程度更好和时效性更高.     

一种新的高校自动排考算法

针对目前高校自动排考算法的不足,提出了一种新的高校自动排考算法。算法不仅解决了考试课程、考场及监考教师的自动安排,还实现了重修考生的自动安排,并在监考教师安排算法中利用监考权重系数、时间匹配串提高了监考教师安排的合理性和灵活性,经实际应用表明,算法较好地满足了组织此类考试的要求。     

一种新的高校自动排考算法

针对目前高校自动排考算法的不足，提出了一种新的高校自动排考算法。算法不仅解决了考试课程、考场及监考教师的自动安排，还实现了重修考生的自动安排，并在监考教师安排算法中利用监考权重系数、时间匹配串提高了监考教师安排的合理性和灵活性，经实际应用表明，算法较好地满足了组织此类考试的要求。     

一种基于结构分解和因子分析的贝叶斯网络隐变量发现算法

通过研究粗糙集与图论的关系,提出了以集合为权的加权多重完全多部图的概念,定义了加权多重完全多部图的邻接矩阵,得到了加权完全多部图与决策表的映射关系;给出了粗糙集决策表信息系统的图论形式和决策表信息系统属性约简的图论方法,并根据图论理论对算法进行了优化;得到了在决策表信息系统中,属性的集合不可以约简的充分必要条件;并进一步提出了基于属性置信度的计算方法和多决策属性的处理方法。编程实验结果证明该方法能有效地降低时间和空间复杂度。     

基于图论方法的自动优化排课模型研究

排课问题是高校教务管理工作中劳动强度大且复杂费时的一项核心工作,目前还只能手工凭经验排课,在信息处理自动化不断普及的今天,显得极不协调,原因在于还没有一个行之有效的自动化排课模型.排课过程有很多不允许冲突的关联要素,一但中突就会打乱正常的教学秩序导致教学事故,这是排课模型的研究难点.时间冲突是最基本的冲突限制,如在同一个课时内,不能安排一个教师给两个班级上课,一个班级也不能同时应付两个老师的课.本文对笔者曾经提出的基于图论方法实现自动化排课、调课和优化的排课模型进行了扩展,不但从理论上彻底避免了各种冲突的可能性,并且可以大大提高排课的效率.     

基于信息增益的SLAM图精简

针对基于图论的同时定位与制图中,非线性约束方程组维数随机器人运行距离和时间的增加而不断增大的问题,提出一种基于信息增益的图精简算法.该算法通过评估精简前后特征点信息矩阵相对变化,删除观测信息量小于给定阈值的机器人位姿及相应的观测,达到显著简化优化问题的目的.根据测量球形协方差矩阵假设,给出了信息增益的精确和近似计算方法.通过恢复性图剪枝方法,确保图精简过程中的连通性.蒙特卡洛仿真和开源实验数据计算结果表明,在不引入明显的优化误差前提下,该方法可实现位姿和特征点90%的精简,显著提高图优化效率.     

Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling

This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, using the matrix semi-tensor product, the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph. Second, an equivalent problem of robust graph coloring is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. Third, a kind of examination timetabling is discussed by using the obtained results, and a method to design a practicable timetabling scheme is presented. Finally, the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples.     

优化蚁群算法在排课中的应用策略

针对高校排课面临的问题和挑战,通过分析排课问题的约束条件,将解决排课问题转化为二分图匹配的问题,并给出优化蚁群算法方案,探索高校排课问题的优化策略。     

课程表问题的一种模拟退火超启发式算法

课程表问题是经典的组合优化问题,属于NP-hard问题.长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法.在此基础上提出了一种基于多个图染色启发式规则的模拟退火超启发式算法.在超启发式算法的框架中,用模拟退火算法作为高层搜索算法,多个图染色启发式规则为底层的构造算法.与现有的方法相比,该算法具有很好的通用性,可以很容易推广到考试时间表、会议安排.旅行商问题、背包问题等应用领域.实验表明,该算法是可行有效的,且无一例时间、空间冲突.     

A practical three‐phase ILP approach for solving the examination timetabling problem

A practical mathematical programming based approach is introduced for solving the examination timetabling problem at the German Jordanian University (GJU), whereby the complex process of acquiring a feasible examination timetable is simplified by subdividing it into three smaller sub‐problems (phases). Accordingly, the exams are initially allocated to time slots in phase one, the time slots are then allotted to days in phase two, and finally in phase three the exams are assigned to rooms based on the number of students taking each exam and capacities of the rooms. The solution for each phase is acquired based on an integer linear programming (ILP) formulation, while satisfying a set of hard constraints that ensure comfortable exam timetables for all students and meet the desired requirements set by GJU administrative staff. Furthermore, the solver can be controlled and launched from a student information system named MyGJU Admin, which enabled registrars at the university to easily, quickly, and accurately generate final exam timetables in several standard formats. Moreover, the approach was validated based on recent GJU registration information as well as real‐world benchmark data.     

一种基于遗传算法的排课方法研究

排课问题是一个多约束、多目标的组合优化问题,并且已经被证明是一个NP完全问题。本文基于本校教学管理过程的实际情况,利用遗传算法对排课问题建立数学模型,设计了适应度函数,通过选择、交叉和变异等过程,进化得到最优解。实验结果表明该算法能够有效的解决本校的教务智能排课问题。     

KGDB:统一模型和语言的知识图谱数据库管理系统

知识图谱是人工智能的重要基石,其目前主要有RDF图和属性图两种数据模型,在这两种数据模型之上有数种查询语言,RDF图上的查询语言为SPARQL,属性图上的查询语言主要为Cypher.十年来,各个社区开发了分别针对RDF图和属性图的不同数据管理方法,不统一的数据模型和查询语言限制了知识图谱的更广应用.KGDB （Knowledge Graph Database）是统一模型和语言的知识图谱数据库管理系统：（1）以关系模型为基础,提出统一的存储方案,支持RDF图和属性图的高效存储,满足知识图谱数据存储和查询负载的需求;（2）使用基于特征集的聚类方法解决无类型三元组的存储问题;（3）实现了SPARQL和Cypher两种不同知识图谱查询语言的互操作性,使其能够操作同一个知识图谱.在真实数据集和合成数据集上进行的大量实验表明,KGDB与已有知识图谱数据库管理系统相比,不仅能够提供更加高效的存储管理,而且具有更高的查询效率.KGDB平均比gStore和Neo4j节省了30%的存储空间,基本图模式查询上的实验表明,在真实数据集上的查询速度普遍高于gStore和Neo4j,最快可提高2个数量级.     

A hyperheuristic approach to examination timetabling problems: benchmarks and a new problem from practice

Many researchers studying examination timetabling problems focus on either benchmark problems or problems from practice encountered in their institutions. Hyperheuristics are proposed as generic optimisation methods which explore the search space of heuristics rather than direct solutions. In the present study, the performance of tournament-based hyperheuristics for the exam timetabling problem are investigated. The target instances include both the Toronto and ITC 2007 benchmarks and the examination timetabling problem at KAHO Sint-Lieven (Ghent, Belgium). The Toronto and ITC 2007 benchmarks are post-enrolment-based examination timetabling problems, whereas the KAHO Sint-Lieven case is a curriculum-based examination timetabling problem. We drastically improve the previous (manually created) solution for the KAHO Sint-Lieven problem by generating a timetable that satisfies all the hard and soft constraints. We also make improvements on the best known results in the examination timetabling literature for seven out of thirteen instances for the To ronto benchmarks. The results are competitive with those of the finalists of the examination timetabling track of the International Timetabling Competition.     

A graph coloring constructive hyper-heuristic for examination timetabling problems

In this work we investigate a new graph coloring constructive hyper-heuristic for solving examination timetabling problems. We utilize the hierarchical hybridizations of four low level graph coloring heuristics, these being largest degree, saturation degree, largest colored degree and largest enrollment. These are hybridized to produce four ordered lists. For each list, the difficulty index of scheduling the first exam is calculated by considering its order in all lists to obtain a combined evaluation of its difficulty. The most difficult exam to be scheduled is scheduled first (i.e. the one with the minimum difficulty index). To improve the effectiveness of timeslot selection, a?roulette wheel selection mechanism is included in the algorithm to probabilistically select an appropriate timeslot for the chosen exam. We test our proposed approach on the most widely used un-capacitated Carter benchmarks and also on the recently introduced examination timetable dataset from the 2007 International Timetabling Competition. Compared against other methodologies, our results demonstrate that the graph coloring constructive hyper-heuristic produces good results and outperforms other approaches on some of the benchmark instances.