Solving the Teacher Assignment Problem by Two Metaheuristics

Aldy Gunawan ； Kien Ming Ng

《International Journal of Information and Management Sciences》 22：1 (2011/03) Pp. 73-86

https://doi.org/10.6186/IJIMS.2011.22.1.5

並列摘要

The timetabling problem arising from a university in Indonesia is addressed in this paper. It involves the assignment of teachers to the courses and course sections. We formulate the problem as a mathematical programming model. Two different algorithms, mainly based on simulated annealing (SA) and tabu search (TS) algorithms, are proposed for solving the problem. The proposed algorithms consist of two phases. The first phase involves allocating the teachers to the courses and determining the number of courses to be assigned to each teacher. The second phase involves assigning the teachers to the course sections in order to balance the teachers' load. The performance of the proposed algorithms is evaluated using two sets of real data and some randomly generated problem instances. The computational results show that in general, tabu search performs better than simulated annealing and other previous work. For the real data sets, the computational results show that both proposed algorithms yield better solutions when compared to manual allocation done by the university.

並列關鍵字

Timetabling problem ； teacher assignment ； simulated annealing ； Tabu search

參考文獻

Andrew, G. M.,Collins, R.(1971).Matching faculty to course.College University.46(2),83-89.

Bellanti, F.,Carello, G.,Croce, F. D.,Tadei, R.(2004).A greedy-based neighborhood search approach to a a nurse rostering problem.European Journal of Operational Research.153(1),28-40.

Breslaw, J. A.(1976).A linear programming solution to the faculty assignment problem.Socio-Economic Planning Sciences.10(6),227-230.

Burke, E. K.,de Causmaecker, P.,Berghe, G. V.,Landeghem, H. V.(2004).The state of the art of nurse rostering.Journal of Scheduling.7(6),441-499.

Burke, E. K.,McCollum, B.,Meisel, A.,Petrovic, S.,Qu, R.(2007).A graph-based hyper-heuristic for educational timetabling problems.European Journal of Operational Research.176(1),177-192.