Solving the Teacher Assignment Problem by Two Metaheuristics

10.6186/IJIMS.2011.22.1.5

Aldy Gunawan；Kien Ming Ng

Timetabling problem ； teacher assignment ； simulated annealing ； Tabu search

International Journal of Information and Management Sciences

22：1（2011 / 03 / 01）

73 - 86

英文

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.

1. Andrew, G. M.,Collins, R.(1971).Matching faculty to course.College University,46(2),83-89.
2. 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.
3. Breslaw, J. A.(1976).A linear programming solution to the faculty assignment problem.Socio-Economic Planning Sciences,10(6),227-230.
4. 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.
5. 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.
6. Burke, E. K.,Petrovic, S.(2002).Recent research directions in automated timetabling.European Journal of Operational Research,140(2),2002.
7. Carrasco, M. P.,pato, M. V.(2000).A multiobjective genetic algorithm for the class/teacher timetabling problem.Practice and Theory of Automated Timetabling II, Lecture Notes in Computer Science,Berlin:
8. Carter, M.W.,Laporte, G.(1998).Recent developments in practical course timetabling.Practice and Theory of Automated Timetabling II, Lecture Notes in Computer Science,Berlin:
9. Cerny, V.(1985).A thermodynamical approach to the travelling salesman problem: an efficient stimulation algorithm.Journal of Optimization Theory and Applications,45(1),41-51.
10. Chahal, N.,de Werra, D.(1989).An interactive system for constructing timetables on a PC.European Journal of Operational Research,40(1),32-37.
11. Chen, S-M,Lin, C-H.(2007).Multiple DNA sequence alignment based on genetic simulatied annealing techniques.Information and Management Sciences,18(2),97-111.
12. Costa, D.(1994).A tabu search algorithm for computing an operational timetable.European Journal of Operational Research,76(1),98-110.
13. de Causmaecker, P.,Demeester, P.,Berghe, G. V.(2009).A decomposed metaheuristic approach for a real-world university timetabling problem.European Journal of Operational Research,195(1),307-318.
14. de Werra, D.(1985).An introduction to timetabling.European Journal of Operational Research,19(2),151-162.
15. Drezner, Z.(2005).The extended concentric tabu for the quadratic assignment problem.European Journal of Operational Research,160(2),416-422.
16. Du, D. Z.,Pardalos, P. M.(1998).Handbook of Combinaorial Optimization.The Netherlands:Kluwer Academic Publishers.
17. ErgÏ, A.(1996).GA-based examination scheduling experience at Middle East Technical University.The Practice and Theory of Automated Timetabling I: Selected Papers (PATAT 1995), Lecture Notes in Computer Science,Berlin:
18. Eswaramurthy, V. P.,Tamilarasi, A.(2009).Hybridization of ant colony optimization strategies in tabu search for solving job shop scheduling problems.International Journal of Information and Management Sciences,20(2),173-189.
19. Glover, F.(1990).Tabu search - part II.ORSA Journal on Computing,2(1),4-32.
20. Glover, F.(1989).Tabu search - part I.ORSA Journal on Computing,1(3),190-206.
21. Gross, J.(ed.),Yellen, J.(ed.)(2004).The Handbook of Graph Theory.Boca Raton:CRC Press.
22. Gunawan, A.,Lau, H. C.(2009).Master physician scheduling problem.The proceedings of the 4th Multidisciplinary International Scheduling Conference,Dublin, Ireland:
23. Gunawan, A.,Ng, K. M.,Poh, K. L.(2007).Solving the teacher assignment-course scheduling problem by a hybrid algorithm.International Journal of Computer, Information and Systems Science and Engineering,1(2),136-141.
24. Gunawan, A.,Ong, H. L.,Ng, K. M.(2008).A genetic algorithm for the teacher assignment problem.International Journal of Information and Management Sciences,19(1),1-16.
25. Harwood, G. B.,Lawless, R. W.(1975).Optimizing organizational goals in assigning faculty teaching schedules.Decision Science,6(3),513-524.
26. Kirkpatrick, S.,Gellatt, C. D.,Vecchi, M. P.(1983).Optimization by simulated annealing.Science,220(5),671-680.
27. Leung, J.(ed.)(2004).Handbook of Scheduling: Algorithms, Models and Performance.Boca Raton:CRC Press.
28. Liu, S.,Ong, H. L.(2002).A comparative study of algorithms for the flowshop scheduling problem.Asia-Pacific Jounal of Operational Research,19(2),205-222.
29. Massoodian, S.,Esteki, A.(2008).A hybrid genetic algorithm for curriculum based course timetabling.The proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling,Montreal, Canada:
30. Radhakrishnan, S.,Ventura, J. A.(2000).Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times.International Journal of Production Research,38(10),2233-2252.
31. Rankin, R. C.(1996).Automatic timetabling in practice.The Practice and Theory of Automated Timetabling I: Selected Papers (PATAT 1995), Lecture Notes in Computer Science,Berlin:
32. Saleh Elmohamed, M. A.,Coddington, P.,Fox, G.(1998).A comparison of annealing techniques for academic course scheduling.Practice and Theory of Automated Timetabling II, Lecture Notes in Computer Science,Berlin:
33. Schaerf, A.(1999).A survey of automated timetabling.Artificial Intelligence Review,13(2),87-127.
34. Schaerf, A.,Meisels, A.(2000).Soving employee timetabling problems by generalized local search.AI*IA 99: Advances in Artificial Intelligence: 6th Congress of the Italian Association for Artificial Intelligence, Lecture Notes in Computer Science,Berlin:
35. Schniederjans, M. J.,Kim, G. C.(1987).A goal programming model to optimize departmental perference in course assignments.Computers and Operations Research,14(2),87-96.
36. Schönberger, J.,Mattfeld, D. C.,Kopfer, H.(2004).Memetic algorithm timetabling for non-commercial sport leagues.European Journal of Operational Research,153(1),102-116.
37. Tillett, P. I.(1975).An operations research approach to the assignment of teachers to courses.Socio-Economic Planning Sciences,9(3),101-104.
38. Valdes, R. A.,Crespo, E.,Tamarit, J. M.(2000).Assigning students to course sections using tabu search.Annals of Operations Research,96(1),1-16.
39. Votre, V. P.(2008).MAGHO - A tool for teachers and physical resources assignment and for student's scheduling.The proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling,Montreal, Canada:
40. Wang, Y. Z.(2002).An application of genetic algorithm methods for teacher assignment problems.Expert Systems with Applications,22(4),295-302.
41. Wren, A.(1996).Scheduling, timetabling and rostering - a special relationship?.Practice and Theory of Automated Timetabling I, Lecture Notes in Computer Science,Berlin:
42. Yu, E.,Sung, K. S.(2002).A genetic algorithm for a university weekly course timetabling problem.International Transactions in Operational Research,9(6),703-717.

1. Wang, Xiaoqing,Huang, Ling,Cui, Yaodong(2011).Using Layer Patterns in Solving the Two-Dimensional Cutting Stock Problem.International Journal of Information and Management Sciences,22(2),189-199.