Course timetabling at a Tunisian University: A case study

Abstract

This paper deals with the Course Timetabling Problem at an institution in a Tunisian University. We introduce a heuristic procedure to construct a feasible timetable for all lectures and tutorials taken by different groups of each sub-section of any section. We describe the timetabling problem using a list of all specific hard and soft constraints. We formulate the problem as a set of linear constraints using two sets of binary variables corresponding to lectures and tutorials, respectively. This heuristic is illustrated with real data for a sub-section of the Faculty of Economics and Management Sciences of Sfax in Tunisia, and the resulting timetables are compared with those generated manually. The results of another full section have confirmed the good quality of the proposed heuristic when compared with the hand made solution.

Keywords

Educational timetabling / integer programming / implementations / heuristic search

References

[1] Al-Yakoob S.M., Sherali H.D.. Mathematical programming models and algorithms for a class-faculty assignment problem. European Journal of Operational Resarch, 2006, 173: 488-507.

[2] Aubin J., Ferland J.A.. A Large scale timetabling problem. Computers and Operations Research, 1989, 16: 67-77.

[3] Burke E.K., MacCathy B., Petrovic S., Qu R.. Multiple-retrieval case-based reasoning for course timetabling problems. Journal of the Operational Research Society, 2006, 57: 148-162.

[4] Burke E.K., MacCathy B., Petrovic S., Qu R.. Case-base reasoning in course timetabling: an attribute graph approach. In: Case-based reasoning research and development. Lecture Notes in Artificial Intelligence, 2001, 2080: 90-104.

[5] Burke E.K., MacCathy B., Petrovic S., Qu R.. Structured cases in cases based reasoning-re-using and adapting cases for time-tabling problems. Knowledge-Based System, 2000, 13: 159-165.

[6] Burke, E.K., MacCathy, B.L., Petrovic, S. & Qu, R. (2002). Knowledge discovery in hyper-heuristic using case-based reasoning on course timetabling. In: The 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 2740, 90–103, Springer-Verlag

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

[8] Burke E.K., Petrovic S., Qu R.. Case-based heuristic selection for timetabling problems. Journal of Scheduling, 2006, 9: 115-132.

[9] Dammak, A., Elloumi, A. & Kamoun, H. (2009). Lecture timetabling at a Tunisian university. Accepted for publication and to appear in International Journal of Operational Research, 4 (2)

[10] Daskalaki S., Birbas T., Housos E.. An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 2004, 153(1): 117-135.

[11] De Werra, D. (1969). Résolution de problèmes d’horaire par la théorie des graphes. Doctoral Thesis EPFL N° 96, Département de mathématique

[12] De Werra, D. (1995). Some combinatorial models for course scheduling. In: The 1st International Conference on the Practice and Theory of Automated Timetabling, 296–308, Lecture Notes in Computer Science 1408, Springer-Verlag

[13] Dinkel J.J., Mote J., Venkataramanan M.A.. An efficient decision support system for academic course scheduling. Operations Research, 1989, 37: 853-864.

[14] Ferland J.A., Fleurent C.. SAPHIR: A decision support system for course scheduling. Interfaces, 1994, 24(2): 105-115.

[15] Ferland J.A., Roy S.. Timetabling problem for university as assignment of activities to resources. Computers and Operations Research, 1985, 12: 207-218.

[16] Glassey C.R., Mizrach M.. A decision support system for assigning classes to rooms. Interfaces, 1986, 16(5): 92-100.

[17] Timothy, A.R. (2004). A study of university timetabling that blends graph coloring with the satisfaction of various essential and preferential conditions, Ph.D. Thesis. Rice University

[18] Tripathy A.. A. school timetablinga case in large binary integer linear programming. Management Science, 1984, 30: 1473-1489.