Published on Sep 05, 2023
A college timetable is a temporal arrangement of a set of classes and classrooms in which all given constraints are satisfied. Timetabling has long been known to belong to the class of problems called NP hard. This project introduces a practical timetabling algorithm capable of taking care of both strong and weak constraints effectively, used in an automated timetabling system.
Rich Internet applications (RIA) are web applications that have the features and functionality of traditional desktop applications. RIAs typically transfer the processing necessary for the user interface to the web client but keep the bulk of the data (i.e., maintaining the state of the program, the data etc) back on the application server. We have used the Google Web Toolkit, which is RIA framework, for the same purpose.
Our project reduces the overhead on server of rendering client’s UI components and makes room for processing time of Timetable Generator Algorithm. Our Timetabling Algorithm is main component of our project which produces the HTML based weekly timetable sheet as the output.
Our project takes various inputs from the user such as Teacher List, Course List, Semester List, Room List, Day List and Timeslot as well as various rules, facts and constraints using web based forms, which are stored in XML based knowledge base.
This knowledge base serves as input to our Timetable Generator Algorithm residing on server machine. Both GWT Client Side UI code and our algorithm are written in JAVA, which makes our project platform independent. Further benefits of choosing these frameworks are explained in later part of report with practically acceptable results.
An algorithm for constructing a timetable has to assign instances of the different resource classes to the event class instances. Some of these assignments are predetermined and cannot be changed, and some have to be done during the planning phase. To construct a timetable, one of the views mentioned in above section is used. In the school timetabling case our algorithm might use the class view to assign a subject, teacher and room to a lesson. In this case the class is fixed and the other instances have to be assigned to. Additionally, a time interval has to be assigned to each event class instance.
For each viewing perspective there are as many timetables as instances of this class to be planned exist. If we have t teachers at a high school, for example, t different teacher timetables belong to them. That is, if there exist l lessons in a high school timetabling problem, furthermore t teachers, r rooms and c classes, the number of instances of event classes including all views will be (t+r+c)×l. The timetables of the instances of one planning class contain all information necessary to construct the timetables for the instances of the other planning classes: i.e. the timetables of the different views can be mapped to timetables of other views. In the school timetabling case the t teachers’ timetables can be mapped to the r rooms’ timetables
That is why it is usually sufficient for a timetabling program to save the timetables of one resource type only. This avoids data redundancy caused by storing the same event information in different places, i.e. from different views.
Nevertheless, to be able to check constraint violations, translations to other views have to be done, for example to compute the number of assigned lessons of a teacher when working with the class view. Otherwise expensive computing time has to be accepted in order to compute the necessary information.
