A Scatter search algorithm for exam scheduling. (c2006)

LAUR Repository

Show simple item record

dc.contributor.author Isahakian, Vatche Raffi
dc.date.accessioned 2011-09-26T12:28:08Z
dc.date.available 2011-09-26T12:28:08Z
dc.date.copyright 2006 en_US
dc.date.issued 2011-09-26
dc.date.submitted 2006-05-30
dc.identifier.uri http://hdl.handle.net/10725/630
dc.description Includes bibliographical references (leaves 52-56). en_US
dc.description.abstract At universities where students enjoy flexibility in selecting courses, the Registrar's office aims to generate an appropriate exam schedule for numerous courses and large number of students. An appropriate exam schedule should show fairness towards all students, respecting criteria and constraints: (a) eliminating or minimize the number of simultaneous exams; (b) minimize the number of consecutive exams; (c) minimize the number of multiple exams a student has per day; (d) exams should fit in rooms with predefined capacity; and (e) the number of exam periods is limited. These constraints are conflicting in nature. Hence, finding an optimal solution is challenging and the problem of exam scheduling is an NP-complete problem. Solving this problem in a reasonable amount of time requires the use of heuristic approaches. A good heuristic algorithm should aim to minimize the above mentioned constraints. In this work, we develop an evolutionary algorithm based on the scatter search approach for finding good suboptimal solutions for exam scheduling. This approach is based on maintaining a population of solutions for the purpose of generating new trial solutions. We perform experimental evaluation of our suggested algorithm on real data and compare our results with the registrar's manual schedule in addition to other optimization heuristic algorithms: Simulated Annealing, Genetic Algorithm, Three Phase Simulated Annealing (3PSA); a clustering based algorithm (FESP), and a hybrid algorithm (FESPSA).Our experimental results show that our adapted scatter search algorithm generated results that are better than FESP, 3PSA, FESPSA algorithms and the registrar's manual schedule, and it is comparable with the results generated by GA and SA. en_US
dc.language.iso en en_US
dc.subject Mathematical optimization en_US
dc.subject Evolutionary programming (Computer science) en_US
dc.subject Heuristic programming en_US
dc.subject Computer algorithms en_US
dc.title A Scatter search algorithm for exam scheduling. (c2006) en_US
dc.type Thesis en_US
dc.term.submitted Spring en_US
dc.author.degree MS in Computer Science en_US
dc.author.school Arts and Sciences en_US
dc.author.idnumber 200105487 en_US
dc.author.commembers Dr. Ramzi Haraty
dc.author.commembers Dr. Danielle Azar
dc.author.woa OA en_US
dc.description.physdesc 1 bound copy: xii, 56 leaves; 30 cm. available at RNL. en_US
dc.author.division Computer Science en_US
dc.author.advisor Dr. Nasha't Mansour
dc.keywords Evolutionary algorithm en_US
dc.keywords Exam scheduling en_US
dc.keywords Multiple criteria optimization en_US
dc.keywords Meta-heuristics en_US
dc.keywords Scatter search en_US
dc.keywords Timetabling en_US
dc.identifier.doi https://doi.org/10.26756/th.2006.27 en_US
dc.publisher.institution Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account