The week's pick
Random Articles
Reseach Article
Parallel Genetic Algorithm for High School Timetabling
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 170 - Number 6 |
| Year of Publication: 2017 |
| Authors: Sanjay R. Sutar, Rajan S. Bichkar |
10.5120/ijca2017914851
|
Sanjay R. Sutar, Rajan S. Bichkar . Parallel Genetic Algorithm for High School Timetabling. International Journal of Computer Applications. 170, 6 ( Jul 2017), 1-5. DOI=10.5120/ijca2017914851
Abstract
The high school timetabling problem is a combinatorial optimization problem, proved to be NP-hard. It is a task to assign class–teacher interactions to rooms and timeslots of a weekly schedule. The nature of the problem varies depending on the region and institution. It has several hard and soft constraints. It means finding an assignment, such that no hard constraints are violated and the number of violations of soft constraints is minimized. Large and complex high school timetabling problem taken from real life, often takes long time to do manually. Hence, automated timetabling has attracted researchers since 1980s and many techniques have been proposed to solve it. Genetic Algorithm can be effectively used to solve such difficult problem. We propose the Parallel Genetic Algorithm (PGA) with customized operators and probabilistic repair to solve “hard timetabling” test problems hdtt4, hdtt5 and hdtt6 given by Professor Kate Smith-Miles in OR-Library. The optimal objective function for each of these problems is no clashes and fulfilling teacher’s workload on each class in given room. The functions are designed for intelligent operators and repair. The PGA consisting operators augmented with problem specific knowledge and probabilistic repair in crossover converges faster than Simple Genetic Algorithm (SGA) and give solution within few seconds. The results are compared with the recent work carried out using different methodologies on same data set.
References
- D. Abramson and J. Abela, “A Parallel Genetic Algorithm for Solving the School Timetabling Problem,” Appeared in 15th Australian Computer Science Conference, pp. 1-11, Hobart, February, 1992
- Alberto Colorni, Marco Dorigo and Vittorio Maniezzo, “Metaheuristics for Highschool Timetabling,” Computational Optimization and Applications- 9, pp. 275–298, 1998
- Andrea Schaerf, “Local Search Techniques for Large High School Timetabling Problems,” IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, Vol. 29, No. 4, July, 1999
- Adora E. Calaor, Augusto Y. Hermosilla and Bobby O. Corpus Jr., “Parallel Hybrid Adventures with Simulated Annealing and Genetic Algorithms,” Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN), IEEE, 2002
- Alpay Alkan and Ender Ozcan, “Memetic Algorithms for Timetabling,” Congress on Evolutionary Computation (CEC), IEEE, 2003
- Leonardo Aparecido Ciscon, Humberto Cesar Brandao de Oliveira, Michelle Cristina Alves Andrade, Guilherme Bastos Alvarenga and Ahmed Ali Abdalla Esmin, “The School Timetabling Problem: a focus on elimination of open periods and isolated classes,” Proceedings of the 6th International Conference on Hybrid Intelligent Systems (HIS), IEEE, 2006
- Rushil Raghavjee and Nelishia Pillay, “Evolving Solutions to the School Timetabling Problem,” World Congress on Nature & Biologically Inspired Computing (NaBIC), IEEE, 2009
- Nedim Srndic, Emir Pandzo, Mirza Dervisevic and Samim Konjicija, “The Application of a Parallel Genetic Algorithm to Timetabling of Elementary School Classes- A Coarse Grained Approach,” 22nd International Symposium on Information, Communication and Automation Technologies, IEEE, 2009
- Eugene Ruben Ramirez, “Using Genetic Algorithms to Solve High School Course Timetabling Problems,” A Thesis Presented to the Faculty of San Diego State University in Partial Fulfillment of the Requirements for the Degree, Master of Science in Computer Science, 2010
- Michael Pimmer and Gunther R. Raidl, “A Timeslot-Filling Heuristic Approach to Construct High-School Timetables,” The 9th Metaheuristics International Conference, MIC, 2011
- Nelisha Pillay, “A Comparative Study of Hyper-Heuristics for Solving the School Timetabling Problem,” Proceedings of the South African Institute for Computer Scientists and Information Technologists Conference, (SAICSIT’13), pp. 278-285, 2013
- George H.G. Fonseca and Haroldo G. Santos, “Memetic Algorithms for the High School Timetabling Problem,” IEEE Congress on Evolutionary Computation, México, 2013
- Nelishia Pillay, “A survey of school timetabling research,” Annals of Operation Research, 218:261–293, Springer Science Business Media, New York,2014
- R. Raghavjee and N Pillay, “A genetic algorithm selection perturbative hyper-heuristic for solving the school timetabling problem,” Orion Journal, Vol. 31 (1), pp. 39-60, 2015
- D. Abramson and H. Dang, "School timetables: a case study in simulated annealing: sequential and parallel algorithms," Lecture Notes in Economics and Mathematics Systems, V.Vidal(Ed.), Springer-Verlag Berlin, Chapter 5, pp. 103-124, 1993
- M. Randall, D. Abramson and C. Wild, "A general meta-heuristic based solver for combinatorial optimization problems," Technical report TR99-01, School of Information Technology, Bond University, Queensland, Australia.
- K. A. Smith, D. Abramson and D. Duke, "Hopfield neural networks for timetabling: formulations, methods, and comparative results," Computers and Industrial Engineering, Vol. 44, No. 2, pp. 283-305, 2003
- Matthew Wall, “GAlib: A C++ Library of Genetic Algorithm Components,” Version 2.4, Documentation Revision B, August, 1996, (http://lancet.mit.edu/ga/), Massachusetts Institute of Technology (MIT) (c) 1995-1996, Matthew Wall (c) 1996-2005
- D.E.Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison-Wesley, 1989
- Sanjay R. Sutar, Rajan S. Bichkar, “Genetic Algorithms based Timetabling using Knowledge Augmented Operators”, International Journal of Computer Science and Information Security, (1947-5500), pp.570-579, Vol.14, No.11, 2016
Index Terms
Keywords