The Genetic Algorithm Applied Research In The University Course Scheduling System

In 1963 , C.C.Gotlieb raised the mathematical model of Curriculum Schedule Problem in his paper 《The Construction of Class-Teacher Time-Tables》 , this symboled the researching of CSP had enter the science domain fomally. In 1976, S.Even proved that CSP is a NP- Completed problem in his paper 《On The Complexity of Timetable And Multi Commodity Flow Problems》 at first. In mainland ,Tsinghua university delivered the experimentally researched result of Zhangxi Lin and Yaorui Lin about this problem in 《JOURNAL OF TSINGHUA UNIVERSITY(SCIENSE AND TECNOLOGY)》. Subsequently, parts of native other universities also begined researching work about this problem. This paper mainly research following several content:1. This paper discusses all the elements involved in the (CSP). and the process of man-made curriculum schedule. These analysis get such a conclusion as, CSP is a NP-Completed combination optimization problem. In this case, we design a Genetic Algorithms to resolve it.2. Time-Arranged AlgorithmThis algorithm is based on classic Genetic Algorithms. In this problem, we make some improvements on the classic Genetic Algorithms, to make it more suitable for CSP, for example, make the first generation more equalized to cover all the population; use the self-adapt Pc and Pm; divide the whole population into several sub population, etc. GA is used on 2 different level in CSP. On the first level, GA is going to find several almost-best arrangements for one single curriculum. On the second level, GA is going to determine in what sequence to arrange all the curriculums, the result is best.3. Classroom-arranged algorithmBesides GA, we also design an algorithm to arrange classroom for a curriculum. This algorithm works based on 'Priority classrooms', to find a reasonable classroom for every curriculum. We also set 3 sub algorithms to prevent the 'CurriculumSkipped' problem happening or resolve it if happens. By all of them, we almost could resolve the 'Curriculum Skipped' problem easily.4. System AchievementIn this paper, we finish several mainly module involved algorithm.lt works effectly.The model we make here works very well in CSP. We believe that it will work even better in the future with the development of GA and CSP.