Structure based partial solution search for the examination timetabling problem.
Loading...
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The aim of this work is to present a new approach, namely, Structure Based Partial Solution
Search (SBPSS) to solve the Examination Timetabling Problem. The success of the
Developmental Approach in this problem domain suggested that the strategy of searching the
spaces of partial timetables whilst constructing them is promising and worth pursuing. This
work adopts a similar strategy. Multiple timetables are incrementally constructed at the same
time. The quality of the partial timetables is improved upon by searching their partial solution
spaces at every iteration during construction. Another key finding from the literature survey
revealed that although timetables may exhibit the same behaviour in terms of their objective
values, their structures or exam schedules may be different. The challenge with this finding is
to decide on which regions to pursue because some regions may not be worth investigating due
to the difficulty in searching them. These problematic areas may have solutions that are not
amenable to change which makes it difficult to improve them. Another reason is that the
neighbourhoods of solutions in these areas may be less connected than others which may restrict
the ability of the search to move to a better solution in that neighbourhood. By moving to these
problematic areas of the search space the search may stagnate and waste expensive
computational resources. One way to overcome this challenge is to use both structure and
behaviour in the search and not only behaviour alone to guide the search. A search that is guided
by structure is able to find new regions by considering the structural components of the
candidate solutions which indicate which part of the search space the same candidates occupy.
Another benefit to making use of a structure-based search is that it has no objective value bias
because it is not guided by only the objective value. This statement is consistent with the
literature survey where it is suggested that in order to achieve good performance the search
should not be guided by only the objective value. The proposed method has been tested on three popular benchmark sets for examination timetabling, namely, the Carter benchmark set; the
benchmark set from the International Timetabling competition in 2007 and the Yeditepe
benchmark set. The SBPSS found the best solutions for two of the Carter problem instances.
The SBPSS found the best solutions for four of the competition problem instances. Lastly, the
SBPSS improved on the best results for all the Yeditepe problem instances.
Description
Doctoral Degree. University of KwaZulu-Natal, Pietermaritzburg.