The week's pick
Reseach Article
University Timetabling based on Hard Constraints using Genetic Algorithm
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 42 - Number 15 |
| Year of Publication: 2012 |
| Authors: Sanjay R. Sutar, Rajan S. Bichkar |
10.5120/5766-7964
|
Sanjay R. Sutar, Rajan S. Bichkar . University Timetabling based on Hard Constraints using Genetic Algorithm. International Journal of Computer Applications. 42, 15 ( March 2012), 1-7. DOI=10.5120/5766-7964
Abstract
The proposed system presents a novel approach of solving University timetabling which is NP-hard problem using Genetic Algorithm. Genetic Algorithm is frequently deployed Meta heuristics algorithm which can be effectively used to difficult combinatorial optimization problems. Although, there has been an extensive research towards this field but majority of the research results are much in its nascent stage. The previous researchers have used various methods like Tabu search, Simulated Annealing, network flow, graph coloring, etc. Genetic Algorithms are effective in solving many such optimization problems. The current work presented uses Genetic Algorithm to design an effective model for scheduling with challenging constraints considerations. The objective of the research is to create a model using Genetic Algorithm to the extent it can be used to generate the acceptable schedule using probabilistic operators like mutation and crossover. The design of the fitness function has considered the hard constraints. The simulation shows the better result in minimum time.
References
- Leonardo Aparecido Ciscon, Humberto Cesar Brandão de Oliveira, Michelle Cristina Alves Andrade, Guilherme Bastos Alvarenga, Ahmed Ali Abdalla Esmin, "The School Timetabling Problem: a focus on elimination of open periods and isolated classes", Hybrid Intelligent Systems, HIS'06, Sixth International Conference, Dec. 2006.
- A. Schaerf, "A Survey of Automated Timetabling", Journal Artificial Intelligence, Vol. 13, Issue 2, April 1999.
- Dilip Datta, Kalyanmoy Deb, Carlos M. Fonseca, "Solving Class Timetabling Problem of IIT Kanpur using Multi-Objective Evolutionary Algorithm", in NCRSME 2007 - National Conference of Research Scholars in Mechanical Engineering, (Kanpur, India), Mar. 2007.
- Andrea Schaerf, "Multi-Agent Systems for Optimization Problems: the University Course Timetabling Case Study", WOA, Rende (CS), Italy, July 5th, 2011.
- A. Chaudhuri, D. Kajal, ? "Fuzzy ?Genetic ?Heuristic ?for ?University ?Course ?Timetable ?Problem", ? ?Advance. Soft ?Computing ?Applications, Vol. 2, No. 1, March, 2010, ISSN 2074-8523; 2010.
- Anmar Abuhamdah, "Experimental Result of Late Acceptance Randomized Descent Algorithm for Solving Course Timetabling Problems", IJCSNS- International Journal of Computer Science and Network Security, Vol. 10 No. 1, January 2010.
- Burke, E. K. , Bykov, Y. , Newall, J. , Petrovic, S. , "A Time-Predefined Approach to Course Timetabling", Yugoslav Journal of Operation Research, pp. 139-151. , 2003.
- Edmund Burke, Adam Eckersley, Barry McCollum, Sanja Petrovic, Rong Qu, "Using Simulated Annealing to study behaviour of various Exam Timetabling data sets", The Fifth Metaheuristics International Conference, MIC, 2003.
- Luca Di Gaspero, Andrea Schaerf, "Tabu Search Techniques for Examination Timetabling", Proceeding PATAT '00, Selected papers from the Third International Conference on Practice and Theory of Automated Timetabling- III, 2001.
- E. Burke, K. Jackson, J. H. Kingston, R. Weare, "Automated University Timetabling: The State of the Art", Oxford Mathematics & Physical Sciences Computer Journal, Vol. 40, Issue 9, 565-571.
- URL: http://patat2012. com/information. html, Accessed on Nov-15, 2011.
- URL: http://www. utwente. nl/en, Accessed on Nov-15, 2011.
- Ruibin Bai, Jacek Blazewicz, Edmund K Burke, Graham Kendall, Barry McCollum, "A Simulated Annealing Hyper-heuristic Methodology for Flexible Decision Support", Computer Science Technical Report, 2007.
- Tunçhan Cura, "Timetabling Of Faculty Lectures Using Simulated Annealing Algorithm", Istanbul University, 2007.
- M. Nandhini , Dr. S. Kanmani, "A Survey of Simulated Annealing Methodology for University Course Timetabling", International Journal of Recent Trends in Engineering, Vol. 1, No. 2, May 2009.
- Baki Koyuncu, Mahmut Seçir,"Student Time Table by Using Graph Coloring Algorithm", retrieved from http://www. emo. org. tr/ekler/76e76856c7fea3b_ek. pdf, 2007.
- Nasser R. Sabar, Masri Ayob, Graham Kendall, Rong Qu, "Roulette wheel Graph Colouring for Solving Examination Timetabling Problems", COCOA- 2009, 463-470.
- Dr. Cauvery N. K. , "Timetable Scheduling using Graph Coloring", International Journal of P2P Network Trends and Technology, Vol. 1, Issue2- 2011.
- Ho Sheau Fen, Safaai-Deris, Siti Zaiton-Mohd Hashim, "Investigating Constraint-Based Reasoning for University Timetabling Problem", Proceedings of the International Multi Conference of Engineers and Computer Scientists, Vol. 1, IMECS, March 18 - 20, 2009.
- Ender Özcan, Alpay Alkan, "A Memetic Algorithm for Solving a Timetabling Problem: An Incremental Strategy", MISTA 2007.
- Nguyen Quoc Viet Hung, Ta Quang Binh, Duong Tuan Anh, "A Memetic Algorithm for Timetabling", Research Informatics Vietnam-Francophony, Can Tho, Vietnam, 289 – 294, February, 2005.
- Luca Di Gaspero, Andrea Schaerf, "Tabu search techniques for examination timetabling". In E. Burke and W. Erben, editors, Practice and Theory of Automated Timetabling, Vol. 2079, Lecture Notes in Computer Science, pages 104-117. Springer Verlag, Berlin-Heidelberg, Germany, 2001.
- Jean-François Cordeau, Brigitte Jaumard, Rodrigo Morales, "Efficient Timetabling Solution with Tabu Search", International Timetable Competition, 2003.
- Ben Paechter, "A Conflict Tabu Search Evolutionary Algorithm for Solving Constraint Satisfaction Problems". In Proceedings: EvoCOP, 2008.
- Aldy Gunawan, Kien Ming Ng, "Solving the Teacher Assignment Problem by Two Metaheuristics", International Journal of Information and Management Sciences (2011), 73-86.
- Kimmo Nurmi, Jari Kyngäs, "A Framework for School Timetabling Problem", MISTA- 2007.
- P. Cote, T. Wong and R. Sabouri, "Application of a hybrid multi-objective evolutionary algorithm to the uncapacitated exam proximity problem", In: E. K. Burke and M. Trick (eds. ) ,Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling, Springer, Lecture Notes in Computer Science, Vol. 3616, 151-168.
- K. Sheibani, "An evolutionary approach for the examination timetabling problems", In: E. K. Burke and P. De Causmaecker (eds. ), Proceedings of the 4th International Conference on Practice and Theory of Automated Timetabling, August, 2002, Belgium, 387-396.
- W. Erben, "A grouping Genetic Algorithm for graph colouring and exam timetabling",PATAT: Selected Papers from the 3rd International Conference, Springer, Lecture Notes in Computer Science, Vol. 2079, 132-156.
Index Terms
Keywords