Design And Realization Of University Timetabling Based On Genetic Algorithm

Course scheduling is not only a prerequisite for normal teaching activities, butalso an important part of teaching management. It involves classical multi-constrainedoptimization and combination, which has been proved as a NP-complete problemwithin computer applications, due to which a good many scholars have deeplyconducted numerous studies. Course scheduling is affected by many factors whichinteract with each other. In practices, there are no fixed theoretical approaches tocourse scheduling because the education administration differs in differentuniversities. With the development of computer technology, it is of eminentadvantages to solve universities’ difficulties in course scheduling by computer with itshigh-speed computational capability. In general, practical problems are firstlytransformed to mathematical models. Next, mathematical models are conversed intoexecutable programs by programming language to obtain function modules which arecorrespondent to actual demands. Finally, reasonable course scheduling results can beautomatically concluded.Compared with a multitude of solutions to course scheduling problems, geneticalgorithm is relatively more effective. Genetic algorithm, as an excellent and highlystable search algorithm, simulates the mechanism for “survival of the fittest” in natureand local optimal solutions won’t be easily caused in respect of eventual results, so itis a good choice to solve course scheduling problems by this algorithm. In the past,manual scheduling of courses was a major part of teaching at schools, whereas it hasbecome impracticable for large-scale universities with numerous classes, teachers andtypes of courses to simply schedule courses manually. Therefore, this paper studieshow to apply genetic algorithm in course scheduling problems and compiling a set ofcourse scheduling software based on the algorithm in combination with the featurethat it is uneasy to result in local optimization by this algorithm. The test analysis hasproved that there are no inflexible conflicts among the operation results of thissoftware and the course scheduling programs are more humanistic. Moreover, theseprograms don’t needed to be manually adjusted, which is the biggest advantage of thissoftware, as manual adjustment is needed for almost all results as regards previous course scheduling software.Aiming at the university where the author is, this paper solves course schedulingproblems by genetic algorithm and compiles a set of course scheduling software.Main tasks are listed as follows:I. Analyze the demands for course scheduling problems and various relatedconstraints. Some constraints need to be satisfied, while others only exert impactsupon the quality of results. Furthermore, corresponding mathematical models areestablished for course scheduling problems.II. Corresponding databases are designed by SQL Server2008to store largeamounts of data based on actual objects covered by scheduling problems.III. Taking course schedules as chromosome objects for coding this paperschedules courses through three steps of genetic algorithm including selection,crossover and mutation as well as a development tool named Visual Audio2010.IV. Test the software that has been developed in terms of the impact of thefrequency of genetic iteration and data amount upon results. The hardwareenvironment for test includes Pentium E52002.5GHz dual-core processor and2Gmemory. Besides,200teachers,200courses,100classes and200classrooms weretested. The iterative parameter was set as three generations and it took1minute and12seconds for course scheduling.In this thesis, the major research achievement lies in applying mathematicalmodules in course scheduling, compiling a set of software of course schedulingfunctions, testing and analyzing software that has been developed. Manual adjustmentisn’t needed as there were no inflexible conflicts among results.