Call for Paper - January 2022 Edition
IJCA solicits original research papers for the January 2022 Edition. Last date of manuscript submission is December 20, 2021. Read More

Parallel Genetic Algorithm for High School Timetabling

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Sanjay R. Sutar, Rajan S. Bichkar
10.5120/ijca2017914851

Sanjay R Sutar and Rajan S Bichkar. Parallel Genetic Algorithm for High School Timetabling. International Journal of Computer Applications 170(6):1-5, July 2017. BibTeX

@article{10.5120/ijca2017914851,
	author = {Sanjay R. Sutar and Rajan S. Bichkar},
	title = {Parallel Genetic Algorithm for High School Timetabling},
	journal = {International Journal of Computer Applications},
	issue_date = {July 2017},
	volume = {170},
	number = {6},
	month = {Jul},
	year = {2017},
	issn = {0975-8887},
	pages = {1-5},
	numpages = {5},
	url = {http://www.ijcaonline.org/archives/volume170/number6/28071-2017914851},
	doi = {10.5120/ijca2017914851},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

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

  1. 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
  2. Alberto Colorni, Marco Dorigo and Vittorio Maniezzo, “Metaheuristics for Highschool Timetabling,” Computational Optimization and Applications- 9, pp. 275–298, 1998
  3. 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
  4. 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
  5. Alpay Alkan and Ender Ozcan, “Memetic Algorithms for Timetabling,” Congress on Evolutionary Computation (CEC), IEEE, 2003
  6. 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
  7. Rushil Raghavjee and Nelishia Pillay, “Evolving Solutions to the School Timetabling Problem,” World Congress on Nature & Biologically Inspired Computing (NaBIC), IEEE, 2009
  8. 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
  9. 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
  10. Michael Pimmer and Gunther R. Raidl, “A Timeslot-Filling Heuristic Approach to Construct High-School Timetables,” The 9th Metaheuristics International Conference, MIC, 2011
  11. 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
  12. George H.G. Fonseca and Haroldo G. Santos, “Memetic Algorithms for the High School Timetabling Problem,” IEEE Congress on Evolutionary Computation, México, 2013
  13. Nelishia Pillay, “A survey of school timetabling research,” Annals of Operation Research, 218:261–293, Springer Science Business Media, New York,2014
  14. 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
  15. 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
  16. 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.
  17. 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
  18. 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
  19. D.E.Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison-Wesley, 1989
  20. 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

Keywords

Simple Genetic Algorithm, Parallel Genetic Algorithm, Hard Timetabling, Repair