Computerised Heuristic Algorithm for Multi-location Lecture Timetabling

This research focuses on multi-location coursework timetabling problem for Master of Science in Human Resource Development (MSc HRD) at the Faculty of Cognitive Sciences and Human Development (FCSHD), Universiti Malaysia Sarawak (UNIMAS). The MSc HRD degree is designed especially for working profess...

Full description

Saved in:

Bibliographic Details
Main Author:	Kuan, Huiggy
Format:	Thesis
Language:	English English
Published:	2020
Subjects:	QA75 Electronic computers Computer science
Online Access:	http://ir.unimas.my/id/eprint/30319/1/Computerised%20Heuristic%20Algorithm%20for%20Multi-Location%20Lecture%20Timetabling%20%2824%20pgs%29.pdf http://ir.unimas.my/id/eprint/30319/6/Kuan%20%20ft.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-unimas-ir.30319
record_format	uketd_dc
institution	Universiti Malaysia Sarawak
collection	UNIMAS Institutional Repository
language	English English
topic	QA75 Electronic computers Computer science
spellingShingle	QA75 Electronic computers Computer science Kuan, Huiggy Computerised Heuristic Algorithm for Multi-location Lecture Timetabling
description	This research focuses on multi-location coursework timetabling problem for Master of Science in Human Resource Development (MSc HRD) at the Faculty of Cognitive Sciences and Human Development (FCSHD), Universiti Malaysia Sarawak (UNIMAS). The MSc HRD degree is designed especially for working professionals to seek advanced knowledge, skills and confidence in the areas of human resource development and management. The courses are conducted during weekends. Apart from the main campus at Kota Samarahan it is also being offered at other learning centres in Malaysia, in order to fulfil the high market demand to obtain a master degree. Due to this, the lecturers are assigned to different teaching locations. This situation has made the timetabling of lectures very challenging. Moreover, the process of current manual timetabling practice to produce a clash-free timetable is time-consuming. Besides that, the current timetabling practice needs to fulfil constraints such as where lecturer’s unavailable dates, different types of teaching slot, team-teaching among lecturers, the lecturer can only conduct one course or at one location at one time, total teaching hours for a course and even distribution of lecture sessions and lecturer duty. The objective of this study is to design a heuristic model for multi-location timetabling problem. A two-stage heuristic algorithm is proposed to solve the multi-location timetabling problem on MSc HRD coursework programme. The proposed two-stage heuristic algorithm consists of Lecturer Grouping Stage which allocates the lecturers into different team-teaching groups. After that, the algorithm proceeds to Group Allocation Stage in a round robin optimisation. The lecturer’s unavailability is considered in Stage II as well. Real data from two semesters were collected from FCSHD to test the feasibility of the proposed solution. The simulator generates clash-free timetable in less than a minute, while fulfilling the unavailability dates of lecturers and different types of teaching slot. On average, more than 80% of the timetabled days fall within the acceptable range of the week’s break between lecture sessions. A set of sensitivity analysis has also been conducted under different scenarios, such as the unavailability dates of lecturers, teaching slot type for locations and team-teaching basis. The results show that the proposed solution is effective and robust in solving MSc HRD coursework programme multi-location timetabling problem.
format	Thesis
qualification_level	Master's degree
author	Kuan, Huiggy
author_facet	Kuan, Huiggy
author_sort	Kuan, Huiggy
title	Computerised Heuristic Algorithm for Multi-location Lecture Timetabling
title_short	Computerised Heuristic Algorithm for Multi-location Lecture Timetabling
title_full	Computerised Heuristic Algorithm for Multi-location Lecture Timetabling
title_fullStr	Computerised Heuristic Algorithm for Multi-location Lecture Timetabling
title_full_unstemmed	Computerised Heuristic Algorithm for Multi-location Lecture Timetabling
title_sort	computerised heuristic algorithm for multi-location lecture timetabling
granting_institution	Universiti Malaysia Sarawak (UNIMAS)
granting_department	Faculty of Computer Science and Information Technology
publishDate	2020
url	http://ir.unimas.my/id/eprint/30319/1/Computerised%20Heuristic%20Algorithm%20for%20Multi-Location%20Lecture%20Timetabling%20%2824%20pgs%29.pdf http://ir.unimas.my/id/eprint/30319/6/Kuan%20%20ft.pdf
_version_	1794023010510831616
spelling	my-unimas-ir.303192024-01-15T08:58:32Z Computerised Heuristic Algorithm for Multi-location Lecture Timetabling 2020 Kuan, Huiggy QA75 Electronic computers. Computer science This research focuses on multi-location coursework timetabling problem for Master of Science in Human Resource Development (MSc HRD) at the Faculty of Cognitive Sciences and Human Development (FCSHD), Universiti Malaysia Sarawak (UNIMAS). The MSc HRD degree is designed especially for working professionals to seek advanced knowledge, skills and confidence in the areas of human resource development and management. The courses are conducted during weekends. Apart from the main campus at Kota Samarahan it is also being offered at other learning centres in Malaysia, in order to fulfil the high market demand to obtain a master degree. Due to this, the lecturers are assigned to different teaching locations. This situation has made the timetabling of lectures very challenging. Moreover, the process of current manual timetabling practice to produce a clash-free timetable is time-consuming. Besides that, the current timetabling practice needs to fulfil constraints such as where lecturer’s unavailable dates, different types of teaching slot, team-teaching among lecturers, the lecturer can only conduct one course or at one location at one time, total teaching hours for a course and even distribution of lecture sessions and lecturer duty. The objective of this study is to design a heuristic model for multi-location timetabling problem. A two-stage heuristic algorithm is proposed to solve the multi-location timetabling problem on MSc HRD coursework programme. The proposed two-stage heuristic algorithm consists of Lecturer Grouping Stage which allocates the lecturers into different team-teaching groups. After that, the algorithm proceeds to Group Allocation Stage in a round robin optimisation. The lecturer’s unavailability is considered in Stage II as well. Real data from two semesters were collected from FCSHD to test the feasibility of the proposed solution. The simulator generates clash-free timetable in less than a minute, while fulfilling the unavailability dates of lecturers and different types of teaching slot. On average, more than 80% of the timetabled days fall within the acceptable range of the week’s break between lecture sessions. A set of sensitivity analysis has also been conducted under different scenarios, such as the unavailability dates of lecturers, teaching slot type for locations and team-teaching basis. The results show that the proposed solution is effective and robust in solving MSc HRD coursework programme multi-location timetabling problem. Universiti Malaysia Sarawak (UNIMAS) 2020 Thesis http://ir.unimas.my/id/eprint/30319/ http://ir.unimas.my/id/eprint/30319/1/Computerised%20Heuristic%20Algorithm%20for%20Multi-Location%20Lecture%20Timetabling%20%2824%20pgs%29.pdf text en public http://ir.unimas.my/id/eprint/30319/6/Kuan%20%20ft.pdf text en validuser masters Universiti Malaysia Sarawak (UNIMAS) Faculty of Computer Science and Information Technology Abdullah, S., Turabieh, H., McCollum, B., & McMullan, P. (2012). A hybrid metaheuristic approach to the university course timetabling problem. Journal of Heuristics, 18(1), 1-23. Adewumi, A. O., Sawyerr, B. A., & Montaz Ali, M. (2009). A heuristic solution to the university timetabling problem. Engineering Computations, 26(8), 972-984. Adriaen, M., De Causmaecker, P., & Berghe, G. V. (2003). Decentralised course timetabling in a large hierarchical organisation. Proceedings MISTA. Aladag, C. H., & Hocaoglu, G. (2007). A tabu search algorithm to solve a course timetabling problem. Hacettepe Journal of Mathematics and Statistics, 36(1), 53-64. Almeida, M. W. S., Medeiros, J. P. S., & Oliveira, P. R. (2015). Solving the academic timetable problem thinking on student needs. In Machine Learning and Applications (ICMLA), 2015 IEEE 14th International Conference on (pp. 673-676). IEEE. Al-Omari, H., & Sabri, K. E. (2006). New graph coloring algorithms. American Journal of Mathematics and Statistics, 2(4), 739-741. Burke, E. K., & Newall, J. P. (2004). Solving examination timetabling problems through adaption of heuristic orderings. Annals of Operations Research, 129(1-4), 107-134. Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266-280. Burke, E. K., Cowling, P., & Silva, J. L. (2001). Hybrid population-based metaheuristic approaches for the space allocation problem. In Evolutionary Computation, 2001. Proceedings of the 2001 Congress on (Vol. 1, pp. 232-239). IEEE. Burke, E. K., Kendall, G., & Soubeiga, E. (2003). A tabu-search hyperheuristic for timetabling and rostering. Journal of Heuristics, 9(6), 451-470. Burke, E. K., Petrovic, S., & Qu, R. (2006). Case-based heuristic selection for timetabling problems. Journal of Scheduling, 9(2), 115-132. Burke, E., & Erben, W. (Eds.). (2003). Practice and Theory of Automated Timetabling III: Third International Conference, PATAT 2000 Konstanz, Germany, August 16-18, 2000 Selected Papers (Vol. 2079). Springer. Burke, E., & Rudova, H. (Eds.). (2007). Practice and Theory of Automated Timetabling VI: 6th International Conference, PATAT 2006 Brno, Czech Republic, August 30-September 1, 2006 Revised Selected Papers (Vol. 3867). Springer. Burke, E., Bykov, Y., & Petrovic, S. (2000). A multicriteria approach to examination timetabling. In International Conference on the Practice and Theory of Automated Timetabling (pp. 118-131). Springer, Berlin, Heidelberg. Chaudhuri, A., & De, K. (2010). Fuzzy genetic heuristic for university course timetable problem. International Journal of Advances in Soft Computing and its Application, 2(1), 100-121. Chowdhary, A., Kakde, P., Dhoke, S., Ingle, S., Rushiya, R., & Gawande, D. (2014). Timetable generation system. International Journal of Computer Science and Mobile Computing, 3(2), 410-414. Cooper, T. B., & Kingston, J. H. (1995). The complexity of timetable construction problems. In International Conference on the Practice and Theory of Automated Timetabling (pp. 281-295). Springer, Berlin, Heidelberg. Dammak, A., Elloumi, A., Kamoun, H., & Ferland, J. A. (2008). Course timetabling at a Tunisian university: A case study. Journal of Systems Science and Systems Engineering, 17(3), 334-352. Dandashi, A., & Al-Mouhamed, M. (2010). Graph coloring for class scheduling. In Computer Systems and Applications (AICCSA), 2010 IEEE/ACS International Conference on (pp. 1-4). IEEE. Daskalaki, S., & Birbas, T. (2005). Efficient solutions for a university timetabling problem through integer programming. European Journal of Operational Research, 160(1), 106-120. Davoudzadeh, M., Rafeh, R., & Rashidi, R. (2009). A Linear Solution for the University Timetabling Problem. In Computer and Electrical Engineering, 2009. ICCEE'09. Second International Conference on (Vol. 2, pp. 54-57). IEEE. Di Stefano, C., & Tettamanzi, A. G. (2001, April). An evolutionary algorithm for solving the school time-tabling problem. In Workshops on Applications of Evolutionary Computation (pp. 452-462). Springer, Berlin, Heidelberg. Ferdoushi, T., Das, P. K., & Akhand, M. A. H. (2014). Highly constrained university course scheduling using modified hybrid particle swarm optimization. In Electrical Information and Communication Technology (EICT), 2013 International Conference on (pp. 1-5). IEEE. Fred, N. (2017). Students’ perception of quality of time resources in teacher education programmes in the Universities in Nakuru County, Kenya. Mara Research Journal of Humanities & Social Sciences-ISSN: 2519-1489, 1(1), 86-93. Ganguli, R., & Roy, S. (2017). A study on course timetable scheduling using Graph Coloring Approach. International Journal of Computational and Applied Mathematics, 12(2), 469-485. Goltz, H. J., & Matzke, D. (1999). University timetabling using constraint logic programming. In International Symposium on Practical Aspects of Declarative Languages (pp. 320-334). Springer, Berlin, Heidelberg. Han, L., & Kendall, G. (2003). An investigation of a tabu assisted hyper-heuristic genetic algorithm. In Evolutionary Computation, 2003. The 2003 Congress on (Vol. 3, pp. 2230-2237). IEEE. Han, L., & Kendall, G. (2003). Guided operators for a hyper-heuristic genetic algorithm. In Australasian Joint Conference on Artificial Intelligence (pp. 807-820). Springer, Berlin, Heidelberg. Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. London, England: MIT Press. Houhamdi, Z., Athamena, B., Abuzaineddin, R., & Muhairat, M. (2019). A Multi-Agent System for Course Timetable Generation. TEM Journal, 2019(1), 211-221. Junn, K. Y., Obit, J. H., & Alfred, R. (2017). A constraint programming approach to solving university course timetabling problem (UCTP). Advanced Science Letters, 23(11), 11023-11026. Junn, K. Y., Obit, J. H., & Alfred, R. (2017). The Study of Genetic Algorithm Approach to Solving University Course Timetabling Problem. In International Conference on Computational Science and Technology (pp. 454-463). Springer, Singapore. Kostuch, P. (2004). The university course timetabling problem with a three-phase approach. In International Conference on the Practice and Theory of Automated Timetabling (pp. 109-125). Springer, Berlin, Heidelberg. Lewis, R. (2008). A survey of metaheuristic-based techniques for university timetabling problems. OR Spectrum, 30(1), 167-190. Lih, B. C., San Nah, S., & Bolhassan, N. A. (2015). A study on heuristic timetabling method for faculty course timetable problem. In IT in Asia (CITA), 2015 9th International Conference on (pp. 1-3). IEEE. Lindahl, M., Mason, A. J., Stidsen, T., & Sorensen, M. (2018). A strategic view of university timetabling. European Journal of Operational Research, 266(1), 35-45. Mauritsius, T. (2018). A three phase heuristic for examination timetabling problem. In 2018 International Conference on Information Management and Technology (pp. 1-9). IEEE. McCollum, B. (2007). A perspective on bridging the gap between theory and practice in university timetabling. Practice and Theory of Automated Timetabling VI, 3-23. Meisels, A., & Kaplansky, E. (2002). Scheduling agents–distributed timetabling problems. In International Conference on the Practice and Theory of Automated Timetabling (pp. 166-177). Springer, Berlin, Heidelberg. Mirrazavi, S. K., Mardle, S. J., & Tamiz, M. (2003). A two-phase multiple objective approach to university timetabling utilising optimisation and evolutionary solution methodologies. Journal of the Operational Research Society, 54(11), 1155-1166. Murray, K., Muller, T., & Rudova, H. (2006). Modeling and solution of a complex university course timetabling problem. In International Conference on the Practice and Theory of Automated Timetabling (pp. 189-209). Springer, Berlin, Heidelberg. Padmini, M. V., & Athre, K. (2010). Efficient design of university timetable. In 2010 IEEE International Conference on Electro/Information Technology (pp. 1-5). IEEE. Pandey, J., & Sharma, A. K. (2016). Survey on university timetabling problem. In Computing for Sustainable Global Development (INDIACom), 2016 3rd International Conference on (pp. 160-164). IEEE. Parera, S., Sukmana, H. T., & Wardhani, L. K. (2016). Application of genetic algorithm for class scheduling (Case study: Faculty of science and technology UIN Jakarta). In Cyber and IT Service Management, International Conference on (pp. 1-5). IEEE. Petrovic, S., & Burke, E. (2004). University timetabling. In Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter 45. Pillay, N. (2016). A review of hyper-heuristics for educational timetabling. Annals of Operations Research, 239(1), 3-38. Rossi-Doria, O., & Paechter, B. (2004). A memetic algorithm for university course timetabling. In Combinatorial Optimisation 2004 Book of Abstracts, 56. Lancaster University Lancaster, UK. Sabar, N. R., Ayob, M., Qu, R., & Kendall, G. (2012). A graph coloring constructive hyper-heuristic for examination timetabling problems. Applied Intelligence, 37(1), 1-11. Santiago-Mozos, R., Salcedo-Sanz, S., DePrado-Cumplido, M., & Bousoño-Calzón, C. (2005). A two-phase heuristic evolutionary algorithm for personalizing course timetables: a case study in a Spanish university. Computers & Operations Research, 32(7), 1761-1776. Sarin, S. C., Wang, Y., & Varadarajan, A. (2010). A university-timetabling problem and its solution using Benders’ partitioning—a case study. Journal of Scheduling, 13(2), 131-141. Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87-127. Schimmelpfeng, K., & Helber, S. (2007). Application of a real-world university-course timetabling model solved by integer programming. OR Spectrum, 29(4), 783-803. Sigl, B., Golub, M., & Mornar, V. (2003). Solving timetable scheduling problem using genetic algorithms. In Information Technology Interfaces, 2003. ITI 2003. Proceedings of the 25th International Conference on (pp. 519-524). IEEE. Socha, K., Knowles, J., & Sampels, M. (2002). A max-min ant system for the university course timetabling problem. In International Workshop on Ant Algorithms (pp. 1-13). Springer, Berlin, Heidelberg. Socha, K., Sampels, M., & Manfrin, M. (2003). Ant algorithms for the university course timetabling problem with regard to the state-of-the-art. In Workshops on Applications of Evolutionary Computation (pp. 334-345). Springer, Berlin, Heidelberg. Thanh, N. D. (2007). Solving timetabling problem using genetic and heuristic algorithms. In Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2007. SNPD 2007. Eighth ACIS International Conference on (Vol. 3, pp. 472-477). IEEE. Wahid, J., & Hussin, N. M. (2016). Combination of graph heuristics in producing initial solution of curriculum based course timetabling problem. In AIP Conference Proceedings (Vol. 1761, No. 1, p. 020104). AIP Publishing.

Computerised Heuristic Algorithm for Multi-location Lecture Timetabling

Similar Items