Enhanced Intelligent Water Drops Algorithm for University Examination Timetabling Problems
The University Examination Timetabling Problem (UETP) involves assigning a set of exams into a certain number of timeslots that are to a certain set of constraints. In spite of several techniques reported in the literature have been applied to solve the examination timetabling problem, the final s...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Subjects: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | The University Examination Timetabling Problem (UETP) involves assigning a set of exams into a certain number of timeslots that are to a certain set of constraints. In spite of
several techniques reported in the literature have been applied to solve the examination
timetabling problem, the final solution is not yet reached. This motivates the researchers
to investigate other methods. This thesis presents an investigation of using the Intelligent Water Drops (IWD) algorithm to construct and produce good quality solutions for
the UETP. The IWD is a recent metaheuristic population-based algorithm belonging to
the swarm intelligent category which simulates the dynamic of the river systems. The
main motivations for investigating IWD algorithm are: (i) IWD has been successfully employed to solve many optimization problems. (ii) The global search and fast convergence
ability of the intelligent water drops algorithm make it efficient to the problem (Noferesti
and Shah-Hosseini, 2012). (iii) It is a constructive-based meta-heuristic algorithm which
means, the solution is incrementally constructed (step by step) until the complete solution
is obtained (Noferesti and Shah-Hosseini, 2012). (iv) In addition, IWD has two variables
that have a large effect on the performance and the convergence of the algorithm (Alijla
et al., 2013). However, the IWD algorithm has not been investigated in terms of dealing
with the university timetabling problems.
The major objective of this study is to investigate the use of the IWD algorithm to generate good quality solutions with minimum penalty value for the UETP. First, the AdaptedIWD involves the modification of IWD operators in order to cope with the nature of UETP.
However, the Adapted-IWD algorithm has weaknesses in handling diversity and exploitation capability. This was addressed by modifying the Adapted-IWD. The modified
version is called Modified-IWD. The solution’s construction is modified using the concept
of global best operator that is used in the Particle Swarm Optimization (PSO). Although
the results of the Modified-IWD were very promising, the hybrid versions of IWD appear to achieve higher quality results. The purpose of using the hybrid version of IWD
(Hybrid-IWD) proposed is to improve the balance between exploration and exploitation
of the UETP’s search space. The three IWD algorithms proposed were tested on Carter
dataset.
The experimental results demonstrated that both the Modified-IWD and the HybridIWD performed better than the Adapted-IWD. In addition, the Hybrid-IWD obtained
seven best results in comparison with the best known results for the heuristic and the
hyper-heuristic approaches in the literature (the percentage of the improvement was between 0.1% and 4.43%. The Hybrid-IWD algorithm achieved the first rank by using the
Friedman test), three best results in comparison with the swarm intelligent approaches
(the percentage of the improvement was between 0.04% and 2.46% and the Hybrid-IWD
achieved the second rank), and achieved one best results (with the improvement of 0.01%
and second rank for the Hybrid-IWD) in comparison with the other metaheuristic approaches in the literature. A case study conducted with USIM Tamhidi programs to evaluate the Hybrid-IWD algorithm has produced a successful Tamhidi exam timetable in
comparison with manual approach. |
|---|