Cover Image

Solving ump examination timetabling problem using dynamic exploration step counting hill climbing algorithm

Examination timetabling is a process that involves assigning exams to available timeslot and room(s) to satisfy the hard and soft constraints. An example of such constraint includes no clashing, back-to-back examinations, room capacity constraints and many others. These constraints complicate the as...

Full description

Saved in:
Bibliographic Details
Main Author: Chang, Ling Shing
Format: Thesis
Language:English
Published: 2022
Subjects:
Q Science (General)
QA75 Electronic computers. Computer science
Online Access:http://umpir.ump.edu.my/id/eprint/37644/1/ir.Solving%20ump%20examination%20timetabling%20problem%20using%20dynamic%20exploration%20step%20counting%20hill%20climbing%20algorithm.pdf
http://umpir.ump.edu.my/id/eprint/37644/
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.ump.umpir.37644
record_format eprints
spelling my.ump.umpir.376442023-09-15T07:48:01Z http://umpir.ump.edu.my/id/eprint/37644/ Solving ump examination timetabling problem using dynamic exploration step counting hill climbing algorithm Chang, Ling Shing Q Science (General) QA75 Electronic computers. Computer science Examination timetabling is a process that involves assigning exams to available timeslot and room(s) to satisfy the hard and soft constraints. An example of such constraint includes no clashing, back-to-back examinations, room capacity constraints and many others. These constraints complicate the assignment of examination to available timeslot and room(s). UMP currently operates from two separate campuses in Gambang and Pekan, Pahang, Malaysia. Operating from two distant campuses forms new constraints different from those reported in the literature. These new constraints further complicate the problem in obtaining a feasible and quality examination timetable. Furthermore, there is no formal mathematical model to assist UMP in evaluating the quality of the examination timetable. Therefore, this forms the motivation of this research to solve the UMP examination timetabling problem with the new examination constraints. The work starts by developing a formal mathematical model based on the new constraints and generates a feasible initial solution of the examination timetable that satisfies the hard and soft constraints (as much as possible). Then, the initial solution is improved using our enhanced algorithm called dynamic exploration step counting hill climbing (DESCHC). The DESCHC employs a dynamic decay rate value to encourage exploration of the search space. The cost bound that acts as the level of acceptance dynamically changes depending on the acceptance of the candidate and improvement in the penalty cost. Experimental results show that DESCHC was able to produce quality solutions. In semester 1-2014/2015, DESCHC produced a solution that is 92.86% better than the UMP examination timetable. In semester 2-2014/2015, DESCHC produced a solution that is 96.13% better than the UMP examination timetable. Moreover, the solution produced by DESCHC satisfies all of the hard constraints that the UMP examination timetable failed to achieve. 2022-02 Thesis NonPeerReviewed pdf en http://umpir.ump.edu.my/id/eprint/37644/1/ir.Solving%20ump%20examination%20timetabling%20problem%20using%20dynamic%20exploration%20step%20counting%20hill%20climbing%20algorithm.pdf Chang, Ling Shing (2022) Solving ump examination timetabling problem using dynamic exploration step counting hill climbing algorithm. Masters thesis, Universiti Malaysia Pahang (Contributors, Thesis advisor: Mohd Nizam, Mohmad Kahar).
institution Universiti Malaysia Pahang
building UMP Library
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Malaysia Pahang
content_source UMP Institutional Repository
url_provider http://umpir.ump.edu.my/
language English
topic Q Science (General)
QA75 Electronic computers. Computer science
spellingShingle Q Science (General)
QA75 Electronic computers. Computer science
Chang, Ling Shing
Solving ump examination timetabling problem using dynamic exploration step counting hill climbing algorithm
description Examination timetabling is a process that involves assigning exams to available timeslot and room(s) to satisfy the hard and soft constraints. An example of such constraint includes no clashing, back-to-back examinations, room capacity constraints and many others. These constraints complicate the assignment of examination to available timeslot and room(s). UMP currently operates from two separate campuses in Gambang and Pekan, Pahang, Malaysia. Operating from two distant campuses forms new constraints different from those reported in the literature. These new constraints further complicate the problem in obtaining a feasible and quality examination timetable. Furthermore, there is no formal mathematical model to assist UMP in evaluating the quality of the examination timetable. Therefore, this forms the motivation of this research to solve the UMP examination timetabling problem with the new examination constraints. The work starts by developing a formal mathematical model based on the new constraints and generates a feasible initial solution of the examination timetable that satisfies the hard and soft constraints (as much as possible). Then, the initial solution is improved using our enhanced algorithm called dynamic exploration step counting hill climbing (DESCHC). The DESCHC employs a dynamic decay rate value to encourage exploration of the search space. The cost bound that acts as the level of acceptance dynamically changes depending on the acceptance of the candidate and improvement in the penalty cost. Experimental results show that DESCHC was able to produce quality solutions. In semester 1-2014/2015, DESCHC produced a solution that is 92.86% better than the UMP examination timetable. In semester 2-2014/2015, DESCHC produced a solution that is 96.13% better than the UMP examination timetable. Moreover, the solution produced by DESCHC satisfies all of the hard constraints that the UMP examination timetable failed to achieve.
format Thesis
author Chang, Ling Shing
author_facet Chang, Ling Shing
author_sort Chang, Ling Shing
title Solving ump examination timetabling problem using dynamic exploration step counting hill climbing algorithm
title_short Solving ump examination timetabling problem using dynamic exploration step counting hill climbing algorithm
title_full Solving ump examination timetabling problem using dynamic exploration step counting hill climbing algorithm
title_fullStr Solving ump examination timetabling problem using dynamic exploration step counting hill climbing algorithm
title_full_unstemmed Solving ump examination timetabling problem using dynamic exploration step counting hill climbing algorithm
title_sort solving ump examination timetabling problem using dynamic exploration step counting hill climbing algorithm
publishDate 2022
url http://umpir.ump.edu.my/id/eprint/37644/1/ir.Solving%20ump%20examination%20timetabling%20problem%20using%20dynamic%20exploration%20step%20counting%20hill%20climbing%20algorithm.pdf
http://umpir.ump.edu.my/id/eprint/37644/
_version_ 1778161078304243712
score 13.211869

Similar Items