Variable Neighborhood Descent and Whale Optimization Algorithm for Examination Timetabling Problems at Universiti Malaysia Sarawak
The examination timetabling problem, which involves the allocation of exams to limited resources such as timeslots and rooms, while satisfying constraints. While the existing literature predominantly addresses uncapacitated or capacitated formulations of this problem, this study seeks to bridge the...
| 第一著者: | |
|---|---|
| フォーマット: | 学位論文 |
| 言語: | 英語 英語 英語 |
| 出版事項: |
University of Malaysia, Sarawak
2025
|
| 主題: | |
| オンライン･アクセス: | http://ir.unimas.my/id/eprint/49906/ |
| Abstract | Abstract here |
| 要約: | The examination timetabling problem, which involves the allocation of exams to limited resources such as timeslots and rooms, while satisfying constraints. While the existing literature predominantly addresses uncapacitated or capacitated formulations of this problem, this study seeks to bridge the gap between theoretical research and practical application. Specifically, it investigates a real-world examination timetabling problem at Universiti Malaysia Sarawak, proposing a unified framework that incorporates both uncapacitated and capacitated formulations. A mathematical model grounded in real-world data was developed to capture the latest operational requirements. The model employs a two-level structure, where the first level uses standard soft constraints as the objective function to evaluate solution quality, while the second level dynamically adapts to faculty-specific preferences. A constructive algorithm was developed to generate an initial feasible solution, which was subsequently refined using two primary approaches to evaluate their efficiency: Iterative Threshold Pipe Variable Neighborhood Descent (IT-PVND), and a modified Whale Optimization Algorithm (WOA). The IT-PVND adjusts acceptance criteria using a simple iteration parameter, permitting the acceptance of improved solutions and those below a predefined threshold for a set number of iterations to prevent premature convergence to local optima. The original WOA is modified by replacing the equations designed for continuous problem domains with local search methods, enhancing its adaptability to discrete optimization problems. Both IT-PVND and the modified WOA achieved measurable efficiency gains over proprietary software and manual scheduling when applied to real-world data. They also proved competitive against established methods in the literature when validated on the Toronto problem, demonstrating robustness and effectiveness across diverse instances. Furthermore, the research provided practical insights by comparing centralized and decentralized scheduling strategies, offering universities evidence-based guidance on balancing efficiency and space utilization. Future studies could expand the scope of datasets to validate the centralized framework at the full institutional level rather than only at selected faculties. Moreover, the hybrid WOA introduced here can be further extended — and complemented with other metaheuristics — to address broader domains of scheduling and resource allocation beyond exam timetabling. |
|---|