Algorithm

We discovered that it was hard to find an existing algorithm that made the best possible timetable without generating all possible timetables first. An algorithm that involves generating all timetables is slow, and definitely a bad choice on mobile devices, many of which are running with very little memory to spare already. In the end, we decided to build our own algorithm, and we explain it in detail below.


Intuitively, we build a graph of nodes to generate the timetable schedules.

Node is an abstract object to represent a section of one course lecture/tutorial/practical. Node contains the information of a section which is course name, course time, section number and location.

node1

For example, if MAT137Y1(Calculus I) course has 3 lecture sections and 20 tutorial sections, then for this course, the algorithm generates 3 nodes for the lecture sections and 20 nodes for the tutorial sections. The 3 nodes are siblings to each other and the 20 nodes are also siblings to each other. So sibling relationship between nodes
is valid if the nodes are different sections of the lecture/tutorial/practical of the same course.

The algorithm connects two nodes if they are not siblings to each other and their times do not conflict each other.

nodes

While connecting two nodes, the algorithm puts a cost to the edge by user preference. If user selected “Evenly spread” (which means to make the timetable as evenly spread throughout the week as possible), then the algorithm calculates the number of common days between two nodes and sets it as the cost of the edge. So the more common days the nodes have, the more expensive to connect to each other. If the user wants to make a packed timetable, then the algorithm reverses the cost for the evenly spread option. In this case, the more common days the nodes have, the cheaper to connect to each other.

node2

An example of setting the costs for the edges when user wants a evenly spread timetable

Since we set the cost in different ways depending on user preference, whenever we connect a new node to the path (which is the list of nodes put on the timetable so far), we can get the most suitable node for the path based on the cost.
Basically, the algorithm tries to make the graph include all the courses chosen by the user with the least cost.

The objective of the algorithm is to choose a node for each type of course section to put onto the timetable. For example, if the user selected CSC108H1F (which has a lecture section and a tutorial section), then the algorithm puts a CSC108H1FL node and a CSC108H1FT node onto the timetable.

The algorithm starts to generate a graph from a node in the course with the least of number of sections (i.e., the course with the least number of sibling nodes; the start node should also have the least cost among its siblings). If the algorithm fails to generate a complete timetable from the start node, then it tries to generate again with another sibling node of the start node. So for the worst case, the number of trials for generating a timetable is the same as the number of siblings that the course with the least of number of sections has. Once the graph adds a node to the path, then the siblings of that node will not be included in the path, so that the timetable does not contain duplicate courses.

One optimization issue we had was setting the node edges. If we try to generate one graph for two semesters, a lot of computation would be wasted for setting the edges because if there is a node for only the fall semester and a node for only the spring semester, checking whether we need to connect them will be unnecessary (Since we cannot include a spring class in the fall timetable). Hence, we generate a graph separately for each semester.

However, another problem occurred for this case because of the Y courses. If the user selected at least one Y course, then we need to include/exclude the same combination of Y nodes for both semesters in one timetable generation. Therefore, if there is at least one Y course selcted, then for each trial, the algorithm chooses a combination of Y nodes as fixed start nodes and excludes their siblings from the timetable.

For efficiency, the algorithm does not store all the possible combinations of Y course nodes. Instead, if the algorithm failed to generate a complete timetable, then it calculates the next combination. During the calculation, if the nodes in a combination conflict each other, then the algorithm jumps to the next possible combination. The loop invariant for this process is that the total cost of the previous combination is less than the current combination.
In the case where all the possible start nodes failed to generate a complete timetable, we try to find the “best conflict timetable”, which is a timetable with the least number of conflicts. The algorithm keeps a global instance variable for the best conflict timetable and update it in each trial, if this trial generates a conflict timetable with less conflicts than the previous one.

The basic algorithm procedure is written above. There are also other little tricks we used to optimize the algorithm, which we will not explain in too much detail here. For example, before we add a node to the path, we check if it is possible to make a graph for a complete timetable from this node. We make sure that this node does not conflict with any of the nodes that are currently in the path, and it is connected to at least one node for all the types of courses sections we want to put onto the timetable.

In conclusion, this algorithm guarantees to find a complete timetable if it’s possible, and the number of trials for generating the timetable will be finite. Currently, the algorithm works fast on the Android devices we have tested.

We speculate that this algorithm can be used not only for scheduling school timetables, but also for other daily/weekly/monthly events as well. For instance, if the F/S section nodes represent some events for one day, then the Y section nodes would represent some events that span more than one day.

We hope this summary gave you some ideas for implementing your own scheduling program!
Also, any suggestions are welcome! We are eager to learn from you!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s