Abstract：Focusing on the issue that local search algorithm is prone to fall into the local optimum and does not adapt to the course arrangement under multiple constraints, an automated course arrangement algorithm based on multi-class iterated local search was proposed. Firstly, the course arrangement problems were classified by the multi-class classifier according to the characteristics of the problems to guide the neighborhood selection and parameter setting of the iteration local search. Then, in the process of iterated local search, the sequence-based greedy algorithm was used to obtain the feasible solutions. Finally, the problem characteristics oriented two-temperature control simulated annealing algorithm was used to search for local optimal solution in the neighborhood and the current optimal solution was perturbed by a specific strategy and iterated as the new initial solution to achieve global optimization. The proposed algorithm was tested on two internationally famous datasets, which are the second international timetabling competition dataset and Lewis 60 dataset. The experimental results show that, compared with the existing efficient algorithms in current literatures, the proposed algorithm has higher efficiency and solution quality.
[1] EVEN S, ITAI A, SHAMIR A. On the complexity of time table and multi-commodity flow problems[C]//SFCS 1975:Proceedings of the 16th Annual Symposium on Foundations of Computer Science. Washington, DC:IEEE Computer Society, 2008:184-193. [2] MCCOLLUM B, SCHAERF A, PAECHTER B, et al. Setting the research agenda in automated timetabling:the second international timetabling competition[J]. Informs Journal on Computing, 2010, 22(1):120-130. [3] BURKE E K, MCCOLLUM B, MEISELS A, et al. A graph-based hyper-heuristic for educational timetabling problems[J]. European Journal of Operational Research, 2007, 176(1):177-192. [4] BATTISTUTTA M, SCHAERF A, URLI T. Feature-based tuning of single-stage simulated annealing for examination timetabling[J]. Annals of Operations Research, 2017, 252(2):239-254. [5] HOOSHMAND S, BEHSHAMEH M, HAMIDI O. A tabu search algorithm with efficient diversification strategy for high school timetabling problem[J]. International Journal of Computer Science & Information Technology, 2013, 5(4):21-34. [6] BURKE E K, ECKERSLEY A J, MCCOLLUM B, et al. Hybrid variable neighbourhood approaches to university exam timetabling[J]. European Journal of Operational Research, 2010, 206(1):46-53. [7] ABDELHALIM E A, EL KHAYAT G A. A Utilization-based Genetic Algorithm for solving the university timetabling problem (UGA)[J]. Alexandria Engineering Journal, 2016, 55(2):1395-1409. [8] THEPPHAKORN T, PONGCHAROEN P, HICKS C. An ant colony based timetabling tool[J]. International Journal of Production Economics, 2014, 149:131-144. [9] ALZAQEBAH M, ABDULLAH S. Artificial bee colony search algorithm for examination timetabling problems[J]. International Journal of Physical Sciences, 2011, 6(17):4264-4272. [10] AL-BETAR M A, KHADER A T. A harmony search algorithm for university course timetabling[J]. Annals of Operations Research, 2012, 194(1):3-31. [11] LEWIS R, PAECHTER B. Finding feasible timetables using group-based operators[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(3):397-413. [12] TUGA M, BERRETTA R, MENDES A. A hybrid simulated annealing with kempe chain neighborhood for the university timetabling problem[C]//Proceedings of the 6th IEEE/ACIS International Conference on Computer and Information Science. Piscataway, NJ:IEEE, 2007:400-405. [13] LIU Y K, ZHANG D F, CHIN F YL. A clique-based algorithm for constructing feasible timetables[J]. Optimization Methods & Software, 2011, 26(2):281-294. [14] MVHLENTHALER M, WANKA R. A novel event insertion heuristic for creating feasible course timetables[C]//Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling. Berlin:Springer, 2010:294-304. [15] CESCHIA S, GASPERO L D, SCHAERF A. Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem[J]. Computers & Operations Research, 2012, 39(7):1615-1624. [16] QAUROONI D, AKBARZADEH-T M-R. Course timetabling using evolutionary operators[J]. Applied Soft Computing, 2013, 13(5):2504-2514. [17] MVLLER T. ITC2007 solver description:a hybrid approach[J]. Annals of Operations Research, 2009, 172(1):429-446. [18] LÜ Z P, HAO J K. Adaptive tabu search for course timetabling[J]. European Journal of Operational Research, 2010, 200(1):235-244. [19] ABDULLAH S, TURABIEH H, MCCOLLUM B, et al. A hybrid metaheuristic approach to the university course timetabling problem[J]. Journal of Heuristics, 2012, 18(1):1-23. [20] BELLIO R, DI GASPERO L, SCHAERF A. Design and statistical analysis of a hybrid local search algorithm for course timetabling[J]. Journal of Scheduling, 2012, 15(1):49-61. [21] BELLIO R, CESCHIA S, DI GASPERO L, et al. Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem[J]. Computers & Operations Research, 2016, 65(C):83-92.
2019, Vol. 39 
