计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (23): 236-238.DOI: 10.3778/j.issn.1002-8331.2009.23.067

• 工程与应用 • 上一篇    下一篇

分组遗传算法优化大学考试时间表

张 磊1,张博锋2   

  1. 1.上海行知学院 计算机系,上海 201900
    2.上海大学 计算机科学与工程学院,上海 200072
  • 收稿日期:2008-04-29 修回日期:2008-07-22 出版日期:2009-08-11 发布日期:2009-08-11
  • 通讯作者: 张 磊

Study of application of grouping genetic algorithm in examination timetabling problem

ZHANG Lei1,ZHANG Bo-feng2
  

  1. 1.Department of Computer,Shanghai Xingzhi College,Shanghai 201900,China
    2.School of Computer Engineering and Science,Shanghai University,Shanghai 200072,China
  • Received:2008-04-29 Revised:2008-07-22 Online:2009-08-11 Published:2009-08-11
  • Contact: ZHANG Lei

摘要: 大学考试时间表是一个多约束条件下的优化问题。传统遗传算法寻优的计算量是指数级的规模,而寻优的操作有可能会破坏时间表的硬约束条件,从而最终得到的解并不一定理想甚至不可行。该文从某高校的实际应用出发,对用图着色模型得到的已经满足了硬约束条件的初始考试时间表,用改进的分组遗传算法在既不破坏硬约束条件也不延长考试周的条件下扩大并平均分配了学生的复习时间,并且还大大减少了寻优的计算量。

Abstract: University exam timetabling problem belongs to optimization problem based on many constraints.The caculation of tradional genetic algorithm reached to index-size and the operation maybe break the hard constraints and can not find an ideal or feasible solution.This paper optimizes initial solution which satisfies hard constraints and concludes from relationship color algorithm by grouping genetic algorithm from practical applications.Maximize students’ study time under fixed examination week,cut down the caculation and don’t break the hard constraints.

中图分类号: