22
Building a Timetable Generator
About a year ago, I began planning my final project for school. The main goal was to solve a real-world problem while learning to work on a large project independently. It is no secret that this wasn't my first large project; however, It wasn't a smooth process. This post is a reflection on the process.
The current system for making timetables involves a conditional excel sheet in which you would drag boxes around until they fit. My goal was to make that process easier for the client. They needed an app that would allow them to make timetables with zero chance of overlap or double-booking.
The problem of programmatically creating timeslots that fit into a timetable as a whole is NP-Complete. I would have to evaluate all possible combinations to find a semi optimal solution.
A similar problem which is also NP-Complete is the Knapsack problem. For those who are unfamiliar; with the Knapsack problem, you start with a Knapsack that can hold a finite amount of items let's say 40lbs. From a selection of items in a shop all with differing weights, what arrangement of items would you steal to obtain the highest possible value which fit in the 40lbs limit.
One way to solve such a problem is by use of greedy algorithms; which pick an optimal move at each step to achieve a "good enough solution". (Note that there are other possibilities such as Genetic Algorithms).
However, this is a timetable that relies on a lot of different variables. For instance "do specific classes need a specific professor due to experience level?" or "would specific classes be better off having the same professor as they did previously?". Thus neither of the stated "automated" solutions are feasible for my problem.
Instead, I took a step back. Away from all this maths and algorithms which are edging dangerously close to machine learning. I decided the best description for my solution is "smart suggestive filtering". In order to make timetable generation easier for my client, I would display all the data in such as way that overlap is impossible, the system would suggest which classes should be on what timeslot while maintaining the freedom for a human to make decisions.
I find the best way to start any project is to set your requirements straight and build on top of them. The requirements I set for this project were as follows:
- Define database relationships and be able to store the data needed for the app.
- Be able to authenticate the user and secure API endpoints.
- Create endpoints for retrieving data for specific year groups.
- Be able to assign a timestamp to specific lessons for a class.
- View all the classes which have timestamps and those which do not.
- Run reports on the data.
Starting with the data; I made a list of all the entities and attributes I would need. From this, it was just a case of putting it all in an ER diagram and determining the relationships.
Note that this isn't normalised in any way, for me it was better to have a structured database that makes sense rather than lots of tables which would have just made the queries more complicated than they already are.
A useful way to see how your data will flow is to create mockups of UIs. This will allow you to map out what is going to happen to the data, how it will be presented before you start coding. I find this makes the whole process easier down the line. I made my mockups in Figma which allowed me to plan user interactions as well.
I decided to use Django Rest Framework on the backend, because that is what I am most familiar with and React on the Frontend. I chose React because I was still learning Vue at the time and didn't quite have the confidence to undertake such a large project in Vue.
The first roadblock I came across is that Foreign Keys return Ids when serialized. To help me with this I made an abstract base class which converts the objects of ids into an object of data.
class SharedMethods:
@staticmethod
def ExtractValuesById(DataCollection):
TeacherVal = Teacher.objects.get(id=DataCollection['Teacher']).name
RoomVal = Room.objects.get(id=DataCollection['Room']).RoomNumber
SubjectVal = Subject.objects.get(id=DataCollection['Subject']).name
ClassGroupVal = ClassGroup.objects.get(id=DataCollection['ClassGroup']).classCode
data = {
'id': DataCollection['id'],
'Day': DataCollection['Day'],
'Unit': DataCollection['Unit'],
'Teacher': TeacherVal,
'Room': RoomVal,
'Subject': SubjectVal,
'ClassGroup': ClassGroupVal
}
return dataBy doing I could reuse this code wherever I needed it by inheriting it into other viewset classes.
While filtering the data I needed a way to get all the free teachers, because teachers teach more than one lesson a week I couldn't have a field for "isFree" on the teacher model.
To work around this finding set differences between all teachers and all teachers who are teaching on a specific day.
currentOccupiedTeachers = Timeslot.objects.filter(Day=day, Unit=f'Unit{unit}')
currentTeacherData = TimeslotSerializer(currentOccupiedTeachers,many=True).data
occupiedTeacherIds = set([timeslot['Teacher'] for timeslot in currentTeacherData])
# Get Ids of all teachers
allTeachers = Teacher.objects.all()
allTeacherData = TeacherSerializer(allTeachers, many=True).data
allTeacherIds = set([teacher['id'] for teacher in allTeacherData])
freeTeachers = allTeacherIds - occupiedTeacherIdsI used two sets to make sure they are unique and subtracted one from the other to get all the teachers who do not have timeslots on a specified day. From there it is easily converted to a queryset like so:
FreeTeacher = Teacher.objects.filter(id__in=freeTeachers)I also found that I needed more specific queries. I needed to determine if a field has one value or another. Django has a neat function Q which allows you to form composite queries:
from django.db.models import Q
query = Q(Description='ICT') | Q(Description='Computing')
queryset = Room.objects.filter(query, id__in=outPutFilteredRooms)Here the filter will match if the Description is "ICT" or "Computing".
One way in which I suggested options for the timetable is by making sure the recommended option is first. Each yeargroup has a set amount of each lesson which they need on their timetable for instance 6 maths lessons per week. So I make sure the subject they have the least of is on top. However using Model.objects.filter() doesn't preserve order. Hence we can use this handy trick:
from django.db.models import When,Case
currentAmounts = self.__getCurrentSubjectTotals(class_, allSubjects)
subjectMissingIds = self.__getMissingSubjectAmounts(currentAmounts, pk)
preserveOrder = Case(*[When(pk=pk, then=pos) for pos,pk in enumerate(subjectMissingIds)])
subjectFrequencyQueryset = Subject.objects.filter(
yearGroup__name = f'Yr{pk}',
id__in=subjectMissingIds).order_by(preserveOrder)
serializedSubjects = SubjectSerializer(subjectFrequencyQueryset, many=True)
return Response(serializedSubjects.data)Using Case Where Enumerate will make sure the order of the array you pass in is preserved in the query.
(Coming Soon)
The whole year in which this app has been in the making has taught me the importance of planning. If I didn't plan so much of the app beforehand, writing the code would have been unnecessarily difficult.
I also learned how vital a good client-dev communication is for maintaining the stabilty of a project.
Finally I explored the ways of Agile Development. Agile is a project management methodology in the SDLC and focuses on involving the customer in every step of the development process, it was developed to overcome the drawbacks of the standard waterfall model.
It does this by breaking down the entire project into smaller development lifecycles called iterations or sprints. In Agile for every sprint, you develop a version of the working software called the increment.
I found this very useful for the project as the clients view on how the app worked was my top most priority, for the best possible UX.
Overall I am pretty happy with the product. If I could do it again I would swap out Zustand for Redux Toolkit, because I got to the point where small state slices began to look really messy.
I would also handle error messages a lot better. A custom component which showed errors would have been more user friendly.
22