摘要
课程表问题(Timetablingproblem,简称TTP)是时间表问题之一,也是NP难问题。根据大学授课形式的特点建立了大学课程表问题的数学模型,并给出了求解该问题的遗传算法。为了提高解的质量和加快收敛速度,当相同时间段内班级重复出现时,给出了寻找可能的新位置的方法,并将其嵌入遗传算法,实验结果表明该方法是可行和有效的。
Timetabling problem is not only one of the timetable problems but also a kind of NP-complete problem.According to the characteristics of lecturing method in university,a mathematical model was set up and a genetic algorithm for the problem was introduced.To improve solution quality and accelerate convergence speed,a method of looking for new possible position was provided and was embedded in genetic algorithm when the same classes or courses appear repeatedly at the same time.The experiment result shows that the method is feasible and effective.
出处
《鞍山科技大学学报》
2005年第1期26-29,共4页
Journal of Anshan University of Science and Technology
关键词
课程表问题
模型
遗传算法
NP难问题
university timetabling problem
model
genetic algorithm
NP-complete problem
