Fuzzy methodologies for automated University timetabling solution construction and evaluation

This thesis presents an investigation into the use of fuzzy methodologies for University timetabling problems. The first area of investigation is the use of fuzzy techniques to combine multiple heuristic orderings within the construction of timetables. Different combinations of multiple heuristic or...

Full description

Saved in:

Bibliographic Details
Main Author:	Asmuni, Hishammuddin
Format:	Thesis
Language:	English
Published:	2008
Subjects:	QA76 Computer software
Online Access:	http://eprints.utm.my/id/eprint/7859/1/HishammuddinAsmuni2008.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.7859
record_format	uketd_dc
spelling	my-utm-ep.78592018-07-19T01:38:49Z Fuzzy methodologies for automated University timetabling solution construction and evaluation 2008-06 Asmuni, Hishammuddin QA76 Computer software This thesis presents an investigation into the use of fuzzy methodologies for University timetabling problems. The first area of investigation is the use of fuzzy techniques to combine multiple heuristic orderings within the construction of timetables. Different combinations of multiple heuristic ordering were examined, considering five graph-based heuristic orderings - Largest Degree, Saturation Degree, Largest Enrolment, Largest Coloured Degree and Weighted Largest Degree. The initial development utilised only two heuristic orderings simultaneously and subsequent development went on to incorporate three heuristic orderings simultaneously. A central hypothesis of this thesis is that this approach provides a more realistic scheme for measuring the difficulty of assigning events to time slots than the use of a single heuristic alone. Experimental results demonstrated that the fuzzy multiple heuristic orderings (with parameter tuning) outperformed all of the single heuristic orderings and non-fuzzy linear weighting factors. Comprehensive analysis has provided some key insights regarding the implementation of multiple heuristic orderings. Producing examination timetables automatically has been the subject of much research. It is generally the case that a number of alternative solutions that satisfy all the hard criteria are possible. Indeed, there are usually a very large number of such feasible solutions. Some method is required to permit the overall quality of different solutions to be quantified, in order to allow them to be compared, so that the best may be selected. In response to that demand, the second area of investigation of this thesis is concerned with a new evaluation function for examination timetabling problems. A novel approach, in which fuzzy methods are used to evaluate the end solution quality, separate from the objective functions used in solution generation, represents a significant addition to the literature. The proposed fuzzy evaluation function provides a mechanism to allow an overall decision in evaluating the quality of a timetable solution to be made based on common sense rules that encapsulate the notion that the timetable solution quality increases as both the average penalty and the highest penalty decrease. New algorithms to calculate what is loosely termed the lower limits and upper limits of the proximity cost function for any problem instance are also presented. These limits may be used to provide a good indication of how good any timetable solution is. Furthermore, there may be an association between the proposed lower limit and the formal lower bound. This is the first time that lower limits (other than zero) have been established for proximity cost evaluation of timetable solutions. 2008-06 Thesis http://eprints.utm.my/id/eprint/7859/ http://eprints.utm.my/id/eprint/7859/1/HishammuddinAsmuni2008.pdf application/pdf en public http://etheses.nottingham.ac.uk/514/ phd doctoral The University of Nottingham School of Computer Science Ministry of Science, Technology and Science (MOSTI) Malaysia
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	QA76 Computer software
spellingShingle	QA76 Computer software Asmuni, Hishammuddin Fuzzy methodologies for automated University timetabling solution construction and evaluation
description	This thesis presents an investigation into the use of fuzzy methodologies for University timetabling problems. The first area of investigation is the use of fuzzy techniques to combine multiple heuristic orderings within the construction of timetables. Different combinations of multiple heuristic ordering were examined, considering five graph-based heuristic orderings - Largest Degree, Saturation Degree, Largest Enrolment, Largest Coloured Degree and Weighted Largest Degree. The initial development utilised only two heuristic orderings simultaneously and subsequent development went on to incorporate three heuristic orderings simultaneously. A central hypothesis of this thesis is that this approach provides a more realistic scheme for measuring the difficulty of assigning events to time slots than the use of a single heuristic alone. Experimental results demonstrated that the fuzzy multiple heuristic orderings (with parameter tuning) outperformed all of the single heuristic orderings and non-fuzzy linear weighting factors. Comprehensive analysis has provided some key insights regarding the implementation of multiple heuristic orderings. Producing examination timetables automatically has been the subject of much research. It is generally the case that a number of alternative solutions that satisfy all the hard criteria are possible. Indeed, there are usually a very large number of such feasible solutions. Some method is required to permit the overall quality of different solutions to be quantified, in order to allow them to be compared, so that the best may be selected. In response to that demand, the second area of investigation of this thesis is concerned with a new evaluation function for examination timetabling problems. A novel approach, in which fuzzy methods are used to evaluate the end solution quality, separate from the objective functions used in solution generation, represents a significant addition to the literature. The proposed fuzzy evaluation function provides a mechanism to allow an overall decision in evaluating the quality of a timetable solution to be made based on common sense rules that encapsulate the notion that the timetable solution quality increases as both the average penalty and the highest penalty decrease. New algorithms to calculate what is loosely termed the lower limits and upper limits of the proximity cost function for any problem instance are also presented. These limits may be used to provide a good indication of how good any timetable solution is. Furthermore, there may be an association between the proposed lower limit and the formal lower bound. This is the first time that lower limits (other than zero) have been established for proximity cost evaluation of timetable solutions.
format	Thesis
qualification_name	Doctor of Philosophy (PhD.)
qualification_level	Doctorate
author	Asmuni, Hishammuddin
author_facet	Asmuni, Hishammuddin
author_sort	Asmuni, Hishammuddin
title	Fuzzy methodologies for automated University timetabling solution construction and evaluation
title_short	Fuzzy methodologies for automated University timetabling solution construction and evaluation
title_full	Fuzzy methodologies for automated University timetabling solution construction and evaluation
title_fullStr	Fuzzy methodologies for automated University timetabling solution construction and evaluation
title_full_unstemmed	Fuzzy methodologies for automated University timetabling solution construction and evaluation
title_sort	fuzzy methodologies for automated university timetabling solution construction and evaluation
granting_institution	The University of Nottingham
granting_department	School of Computer Science
publishDate	2008
url	http://eprints.utm.my/id/eprint/7859/1/HishammuddinAsmuni2008.pdf
_version_	1747814716727623680

Fuzzy methodologies for automated University timetabling solution construction and evaluation

Similar Items