基于GENET的时间表问题自动求解算法  

A GENET-based Algorithm for Automated Timetabling

作　　者：朱文兴[1] 张千里[1] 

机构地区：[1]福州大学计算机科学与技术系,福建福州350002

出　　处：《小型微型计算机系统》2003年第7期1335-1337,共3页Journal of Chinese Computer Systems

基　　金：国家 973项目 ( G19980 3 0 60 0 )资助 ;福建省自然科学基金 ( A0 0 10 0 10 )资助 ;福建省教育厅基金( JA0 0 14 3 )资助 ;福州大学科技发展基金 ( XKJ( QD) -0 12 2 )资助

摘　　要：构造大学考试时间表自动生成系统是一个知名的问题 .本文用约束满足问题模型来描述大学考试时间表问题 ,并提出了一个基于 GENET的局部搜索算法来解该问题 .该算法采用一些问题相关的策略来提高局部搜索效率 .实验结果表明 ,将“强约束违反”转化为“弱约束违反”的方法能大大地提高算法性能 ,使该算法优于The problem of constructing an automated timetabling system for university examination is a well known one. In this paper, the timetabling problem is formulated as a constraint satisfaction problem. A local search algorithm based on GENET is described to solve this problem. The algorithm incorporates some problem specific strategies to enhance the local search. Our experiment shows that the performance of our algorithm was improved greatly after adopt the method of converting 'strong constraint violation' to 'weak constraint violation'. The proposed algorithm is much better than GENET and other evolutionary algorithm.

关 键 词：时间表问题 约束满足问题 GENET算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]