Scheduling Algorithm

Definitions

• A Course is an abstract container for lectures
• A Lecture belongs to a course, and may have zero or more sections
• A Section must belong to a lecture. Sections of the same lecture are interchangeable
• A Custom Event is any arbitrary event defined by the user

Requirements

Given a collection of lectures, sections, and custom events, any created schedule must fulfill the following requirements:

1. All custom events are in the schedule
2. One lecture from each course is in the schedule
3. If many lectures for the course are given, then any one lecture can be used
4. None of the lectures can conflict
5. If a lecture has sections, then one corresponding section is in the schedule

The goal of the scheduling algorithm is produce all schedules that fit this criteria.

Implementation overview

The controller...

1. filters the given list of classes to get the lectures
2. creates a Cartesian product of these lectures (req 2)
3. adds the custom events to each combination (req 1)
4. filters out any conflicting combinations (req 3)

The combinations are given to the scheduling service and it... 1.

Scheduling Groups

Now we extend the algorithm above to the situation when a user has a set of required courses and up to 3 sets of optional courses. In this situation, all the required courses must be in the schedules, and one course from each optional group must be in each schedule.

Example

Let's say the user wants to schedule the following courses. In this example it's easy to see their intent: they have to take the Math and Physics course for their major, and they are trying to fulfill their art and history general education requirements. So the user doesn't really care which Art or History class they take.

requiredCourses: MATH 1, PHYS 2
optionalGroupA: ART 1, ART 2, MUSIC 2
optionalGroupB: HIST 1, HIST 2, CLASSICS 1
optionalGRoupC: N/A

MATH 1, and PHYS 2 have to be in every schedule. Then one course must be taken from groups A and B respectfully. Here are examples of the first couple schedules that would be returned:

[MATH 1, PHYS 2, ART 1, HIST 1]
[MATH 1, PHYS 2, ART 2, HIST 1]
[MATH 1, PHYS 2, ART 1, CLASSICS 1]

As you can see, the number of schedules grows quickly as more optional courses are given. So the algorithm should perform a breadth-first search so the user can see a representative set of schedules.

Algorithm

• Breadth-first search across the optional groups
  • How do we choose how deep to go before moving to the next course?
• Pagination
  • Request params:
    • page
    • page size
    • required courses
    • optional groups A, B, C
    • custom events (also required)
  • Response info
    • array of schedules
    • total: the total number of schedules (not just on this page). Calculated as the product of all the lists of courses. The LazyCartesianProductScheduler has a snippet to calculate the total number of combinations. So we can extend and re-use that for the course groups.