Algorithm Research On Course Scheduling Problem

In recent years, expanding enrollment and the increasing types of courses in universities resulted in the great difficultyto the school teaching management work. Teaching management is a complex project, which holds the largest, the highest complexity for the timetabling problem that is a provedNP problem. In the course of timetabling, the grade, the types of courses, classroom capacity, teacher type, class time, teachers and other factors should be take into comprehensive consideration in order to achieve the rational planning of teaching resources. Therefore, how to optimize the university curriculum arrangement to improve the availability of school teachers, classroom teaching resources is the goal pursued by all schools.The timetabling, which not only involves the allocation of teaching resources, but also whether the school teaching goal can be achieved,has been the focus of many scholars at home and abroad. In integrating the complex and changeable resources,the reasonable and efficient arrangement taken byautomatic course scheduling system can meet the needs of the school educational activities, improve the utilization rate of the school teaching resources, ensures the smooth implementation of the teaching task and controls the teaching cost effectively.It isof practical significance to the development of the school and our country’s educational undertaking.Solving the timetabling problem can deal with the shortage of resources encountered during the process of reform in college enrollment, the credit system practice. Besides,it can give some references to other scheduling, including the education system examination arrangement, administrative or commercial meeting arrangement, the vehicle schedule of transportation department,and so on.The curriculum table is for scheduling curriculum to give the reasonable arrangement in teaching activities, thus scientific course arrangementcan make the teaching affairs in good order and well arranged. Therefore, the related institutions and personnel should take the reasonable layout of the curriculum. In the earlier times, the curriculum scheduling is taken in the artificial way, resulting in wasting a lot of time and energy and bringing scheduling conflict due to inconsideration. Later, many scholars at home and abroad systematically studied on the course scheduling problem, using genetic algorithm, simulated annealing algorithm, ant colony algorithm, branch and bound algorithm in it. Despite the fact that the used methods greatly improve efficiency and rationality,there is the lack in the scientific curriculum.The algorithm principle and application in common are as follows:in the application of genetic algorithm, the encoding scheme, fitness function and genetic operators are necessary, and then organization and search is taken using the information in the evolution. The next step of calculation can be continued for the one holding great applicability; genetic algorithm has the advantages of simple and strong independence, but there exists weak ability in dealing with constraints. Tabu search algorithm is to construct a tabu list which makes the move listed in the ban to avoid the cycle; the climbing cycle takes strong ability, memory ability, and can jump out of local optimal solution. The simulated annealing algorithm uses schedule parameters to control the process of algorithm, and it can provide approximate optimal solution in polynomial time. Although the process is more complex, it is more favorable for solving large-scale nonlinear programming problems. The ant colony algorithm using positive feedback principle, to a certain extent, can speed up the evolution process, and is an essentially parallel implementation of the algorithm. Different individuals in the process of continuous information exchange and transmission cooperate to find a better solution. The basic idea of the branch and bound method is to search for all feasible solutions (limited number) to optimized problem with constraints. In the specific implementation, all the feasible solution space is continuously splitted into smaller branch,and a lower bound or the upper bound can be calculated for the value of solutions within each subset (called bound). In each branch, those subsets of feasible solutions which are beyond the known values are no longer branched In this way, many subsets of solutions (i.e. search many nodes on the tree) can not be considered, thus narrowing the search range. This process has been carried out to find out the feasible solutions which will not overrange the boundary of any subset of boundaries.From the above analysis, different intelligent algorithms have their own characteristics, and in solving the course timetabling problem, they have their own advantages and disadvantages. Since a single method is difficult in achieving the desired objectives, it is inevitable to combine the different algorithm integration to build a more advanced algorithm. The genetic algorithm has a strong ability to adapt, but it has poor convergence, while ant colony algorithm has better convergence, it has higher requirements on the operation data. If the two methods can be integrated so as to turn the results of the genetic algorithm into the initial value of the ant colony algorithm, the problem can be solved perfectly. Thus, this paper presents a new hybrid algorithm based on genetic algorithm and ant colony algorithm to improve the existing single algorithm. In this paper, the test on the application of genetic algorithm and ant colony algorithm in course scheduling, and then take the new hybrid algorithms into application. The experiment results showed that the hybrid algorithm in the running time, adaptability and convergence is improved obviously. It is more reasonable, and has a very strong research significance and practical value.This paper mainly focuses on the research of the intelligent course scheduling system:First, this paper analyzes the importance and value in the couse scheduling, summarizes the status quo of the domestic and international research on it and introduces the existing problems and its complexities in the intellengence calculating. In addition, the paper describes the common course scheduling model and algorithm, and overviews the the defects and strengths.Then, taking the optimization of scheduling as the goal, on the basis of the existing various algorithms, this paper focuses on the research of the genetic algorithm and ant colony algorithm to improves efficiency of scheduling. The usage of the selection operation, crossover operation and mutation operation can improve the genetic algorithm in applying the course scheduling to reduce the conflict. By improving the heuristic function, the time consuming of the random selection path of the ant algorithm is improved.Finally, in order to achieve an efficient of timetabling, the ant algorithm and ant colony algorithm are combined firstly. On the base of the fast search which is operated by genetic algorithm, the fast convergence and global optimization of ant colony algorithm is used to obtain the optimum for the properties. In the function, the combination of the two algorithms is better than the single algorithm. In addition, other algorithm can also be used for the problem, then, whether their combination and the effect is good has become a development direction of future research.