/
Autotimetabler

Autotimetabler

Owned by Martin Knezevic (Unlicensed)
Last updated: Sept 02, 2022 by Mun Joon Teo (Unlicensed)
4 min read

The Algorithm

The autotimetabler algorithm is written in Python, using Google’s OR-Tools software for optimization problems, specifically the CP-SAT Solver (used for constraint programming). https://en.wikipedia.org/wiki/Constraint_programming or CP simply tries to find a solution to a variable-assignment task given certain constraints. From this point of view, the goal of the autotimetabling algorithm is to find a suitable timetable, rather than the best timetable. It does not try to find a solution that will maximize or minimize a value and its constraints (which is mainly why it is so fast). Additional constraints should be formulated accordingly (e.g. instead of asking it to schedule classes to be as close to the start of the week as possible, ask to ensure there is at most one class than is later is the week than Tuesday).

The algorithm first processes its data, then creates a CP model, adds contraints, and calls a solver to solve the model. The actual solving of the model is all handled for us by Google the library; all we do is define the constraints.

Read the complete documentation here.

Processing Data

Data processing occurs in the useEffect hook in Autotimetabler.tsx

From the currently selected courses, the data must first be transformed to be in a suitable format for the model. This is stored in the targetActivities variable.

  1. From a course’s activities, filter out lectures and exams, then convert the data for each activity into the form [activityName, [activities]] e.g. ["Laboratory", [{ClassData}, {ClassData}]]

  2. Combine all arrays generated above into a single array

  3. Grab only the class data from each item in the array

  4. Filter each list of class data to only include lists having classes with periods

  5. Remove the classes without any periods from each class list

Next, hasMode is an array stating whether an activity is offered in person, online, or both. Each entry in hasMode is in the form [hasInPerson, hasOnline] and corresponds to the entry at the same index in targetActivities.

Then, targetActivities is mapped to a PeriodInfo object for each category of class - hybrid, in person and online. The PeriodInfo object is as follows:

interface PeriodInfo { // The number of periods the class has per week periodsPerClass: number; // For each class in the activity there are periodsPerClass groups // of (period.time.day, period.time.start) pairs // i.e. periodTimes.length == activity.classes.length * periodsPerClass * 2 periodTimes: Array<number>; // The ith period has duration[i] in hours durations: Array<number>; }

An example of periodTimes is [5, 14, 5, 14, 1, 12]. This denotes that there are two classes on Friday beginning at 2pm, and a class on Monday beginning at 12pm. Note that there is no separation between each pair in periodTimes, thus why periodsPerClass is necessary to define the bounds for each class.

This data is then sent to the autotimetabling server with the provided user preferences which are in the following format:

{ 'start': The earliest desired starting time of all classes (number), 'end': The latest desired ending time of all classes (number), 'days': Which days classes should be restricted to e.g. 12345 for all days (string), 'gap': The minimum number of hours to place between classes (number), 'maxdays': The maximum number of different days classes can occur on (number), }

The Model

The core of the model works by defining interval variables that have a set of possible start times (the class times) of certain sizes (class duration plus minimum gap between classes), and asking for an non-overlapping assignment of these variables (i.e. no class clashes). Each of these interval variables are associated with a integer variable which is constrained by the domain of possible start times for that class. A start time identifies a day of the week and a time of day, and is given by a 3 digit number where the first digit denotes the day (1 for Monday, 2 for Tuesday, etc.) and the next two digits the time.

Constraints on days of the week (such as maximum days of uni a week, or permitted days of the week) are thus implemented with constraints on the result of division by 100 of the class start times. If maximum days is less than five, then the days of the classes are constrained to one value out of a pool of possible day values, which are enforced by conditionally enforced boolean variables (see here for documentation and examples of this technique).

The earliest start time and latest end time constraints are implemented through interval variables which ‘cover up’ the start of the day and the end of the day respectively for each day, and so cannot be overlapped with by class intervals for those time slots.

Types of Classes

There are several types of classes. The two normally-complex types are those that are formed of a single period of class a week, and those that are formed from a consecutive two-period block of class on the same day (e.g. tut-labs). The specially-complex type is that which is formed of 2 or more ‘linked’ periods that range across the week (i.e. classes with multiple periods of class on different days of the week). Due to the unpredictability of the placement of these periods, these classes must be handled with special logic which enforces exactly one group out of the possible groups of periods that class may take.

Notes on the Code

  • The CP model only works with integers. To deal with decimal values, such as classes on the half-hour mark, stuff gets mutliplied by 2

    • This can be expanded to a higher multiplier, but a multiplier higher than 4 will require the days-multipler (100) to be changed to 1000

  • Every variable in the model wants to be initialized with a unique name

    • "x%i" % i ← these sort of weird looking python strings facilitate this but can be mostly ignored

Related content