Document Type : Research Paper
Author
Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran
Abstract
This paper considers the problem of university course timetabling. In this problem, there are a set of courses, lecturers and classrooms. The objective is to assign schedule courses so as to maximize the total preference of lecturer-course, lecturer-day and course-day. The paper first formulates the problem in form of linear integer programming model. Using the model and commercial software, the small sized instances are optimally solved. Then, the paper proposes three different algorithms based on imperialist competitive algorithm, simulated annealing and variable neighborhood search. The algorithms employ several novel procedures such as encoding scheme, move operator, crossing operators. The algorithms are tuned and evaluated with optimal solutions found by the model. Then, they are evaluated by comparing their performance. The results show that imperialist competitive algorithm outperforms the other algorithms.
Keywords
Main Subjects
[1] Aladag, C.H., Hocaoglu, G., and Basaran M.A. (2009). “The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem”, Expert Systems with Applications, 36, pp. 12349–12356.
[2] Al-Yakoob, S.M., and Sherali, H.D. (2007). “A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations”, European Journal of Operational Research, 180, pp. 1028–1044.
[3] Bardadym, V.A. (1996). “Computer-aided school and university timetabling: The new wave”. In E. Burke and P. Ross (Eds.), Practice and theory of automated timetabling. Lecture notes in computer science, 1153, pp. 22–45. Berlin: Springer.
[4] Boland, N., Hughes, B.D., Merlot, L.T.G., and Stuckey P.J. (2008). “New integer linear programming approaches for course timetabling”, Computers and Operations Research, 35, pp. 2209–2233.
[5] Burke, E.K., Eckersley, A.J., McCollum, B., Petrovic, S., and Qu R. (2010). “Hybrid variable neighbourhood approaches to university exam timetabling”, European Journal of Operational Research, 206, pp. 46–53.
[6] Burke, E.K., McCollum, B., Meisels, A., Petrovic, S., and Qu, R. (2007). “A graph-based hyper-heuristic for educational timetabling problems”, European Journal of Operational Research, 176, pp. 177–192.
[7] Causmaecker, P.D., Demeester P., and Vanden Berghe, G. (2009). “A decomposed metaheuristic approach for a real-world university timetabling problem”, European Journal of Operational Research, 195, pp. 307–318.
[8] Daskalaki, S., and Birbas, T. (2005). “Efficient solutions for a university timetabling problem through integer programming”, European Journal of Operational Research, 160, pp. 106–120.
[9] Dimopoulou, M., and Miliotis, P. (2004). “An automated university course timetabling system developed in a distributed environment: A case study”, European Journal of Operational Research, 153, pp. 136–147.
[10] Flesza, K., and Hindi, K.S. (2004). “Solving the resource-constrained project scheduling problem by a variable neighborhood search”, European Journal of Operational Research, 155, pp. 402–413.
[11] Hansen, P., and Mladenovic, N. (2001). “Variable neighborhood search: principles and applications”, European Journal of Operational Research, 130, pp. 449–467.
[12] Liao, C.J., and Cheng, C.C. (2007). “A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date”, Computers and Industrial Engineering, 52, pp. 404–413.
[13] Lü, Z., and Hao, J.K. (2010). “Adaptive Tabu Search for course timetabling”, European Journal of Operational Research, 200, pp. 235–244.
[14] Teoh, C.K., Wibowo, A., and Ngadiman, M.S. (2013). Review of state of the art for metaheuristic techniques in Academic Scheduling Problems, Artificial Intelligence Review, 10.1007/s10462-013-9399-6.
[15] Mladenovic, N., and Hansen, P. (1997). “Variable neighborhood search”, Computers and Operations Research, 24, pp. 1097–1100.
[16] MirHassani, S.A. (2006). “A computational approach to enhancing course timetabling with integer programming”, Applied Mathematics and Computation, 175, pp. 814–822.
[17] MirHassani, S.A., and Habibi, F., (2013). Solution approaches to the course timetabling problem, Artificial Intelligence Review, 39, pp. 133-149.
[18] Shiau, D.F. (2011). “A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences”, Expert Systems with Applications, 38, pp. 235–248.
[19] Turabieh, H., Abdullah, S. (2011). “An integrated hybrid approach to the examination time tabling problem”, Omega, 39, pp. 598–607.
[20] Wang, Y.Z. (2002). “An application of genetic algorithm methods for teacher assignment problems”, Expert Systems with Applications, 22, pp. 295–302.
[21] Wang, Y.Z. (2003). “Using genetic algorithm methods to solve course scheduling problems”, Expert Systems with Applications, 25, pp. 39-50.
[22] Zhang, D., Liu, Y., M’Hallah, R., and Leung, S.C.H. (2010). “A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems”, European Journal of Operational Research, 203, pp. 550–558.
[23] Atashpaz-Gargari, E., and Lucas, C., (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congress Evolutionary Computers, Singapore, pp. 4661–4667.
[24] Atashpaz-Gargari, E., Hashemzadeh, F., Rajabioun, R., and Lucas, C., (2008). Colonial competitive algorithm, a novel approach for PID controller design in MIMO distillation column process. International Journal of Intelligent Computation and Cyberntic, 1, pp. 337–355.
[25] Bagher, M., Zandieh, M., and Farsijani, H., (2010). Balancing of stochastic U-type assembly lines: an imperialist competitive algorithm. International Journal of Advanced Manufacturing Technology, 54, pp. 271–285.
[26] Banisadr, A.H., Zandieh, M., and Mahdavi, I., (2013). A hybrid imperialist competitive algorithm for single-machine scheduling problem with linear earliness and quadratic tardiness penalties. International Journal of Advanced Manufacturing Technology, pp. 981-989.
[27] Zhou, W., Yan, J., Li, Y., Xia, C., and Zheng, J., (2013). Imperialist competitive algorithm for assembly sequence planning. International Journal of Advanced Manufacturing Technology, 67, pp. 2207-2216.
[28] Kolon, M., (1999). Some new results on simulated annealing applied to the job shop scheduling problem. European Journal of Operational Research, 113, pp. 123–136.
[29] Naderi, B., Zandieh, M., Khaleghi Ghoshe Balagh, A., and Roshanaei, V., (2009). “An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness”, Expert Systems with Applications, 36, pp. 9625–9633.
[30] Kahar, M.N.M., and Kendall, G. (2010). “The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution”, European Journal of Operational Research, 207, pp. 557–565.
)