Optimal solution to timetable scheduling problem using 0-1 integer programming: A case study of a school in Sri Lanka

Abstract

In many real world scenarios scheduling is applied to perform a particular task efficiently while overcoming the limitations to perform that task. Educational field is an area where scheduling is essential. In this article a time table schedule is implemented to a particular section in a school which will arrange a sequence of classes between students and teachers. The Technology subject stream was introduced to the education system in Sri Lanka in 2013. Due to the lack of resources most of the schools which started the new subject stream face difficulties in implementing a proper time table schedule. A major school in the Central province in Sri Lanka was used as a case study. The main objective of the study is to maximally assign teachers to the classes based on their precedence levels and availability. An integer programming model was implemented in order to achieve the above mentioned objective. A set of binary (0 or 1) integer decision variables were defined in order to check whether a teacher is allocated to a class in a given time slot or not. The set of constraints that should be satisfied in order to achieve the optimal allocation of teachers are, each subject should be taught exactly 1 time slot in a given day (a given working day consists of 5 time slots), each subject should cover exactly 5 time slots per week, the school has limited number of class rooms (6 class rooms) to conduct several subjects at the same time, some teachers are not available for the technological section in certain time slots, a teacher cannot teach two classes at the same time. The optimal feasible allocation of teachers to the classes while satisfying the set of constraints can be obtained using Microsoft Excel package. Then with the use of the obtained results, a time table schedule can be implemented for the section. The existing time table schedule for the section was obtained with the past experience and inquiries made by both teachers and students. Thus an optimum, feasible allocation of teachers was obtained after a series of trials. But with the use of the implemented integer programming model an accurate schedule can be implemented easily. By making few changes to the model, it can be used to construct time table schedules for the other sections of the school as well.