Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem
Examination timetabling problem is a nontrivial task due to its NP-hard nature as well as the involvement of numerous constraints. Moreover, solving capacitated examination timetabling is more challenging compared to uncapacitated one. This paper implements graph heuristic with hill climbing search...
| Main Authors: | , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English English |
| Published: |
2015
|
| Subjects: | |
| Online Access: | http://umpir.ump.edu.my/id/eprint/11072/1/Combination%20of%20Graph%20Heuristic%20with%20Hill%20Climbing%20Search%20for%20Solving%20Capacitated%20Examination%20Timetabling%20Problem.pdf http://umpir.ump.edu.my/id/eprint/11072/7/fskkp-ashis%20kumar%20mandal-combination%20of%20graph%20heuristic.pdf |
| _version_ | 1796990918579978240 |
|---|---|
| author | Ashis Kumar, Mandal M. N. M., Kahar |
| author_facet | Ashis Kumar, Mandal M. N. M., Kahar |
| author_sort | Ashis Kumar, Mandal |
| collection | UMP |
| description | Examination timetabling problem is a nontrivial task due to its NP-hard nature as well as the involvement of numerous constraints. Moreover, solving capacitated
examination timetabling is more challenging compared to uncapacitated one. This paper implements graph heuristic with hill climbing search to solve the capacitated examination timetabling considering partial examination assignment concepts. The algorithm starts with ordering all the exams according to graph heuristic approach and then partial exams are considered for construction. Afterwards, the qualities of these exams are improved using hill climbing search. The entire process continues until scheduling all the exams. The effects of different graph heuristic orderings and exam assignment values on the quality of the solutions are studied. We test the proposed approach on ITC2007 benchmark exam datasets which contains highly constraint capacitated datasets. Experimental results reveal that the approach is able to produce quality solutions for all datasets and competitive results with competition results. |
| first_indexed | 2024-03-06T11:58:38Z |
| format | Conference or Workshop Item |
| id | UMPir11072 |
| institution | Universiti Malaysia Pahang |
| language | English English |
| last_indexed | 2024-03-06T11:58:38Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | UMPir110722020-02-21T07:44:04Z http://umpir.ump.edu.my/id/eprint/11072/ Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem Ashis Kumar, Mandal M. N. M., Kahar QA76 Computer software Examination timetabling problem is a nontrivial task due to its NP-hard nature as well as the involvement of numerous constraints. Moreover, solving capacitated examination timetabling is more challenging compared to uncapacitated one. This paper implements graph heuristic with hill climbing search to solve the capacitated examination timetabling considering partial examination assignment concepts. The algorithm starts with ordering all the exams according to graph heuristic approach and then partial exams are considered for construction. Afterwards, the qualities of these exams are improved using hill climbing search. The entire process continues until scheduling all the exams. The effects of different graph heuristic orderings and exam assignment values on the quality of the solutions are studied. We test the proposed approach on ITC2007 benchmark exam datasets which contains highly constraint capacitated datasets. Experimental results reveal that the approach is able to produce quality solutions for all datasets and competitive results with competition results. 2015 Conference or Workshop Item PeerReviewed application/pdf en http://umpir.ump.edu.my/id/eprint/11072/1/Combination%20of%20Graph%20Heuristic%20with%20Hill%20Climbing%20Search%20for%20Solving%20Capacitated%20Examination%20Timetabling%20Problem.pdf application/pdf en http://umpir.ump.edu.my/id/eprint/11072/7/fskkp-ashis%20kumar%20mandal-combination%20of%20graph%20heuristic.pdf Ashis Kumar, Mandal and M. N. M., Kahar (2015) Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem. In: 4th International Conference on Software Engineering and Computer Systems (ICSECS 2015) , 19-21 August 2015 , Kuantan, Pahang. pp. 118-123.. http://dx.doi.org/10.1109/ICSECS.2015.7333095 |
| spellingShingle | QA76 Computer software Ashis Kumar, Mandal M. N. M., Kahar Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem |
| title | Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem |
| title_full | Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem |
| title_fullStr | Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem |
| title_full_unstemmed | Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem |
| title_short | Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem |
| title_sort | combination of graph heuristic with hill climbing search for solving capacitated examination timetabling problem |
| topic | QA76 Computer software |
| url | http://umpir.ump.edu.my/id/eprint/11072/1/Combination%20of%20Graph%20Heuristic%20with%20Hill%20Climbing%20Search%20for%20Solving%20Capacitated%20Examination%20Timetabling%20Problem.pdf http://umpir.ump.edu.my/id/eprint/11072/7/fskkp-ashis%20kumar%20mandal-combination%20of%20graph%20heuristic.pdf |
| work_keys_str_mv | AT ashiskumarmandal combinationofgraphheuristicwithhillclimbingsearchforsolvingcapacitatedexaminationtimetablingproblem AT mnmkahar combinationofgraphheuristicwithhillclimbingsearchforsolvingcapacitatedexaminationtimetablingproblem |