[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问题求解算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
33
期数:
2003年第1期
页码:
41-44
栏目:
自动化
出版日期:
2003-01-20

文章信息/Info

Title:
TTP algorithm based on genetic algorithm
作者:
业宁12 梁作鹏1 董逸生1
1 东南大学计算机科学与工程系,南京 210096; 2 南京林业大学信息学院计算机系,南京 210037
Author(s):
Ye Ning12 Liang Zuopeng1 Dong Yisheng1
1 Department of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2 Department of Computer, Nanjing Forestry University, Nanjing 210037, China
关键词:
时间表 排课 遗传算法
Keywords:
timetabling arranging of curriculum schedule genetic algorithm
分类号:
TP182;TP391.75
DOI:
10.3969/j.issn.1001-0505.2003.01.010
摘要:
提出并实现了一种高校自动排课算法,利用遗传算法建立数据模型,定义一个四维的染色体编码方式和包含学生人数、教室座位、特殊课程、教师、班级、一门课的时间间隔等因数的适应度函数.通过切片算子,生成指定要求的基因型个体,用交叉算子和变异算子对基因型个体进行运算,再利用选择算子选择适应度函数值较高的染色体编码方案,最后对优化的染色体按指定方向切片,生成教师课表、学生课表和教室课表.对某高校的真实数据进行实验,结果显示无一例教室、教师、班级冲突,在PⅢ866PC机上运行,耗时为2 323.573 s.该算法可以推广到车辆调度、会议安排、超大规模电路板设计等应用领域.
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.

备注/Memo

备注/Memo:
基金项目: 江苏省“九五”重点攻关课题资助项目(BJ98017-1)、江苏省“十五”高科技资助项目(BJ2001013)和南京林业大学科研基金重点课题资助项目(X02-070-1(Z)).
作者简介: 业宁(1967—),男,博士生; 董逸生(联系人),男,教授,博士生导师,ysdong@seu.edu.cn.
更新日期/Last Update: 2003-01-20