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

Improved Graph-Based Algorithm for the University Examination Timetabling Problem

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

A graph-based algorithm is developed in this paper to slove the university examination timetabling problem, by transforming the classical graph model and improving the greedy algorithm. The improved algorithm can be used to meet more complicated constrain conditions in the real university credit envioronment, such as cross-major, trans-grade, minor-study and so on. The algorithm aims to slove the soft-constrain objects, which are achived by manual optimizing in the most tradition researches and cases. Firstly, the algorithm is discussed to transfer the classical graph coloring model into a clique cover problem of a weighted undirected graph. Then the greedy algorithm is impoved by the deep-first strategy, to search the solutions which satisfies both the hard-constrains and soft-constrains. The improved algorithm is proved to be better than the greedy algorithm for the solution is more reasonable, and better than the manual work for the time consumed is less. The improved algorithm can enhance the efficiency of the university timetabling, which is helpful to the academic management of our university in recent years.