# [1]业宁,梁作鹏,董逸生.一种基于遗传算法的TTP问题求解算法[J].东南大学学报(自然科学版),2003,33(1):41-44.[doi:10.3969/j.issn.1001-0505.2003.01.010] 　Ye Ning,Liang Zuopeng,Dong Yisheng.TTP algorithm based on genetic algorithm[J].Journal of Southeast University (Natural Science Edition),2003,33(1):41-44.[doi:10.3969/j.issn.1001-0505.2003.01.010] 点击复制 一种基于遗传算法的TTP问题求解算法() 分享到： var jiathis_config = { data_track_clickback: true };

33

2003年第1期

41-44

2003-01-20

## 文章信息/Info

Title:
TTP algorithm based on genetic algorithm

1 东南大学计算机科学与工程系,南京 210096; 2 南京林业大学信息学院计算机系,南京 210037
Author(s):
1 Department of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2 Department of Computer, Nanjing Forestry University, Nanjing 210037, China

Keywords:

TP182;TP391.75
DOI:
10.3969/j.issn.1001-0505.2003.01.010

Abstract:
A time table problem(TTP)algorithm is proposed to conduct the arrangement of curriculum schedule in universities. First, a data model is set up using genetic algorithms(GA)and then a 4-dimension chromosome representation and a fitness function are defined, the former including time, day, classroom and course, and the latter including student number, seats, special courses, teachers, classes and intervals of courses. Genotype individuals are generated through slice operators and then crossover operators and mutation operators are used to operate these individuals. The best scheme of chromosome representation in which fitness function value is higher is selected by section operators. Finally the teacher curriculum schedule, student curriculum schedule and classroom curriculum schedule can be achieved by the optimum chromosome in some dimensions. This method was tested with real-world data sets and the result is satisfactory. This algorithm is also applicable in vehicle dispatch, conference arrangement, VLSI(very large scale integration)and other fields.

## 参考文献/References:

[1] Hans-Joachim Goltz,Dirk Matzke.University timetabling using constraint logic programming[A].In: PACLP’99[C].London,1999.529-535.
[2] Hans-Joachim Goltz,Georg Küchler,Dirk Matzke.Constraint-based timetabling for universities[A].In: Proc INAP’98 11th Int Conf on Applications of Prolog[C].Tokyo,1998.75-80.
[3] Hana Rudova,Ludek Matyska.FIMU-RS-99-09 timetabling with annotations[R].Brno,Czech Republic:Faculty of Informatics,Masaryk University,1999.17
[4] Colorni A,Dorigo M,Maniezzo V.Tech rep.90-060 A genetic algorithm to solve the timetable problem[R].Politecnico di Milano,Italy.1992.http://citeseer.nj.nec.com/context/638417/182445.
[5] Andrea Schaerf.CS-R9567 A survey of automated timetabling[R].CWI,Amsterdam,NL,Holland,1995.
[6] Legierski W.Search strategy for constraint-based class-teacher timetabling[A].In:PATAT 2000[C].Konstanz Germany,2000.155-169.
[7] Michael W.Carter:a comprehensive course timetabling and student scheduling system at the University of Waterloo[A].In: PATAT 2000[C].Konstanz,Germany,2000.64-84.
[8] Michael A.Trick:a schedule-then-break approach to sports timetabling[A].In:PATAT 2000[C].Konstanz Germany,2000.242-253.
[9] Rudov H,Murray K.University course timetabling with soft constraints[A].In: PATAT 2000[C].Konstanz Germany,2000.73-89.
[10] Holland J H.Adaptation in nature and artificial systems[M].Michigan:The University of Michigan Press,1975; Massachusetts:MIT Press,1992.11-56.
[11] Goldberg D E,Lingle R.Alleles,loci,and the traveling salesman problem[A].In:Proc of the 1st Int Conf on Genetic Algorithms ICGA-85[C].Pittsburgh,PA,USA,1985.154-159.