摘要
大学课程表问题UTP是一个应用广泛的、典型的组合优化和不确定性调度问题,并且已经被证明是NP完全问题。本文提出了一种分阶段解决大学课程表问题的算法,将课程表问题划分为时间安排和空间安排两个阶段,分别采用智能算法和最佳适应算法逐段求解,并最终求得全局较优解。通过设计实验对算法进行分析,结果表明这种分阶段决策算法在保证课表质量的同时能够有效减小遗传算法在求解UTP问题中的复杂度,提高程序的运行速度。
University timetable problem （UTP） is a widely-applied typical combination optimization and uncertain management problem. UTP has been proved to be a NP-complete problem. In this paper, a phase-divided algorithm is proposed to solve the university timetable problem. It divides the course timetabling problem into two phases： arranging time by an intelligent algorithm and arranging classroom by a best-fit algorithm, and gets the whole solution by resolving each phase of the problem. Then the divided phase algorithm are compared with the classical genetic algorithm, which shows that the divided phase algorithm reduces the complicacy in the mean time of ensuring the quality of results, and improves the running speed of the program.
出处
《计算机工程与科学》
CSCD
北大核心
2009年第6期71-74,78,共5页
Computer Engineering & Science
关键词
大学课程表问题
分阶段
遗传算法
排课
university timetable problem
phase-divided
genetic algorithm
curriculum scheduling
