Schedule/Time tabling research

[ejmg]

Schedule resolution logic

The primary logic/feature of this project is the resolution of professor schedules and university courses that need to be taught. Update: we need to research how to best approach this problem such that we can actually achieve the feature without getting bogged down in the complexity of the problem (or in implementing it with adequate abstractions to extend, and thus having to deal with the complexity of the greater problem).

Assignees

@ejmg

Background

after researching the problem sometime over the weekend, I've realized that we are dealing with a sub-problem of the highschool timetabling problem, which finds itself in the category of NP-Complete/Hard problems.

As a result of that research plus general uncertainty of what direction to go in, the original task, schedule resolution logic did not get implemented for sprint 1. Instead, we are splitting this issue into two:

1. schedule resolution research
2. schedule resolution mvp

the goal is for both of these to get figured out by the end of sprint 2.

Constraints and Assumptions

Blockers

1 and #2

Design Changes

TBD

References

Here's a listing of some resources I've read on the issue, aside from the minimal wiki entry:

• Solving High School Timetabling with Satisfiability Modulo Theories by Demirovic and Musliu
• School timetable construction: Algorithms and complexity by Willemen
• Modeling High School Timetabling as Partial WeightedmaxSAT by Demirovic and Musliu
• Models and Algorithms forSchool Timetabling –A Constraint-Programming Approach by Marte

[ejmg]

Fairly critical updates given in task description directly

[ejmg]

research update

summary

Upon further review and analysis of the requirements for this feature, the mvp implementation in #24 will approach the problem with an ad-hoc "logic engine" of sorts with a set of scheduling exceptions and conditions that can be associated with a specific instructor.

background

I fear that the mvp's setup will calcify as the defacto implementation hereon, but the time and cost of investing in a bespoke implementation is too high for the given requirements and timeline. I would ideally like to get something going in Prolog or a constraint solver DSL, but don't have enough time to learn how to frame the problem adequately.

proposed approach

Based on the requirements provided and some further analysis, I've distilled the problem of scheduling, for our given instance of generalized high school time tabling problem, as a loose set of scheduling exceptions and conditions. This is my best attempt of providing a look into the mental model that will go into the scheduling logic engine.

Exceptions, to me, are defined a set of abnormalities to a regular schedule. These should be taken roughly as "one-off" rules that exist independently of other concerns. A professor who cannot teach at 10:00AM-11:00AM has a scheduling exception. Similarly, when a professor cannot teach on Mondays, this is an exception to their schedule.

Conditions are systemic and are predicated on other exceptions and conditions, whether from "within" the same instructor's schedule or in relation to another instructor's schedule. When professor X cannot teach at a time that overlaps with professor Y, this is taken as a scheduling condition. When professor X can only teach classes back-to-back in a continuous fashion, this is also a scheduling condition.

In general, I take scheduling conditions as the "rules" of schedule to be generated while exceptions are... exceptions to the rules that determine schedules that can be generated.

I'm going to figure out how to implement these set of scheduling exceptions and conditions in the most crude and basic way possible. This means relying largely on Rust's built-in type system and with only those third party libraries that have a high return like chrono for time/date handling.