Automatic Course Scheduling Problem Based On Genetic Algorithm

Timetabling Problem (TP) is a Multiobjective Combination Optimization Problem with constraints, and also has been proved NP-Completed.Genetic Algorithm (GA) is a high-effective randomly searching algorithm, based on the nature evolution. It is a very effective algorithm to resolve NP-Completed Combination Optimization Problem. The paper is aimed at solving timetabling problem using GA. The main content are as following:1. We systematically and completely discuss factors, restrictions, objective and difficulty attached to TP, describes TP by mathematic model, and bring forward the whole frame and technology route of methods.2. Giving out Entity-Relation Drawing (ERD) and class illustration, designing data structure, we study many sub-algorithms in course of solving problem, put forward a random arrangement algorithm having local heuristic backdating ability to find feasible solution quickly and easily.3. Giving out quantitative analysis of some objective of inkling, we establish objective optimization space of TP.4. We study chromosome coding and heredity operator designing aimed at TP, then introduce the multiobjective decision-making concordance model, put forward a fitness computation mode base on multiobjective concordance decision-making model and improve the generalized structure of GA, form a coordinated multiobjective optimization algorithm of TP.5. We use VC++ and Delphi as basic development tools, MS SQL SERVER2000 as database, design and realize auto-timetabling system based on GA. After an example having two campuses, 2295 teachers, 996 classes and 1973 schemas has been solved in objective space consisted of four factors of slot- superior, distributing-uniformity-on-day, time-prefer of teacher and hour- density of teacher. The solution is satisfied. The algorithm is steady and optimize-ward. The system has been applied inseveral schools including Zhejiang University of technology and improves timetabling efficiency greatly.