Heuristic Algorithms For Solving Educational Timetabling Problem

Educational Timetabling problem involves university course timetabling,examination timetabling and other practical problem.Constructing a reasonable and feasible timetable that can achieve high satisfaction in all aspects is the fundamental of ensuring the normal and smooth operation of school teaching activities.Due to the enrollment expansion in successive years and a series of higher education teaching reforms,timetabling arrangement become difficult for most colleges and universities in China.Additionally,with the college entrance examination reform,the contradiction between the reform requirements and the high school resource shortage has further aggravated,and constructing a reasonable timetable that satisfies the cultivation objectives of students' personality such as "one student,one timetable" become quite difficult.Therefore,it is of great practical significance to design efficient heuristics for this problem so as to make full use of existing educational resources and improve the school-running efficiency.The educational timetabling problem is a well-known NP-hard combination optimization problem,which means that there is no exact polynomial-time algorithm for it.Heuristic algorithms seek high-quality solutions within a reasonable time to maintain a balance between algorithm speed and accuracy.Consequently,the main approach for solving the combination optimization problem is to design highly efficient heuristics or meta-heuristics algorithms.Although several sessions of the International Timetabling Competitions have been hold,and many research results and significant advancements have been made,there is still room for improvement in terms of efficiency and quality for current methods.In this dissertation,heuristic algorithms are designed to solve several hot issues in the field of Educational Timetabling,including UCTP(University Course Timetabling Problem)and its simplified model,as well as the new college entrance examination shift scheduling problem,and benchmark instances and specific practical cases are used to evaluate the proposed algorithms.Compared with the existing efficient algorithms and application examples,the results show that the proposed algorithms have higher efficiency and solution quality.The major contributions of this dissertation are outlined as follows:1.An iterated local search algorithm is proposed for the simplified model of UCTPThe simplified model of UCTP is converted into an optimization problem with one objective,and then an iterated local search algorithm based on Simulated Annealing(SA)is proposed,which uses two temperature-controlled annealing processes to make the search process more flexible.According to the specific characteristics of the problem,a unique accepting criterion for a candidate solution and an improvement perturbation operator are designed.The proposed algorithm is evaluated on a widely used dataset containing 60 problem instances,and the results show that the proposed algorithm can find 58 feasible solutions out of 60 instances,which significantly outperforms all the reference algorithms.In addition,the upper bounds on unallocated events of the two large instances whose feasible solutions cannot be found are greatly improved by the proposed algorithm.2.A new heuristic competitive search algorithm is proposed to solve the UCTPTo overcome the shortcomings of iterated local search algorithm search rigidity,a competitive search algorithm based on iterative local search is proposed for UCTP problem,whose characteristics include:different selection probabilities are set for the neighborhoods;with the competitive exploration of different solution space regions,it is possible to find promising regions faster,and then local search strategies are used to deeply explore the regions.This process is repeated until a near-optimal solution is obtained.The proposed method has been applied to a well-known university course timetabling international competition instances containing 21 instances.The results are compared with the result obtained by other six methods from the literature,and it demonstrates that the method is able to produce improved solutions for 14 instances,which significantly outperforms the reference algorithms.It's worth noting that the competitive search algorithm is a general algorithmic framework that can be used to solve other combinatorial optimization problems.3.Class division arrangement model and timetable scheduling model are constructedUnder the background of the reform of college entrance examination,the shift-based teaching has brought great challenges to the class division and timetable scheduling.On the basis of field research,this dissertation thoroughly analyses the rules,characteristics and related factors of class-division and timetable scheduling,and puts forward the class-division model and timetable scheduling model,which lays a theoretical foundation for designing the timetable scheduling algorithm and evaluating the advantages and disadvantages of the timetable scheduling algorithm.4.A multi-phase heuristic algorithm is designed for the high school timetable problemAccording to the class division arrangement and timetable scheduling model,a competitive search based multi-phase heuristic algorithm is proposed.In the class division arrangement phase,considering the coupling of the curriculum characteristics and the course combination,a greedy strategy is firstly proposed to achieve the optimization of the course combination,and then the maximum matching between students and classes is determined through the heuristic local search.In the timetable scheduling phase,a double-match class strategy is designed to bind the two classes making them move synchronously in the process of timetable scheduling.The iteration reduces the violation of other constraints and gradually approaches the optimal solution.The algorithm was experimentally assessed by an actual case from a high school in Zhejiang Province,and the result shows that 19 classrooms are enough for class division arrangement by the proposed algorithm,while 3 more classrooms are needed in the actual case.Moreover,the number of students and classes involving in double-match classes are far less than those in the actual case,demonstrating the effectiveness of our algorithm.The above research shows that a highly efficient heuristic algorithm could be obtained by studying the problem thoroughly,constructing neighborhood based on the problem-specific characteristics and combining the advantages of different meta-heuristic algorithms.In future research,we will continue to improve the efficiency and scope of application of the algorithm via further research on the problem-specific characteristics,based on which,we will design and develop an efficient,intelligent and convenient timetable scheduling prototype system.