Document Type : Original Research Paper


Computer Engineering Department, Faculty of Engineering, University of Isfahan, Isfahan, Iran


Designing timetables, for example course timetables in an institute, is one of the most complicated and time-consuming challenges for personnel. Automating it, not only can help the personnel to manage their work better, but also can be considered as a desired sample to assess the ways of planning and to tackle the constraint satisfaction in artificial intelligence. In this paper, genetic algorithms are primarily studied and then it is applied for optimization of an imaginary faculty course timetable. The new designed algorithm is based on keeping the better chromosomes of the population and employing genetic operators on the others in order to improve the overall quality of genes. Some other amendments are also carried out to develop a more capable genetic algorithm for TT applications, compared to the standard one. According to the tests, the new GA algorithm will be more successful in generating high fidelity TTs which do not break any hard constraint. The proposed ideas, in this approach are applicable in other similar situations.


Main Subjects

[1] Carter M., A Comprehensive Course Timetabling and Student Scheduling System at the University of Waterloo, Lecture Notes in Computer Science, Vol. 2079, 2001, pp. 64-82. [2] Burke E., Elliman D., Wearer R., A Genetic Algorithm based University Timetabling System, Proceedings of the 2nd East-West International Conference on Computer Technologies in Education, 1994, pp. 35-40. [3] Russell S., Norvig P., Artificial Intelligence: A Modern Approach, 3 rd Ed., Prentice Hall, 2009. ]1 ]علیرضا مهدی، مقدمهای بر الگوریتم های ژنتیک و کاربردهای آن، ناقوس اندیشه، 4۱8۵ . [5] Goldberg D., Genetic Algorithms in Search, Optimization and Machine Learning, AddisonWelsy, 1998. [6] Whitely D., A Genetic Algorithm Tutorial, Journal of Statistics and Computing Vol. 4, 1994, pp. 65-85. [7] Rossi-Doria O., Paechter B, A Memetic Algorithm for University Course Timetabling, Proceedings of the CO2004 Conference, Lancaster, UK, 2004, p. 65. [8] Erben W., Keppler J., A Genetic Algorithm Solving a Weekly Course-timetabling Problem, Proceedings of The First International Conference on The Practice and Theory of Automated Timetabling, Edinburgh, UK, 1995, pp. 198-211. [9] Abramson D., Abela J., A Parallel Genetic Algorithm for Solving the School Timetabling Problem, Proceedings of the 15th Australian Computer Science Conference, Hobart, Australia, 1992, pp.101. [10] Abdullah S., Burke E., McCollum B., An Investigation of Variable Neighbourhood Search for University Course Timetabling, Proceedings of the 2nd Multidisciplinary Conference on Scheduling: Theory and Applications, 2005, pp. 413-427. [11] Vorac J., Vondrak I., Vlcek K., School Timetabling Using Genetic Algorithm, Technical Report, VSB-Technical University of Ostrava, Czech Republic, 2002. [12] Cooper T., Kingston J., The Complexity of Timetable Construction Problems, Lecture Notes in Computer Science, Vol. 1153, 1996, pp. 281-295. [13] Beligiannisa G., Moschopoulosa C., Kaperonisa G., Likothanassisa D., Applying Evolutionary Computation To The School Timetabling Problem: The Greek Case, Journal of Computers & Operations Research, Vol. 35, 2008, pp. 1265–1280. [14] Pillay N., Banzhaf W., An Informed Genetic Algorithm For The Examination Timetabling Problem, Journal of Applied Soft Computing, Vol. 10, 2010, pp. 457–467. [15] Wilke P., Ostler J., Benchmarking CurriculumBased Course Timetabling: Formulations, Data Formats, Instances, Validation, and Results, Proceedings of the 7th International Conference for the Practice and Theory of Automated Timetabling (PATAT'2008), Montreal, Canada, 2008. ]41 ]نیپولیتان ریچارد و نعیمیپور کیومرث، طراحی الگوریتم ها با شبه کدهای ++C ،جهاد دانشگاهی مشهد، 4۱84 ،صفحه 868