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!
|
| id |
my-usim-ddms-12866 |
|---|---|
| record_format |
uketd_dc |
| spelling |
my-usim-ddms-128662024-05-29T05:01:22Z Enhanced Intelligent Water Drops Algorithm for University Examination Timetabling Problems Bashar AbedAl Mohdi Talal AlDeeb 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. Universiti Sains Islam Malaysia 2016-05 Thesis en https://oarep.usim.edu.my/handle/123456789/12866 https://oarep.usim.edu.my/bitstreams/d178a41a-ab67-4b2a-b77d-383a62313382/download 8a4605be74aa9ea9d79846c1fba20a33 Universities and colleges Examinations Data processing |
| institution |
Universiti Sains Islam Malaysia |
| collection |
USIM Institutional Repository |
| language |
English |
| topic |
Universities and colleges Examinations Data processing |
| spellingShingle |
Universities and colleges Examinations Data processing Bashar AbedAl Mohdi Talal AlDeeb Enhanced Intelligent Water Drops Algorithm for University Examination Timetabling Problems |
| description |
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. |
| format |
Thesis |
| author |
Bashar AbedAl Mohdi Talal AlDeeb |
| author_facet |
Bashar AbedAl Mohdi Talal AlDeeb |
| author_sort |
Bashar AbedAl Mohdi Talal AlDeeb |
| title |
Enhanced Intelligent Water Drops Algorithm for University Examination Timetabling Problems |
| title_short |
Enhanced Intelligent Water Drops Algorithm for University Examination Timetabling Problems |
| title_full |
Enhanced Intelligent Water Drops Algorithm for University Examination Timetabling Problems |
| title_fullStr |
Enhanced Intelligent Water Drops Algorithm for University Examination Timetabling Problems |
| title_full_unstemmed |
Enhanced Intelligent Water Drops Algorithm for University Examination Timetabling Problems |
| title_sort |
enhanced intelligent water drops algorithm for university examination timetabling problems |
| granting_institution |
Universiti Sains Islam Malaysia |
| _version_ |
1812444658779815936 |