No Access

AN ADAPTED CUCKOO OPTIMIZATION ALGORITHM AND GENETIC ALGORITHM APPROACH TO THE UNIVERSITY COURSE TIMETABLING PROBLEM

Department of Computer Science, Faculty of Computing, Universiti Teknologi Malaysia, 81310, UTM, Johor Bahru, Johor, Malaysia

Search for more papers by this author

ANTONI WIBOWO

Department of Computer Science, Faculty of Computing, Universiti Teknologi Malaysia, 81310, UTM, Johor Bahru, Johor, Malaysia

Search for more papers by this author

, and

MOHD. SALIHIN NGADIMAN

Department of Computer Science, Faculty of Computing, Universiti Teknologi Malaysia, 81310, UTM, Johor Bahru, Johor, Malaysia

Search for more papers by this author

https://doi.org/10.1142/S1469026814500023Cited by:10 (Source: Crossref)

Abstract

The university course timetabling problem is an NP-hard and NP-complete problem concerned with assigning a specific set of events and resources to timeslots under a highly-constrained search space. This paper presents a novel metaheuristic algorithm entitled adapted cuckoo optimization algorithm which is derived from the cuckoo optimization algorithm and cuckoo search algorithm. This algorithm includes features such as local random walk on discrete data which mimics the behavior of Lévy flights and an Elitism-based mechanism which echoes back the best candidate solutions and prevents the algorithm from plunging into a curse of dimensionality. The algorithm was tested on a problem instance gathered from a University in Malaysia and the results indicate that the proposed algorithm exhibits very promising results in terms of solution quality and computational speed when compared to genetic algorithms.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in artificial intelligence!

References

V. A. Bardadym, Computer aided school and university timetabling: The new wave, in Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling, eds. E. K. Burke and P. Ross, Edinburgh August/September 1995, Lecture Notes in Computer Science, Vol. 1153 (Springer, 1996), pp 22–45 . Google Scholar
N. A. Ismayilova, M. Sağir and R. N. Gasimov, Math. Comput. Model. 46(8), 1017 (2007), DOI: 10.1016/j.mcm.2007.03.012. Crossref, Google Scholar
E. K. Burke, D. G. Elliman and R. F. Weare, J. Res. Comput. Educ 27(1), 1 (1994). Crossref, Google Scholar
E. K. Burke, D. G. Elliman and R. F. Weare, A hybrid genetic algorithm for highly constrained timetabling problems, Proc. 6th Int. Conf. Genetic Algorithms (ICGA95) (1995) pp. 605–610. Google Scholar
R. Lewis, OR Spectr. 30(1), 167 (2007), DOI: 10.1007/s00291-007-0097-0. Crossref, Google Scholar
O. Rossi-Doriaet al., Practice and Theory of Automated Timetabling IV 2740, eds. E. K. Burke and P. De Causmaecker (Springer, Berlin, 2002) pp. 329–351. Google Scholar
E. Aycan and T. Ayav, Solving the course scheduling problem using simulated annealing, IEEE Int. Advance Computing Conf. (IACC) (2009) pp. 6–7. Google Scholar
D. Zhanget al., Eur. J. Oper. Res. 203(3), 550 (2010), DOI: 10.1016/j.ejor.2009.09.014. Crossref, Google Scholar
D. F. Shiau, Expert Syst. Appl. 38(1), 235 (2011), DOI: 10.1016/j.eswa.2010.06.051. Crossref, Google Scholar
M. Tahar, Int. J. 2(6), 1 (2010). Google Scholar
Z. Lü and J. K. Hao, Eur. J. Oper. Res. 200(1), 235 (2010). Crossref, Google Scholar
M. P. Carrasco and M. V. Pato, Eur. J. Oper. Res. 153(1), 65 (2004), DOI: 10.1016/S0377-2217(03)00099-7. Crossref, Google Scholar
A. Chaudhuri and K. De, Int. J. Adv. Soft Comput. Appl. 2(1), 100 (2010). Google Scholar
A. Gunawan, K. M. Ng and K. L. Poh, Comput. Oper. Res. 39(12), 3074 (2012), DOI: 10.1016/j.cor.2012.03.011. Crossref, Google Scholar
M. Kohshoriet al., Int. J. Comput. Sci. 9(2), 446 (2012). Google Scholar
J. H. Holland , Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence ( University of Michigan Press , 1975 ) . Google Scholar
J. Brownlee , Clever Algorithms: Nature-Inspired Programming Recipes ( Lulu Enterprises , 2011 ) . Google Scholar
P. Civicioglu and E. Besdok, Artif. Intell. Rev. 39, 315 (2011), DOI: 10.1007/s10462-011-9276-0. Crossref, Google Scholar
G. N. Beligianniset al., Comput. Oper. Res. 35(4), 1265 (2008), DOI: 10.1016/j.cor.2006.08.010. Crossref, Google Scholar
C. K. Teoh, A. Wibowo and M. S. Ngadiman, Artif. Intell. Rev. (2013), DOI: 10.1007/s10462-013-9399-6. Google Scholar
X. S. Yang and S. Deb, Cuckoo search via Lévy flights, World Congr. Nature and Biologically Inspired Computing (NaBIC 2009) (Coimbatore, India, 2009) pp. 210–214. Google Scholar
R. Rajabioun, Appl. Soft Comput. 11(8), 5508 (2011), DOI: 10.1016/j.asoc.2011.05.008. Crossref, Google Scholar
X. S. Yang and S. Deb, Comput. Oper. Res. 40(6), 1616 (2013), DOI: 10.1016/j.cor.2011.09.026. Crossref, Google Scholar
M. Tuba, M. Subotic and N. Stanarevic, Modified cuckoo search algorithm for unconstrained optimization problems, Proc. 5th European Conf. European Computing Conf. (Paris, France, 2011) pp. 263–268. Google Scholar
M. Prakash, K. R. Jothi and A. Vigneshwaran, Int. J. Comput. Sci. Telecommun. 3(2), 65 (2012). Google Scholar
K. Chandrasekaran and S. P. Simon, Swarm Evol. Comput. 5, 1 (2012), DOI: 10.1016/j.swevo.2012.01.001. Crossref, Google Scholar
S. Sivanandam and S. Deepa, Introduction to Genetic Algorithms (Springer, 2007) pp. 15–60. Google Scholar
R. E. Bellman , Dynamic Programming ( Princeton University Press , Princeton, NJ , 1957 ) . Google Scholar