Meysam Shahvali Kohshori; Dariush Zeynolabedini; Mehrnaz Shirani Liri; Leila Jadidi

Multi Population Hybrid Genetic Algorithms for University Course Timetabling Problem

Full Text (PDF, 1325KB), PP.1-11

Views: 0 Downloads: 0

Author(s)

Meysam Shahvali Kohshori ^1,* Dariush Zeynolabedini ² Mehrnaz Shirani Liri ¹ Leila Jadidi ³

1. Deportment of Computer Engineering,Izeh Branch, Islamic Azad University, Izeh, Iran

2. Deportment of Computer Enginiering,Shoushtar Branch, Islamic Azad University, Shoushtar, Iran

3. Deportment of Computer Enginiering, Sama Technical and Vocation Training College, Islamic Azad University, Ahvaz Branch, Ahvaz, Iran

* Corresponding author.

DOI: https://doi.org/10.5815/ijitcs.2012.06.01

Received: 14 Jul. 2011 / Revised: 20 Dec. 2011 / Accepted: 13 Feb. 2012 / Published: 8 Jun. 2012

Index Terms

University course timetabling problem(UCTP), genetic algorithm, fuzzy logic, local search, heurestic

Abstract

University course timetabling is one of the important and time consuming issues that each University is involved with it at the beginning of each. This problem is in class of NP-hard problem and is very difficult to solve by classic algorithms. Therefore optimization techniques are used to solve them and produce optimal or near optimal feasible solutions instead of exact solutions. Genetic algorithms, because of multidirectional search property of them, are considered as an efficient approach for solving this type of problems. In this paper three new hybrid genetic algorithms for solving the university course timetabling problem (UCTP) are proposed: FGARI, FGASA and FGATS. In proposed algorithms, fuzzy logic is used to measure violation of soft constraints in fitness function to deal with inherent uncertainly and vagueness involved in real life data. Also, randomized iterative local search, simulated annealing and tabu search are applied, respectively, to improve exploitive search ability and prevent genetic algorithm to be trapped in local optimum. The experimental results indicate that the proposed algorithms are able to produce promising results for the UCTP.

Cite This Paper

Meysam Shahvali Kohshori, Dariush Zeynolabedini, Mehrnaz Shirani Liri, Leila Jadidi, "Multi Population Hybrid Genetic Algorithms for University Course Timetabling Problem", International Journal of Information Technology and Computer Science(IJITCS), vol.4, no.6, pp.1-11, 2012. DOI:10.5815/ijitcs.2012.06.01

Reference

[1]Abdullah S. “Heuristic Approaches for University Timetabling Problems”. PhD thesis, School of Computer Science and Information Technology, The University of Nottingham, United Kingdom, 2006.

[2]ShahvaliM., SanieeM., SajediH. “A fuzzy genetic algorithm with local search for university course timetabling”, pp.250-254, 2011.

[3]Yang S, Jat S. N. “Genetic algorithms with guided and local search strategies for university course timetabling”. IEEE Transactions on System, Man, and Cybernetics -PART C: Applications and Reviews, vol. 41, NO. 1, January, 2011.

[4]Abdullah S, Burke E. K, McCollum B. “Using a randomized iterative improvement algorithm with composite neighborhood structures”. Proceeding of 6th International Conference on Meta-heuristic, pp. 153–169, 2007.

[5]Chaudhuri A, De K. “Fuzzy Genetic Heuristic for University Course Timetable Problem”. International journal of Advance Soft Computing Application, Vol. 2, No. 1, March, .2010.

[6]Daskalaki S, BirbasT, Housos E. “An integer programming formulation for a case study in university timetabling”. European Journal of Operational Research, 153, 117–135, 2004.

[7]Khuri S, Walters T, Sugono Y. “A grouping genetic algorithm for coloring the edges of graphs”. Proceeding of the ACM/SIGAPP Symposium on Applied Computing, ACM Press, pp.422-427, 2000.

[8]White G, Xie B, Zonjic S. “Using tabu search with longer term memoryand relaxation to create examination timetables”. European Journal ofOperational Research, Vol.153, No.16, pp.80-91, 2004.

[9]Welsh D. J. A, Powell M. B. “The upper bound for the chromatic number of a graph and its application to timetabling problems”. The Computer Journal, vol. 11, pp. 41–47, 1967.

[10]Burke E. K, Kendall G, Soubeiga E. “A tabu-search hyper-heuristic for timetabling and rostering”. Journal of Heuristics. 9(6), pp 451-470, 2003.

[11]Smith KA, Abramson D, Duke D. “Hopfield neural networks for timetabling: formulations methods, and comparative results”. Computers andIndustrial Engineering,44(2):283–305, 2003.

[12]Cambazard H, Demazeau F, Jussien N, David P. “Interactively solving school timetabling problems using extensions of constraint programming”.Lecture notes in computer science, vol. 3616, Berlin: Springer;p. 190–207, 2005.

[13]Wren A. “Scheduling, Timetabling and rostering—a special relationship,the practice and theory of automated timetabling”. Lecture notes incomputer science, vol. 1153, Berlin: Springer, p. 46–76, 1996.

[14]Asmuni H, Burke E. K, Garibaldi J. M. “Fuzzy multiple heuristicordering for course timetabling”. Proceeding of the 5th United Kingdom Workshop on Computational Intelligence,London,pp. 302–309, 2005.

[15]Burke E. K., MacCloumn B., Meisels A., Petrovic S., and Qu R.“A Graph-based hyper heuristic for timetabling problems”.European J of Oper Research, 176: 177–192, 2006.

[16]Rossi-Doria O, Sampels M, Birattari M, Chiarandini M, DorigoM,Gambardella L, Knowles J,Manfrin M, Mastrolilli M, PaechterB,PaqueteL,St¨utzle T. “A comparison of the performance of differentmeta-heuristics on the timetabling problem”. Proceeding of 4th International Conference Practical Theory Automated Timetabling (Lecture Notes in Computer Science), vol. 2740, pp. 329–351.

[17]Socha K, Knowles J, Samples M. “A max-min ant system for the university course timetabling problem:. Proceeding of the 3rd International Workshop on Ant Algorithms, Lecture Notes in Computer Science, Springer Verlag, Vol.2463, pp.1-13, . 2002.

[18]Zervoudakis K, Stamatopoulos P. “A generic object-oriented constraint-based model for university course timetabling” .Proceeding of 3rdInternational Conference on the Practice and Theory of Automated Timetabling, Germany, Springer-Verlag. pp 28-47, 2001.

[19]Abdullah S., Burke E. K., and McCollum B.“A Hybrid EvolutionaryApproach to the University Course TimetablingProblem”. Proc of the 2007 IEEE Congres on EvolComput.,pp. 1764–1768, 2007.

[20]Alkan A., OzcanE..“Memetic algorithms for timetablingevolutionary computation”. Proc of the 2003 IEEE CongressonEvolComput., vol. 3, pp. 1796–1802, 2003.

[21]BroderS.“Final examination scheduling”. Comm of the ACM,7(8): 494–498, 1964.

[22]Ten Eikelder HMM, Willemen RJ. “Some complexity aspects of secondary school timetabling problems”. Lecture notes in computer science,vol. 2079, Berlin: Springer; p. 18–27, 2001.

[23]Papoutsis K, Valouxis C, Housos E. “A column generation approach for the timetabling problem of greek high schools”. Journal of the OperationalResearch Society, 54(3):230–8, 2003.

[24]Valouxis C, Housos E. “Constraint programming approach for school timetabling”. Computers and Operations Research, 30(10):1555–72, 2003.

[25]Caldeira JP, Rosa A. “School timetabling using genetic search”. In proceedings of the second international conference on the practice and theoryof automated timetabling (PATAT’97), p. 115–22, 1997.

[26]Fernandes C, Caldeira JP, Melicio F, Rosa AC. “Evolutionary algorithm for school timetabling”. InProceedings of the genetic and evolutionarycomputation conference (GECCO’ 99), vol. 2, p. 1777–83, 1999.

[27]Bufé M, et al. “Automated solution of a highly constrained school timetablingproblem-preliminary results”. Lecture notes in computer science, vol. 2037, Berlin: Springer; 2001. p. 431–40.

[28]Burke E. K.,LandaSilvaD. J.“The design of memetic

[29]algorithms for scheduling and timetabling problemsInN. Krasnogor, W. Hart, and J. Smith (eds.)”, Recent AdvancesinMemetic Algorithms, Studies in Fuzziness and Soft Computing,vol. 166, pp. 289–312, 2004.

[30]http://www.cs.qub.ac.uk/itc2007.

International Journal of Information Technology and Computer Science (IJITCS)