基于改进回溯算法的计算机排课系统  

Solving timetabling problem using improved retrospective algorithm

作　　者：车明[1] 秦存秀[1] 刘凯[1] 

机构地区：[1]天津大学电子信息工程学院,天津300072

出　　处：《沈阳工业大学学报》2006年第6期667-670,696,共5页Journal of Shenyang University of Technology

摘　　要：计算机排课算法一直是一个没有被完美地解决的NP难题,国内外都在对它进行广泛的研究.基于一个中专院校的自动排课系统的实现,通过对当前各种算法的研究、对比、总结,发现当前的排课算法可以分为构造型算法和改进型算法两类,并且这两种算法有着各自的优缺点.为此吸取了遗传算法(改进型算法)和回溯法(构造型算法)的优点,在回溯法中引入了拟人策略和遗传算法中的评价、惩罚机制,经过实际应用的验证,该算法特别适合应用在实际的排课系统中.The algorithms for timetabling have been widely studied but there are no perfect solutions for it yet. Through investigating and comparing the existing algorithms, it has been found that these algorithms can be classified into two categories designated as constructed algorithms and modern algorithms, which show the individual advantages and shortages. In this improved algorithm, the genetic algorithm and some useful rules have been introduced into the retrospective algorithm. The practical application proves that the improved retrospective algorithm is especially suitable as a timetabling system.

关 键 词：计算机排课 回溯算法 适应度 适应度评价函数 硬约束 软约束 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]