Heuristic Algorithm for Multi-Location Lecture Timetabling

San Nah Sze, Huiggy Kuan, Kang Leng Chiew, Wei King Tiong, Chin Siong Heng

Abstract


This paper studies a real faculty timetabling problem with multi-location consideration. Faculty of Cognitive Sciences and Human Development, UNIMAS offers a master's program by coursework to postgraduate students. The construction of timetables for all the courses offered is a tedious process due to constraints such as team-teaching allocation, unavailability dates of lecturers, and multi-location considerations. Therefore, a manually designed timetable is not as practical as it is time consuming when operational constraints must be fulfilled. In this paper, a two-stage heuristic algorithm is proposed to solve this postgraduate coursework timetable problem. This is because the heuristic algorithm is easy to apply and able to generate a feasible solution in a short time. The proposed two-stage heuristic algorithm consists of Lecturer Grouping Stage and Group Allocation Stage. In Stage I, the lecturers are assigned into four lecturer groups with the condition of no identical lecturers in each of the groups. Then, in Stage II, these groups are allocated into a set of academic weeks throughout the semester. The timeslot for each course can be allocated, and the team-teaching slot for the lecturers can be assigned in this stage. The result from the two-stage heuristic algorithm shows remarkable improvement over the real timetables solution by analyzing the distribution of lecture sessions of the courses.


Keywords


university timetabling problem; heuristic algorithm; multi-location; team teaching; coursework timetabling.

Full Text:

PDF

References


A. Chowdhary, P. Kakde, S. Dhoke, S. Ingle, R. Rushiya, and D. Gawande, “Timetable generation system,†Int. J. Comput. Sci. Mob. Comput., vol. 3, no. 2, 2014.

A. Dammak, A. Elloumi, H. Kamoun, and J. A. Ferland, “Course Timetabling at a Tunisian University: a case study,†J. Syst. Sci. Syst. Eng., vol. 17, no. 3, p. 334, 2008.

M. Lindahl, T. J. R. Stidsen, and M. Sørensen, “Strategic, Tactical and Operational University Timetabling,†2017.

M. W. S. Almeida, J. P. S. Medeiros, and P. R. Oliveira, “Solving the Academic Timetable Problem Thinking on Student Needs,†in 2015 IEEE 14th International Conference on Machine Learning and Applications (ICMLA), 2015, pp. 673–676.

N. Pillay, “A review of hyper-heuristics for educational timetabling,†Ann. Oper. Res., vol. 239, no. 1, pp. 3–38, 2016.

M. V Padmini and K. Athre, “Efficient design of university timetable,†in 2010 IEEE International Conference on Electro/Information Technology, 2010, pp. 1–5.

J. Pandey and A. K. Sharma, “Survey on university timetabling problem,†in 2016 3rd International Conference on Computing for Sustainable Global Development (INDIACom), 2016, pp. 160–164.

E. Burke and W. Erben, Practice and Theory of Automated Timetabling III: Third International Conference, PATAT 2000 Konstanz, Germany, August 16-18, 2000 Selected Papers, vol. 2079. Springer, 2003.

A. E. Phillips, C. G. Walker, M. Ehrgott, and D. M. Ryan, “Integer programming for minimal perturbation problems in university course timetabling,†Ann. Oper. Res., vol. 252, no. 2, pp. 283–304, 2017.

G. Woumans, L. De Boeck, J. Beliën, and S. Creemers, “A column generation approach for solving the examination-timetabling problem,†Eur. J. Oper. Res., vol. 253, no. 1, pp. 178–194, 2016.

J. A. Soria-Alcaraz, E. Özcan, J. Swan, G. Kendall, and M. Carpio, “Iterated local search using an add and delete hyper-heuristic for university course timetabling,†Appl. Soft Comput., vol. 40, pp. 581–593, 2016.

T. A. Nugraha, K. T. Putra, and N. Hayati, “University Course Timetabling with Genetic Algorithm: A Case Study,†J. Electr. Technol. UMY, vol. 1, no. 2, pp. 100–105, 2017.

E. A. Abdelhalim and G. A. El Khayat, “A utilization-based genetic algorithm for solving the university timetabling problem (uga),†Alexandria Eng. J., vol. 55, no. 2, pp. 1395–1409, 2016.

R. A. O. Vrielink, E. A. Jansen, E. W. Hans, and J. van Hillegersberg, “Practices in timetabling in higher education institutions: a systematic review,†Ann. Oper. Res., vol. 275, no. 1, pp. 145–160, 2019.

M. Davoudzadeh, R. Rafeh, and R. Rashidi, “A linear solution for the university timetabling problem,†in 2009 Second International Conference on Computer and Electrical Engineering, 2009, vol. 2, pp. 54–57.

T. Ferdoushi, P. K. Das, and M. A. H. Akhand, “Highly constrained university course scheduling using modified hybrid particle swarm optimization,†in 2013 International Conference on Electrical Information and Communication Technology (EICT), 2014, pp. 1–5.

S. Parera, H. T. Sukmana, and L. K. Wardhani, “Application of genetic algorithm for class scheduling (Case study: Faculty of science and technology UIN Jakarta),†in 2016 4th International Conference on Cyber and IT Service Management, 2016, pp. 1–5.

R. Lewis, “A survey of metaheuristic-based techniques for university timetabling problems,†OR Spectr., vol. 30, no. 1, pp. 167–190, 2008.

K. Schimmelpfeng and S. Helber, “Application of a real-world university-course timetabling model solved by integer programming,†Or Spectr., vol. 29, no. 4, pp. 783–803, 2007.

J. Wahid and N. M. Hussin, “Combination of graph heuristics in producing initial solution of curriculum based course timetabling problem,†in AIP Conference Proceedings, 2016, vol. 1761, no. 1, p. 20104.




DOI: http://dx.doi.org/10.18517/ijaseit.10.2.10231

Refbacks

  • There are currently no refbacks.


Published by INSIGHT - Indonesian Society for Knowledge and Human Development