Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approach
The university course timetable problem (UCTP) is typically a combinatorial optimization problem. Manually achieving a useful timetable requires many days of effort, and the results are still unsatisfactory. unsatisfactory. Various states of art methods (heuristic, meta-heuristic) are used to satisf...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Baghdad, College of Science for Women
2021-12-01
|
| Series: | مجلة بغداد للعلوم |
| Subjects: | |
| Online Access: | https://bsj.uobaghdad.edu.iq/index.php/BSJ/article/view/6674 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850055208184315904 |
|---|---|
| author | Zahid Iqbal Rafia Ilyas Huah Yong Chan Naveed Ahmed |
| author_facet | Zahid Iqbal Rafia Ilyas Huah Yong Chan Naveed Ahmed |
| author_sort | Zahid Iqbal |
| collection | DOAJ |
| description | The university course timetable problem (UCTP) is typically a combinatorial optimization problem. Manually achieving a useful timetable requires many days of effort, and the results are still unsatisfactory. unsatisfactory. Various states of art methods (heuristic, meta-heuristic) are used to satisfactorily solve UCTP. However, these approaches typically represent the instance-specific solutions. The hyper-heuristic framework adequately addresses this complex problem. This research proposed Particle Swarm Optimizer-based Hyper Heuristic (HH PSO) to solve UCTP efficiently. PSO is used as a higher-level method that selects low-level heuristics (LLH) sequence which further generates an optimal solution. The proposed approach generates solutions into two phases (initial and improvement). A new LLH named “least possible rooms left” has been developed and proposed to schedule events. Both datasets of international timetabling competition (ITC) i.e., ITC 2002 and ITC 2007 are used to evaluate the proposed method. Experimental results indicate that the proposed low-level heuristic helps to schedule events at the initial stage. When compared with other LLH’s, the proposed LLH schedule more events for 14 and 15 data instances out of 24 and 20 data instances of ITC 2002 and ITC 2007, respectively. The experimental study shows that HH PSO gets a lower soft constraint violation rate on seven and six data instances of ITC 2007 and ITC 2002, respectively. This research has concluded the proposed LLH can get a feasible solution if prioritized. |
| format | Article |
| id | doaj-art-09dac7efccb14fc2a4a345373314fa96 |
| institution | DOAJ |
| issn | 2078-8665 2411-7986 |
| language | English |
| publishDate | 2021-12-01 |
| publisher | University of Baghdad, College of Science for Women |
| record_format | Article |
| series | مجلة بغداد للعلوم |
| spelling | doaj-art-09dac7efccb14fc2a4a345373314fa962025-08-20T02:52:02ZengUniversity of Baghdad, College of Science for Womenمجلة بغداد للعلوم2078-86652411-79862021-12-01184(Suppl.)10.21123/bsj.2021.18.4(Suppl.).1465Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approachZahid Iqbal0Rafia Ilyas1Huah Yong Chan2Naveed Ahmed3School of Computer Sciences, Universiti Sains Malaysia, 11800, Pulau Pinang, Malaysia. & Department of Computer Science, University of Gujrat, Gujrat, Pakistan. Department of Computer Science, University of Gujrat, Gujrat, Pakistan. School of Computer Sciences, Universiti Sains Malaysia, 11800, Pulau Pinang, MalaysiaDepartment of Computer Science, University of Gujrat, GujratThe university course timetable problem (UCTP) is typically a combinatorial optimization problem. Manually achieving a useful timetable requires many days of effort, and the results are still unsatisfactory. unsatisfactory. Various states of art methods (heuristic, meta-heuristic) are used to satisfactorily solve UCTP. However, these approaches typically represent the instance-specific solutions. The hyper-heuristic framework adequately addresses this complex problem. This research proposed Particle Swarm Optimizer-based Hyper Heuristic (HH PSO) to solve UCTP efficiently. PSO is used as a higher-level method that selects low-level heuristics (LLH) sequence which further generates an optimal solution. The proposed approach generates solutions into two phases (initial and improvement). A new LLH named “least possible rooms left” has been developed and proposed to schedule events. Both datasets of international timetabling competition (ITC) i.e., ITC 2002 and ITC 2007 are used to evaluate the proposed method. Experimental results indicate that the proposed low-level heuristic helps to schedule events at the initial stage. When compared with other LLH’s, the proposed LLH schedule more events for 14 and 15 data instances out of 24 and 20 data instances of ITC 2002 and ITC 2007, respectively. The experimental study shows that HH PSO gets a lower soft constraint violation rate on seven and six data instances of ITC 2007 and ITC 2002, respectively. This research has concluded the proposed LLH can get a feasible solution if prioritized.https://bsj.uobaghdad.edu.iq/index.php/BSJ/article/view/6674Auto Timetable, Hyper Heuristic, Particle Swarm Optimizer |
| spellingShingle | Zahid Iqbal Rafia Ilyas Huah Yong Chan Naveed Ahmed Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approach مجلة بغداد للعلوم Auto Timetable, Hyper Heuristic, Particle Swarm Optimizer |
| title | Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approach |
| title_full | Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approach |
| title_fullStr | Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approach |
| title_full_unstemmed | Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approach |
| title_short | Effective Solution of University Course Timetabling using Particle Swarm Optimizer based Hyper Heuristic approach |
| title_sort | effective solution of university course timetabling using particle swarm optimizer based hyper heuristic approach |
| topic | Auto Timetable, Hyper Heuristic, Particle Swarm Optimizer |
| url | https://bsj.uobaghdad.edu.iq/index.php/BSJ/article/view/6674 |
| work_keys_str_mv | AT zahidiqbal effectivesolutionofuniversitycoursetimetablingusingparticleswarmoptimizerbasedhyperheuristicapproach AT rafiailyas effectivesolutionofuniversitycoursetimetablingusingparticleswarmoptimizerbasedhyperheuristicapproach AT huahyongchan effectivesolutionofuniversitycoursetimetablingusingparticleswarmoptimizerbasedhyperheuristicapproach AT naveedahmed effectivesolutionofuniversitycoursetimetablingusingparticleswarmoptimizerbasedhyperheuristicapproach |