On-Line Course Scheduling

Tracy Scott
XCF Project Description

A program for helping students graphically schedule classes.

Summary

ByteBears assists students in graphically scheduling their classes. The primary interface is a CGI based web form. The CGI script connects directly to infocal, retrieves the requested courses, and then generates the ten best schedules corresponding to those courses. The current version also allows you to preschedule other appointments and prioritize them so that they can be more or less important than a course section. For example, you can enter in an appointment for sleep from 800-1000 everyday of the week with a priority of 126, and it will give you the best possible schedule that tries to account for your needed sleep. See below for algorithmic details.

Algorithms

The most difficult task in this project is the system integration aspect. I have no control or affiliation with infocal, so I am at the mercy of the data that they provide. The algorithms try to remain flexible enough to handle outlying cases while still being able to generate schedules automatically.

Tight vs. Loose
The first concern is that for certain classes you can take lecture section 1 and discussion section 201, but for other classes that is not possible. Currently ByteBears supports the two different scheduling methods (the former I'll term loose scheduling and the latter tight scheduling), but only through autocalculation. When time permits I will enhance the CGI form and back-end engine to allow the mode to be specified. Loose and tight scheduling are determined on a per course basis. If a class has discussion sections that don't match any lecture section, ByteBears will schedule that class loosely (which means any combination of lecture and discussion is valid), otherwise it will try to schedule it tightly by default.

Scoring Schedules The second concern to be addressed is how do we determine what is a "good" schedule? Currently the scoring algorithm is purely based on conflicts. It could be possible to bias the score to prefer such things as back to back classes, afternoon classes, etc. The current implementation uses a tournament method where all the loser time slots' (sections, appts, etc.) priorities are summed to provide a score. So, in effect the "best" schedule is defined to be the schedule that minimizes the the sum of the losing priorities. For classes of equal priorities, the shortest duration class is considered the "winner". This minimizes the chances for later conflict penalties. Changing the priorities of classes (currently not possible through the CGI form), can lead to suboptimal performance because the priority comparisons are on a 1-1 scale. For example, class A is 8-9am and has a priority of 3, class B is 8-10am and has a priority of 4, and class C is 9am-10am. The optimal choose to minimize the score is to choose A & C (B looses, so the score=4), but since ByteBears is using a greedy algorithm, B beats A, and the B beats C, so A & C both lose, which leads to a conflict penalty of 3+3=6. The correct approach would be to apply dynamic programming principles from CS170, but since this is only an issue for classes of different priorities (if the priorities are equal, it will choose the shortest class as the winner, which is the correct answer), it was not important enough to address. It also depends on the interpretation of the "good" schedule. For example, you could also take the interpretation that a class of a higher priority beats all classes of lower priority at whatever summed price. That is what the current implementation does.

Future

The next phase is to clean up the CGI interface to allow explicit tight vs. loose scheduling, and extensive testing and fixing. The goal at this point is to be ready to announce it for next semester's scheduling frenzy (ironically when I will no longer need it, but I have found the current version useful at least).

Comments

I found that doing a project that heavily relied on a poor data source (infocal gopher responses) was particularly difficult. The lack of control over the data can easily lead to a loss of motivation and frustration.