Document Type : Research Paper
Authors
Abstract
In this research, optimization of examinations' timetable for university courses, based on a real problem in one of the universities in Iran is studied. The objective function defined for this problem is more practical and realistic than the other objective functions that have been utilized by previous researchers in literature and effectively reflects the real objective of the problem. In order to define the objective function, we have made use of Coulomb's law in electricity that says the magnitude of the electrostatic force of interaction between two point charges is directly proportional to the scalar multiplication of the magnitudes of the charges and inversely proportional to the square of the distance between them. We have defined a repulsive force between any pair of Examinations. The optimum solution is achieved when the sum of all forces is minimized. Hence, the obtained mathematical model is a non-linear programming with binary variables, similar to the quadratic assignment problem (QAP) which is an NP-Hard problem. This sort of problems can be solved exactly only if they are in small sizes. For solving this problem in medium and large scale, some methods are used based on Simulated Annealing (SA) algorithm and Imperialist Competitive algorithm (ICA). These algorithms can reach good sub-optimal solutions in a short period of time. Practical results of this mathematical model are already used in one of the national universities in Iran. The practical results demonstrate the high efficiency and effectiveness of this model.
Keywords
Ahandani, M., Baghmisheh, M., & BadamchiZadeh, M. (2012). Hybrid particle swarm optimization transplanted into a hyper-heuristic structure for solving examination timetabling problem. Swarm and Evolutionary Computation, 7, 21–34.
Alzaqebah M., & Abdullah, S. (2015). Hybrid bee colony optimization for examination timetabling problems. Computers & Operations Research, 54, 142–154.
Arbaoui, T., Boufflet, J., & Moukrim, A. (2013). An Analysis Framework for Examination Timetabling. Symposium on Combinatorial Search.
Burke, E., Eckersley, A., McCollum, B., Petrovic, S., & Qu, R. (2010). Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research, 206, 46–53.
Carter, M., Laporte, G., & Lee, S. (1996). Examination Timetabling: Algorithmic Strategies and Applications. Journal of the Operational Research Society, 47, 373-383.
Dersan C., Robert B., & Yu D. (2010). Applied Integer Programming, Modeling and Solution. John Wiley & Sons, Inc, 64_65.
Ei, S., & Nang, S. (2012). Hyper heuristic based on great deluge and its variants for exam timetabling problem. Journal of Artificial Intelligence & Applications, 1, 149–162.
Jingpeng, L., Ruibin, B., Yindong, S., & Rong, Q. (2015). Search with evolutionary ruin and stochastic rebuild: A theoretic framework and a case study on exam timetabling. European Journal of Operational Research, 242, 798–806.
Kahar, M., & Kendall, G. (2010). The examination timetabling problem at University Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution. European Journal of Operational Research, 207, 557–565.
05 مطالعات مدیریت صنعتی – سال پانزدهم، شماره 44 ، بهار 69
Komijan, A., & Koupaei, M., (2012). A new binary model for university examination timetabling: a case study. Journal of Industrial Engineering International, 8:28.
Masri, A., Hamdan, A., Salwani, A., Othman, Z., & Zakree, M. (2011). Intelligent Examination Timetabling Software. Procedia Social and Behavioral Sciences, 18, 600–608.
Obaid, O., MohdSharifuddin, A., Salama, A., & Mazin, A. (2012). Comparing Performance of Genetic Algorithm with Varying Crossover in Solving Examination Timetabling Problem. Journal of Emerging Trends in Computing and Information Sciences. 10, 1427–1434.
Pillay, N., & Banzhaf, W., (2010). An informed genetic algorithm for the examination timetabling problem. Applied Soft Computing, 10, 457–467.
Salwani, A., & Malek, A. (2013). A hybrid self-adaptive bees algorithm for examination timetabling problems. Applied Soft Computing, 13, 3608–3620.
Syariza, A., Andrzej, B., & Edmund, K. (2014). Adaptive linear combination of heuristic orderings in constructing examination timetables. European Journal of Operational Research, 232, 287–297.
Turabieh, H., & Abdullah, S. (2011). An integrated hybrid approach to the examination timetabling problem. Omega, 39, 598-607.
)