Constructive Initialization of a Genetic Algorithm for the Solution of a Highly Constrained Departmental Timetabling Problem
Peter. U. Eze1, Dawn. C. Walker2, Ifeyinwa E. Achumba3
1Peter. U. Eze, Department of Computer Science, University of Sheffield, Sheffield S10 2TN, United Kingdom, Europe.
2Dr. Dawn. C. Walker, Department of Computer Science, University of Sheffield, Sheffield S10 2TN, United Kingdom, Europe.
3Dr. Ifeyinwa E. Achumba, Department of Electrical & Electronic Engineering, Federal University of Technology Owerri, Imo State, Nigeria.
Manuscript received on July 15, 2016. | Revised Manuscript received on July 25, 2016. | Manuscript published on September 05, 2016. | PP: 18-25 | Volume-6 Issue-4, September 2016. | Retrieval Number: C2855076316/2016©BEIESP
Open Access | Ethics and Policies | Cite | Mendeley
© The Authors. Published By: Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: The University or Departmental Timetabling Problem (UTP or DTP) is a scheduling problem ridden with numerous constraints. Each of the constraints has a complex effect on the ideal solution and their combined effect makes the problem harder to solve. As a solution to this problem, a genetic algorithm (GA) approach was augmented by a process of constructive initialisation and applied to an exemplar scheduling problem in the Department of Computer Science at the University of Sheffield. The problem entailed scheduling of timetabled slots for 33 modules across a range of taught programmes at various levels, delivered by 29 lecturers in 10 lecture theatres and 6 laboratories. A total of eight hard constraints and four soft constraints were considered, for problems of five levels of increasing complexity. It was found that the synergistic solution satisfied all the hard constraints, achieved up to 75% optimisation of the soft constraints, and converged within 500 iterations or an average of 2.74 minutes. These results indicate that the GA, when combined with constructive initialization, will give efficient solution to the DTP problem with constrained variables.
Keywords: Departmental Timetabling Problem, Constructive Initialization, Genetic Algorithm, Scheduling, Constraints