Hybrid particle swarm optimization constraint based reasoning in solving university course timetabling problem

Timetabling is a frequent problem in academic context such as schools, universities and colleges. Timetabling problems (TTPs) are about allocating a number of events (classes, examinations, courses, ect) into a limited number of time slots aiming towards satisfying a set of constraints. TTPs have al...

Full description

Saved in:

Bibliographic Details
Main Author:	Ho, Irene Sheau Fen
Format:	Thesis
Language:	English
Published:	2010
Subjects:	QA75 Electronic computers Computer science
Online Access:	http://eprints.utm.my/id/eprint/15942/5/HoSheauFenMFSKSM2010.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.15942
record_format	uketd_dc
spelling	my-utm-ep.159422017-10-16T08:06:02Z Hybrid particle swarm optimization constraint based reasoning in solving university course timetabling problem 2010-04 Ho, Irene Sheau Fen QA75 Electronic computers. Computer science Timetabling is a frequent problem in academic context such as schools, universities and colleges. Timetabling problems (TTPs) are about allocating a number of events (classes, examinations, courses, ect) into a limited number of time slots aiming towards satisfying a set of constraints. TTPs have also been described as a class of hard-to-solve constrained optimization problems of combinatorial nature. They are classified as constraints-satisfaction problems that intend to satisfy all constraints and optimize a number of desirable objectives. Various approaches have been reported in the literatures to solve TTP, such as graph coloring, heuristic, genetic algorithm and constraint logic programming. Most of these techniques generate feasible but not optimal solutions or results. Therefore, this research focuses on producing a feasible and yet good quality solution for university courses timetabling problem. In this thesis, we proposed a new hybrid approach by exploiting particle swarm optimization (PSO) and constraint-based reasoning (CBR). PSO is used to generate potential solutions to ensure that the algorithm is generic enough to avoiding local minima and problem dependency while utilizing a suitable fitness function. Meanwhile, CBR helps to satisfy constraints more effectively and efficiently by posting and propagating constraints during the process of variable instantiations. CBR procedures are applied to determine the validity and legality of the solution, followed by an appropriate search procedure to improve any infeasible solution and significantly reduce the search space. Results of this study have significantly proven that hybrid PSO-CBR has the ability to produce feasible and good quality solutions using real-world universities and benchmark datasets. 2010-04 Thesis http://eprints.utm.my/id/eprint/15942/ http://eprints.utm.my/id/eprint/15942/5/HoSheauFenMFSKSM2010.pdf application/pdf en public masters Universiti Teknologi Malaysia, Faculty of Computer Science and Information Systems Faculty of Computer Science and Information Systems
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	QA75 Electronic computers Computer science
spellingShingle	QA75 Electronic computers Computer science Ho, Irene Sheau Fen Hybrid particle swarm optimization constraint based reasoning in solving university course timetabling problem
description	Timetabling is a frequent problem in academic context such as schools, universities and colleges. Timetabling problems (TTPs) are about allocating a number of events (classes, examinations, courses, ect) into a limited number of time slots aiming towards satisfying a set of constraints. TTPs have also been described as a class of hard-to-solve constrained optimization problems of combinatorial nature. They are classified as constraints-satisfaction problems that intend to satisfy all constraints and optimize a number of desirable objectives. Various approaches have been reported in the literatures to solve TTP, such as graph coloring, heuristic, genetic algorithm and constraint logic programming. Most of these techniques generate feasible but not optimal solutions or results. Therefore, this research focuses on producing a feasible and yet good quality solution for university courses timetabling problem. In this thesis, we proposed a new hybrid approach by exploiting particle swarm optimization (PSO) and constraint-based reasoning (CBR). PSO is used to generate potential solutions to ensure that the algorithm is generic enough to avoiding local minima and problem dependency while utilizing a suitable fitness function. Meanwhile, CBR helps to satisfy constraints more effectively and efficiently by posting and propagating constraints during the process of variable instantiations. CBR procedures are applied to determine the validity and legality of the solution, followed by an appropriate search procedure to improve any infeasible solution and significantly reduce the search space. Results of this study have significantly proven that hybrid PSO-CBR has the ability to produce feasible and good quality solutions using real-world universities and benchmark datasets.
format	Thesis
qualification_level	Master's degree
author	Ho, Irene Sheau Fen
author_facet	Ho, Irene Sheau Fen
author_sort	Ho, Irene Sheau Fen
title	Hybrid particle swarm optimization constraint based reasoning in solving university course timetabling problem
title_short	Hybrid particle swarm optimization constraint based reasoning in solving university course timetabling problem
title_full	Hybrid particle swarm optimization constraint based reasoning in solving university course timetabling problem
title_fullStr	Hybrid particle swarm optimization constraint based reasoning in solving university course timetabling problem
title_full_unstemmed	Hybrid particle swarm optimization constraint based reasoning in solving university course timetabling problem
title_sort	hybrid particle swarm optimization constraint based reasoning in solving university course timetabling problem
granting_institution	Universiti Teknologi Malaysia, Faculty of Computer Science and Information Systems
granting_department	Faculty of Computer Science and Information Systems
publishDate	2010
url	http://eprints.utm.my/id/eprint/15942/5/HoSheauFenMFSKSM2010.pdf
_version_	1747814999536959488

Hybrid particle swarm optimization constraint based reasoning in solving university course timetabling problem

Similar Items