Computerised Multi-Objective Faculty Exam Timetabling Problem

This research focuses on the final examination timetabling at the Faculty of Computer Science and Information Technology (FCSIT), Universiti Malaysia Sarawak (UNIMAS). In UNIMAS, each faculty needs to schedule a final examination timetable every semester. The large number of students and limited res...

全面介紹

Saved in:

書目詳細資料
主要作者:	Phang, Min Hui
格式:	Thesis
語言:	English
出版:	2019
主題:	QA75 Electronic computers Computer science
在線閱讀:	http://ir.unimas.my/id/eprint/27457/3/Phang%20Min%20Hui%20ft.pdf
標簽:	添加標簽沒有標簽, 成為第一個標記此記錄!

id	my-unimas-ir.27457
record_format	uketd_dc
institution	Universiti Malaysia Sarawak
collection	UNIMAS Institutional Repository
language	English
topic	QA75 Electronic computers Computer science
spellingShingle	QA75 Electronic computers Computer science Phang, Min Hui Computerised Multi-Objective Faculty Exam Timetabling Problem
description	This research focuses on the final examination timetabling at the Faculty of Computer Science and Information Technology (FCSIT), Universiti Malaysia Sarawak (UNIMAS). In UNIMAS, each faculty needs to schedule a final examination timetable every semester. The large number of students and limited resources in each faculty may increase the problem complexity when arranging the final examination timetable. In this study, there is one existing system (FESS 1.0) to generate a clash-free timetable. However, student sectioning, room utilisation, continuous examination gaps and priority courses were not considered. The main objective of this research is to design and build a computationally bounded multi-objective two-stage heuristic algorithm to optimise examination room utilisation. The first stage, course grouping, is mainly to minimise the problem size and clash-free constraints. All the courses are divided into a smaller number of course groups. The course groups are then eased into the second stage of timeslot-room allocation. During the allocation, each course is allocated at ‘best fit room’ in order to maximise the room utilisation and minimise the student sectioning. A few real datasets were collected and experimented with the proposed solution. Overall, the proposed solution is proven to outperform the existing solution in terms of room utilisation, student sectioning, continuous examination and priority course. Besides that, it is also able to accommodate the priority courses constraints well in order to obtain earlier examination dates. Subsequently, a sensitivity analysis was conducted. The increment and decrement in the course size, course-student enrolment size and room size were tested respectively in the solution. All the sensitivity results proved that the proposed solution is effective and robust to solve different types of datasets.
format	Thesis
qualification_level	Master's degree
author	Phang, Min Hui
author_facet	Phang, Min Hui
author_sort	Phang, Min Hui
title	Computerised Multi-Objective Faculty Exam Timetabling Problem
title_short	Computerised Multi-Objective Faculty Exam Timetabling Problem
title_full	Computerised Multi-Objective Faculty Exam Timetabling Problem
title_fullStr	Computerised Multi-Objective Faculty Exam Timetabling Problem
title_full_unstemmed	Computerised Multi-Objective Faculty Exam Timetabling Problem
title_sort	computerised multi-objective faculty exam timetabling problem
granting_institution	Universiti Malaysia Sarawak (UNIMAS)
granting_department	Faculty of Computer Science and Information Technology
publishDate	2019
url	http://ir.unimas.my/id/eprint/27457/3/Phang%20Min%20Hui%20ft.pdf
_version_	1794023005357080576
spelling	my-unimas-ir.274572024-01-15T09:02:18Z Computerised Multi-Objective Faculty Exam Timetabling Problem 2019 Phang, Min Hui QA75 Electronic computers. Computer science This research focuses on the final examination timetabling at the Faculty of Computer Science and Information Technology (FCSIT), Universiti Malaysia Sarawak (UNIMAS). In UNIMAS, each faculty needs to schedule a final examination timetable every semester. The large number of students and limited resources in each faculty may increase the problem complexity when arranging the final examination timetable. In this study, there is one existing system (FESS 1.0) to generate a clash-free timetable. However, student sectioning, room utilisation, continuous examination gaps and priority courses were not considered. The main objective of this research is to design and build a computationally bounded multi-objective two-stage heuristic algorithm to optimise examination room utilisation. The first stage, course grouping, is mainly to minimise the problem size and clash-free constraints. All the courses are divided into a smaller number of course groups. The course groups are then eased into the second stage of timeslot-room allocation. During the allocation, each course is allocated at ‘best fit room’ in order to maximise the room utilisation and minimise the student sectioning. A few real datasets were collected and experimented with the proposed solution. Overall, the proposed solution is proven to outperform the existing solution in terms of room utilisation, student sectioning, continuous examination and priority course. Besides that, it is also able to accommodate the priority courses constraints well in order to obtain earlier examination dates. Subsequently, a sensitivity analysis was conducted. The increment and decrement in the course size, course-student enrolment size and room size were tested respectively in the solution. All the sensitivity results proved that the proposed solution is effective and robust to solve different types of datasets. Universiti Malaysia Sarawak, (UNIMAS) 2019 Thesis http://ir.unimas.my/id/eprint/27457/ http://ir.unimas.my/id/eprint/27457/3/Phang%20Min%20Hui%20ft.pdf text en validuser masters Universiti Malaysia Sarawak (UNIMAS) Faculty of Computer Science and Information Technology Abdul-Rahman, S., Sobri, N. S., Omar, M. F., Benjamin, A. M., & Ramli, R. (2014). Graph coloring heuristics for solving examination timetabling problem at Universiti Utara, Malaysia. Proceedings of the 3rd International Conference on Quantitative Sciences and Its Applications, (pp. 491-496). Aizam, N. A. H., & Uvaraja, V. (2015). Generic model for timetabling problems by integer linear programming approach. International Journal of Mathematical and Computational Sciences, 9(12), 718-725. Asmuni, H., Burke, E. K., Garibaldi, J. M., & McCollumn, B. (2004). Fuzzy multiple heuristic orderings for examination timetabling. Proceedings of the 5th International Conference on Practice and Theory of Automated Timetabling (PATAT 2004), (pp. 334-353), Springer Berlin Heidelberg. Ayob, M., Malik, A. M. A., Abdullah, S., Hamdan, A. R., Kendall, G., & Qu, R. (2007). Solving a practical examination timetabling problem: a case study. Proceedings of the International Conference on Computational Science and Its Applications, (pp. 611-624), Springer Berlin Heidelberg. Bergmann, L. K., Fischer, K., & Zurheide, S. (2014). A linear mixed-integer model for realistic examination timetabling problems. Proceedings of the 10th International Conference of the Practice and Theory of Automated Timetabling (PATAT 2014), (pp. 82-101). Boizumault, P., Delon, Y., & Peridy (1996). Constraint logic programming for examination timetabling. The Journal of Logic Programming, 26(2), 217-233. Burke, E. K., Kendall, G., Newall, J. P., Hart, E., Ross, P., & Schulenburg, S. (2003). Hyper-heuristics: an emerging direction in modern search technology. Handbook of Metaheuristics International Series in Operations Research & Management Science, 57, 457-474. Burke, E. K., Eckersley, A. J., McCollumn, B., Petrovic, S., & Qu, R. (2010). Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research, 206(1), 46-53. Burke, E. K., & Newall, J. P. (2004). Solving examination timetabling problems through adaption of heuristic orderings. Annals of Operations Research, 129, 107-134. Carter, M. W., Laporte, G., & Lee, S. Y. (1996). Examination timetabling: algorithm strategies and applications. Journal of the Operational Research Society, 47, 373-383. Cataldo, A., Ferrer, J., Miranda, J., Rey, P. A., & Sauré, A. (2017). An integer programming approach to curriculum-based examination timetabling. Annals Operations Research, 258(2), 369-393. Chaudhari, A., & De, K. (2013). Fuzzy integer linear programming mathematical models for examination timetable problem. ArXiv, abs/1307.1900. Chmait, N., & Challita, K. (2013). Using simulated annealing and ant-colony optimization algorithms to solve the scheduling problem. Computer Science and Information Technology, 1(3), 208-224. Cowling, P., Kendall, G., & Soubeiga, E. (2000). A hyperheuristic approach to scheduling a sales summit. Proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling, (pp. 176-190). Springer Berlin Heidelberg. Dowsland, K. A., & Thompson, J. M. (2005). Ant colony optimization for the examination scheduling problem. The Journal of The Operational Research Society, 56(4), 426-438. Eley, M. (2006). Ant algorithms for the exam timetabling problem. Proceedings of the 6th International Conference on Practice and Theory of Automated Timetabling VI (PATAT 2006), (pp. 364-382), Springer Berlin Heidelberg. Hosny, M. (2019). Metaheuristic approaches for solving university timetabling problems: a review and case studies from middle eastern universities. Proceedings of EMENA-ISTL 2018, (pp. 10-20), Springer International Publishing. Jamaluddin, N. F., & Aizam, N. A. H. (2016). Timetabling communities’ demands for an effective examination timetabling using integer linear programming. International Journal of Mathematical and Computational Sciences, 10(5), 263-268. Kendall, G., & Hussin, N. M. (2004). A tabu search hyper-heuristic approach to the examination timetabling problem at the MARA University of Technology. Proceedings of the 5th International Conference on Practice and Theory of Automated Timetabling PATAT 2004, (pp. 270-293), Springer Berlin Heidelberg. Mandal, A. K., & Kahar, M. N. M. (2015). Combination of graph heuristic with hill climbing search for solving capacitated examination timetabling problem. Proceedings of the 4th International Conference on Software Engineering and Computer Systems, (pp. 118-123). IEEE. Marie-Sainte, S. L. (2017). A new hybrid particle swarm optimization algorihm for real-world univerisity examination timetabling problem. Proceedings of the Computing Conference, (pp. 157-163). Parker, R. G., & Rardin, R. L. (1988). Discrete optimization. Academic Press Professional, Inc, New York. Pillay, N. (2016). A review of hyper-heuristics for educational timetabling. Annals of Operations Research, 239(1), 3-38. Pillay, N., & Banzhaf, W. (2010). An informed genetic algorithm for the examination timetabling problem. Applied Soft Computing, 10(2), 457-467. Pillay, N., & Ozcan, E. (2017). Automated generation of constructive ordering heuristics for educational timetabling. Annals of Operations Research, 275, 1-28. Sörensen, K., Sevaux, M., & Glover, F. (2017). A history of metaheuristics. Handbook of Heuristics, 1-18. Springer. Wijgers, R., & Hoogeveen, H. (2006). A column generation approach for examination timetabling. Technical report. Utrecht: University Utrecht.

Computerised Multi-Objective Faculty Exam Timetabling Problem

相似書籍