CCE Theses and Dissertations
Date of Award
2005
Document Type
Dissertation
Degree Name
Doctor of Philosophy in Computer Information Systems (DCIS)
Department
Graduate School of Computer and Information Sciences
Advisor
Sumitra Mukherjee
Committee Member
Junping Sun
Committee Member
James D. Cannady
Abstract
The purpose of this thesis is to investigate the suitability and effectiveness of the Particle Swarm Optimization (PSO) technique when applied to the University Examination Timetabling problem. We accomplished this by analyzing experimentally the performance profile-the quality of the solution as a function of the execution time-of the standard form of the PSO algorithm when brought to bear against the University Examination Timetabling problem. This study systematically investigated the impact of problem and algorithm factors in solving this particular timetabling problem and determined the algorithm's performance profile under the specified test environment. Keys factors studied included problem size (i.e., number of enrollments), conflict matrix density, and swarm size. Testing used both real world and fabricated data sets of varying size and conflict densities. This research also provides insight into how well the PSO algorithm performs compared with other algorithms used to attack the same problem and data sets. Knowing the algorithm's strengths and limitations is useful in determining its utility, ability, and limitations in attacking timetabling problems in general and the University Examination Timetabling problem in pal1icular. Finally, two additional contributions were made during the course of this research: a better way to fabricate examination timetabling data sets and the introduction of the PSO-No Conflicts optimization approach. Our new data set fabrication method produced data sets that were more representative of real world examination timetabling data sets and permitted us to construct data sets spanning a wide range of sizes and densities.· The newly derived PSO-No Conflicts algorithm permitted the PSO algorithm to perform searches while still satisfying constraints.
NSUWorks Citation
Daniel R. Fealko. 2005. Evaluating Particle Swarm Intelligence Techniques for Solving University Examination Timetabling Problems. Doctoral dissertation. Nova Southeastern University. Retrieved from NSUWorks, Graduate School of Computer and Information Sciences. (513)
https://nsuworks.nova.edu/gscis_etd/513.