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

Solving timetabling problem using improved retrospective algorithm

计算机排课算法一直是一个没有被完美地解决的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.