Abstract
University course timetabling problem (UCTP) is classified into combinatorial optimisation problems involving many criteria to be considered. Due to many conflict objectives or difference objective units, combining conflicting criteria into a single objective (weight sum approach) may not be the best way of optimisation. The UCTP is well known to be Non-deterministic Polynomial (NP)-hard problem, in which the amount of computational time required to find the solution increases exponentially with problem size. Solving the UCTP manually with/without course timetabling tool is extremely difficult and time consuming. A new multiple objective cuckoo search based timetabling (MOCST) tool has been developed in order to solve the multiple objective UCTP. The cuckoo search via Lévy flight (CSLF) and cuckoo search via Gaussian random walk (CSGRW) using the Pareto dominance approach were embedded in the MOCST program for determining the set of non-dominated solutions. Eleven datasets obtained from Naresuan University in Thailand were conducted in computational experiment. It was found that the CSLF outperformed the CSGRW for almost all datasets whilst the computational times required by the proposed methods were slightly difference.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Jat, S.N., Yang, S.: A guided search non-dominated sorting genetic algorithm for the multi-objective university course timetabling problem. In: Merz, P., Hao, J.-K. (eds.) EvoCOP 2011. LNCS, vol. 6622, pp. 1–13. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20364-0_1
Thepphakorn, T., Pongcharoen, P., Hicks, C.: Modifying regeneration mutation and hybridising clonal selection for evolutionary algorithms based timetabling tool. Math. Probl. Eng. 2015, 16 (2015)
Lutuksin, T., Pongcharoen, P.: Best-worst ant colony system parameter investigation by using experimental design and analysis for course timetabling problem. In: 2nd International Conference on Computer and Network Technology, ICCNT 2010, pp. 467–471 (2010)
Pongcharoen, P., Promtet, W., Yenradee, P., Hicks, C.: Stochastic optimisation timetabling tool for university course scheduling. Int. J. Prod. Econ. 112, 903–918 (2008)
MirHassani, S.A.: A computational approach to enhancing course timetabling with integer programming. Appl. Math. Comput. 175, 814–822 (2006)
Konak, A., Coit, D.W., Smith, A.E.: Multi-objective optimization using genetic algorithms: a tutorial. Reliab. Eng. Syst. Saf. 91, 992–1007 (2006)
Datta, D., Fonseca, C.M., Deb, K.: A multi-objective evolutionary algorithm to exploit the similarities of resource allocation problems. J. Sched. 11, 405–419 (2008)
Abdullah, S., Turabieh, H., McCollum, B., McMullan, P.: A multi-objective post enrolment course timetabling problems: a new case study. In: IEEE Congress on Evolutionary Computation (CEC 2010), pp. 1–7 (2010)
Beyrouthy, C., Burke, E.K., Landa-Silva, D., McCollum, B., McMullan, P., Parkes, A.J.: Towards improving the utilization of university teaching space. J. Oper. Res. Soc. 60, 130–143 (2009)
Yang, X.-S., Chien, S.F., Ting, T.O.: Computational intelligence and metaheuristic algorithms with applications. Sci. World J. 2014, 4 (2014)
Lewis, R.: A survey of metaheuristic-based techniques for university timetabling problems. OR Spectr. 30, 167–190 (2008)
Yang, X.-S., Deb, S.: Engineering optimisation by cuckoo search. Int. J. Math. Model. Numer. Optim. 1, 330–343 (2010)
Yang, X.-S.: Nature-Inspired Metaheuristic Algorithms, 2nd edn. Luniver Press, University of Cambridge, Cambridge (2010)
Teoh, C.K., Wibowo, A., Ngadiman, M.S.: An adapted cuckoo optimization algorithm and genetic algorithm approach to the university course timetabling problem. Int. J. Comput. Intell. Appl. 13, 1450002 (2014)
Li, X., Yin, M.: Modified cuckoo search algorithm with self adaptive parameter method. Inf. Sci. 298, 80–97 (2015)
Valian, E., Tavakoli, S., Mohanna, S., Haghi, A.: Improved cuckoo search for reliability optimization problems. Comput. Ind. Eng. 64, 459–468 (2013)
Yang, X.-S., Deb, S.: Multiobjective cuckoo search for design optimization. Comput. Oper. Res. 40, 1616–1624 (2013)
Thepphakorn, T., Pongcharoen, P., Hicks, C.: An ant colony based timetabling tool. Int. J. Prod. Econ. 149, 131–144 (2014)
Murray, K., Müller, T., Rudová, H.: Modeling and solution of a complex university course timetabling problem. In: Burke, E.K., Rudová, H. (eds.) PATAT 2006. LNCS, vol. 3867, pp. 189–209. Springer, Heidelberg (2007). doi:10.1007/978-3-540-77345-0_13
Ousterhout, J.K., Jones, K.: TCL and the TK Toolkit, 2nd edn. Addison-Wesley, New York (2009)
Thepphakorn, T., Pongcharoen, P.: Heuristic ordering for ant colony based timetabling tool. J. Appl. Oper. Res. 5, 113–123 (2013)
Khadwilard, A., Chansombat, S., Thepphakorn, T., Thapatsuwan, P., Chainate, W., Pongcharoen, P.: Application of firefly algorithm and its parameter setting for job shop scheduling. J. Ind. Technol. 8, 49–58 (2012)
Thepphakorn, T.: Solving complex university course timetabling using metaheuristics. Doctor of Philosophy, Department of Industrial Engineering, Faculty of Engineering, Naresuan University, Phitsanulok, Thailand (2016)
Khadwilard, A.: Multiple objective genetic algorithms for production scheduling in capital goods industries. Master of engineering, Department of Industrial Engineering, Faculty of Engineering, Naresuan University, Phitsanulok, Thailand (2007)
Acknowledgement
This work was partly supported by the Naresuan University Research Fund; grant number R2558C156.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Thepphakorn, T., Pongcharoen, P., Vitayasak, S. (2016). A New Multiple Objective Cuckoo Search for University Course Timetabling Problem. In: Sombattheera, C., Stolzenburg, F., Lin, F., Nayak, A. (eds) Multi-disciplinary Trends in Artificial Intelligence. MIWAI 2016. Lecture Notes in Computer Science(), vol 10053. Springer, Cham. https://doi.org/10.1007/978-3-319-49397-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-49397-8_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49396-1
Online ISBN: 978-3-319-49397-8
eBook Packages: Computer ScienceComputer Science (R0)