Parallel scatter search algorithms for exam timetabling. (c2009)

LAUR Repository

Show simple item record

dc.contributor.author Haidar, Ghia Abdullah Sleiman
dc.date.accessioned 2011-10-27T12:51:15Z
dc.date.available 2011-10-27T12:51:15Z
dc.date.copyright 2009 en_US
dc.date.issued 2011-10-27
dc.date.submitted 2009-06-29
dc.identifier.uri http://hdl.handle.net/10725/938
dc.description Includes bibliographical references (leaves 59-62). en_US
dc.description.abstract University exam timetabling is an important activity for scheduling exams into predefined days, time periods and rooms. Given a set of constraints, exam timetabling is an NP-Hard problem that requires heuristic techniques to be solved adequately within reasonable execution time. For large numbers of exams and students, sequential algorithms are likely to be very time consuming. The purpose of this work is to design and implement a parallel scatter search meta-heuristic algorithm for producing good sub-optimal exam timetables in a reasonable time. Scatter search is a population-based approach that generates solutions over a number of iterations and aims to combine diversification and search intensification. We propose a parallel scatter search that is based distributing the population of candidate solutions over a number of processors in a cluster environment. The main components of scatter search are computed in parallel and an efficient communication technique is employed. Empirical results show that our proposed parallel scatter search algorithm yields good speed-up. Also, they show that the parallel scatter search algorithm improves solution quality since the algorithm explores larger parts of the search space within reasonable time. en_US
dc.language.iso en en_US
dc.subject Parallel algorithms en_US
dc.subject Scattering (Mathematics) en_US
dc.subject Examinations -- Study guides en_US
dc.subject Time perspective en_US
dc.title Parallel scatter search algorithms for exam timetabling. (c2009) 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.commembers Dr. Haidar Harmanani
dc.author.commembers Dr. Abbass Tarhini
dc.author.woa OA en_US
dc.description.physdesc 1 bound copy: xii, 63 p.; ill.; 30 cm. Available at RNL. en_US
dc.author.division Computer Science en_US
dc.author.advisor Dr. Nashaat Mansour
dc.keywords Meta-heuristics en_US
dc.keywords Parallel algorithm en_US
dc.keywords Scatter search en_US
dc.keywords Timetabling en_US
dc.keywords Exam timetabling en_US
dc.identifier.doi https://doi.org/10.26756/th.2009.53 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