Constructing Good Solutions for the Spanish School Timetabling Problem
作者:
AlvarezR.,
MartinG.,
TamaritJ. M.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1996)
卷期:
Volume 47,
issue 10
页码: 1203-1215
ISSN:0160-5682
年代: 1996
DOI:10.1057/jors.1996.149
出版商: Taylor&Francis
关键词: timetabling;scheduling;heuristics
数据来源: Taylor
摘要:
AbstractIn the school timetabling problem a set of lessons (combinations of classes, teachers, subjects and rooms) has to be scheduled within the school week. Considering classes, teachers and rooms as resources for the lessons, the problem may be viewed as the scheduling of a project subject to resource constraints. We have developed an algorithm with three phases. In Phase I an initial solution is built by using the scheme of parallel heuristic algorithm with priority rules, but imbedding at each period the construction of a maximum cardinality independent set on a resource graph. In Phase II a tabu search procedure starts from the solution of Phase I and obtains a feasible solution to the problem. The solution obtained is improved in Phase III. Several procedures based on the calculation of negative cost cycles and shortest paths in a solution graph are used to get more compact timetables.The algorithms have been imbedded in a package designed to solve the problem for Spanish secondary schools. The computational results show its performance on a set of real problems. Nevertheless, it can be applied to more general problems and results on a set of large random problems are also provided.
点击下载:
PDF (5732KB)
返 回