Addressing examination timetabling problem using a partial exams approach in constructive and improvement
The paper investigates a partial exam assignment approach for solving the examination timetabling problem. Current approaches involve scheduling all of the exams into time slots and rooms (i.e., produce an initial solution) and then continuing by improving the initial solution in a predetermined num...
Main Authors: | , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI
2020
|
Subjects: | |
Online Access: | http://umpir.ump.edu.my/id/eprint/28470/1/Addressing%20examination%20timetabling%20problem%20using%20a%20partial%20exams.pdf |
_version_ | 1796994084145987584 |
---|---|
author | Mandal, Ashis Kumar Kahar, M. N. M. Kendall, Graham |
author_facet | Mandal, Ashis Kumar Kahar, M. N. M. Kendall, Graham |
author_sort | Mandal, Ashis Kumar |
collection | UMP |
description | The paper investigates a partial exam assignment approach for solving the examination timetabling problem. Current approaches involve scheduling all of the exams into time slots and rooms (i.e., produce an initial solution) and then continuing by improving the initial solution in a predetermined number of iterations. We propose a modification of this process that schedules partially selected exams into time slots and rooms followed by improving the solution vector of partial exams. The process then continues with the next batch of exams until all exams are scheduled. The partial exam assignment approach utilises partial graph heuristic orderings with a modified great deluge algorithm (PGH-mGD). The PGH-mGD approach is tested on two benchmark datasets, a capacitated examination dataset from the 2nd international timetable competition (ITC2007) and an un-capacitated Toronto examination dataset. Experimental results show that PGH-mGD is able to produce quality solutions that are competitive with those of the previous approaches reported in the scientific literature. |
first_indexed | 2024-03-06T12:42:50Z |
format | Article |
id | UMPir28470 |
institution | Universiti Malaysia Pahang |
language | English |
last_indexed | 2024-03-06T12:42:50Z |
publishDate | 2020 |
publisher | MDPI |
record_format | dspace |
spelling | UMPir284702021-01-26T03:41:03Z http://umpir.ump.edu.my/id/eprint/28470/ Addressing examination timetabling problem using a partial exams approach in constructive and improvement Mandal, Ashis Kumar Kahar, M. N. M. Kendall, Graham QA76 Computer software TA Engineering (General). Civil engineering (General) The paper investigates a partial exam assignment approach for solving the examination timetabling problem. Current approaches involve scheduling all of the exams into time slots and rooms (i.e., produce an initial solution) and then continuing by improving the initial solution in a predetermined number of iterations. We propose a modification of this process that schedules partially selected exams into time slots and rooms followed by improving the solution vector of partial exams. The process then continues with the next batch of exams until all exams are scheduled. The partial exam assignment approach utilises partial graph heuristic orderings with a modified great deluge algorithm (PGH-mGD). The PGH-mGD approach is tested on two benchmark datasets, a capacitated examination dataset from the 2nd international timetable competition (ITC2007) and an un-capacitated Toronto examination dataset. Experimental results show that PGH-mGD is able to produce quality solutions that are competitive with those of the previous approaches reported in the scientific literature. MDPI 2020-05-17 Article PeerReviewed pdf en cc_by_4 http://umpir.ump.edu.my/id/eprint/28470/1/Addressing%20examination%20timetabling%20problem%20using%20a%20partial%20exams.pdf Mandal, Ashis Kumar and Kahar, M. N. M. and Kendall, Graham (2020) Addressing examination timetabling problem using a partial exams approach in constructive and improvement. Computation, 8 (2). pp. 1-28. ISSN 2079-3197. (Published) https://doi.org/10.3390/computation8020046 https://doi.org/10.3390/computation8020046 |
spellingShingle | QA76 Computer software TA Engineering (General). Civil engineering (General) Mandal, Ashis Kumar Kahar, M. N. M. Kendall, Graham Addressing examination timetabling problem using a partial exams approach in constructive and improvement |
title | Addressing examination timetabling problem using a partial exams approach in constructive and improvement |
title_full | Addressing examination timetabling problem using a partial exams approach in constructive and improvement |
title_fullStr | Addressing examination timetabling problem using a partial exams approach in constructive and improvement |
title_full_unstemmed | Addressing examination timetabling problem using a partial exams approach in constructive and improvement |
title_short | Addressing examination timetabling problem using a partial exams approach in constructive and improvement |
title_sort | addressing examination timetabling problem using a partial exams approach in constructive and improvement |
topic | QA76 Computer software TA Engineering (General). Civil engineering (General) |
url | http://umpir.ump.edu.my/id/eprint/28470/1/Addressing%20examination%20timetabling%20problem%20using%20a%20partial%20exams.pdf |
work_keys_str_mv | AT mandalashiskumar addressingexaminationtimetablingproblemusingapartialexamsapproachinconstructiveandimprovement AT kaharmnm addressingexaminationtimetablingproblemusingapartialexamsapproachinconstructiveandimprovement AT kendallgraham addressingexaminationtimetablingproblemusingapartialexamsapproachinconstructiveandimprovement |