CFP last date
16 December 2024
Call for Paper
January Edition
IJAIS solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 16 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Ordered Frequent Itemsets Matrix Based On Fp-Tree Structure And Apriori Algorithm

Abdulkader M. Al-Badani Abdualmajed A. Al-Khulaidi
Random Articles
Reseach Article

Development of a Modified Simulated Annealing to School Timetabling Problem

by Odeniyi, O. A., Omidiora, E. O., Olabiyisi, S. O., Aluko, J. O.
journal cover thumbnail

International Journal of Applied Information Systems
Foundation of Computer Science (FCS), NY, USA
Volume 8 - Number 2
Year of Publication: 2015
Authors: Odeniyi, O. A., Omidiora, E. O., Olabiyisi, S. O., Aluko, J. O.
10.5120/ijais14-451277

Odeniyi, O. A., Omidiora, E. O., Olabiyisi, S. O., Aluko, J. O. . Development of a Modified Simulated Annealing to School Timetabling Problem. International Journal of Applied Information Systems. 8, 2 ( January 2015), 16-24. DOI=10.5120/ijais14-451277

@article{ 10.5120/ijais14-451277,
author = { Odeniyi, O. A., Omidiora, E. O., Olabiyisi, S. O., Aluko, J. O. },
title = { Development of a Modified Simulated Annealing to School Timetabling Problem },
journal = { International Journal of Applied Information Systems },
issue_date = { January 2015 },
volume = { 8 },
number = { 2 },
month = { January },
year = { 2015 },
issn = { 2249-0868 },
pages = { 16-24 },
numpages = {9},
url = { https://www.ijais.org/archives/volume8/number2/708-1277/ },
doi = { 10.5120/ijais14-451277 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-07-05T18:58:42.240306+05:30
%A Odeniyi
%A O. A.
%A Omidiora
%A E. O.
%A Olabiyisi
%A S. O.
%A Aluko
%A J. O.
%T Development of a Modified Simulated Annealing to School Timetabling Problem
%J International Journal of Applied Information Systems
%@ 2249-0868
%V 8
%N 2
%P 16-24
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This work presents a modified simulated annealing applied to the process of solving a typical high school timetabling problem. Preparation of a high school timetable consists basically of fixing a sequence of meetings between teachers and students in a prefixed period of time in such a way that a certain set of constraints of various types is satisfied. The approach presented in the paper has been successfully used to schedule the first time school timetable of Fakunle Comprehensive High School, Osogbo Nigeria during the 2012/2013 session and it was capable of generating timetables for complex problem instances. A task involving 18 Classes, 45 Teachers and 15 Subjects for Junior Secondary School (JSS) with 3 Levels (JSS 1 to JSS 3), and 6 arms each; and 24 Classes, 77 Teachers and 19 Subjects for Senior Secondary School (SSS), with 3 Levels (SSS 1 to SSS 3), and 8 arms (3 for Science Group, 3 for Commercial Group, and 2 for Art Group), for 6 hours, 5 days respectively. The use of the implemented model resulted in significant time saving in the scheduling of the timetables, and a well spread lessons for the teachers. Also none of the teachers and classes was double booked. It was clearly evident that the developed modified simulated annealing reduces the major weakness of slow convergence (convergence at excessive time) associated with the classical simulated annealing.

References
  1. Burke, E. K. and De Causmaecker, P. 2003. The Practice and Theory of Automated Timetabling: Selected Papers from the 4th International Conference. Lecture Note in Computer Science, Berlin: Springer-Verlag, Vol. 2740.
  2. Burke, E. K. and Trick, M. 2005. The Practice and Theory of Automated Timetabling V: Revised Papers from the 5th International Conference, Pittsburgh 2004. Lecture Note in Computer Science, Berlin: Springer-Verlag, vol. 3616.
  3. Gunawan, A. and Ng, K. M. 2011. Solving the Teacher Assignment Problem by Two Metaheuristics. International Journal of Information and Management Sciences, Vol. 22, pp. 73-86.
  4. Kwan, R. S. K. 2004. Bus and train driver scheduling. In: J. Leung (Ed. ), Handbook of Scheduling: Algorithms, Models and Performance. CRC Press, Boca Raton, Chapter 51.
  5. Burke, E. K. , De Causmaecker, P. and Berghe, V. G. 2004. Novel metaheuristic approaches to nurse rostering problems in Belgian hospitals. In: J. Leung (Ed. ), Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman Hall/CRC Press, Vol. 44, pp. 1-18.
  6. Gunawan, A. and Lau, H. C. 2009. Master physician scheduling problem. In Proceedings of the 4th Multidisciplinary International Scheduling Conference, 10-12 August, Dublin, Ireland.
  7. Schonberger, J. , Mattfeld, D. C. and Kopfer, H. 2004. Memetic algorithm timetabling for noncommercial sport leagues. European Journal of Operational Research, Vol. 153, No. 1, pp. 102-116.
  8. Tsuchiya, K. and Takefuji, Y. 1997. A neural network parallel algorithm for meeting scheduling problems. Applied Intelligence, Vol. 7, No. 3, pp. 205-213.
  9. Burke, E. K. and Rudova, H. 2007. The Practice and Theory of Automated Timetabling: Selected Papers from the Sixth International Conference. Lecture Note in Computer Science, Berlin: Springer-Verlag.
  10. Burke, E. K. , MacCarthy, B. L. , Petrovic, S. and Qu, R. 2006. Multiple retrieval case-based reasoning for course timetabling problems. Journal of Operations Research Society (JORS), Vol. 57, No. 2, pp. 148-162.
  11. Mccollum, B. 2006. University timetabling: bridging the gap between research and practice. In: E. H. R. Burke (Ed. ), Proceedings of the 6th International Conference on Practice and Theory of Automated Timetabling, pp. 15-35.
  12. Nurmi, K. and Kyngas, J. 2007. A framework for school timetabling problem. In Proceedings of 3rd Multidisciplinary International Scheduling Conference: Theory and Applications, Paris, pp. 386-393.
  13. Schaerf, A. 1995. A survey of automated timetabling, Technical Report CS-R9567. In Centrum Voor Wiskundeen Informatical Amsterdam, Netherlands, Vol. 115, pp. 33, ISSN: 0169-118X. .
  14. Post, G. , Ahmadi, S. , Daskalaki, S. , Kingston, J. H. , Kyngas, J. , Nurmi, C. , Ranson, D. and Ruizenaar, H. (2010). An XML format for benchmarks in high school timetabling. Retrieved from http://www. home. utwente. nl~postgf/BenchmarkSchoolTimetabling/. .
  15. De Werra, D. (1985). An introduction timetabling. European Journal of Operational Research, Vol. 19, No. 2, pp. 151-162.
  16. Abdennadher, S. and Marte, M. 2000. University course timetabling using constraint handling rules. Journal of Applied Artificial Intelligence, Vol. 14, No. 4, pp. 311-326.
  17. Mahar, K. 2006. Automatic generation of University timetables: an evolutionary approach. IADIS, ISBN: 972-8924-09-7.
  18. De Werra, D. 1996. Some combinatorial models for course scheduling. In: Lecture Note in Computer Science, Berlin: Springer-Verlag, Vol. 1153, pp. 296-308.
  19. Burke, E. and Carter, M. W. 1998. The Practice and Theory of Automated Timetabling: Selected Papers from the Second International Conference. Lecture Notes in Computer Science, Berlin: Springer-Verlag, Vol. 1408.
  20. Schaerf, A. 1999. A survey of automated timetabling. Artificial Intelligence Review, Vol. 13, No. 2, pp. 87-127.
  21. Petrovic, S. and Burke, E. K. 2004. University timetabling. In: J. Leung (Ed. ), Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapter 45, Chapman Hall/CRC Press.
  22. Qu, R. , Burke, E. K. , Mccollum B. , Merlot, L. T. G. and Lee, S. Y. 2006. A Survey of search methodologies and automated approaches for examination timetabling, Technical Report NOTTCS-TR-2006-4, School of CSiT, University of Nottingham, UK.
  23. Lewis, R. 2007. A survey of meta-heuristic based techniques for University timetabling problems. Operation Research (OR) Spectrum. Retrieved from http://www. w3schools. com/xml/ or http://en. wikipeda. org/wiki/xml.
  24. Wilke, P. , Grobner, M. and Oster, N. 2002. A hybrid genetic algorithm for school timetabling. In: B. Mckay and J. Slaney (Eds. ), Al2002: Advances in Artificial Intelligence, 15th Australlian Joint Conference on Artificial Intelligence, Canberra, Australia. Lecture Notes in Computer Science, Berlin: Springer-Verlag, Vol. 2557, pp. 455-464.
  25. Santos, H. G. , Ochi, L. S. and Souza, M. J. F. 2004. A tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem. In: Proceedings of the 5th International Conference on Practice and Theory of Automated Timetabling, Brazil, pp. 343-358
  26. Valouxis, C. and Housos, E. 2003. Constraint programming approach for school timetabling. Computers and Operations Research, Vol. 30, pp. 1555-1572.
  27. Abramson, D. , Krishnamoorthy, M. and Dang, M. H. 1996. Simulated annealing cooling schedules for the school timetabling problem. Asia-Pacific Journal of Operational Research, Vol. 16, pp. 1-22.
  28. Gunawan, A. and Ng, K. M. 2011. Solving the teacher assignment problem by two metaheuristics. International Journal of Information and Management Sciences, Vol. 22, pp. 73-86.
  29. Willemen, R. J. 2002. School timetable construction: Algorithm and complexity, Doctoral Thesis, Technical University Eindhoven, Netherlands.
  30. Burke, E. K. , MacCarthy, B. L. , Petrovic, S. and Qu, R. 2006. Multiple retrieval case-based reasoning for course timetabling problems. Journal of Operations Research Society (JORS), Vol. 57, No. 2, pp. 148-162.
  31. Myszkowski, P. and Norberciak, M. 2003. Evolutionary algorithms for timetable problems, Annales UMCS, Sectio Informatica, Lublin,Vol. I.
  32. Zahra, N. A. 2005. Hybrid heuristics for examination timetabling problem. Applied Mathematics and Computation, Vol. 163, No. 2, pp. 705-733.
  33. Kirkpatrick, S. , Gellatt, C. D. and Vecchi, M. P. 1983. Optimization by Simulated Annealing. Science, Vol. 220, No. 5, pp. 671-680.
  34. Cerny, V. 1985. A thermodynamic approach to the travelling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Application, Vol. 45, pp. 41-55.
  35. Eglese, R. W. 1990. Simulated annealing: A tool for operation research. European Journal of Operations Research, Vol. 46, pp. 271-281.
  36. Johnson, D. and C. , Mcgeoch, L. 1992. The travelling salesman problem: a case study in local optimization. In: E. H. Aarts and J. K. Lenstra (Eds. ), Local Search in Combinatorial Optimization. John Wiley and Sons, Chichester, England.
  37. Olabisiyi, S. O. , Omidiora, E. O. and Oyeleye, C. A. 2005. Asymptotic time complexity analysis for two dimensional object inspection using string matching. Science Focus, Nigeria, Vol. 10, No. 3, pp. 83-89.
  38. Olabiyisi, S. O. , Akanmu T. A. , Oyeleye, C. A. , Sabayo, O. D. and Adelana, J. B. 2007. Complexity analysis of a new edge-adaptive zooming algorithm for digital image. Journal of Res. Phys. Sci. , Vol. 3, No. 2, pp. 67-71.
  39. Omidiora, E. O. , Olabiyisi, S. O. , Arulogun, O. T. , Oyeleye, C. A. and Adegbola. A. 2009. A prototype of an access control system for a computer laboratory scheduling. AICTTRA 2009 Proceedings, Obafemi Awolowo University, Ile Ife, Nigeria, pp. 114-120.
  40. Oyeleye, C. A. , Olabiyisi, S. O. , Omidiora, E. O. , and Fagbola, T. 2014. Hybrid metaheuristic of simulated annealing and genetic algorithm for solving examination timetabling problem. International Journal of Computer Science and Engineering (IJCSE), ISSN(P):2278-9960, ISSN(E): 2278-9979, Vol. 3, Issue 5, (Sep. 2014), pp. 7-22.
  41. JanakiRam, D. , Screenivas, T. H. and Ganapathy S. K. 1996. Parallel simulated annealing algorithm. Journal of Parallel and Distributed Computing, Vol. 37, pp. 207-212.
  42. Thompson, J. M. and Dowsland, K. A. 1998. A robust simulated annealing based examination timetabling system. Computers and Operational Research, Vol. 25, No. 7/8, pp. 637-648.
  43. Hertz, A. and Widmer, M. 2003. Guidelines for the use of metaheuristics in combinatorial optimization. European Journal of Operational Research, Vol. 151, pp. 247-252
  44. Maniezzo, V. , Colorni, A. and Dorigo, M. 1995. Algodesk: an experimental comparison of eight evolutionary heuristics applied to the Quadratic Assignment Problem. European Journal of Operational Research, Vol. 81, No. 1, pp. 188-205.
  45. Newall, J. P. 1999. Hybrid methods for automated timetabling, Doctoral Thesis, Department of Computer Science, University of Nottingham, UK.
  46. Holland, J. H. 1975. Adaption in natural and artificial systems. University of Michigan Press, Ann Arbor, Michigan. (Reprinted by MIT Press, 1992).
  47. Glover, F. 1989. Tabu Search-Part I. ORSA Journal on Computing, Vol. 1, No. 3, pp. 190-206.
  48. Glover, F. 1990. Tabu Search-Part II. ORSA Journal on Computing, Vol. 2, No. 1, pp. 4-32.
  49. Bertsimas, D. and Tsitsiklis, J. 1993. Simulated annealing. Statistical Science, Vol. 8, No. 1, pp. 10-15.
  50. Yang, R. L. 2000. Convergence of the simulated annealing algorithm for continuous global optimization. Journal of Optimization Theory and Applications, Vol. 104, No. 3, pp. 691-716.
  51. Van Laarhoven, P. J. M. and Aarts, E. H. L. 1987. Simulated annealing: theory and applications. Dordrecht: D. Reidel Publishing Company, Kluwer Academic Publishers Group.
  52. Aarts, E. H. L and Korst, J. 1989. Simulated annealing and boltzmann machines. John Wiley and Sons, New York.
  53. Elmohamed, S. , Coddington, P. and Fox, G, 1998. A comparison of annealing techniques for academic course scheduling. In: E. Burke and M. Carter (Eds. ), The Practice and Theory of Automated Timetabling: Selected Papers from the Second International Conference. Lecture Notes in Computer Science. Berlin: Springer-Verlag, Vol. 1408, pp. 92-112.
  54. Dowsland, K. A. 1996. Simulated annealing solutions for multi-objective scheduling and timetabling. In: Modern Heuristic Search Methods. John Wiley and Sons, Chichester, England, pp. 155-166.
  55. Van Laarhoven, P. J. M. , Aarts, E. H. L. , and Lenstra, J. K. 1992. Job shop scheduling by simulated annealing. In Operation Research, Vol. 40, pp. 113-125.
  56. Allwright, James, R. A. and Carpenter, D. B. 1989. A distributed implementation of simulated annealing for the traveling salesman problem. Parallel Comput. Vol. 10, pp. 335-338.
  57. Abramson, D. 1992. A very high speed architecture for simulated annealing. IEEE Computer, pp. 27-36.
  58. Lam, J. and Delosme, J. M. 1988. An efficient simulated annealing schedule: implementation and evaluation, Report 8817, Department of Computer Science and Department of Electrical Engineering, Yale University.
  59. Johnson, D. , Aragon, C. , Mcgeoch, L. and Schevon, C. 1990. Optimization by simulated annealing: an experimental evaluation, Part 1: Graph Partitioning. Operational Research, Vol. 37, pp. 865-892.
  60. Johnson, D. , Aragon, C. , Mcgeoch L. and Schevon, C. 1991. Optimization by simulated annealing: an experimental evaluation, Part II: Graph Colouring and Number Partitioning. Operational Research, Vol. 39, pp. 378-406.
  61. Odeniyi, O. A. 2014. A modified simulated annealing approach for school timetabling. An unpublished M. Tech. Thesis, Ladoke Akintola University of Technology, Ogbomoso, Nigeria.
  62. Smith, K. A. , Abramson, D. and Duke, D. 2003. Hopfield neural networks for timetabling: Formulation, methods, and comparative results. Computers and Industrial Engineering, Vol. 44, No. 2, pp. 283-305.
  63. Kohonen J. 1999. A brief comparison of simulated annealing and genetic algorithm approaches. Term Paper for the Three Concepts Utility Course, Department of Computer Science, University of Helsinki.
  64. McCollum, B. 2006. University timetabling: bridging the gap between research and practice. In: E. H. R. Burke (Ed. ), Proceedings of the 6th International Conference on Practice and Theory of Automated Timetabling, pp. 15-35.
Index Terms

Computer Science
Information Sciences

Keywords

NP-Complete Constraint Satisfaction Combinatorial Optimization Scheduling Modified Simulated Annealing

Powered by PhDFocusTM