Improved Graph-Based Algorithm for the University Examination Timetabling Problem
CSTR:
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference [16]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    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.

    Reference
    1 Eemund KB, Mccollum B, Meisels A, Petrovic S, Rong Q. A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research, 2007, 176(1): 177-192.
    2 王卿,路晓伟.高等院校学分制教学排考问题算法设计.上海理工大学学报,2007,(6):583-586.
    3 董健兴,栾勇,闫君政.基于图论的高校排考算法.计算机系统应用,2011,(5):177-179.
    4 冯珊珊,张月琴,郭旭敏.基于改进图着色理论的聚类算法.计算机工程与设计,2013,(5):1740-1743.
    5 Abdulia S. Heuristic approaches for university timetabling problems[Ph.D. Thesis]. Nottinghamshire: University of Nottingham, School of Computer Science and Information Techno, 2006.
    6 Causmaecker PD, Demeester P, Berghe GV. A decomposed metaheuristic approach for a real-world university timetabling problem. European Journal of Operational Research, 2009, 195(1): 307-318.
    7 田岭.大学自动排考算法设计与实现.计算机工程与设计,2007,(10):2443-2445.
    8 龙恒,谭彩明.基于遗传算法的排考系统.计算机系统应用,2014,(1):184-187.
    9 胡义伟,谢勇,郑金华.基于遗传算法的综合性大学排课系统研究.中国教育信息化,2007,21:54-55.
    10 李红婵,朱颢东.采用十进制免疫遗传算法求解高校排课问题.系统工程理论与实践,2012,(9):2031-2036.
    11 王卿,路晓伟.高等院校学分制教学排考问题算法设计.上海理工大学学报,2007,(6):583-586.
    12 董传良,仝月荣,洪奕茜.高校选课制下自动排考系统的设计和实现.实验技术与管理,2011,(6):4-6,15.
    13 王俊生,戴云龙.基于层次分析法的自动排课课程优先级模型.现代教育技术,2009,(11):32-35.
    14 胡世清.高校排课多元优化策略与自动实现方法的研究.现代教育技术,2011,(7):105-109.
    15 姚双良,顾夏灵.学分制环境下高校自动排考算法的设计与实现.信息技术,2013,(10):43-45,52.
    16 周昭涛.文本聚类分析效果评价及文本表示研究[学位论文].北京:中国科学院研究生院(计算技术研究所),2005.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

崔丽.高校学分制环境下排考问题的改进图算法.计算机系统应用,2015,24(3):220-225

Copy
Share
Article Metrics
  • Abstract:1317
  • PDF: 2443
  • HTML: 0
  • Cited by: 0
History
  • Received:July 08,2014
  • Revised:August 15,2014
  • Online: March 04,2015
Article QR Code
You are the first990607Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063