Modeling and solving timetabling problems of academic departments using linear programming techniques

Abstract

Time table is said to be the second clock which indicates all the activities undertaken in all kinds of academic institutions. A well-constructed timetable establishes a natural rhythm and routine, which can be comforting to the teachers and associated infrastructure. The problem of constructing timetables for academic departments of universities has been a classical, complicated, combinatorial problem and a time consuming one; always characterized by inconveniences such as clashes that have to be sorted out, while in practice and it necessitates a better solution. Existing commercialized tools are not fruitfully succeeding with user or client requirements especially in terms of academic departments in Universities. Globally available optimization techniques are very efficient and but do not address the requirements of an academic department. Comparably Linear-Programming is the most powerful optimization techniques in which optimality can be obtained for a linear objective function subject to set of linear constraints. In this study an attempt was made to formulate the timetable scheduling as an appropriate linear programming problem which can be easily solved using Excel-Solver. The Linear-Program was formulated by especially prioritizing the teachers’ preference and subject to the constraints such as weekly minimum number of assignments, availability of the number of class rooms, taking into account the number of teachers and student groups in order to minimize the clashes. As per the efforts made by addressing diverse aspects by means of accompanying linear programming techniques and using Excel solver, there was a strong possibility to attain the optimal solution for more simplified derivation of well-constructed timetables. In future, it could be utilized to develop a more efficient a user friendly tool, using JAVA to generate timetables for academic departments in universities.