Generating potential schedules for college students.

Question

Hello,

Here is my problem: I am designing an application that will allow students to select the classes they want to take for the semester and create potential schedule layouts for them. Each class typically has several possible sections that occur at different times.

So I am looking for a good data structure to use in order to develop an algorithm that will do this.

Is there a common way to do this? Any data structures and/or algorithms I can apply to this situation? I am just looking for a place to get started.

EDIT: The classes tend to be Monday, Wednesday, Friday or Tuesday, Thursday. In a lot of cases there are also labs or recitations that occur at various times during the week

Thanks, Rob

Answer 1

I would use a tree
At each node (which represents a class) branch for each section and an additional branch for not taking the course
You can prune for scheduling conflicts at any time

This shouldn't get too big as long as you aren't storing these forever, and as long as you don't include too many courses per student per semester

---

The tree would be rooted at any arbitrary class. Each branch from root would be a section of that class (and the extra branch for not taking it) Then at the end of each of these branches you have more nodes. These nodes would all represent the second class you're fitting in the schedule.
Each of these nodes would have another branch for each section of the second class. And so on.

ex:

              math  
 /            /           \  
2:00        1:00         blank  
  |           |             |  
 p.e          p.e           p.e  
/    \        /   \        /  \   
2:00  blank  2:00  blank  2:00 blank  
 |  
conflict

Answer 2

Does each class have the same schedule each day of the week? Or are they like mine were, where some were MWF, others TuTh, and others Sat?

If all the classes are at the same time every day of the week, the model's pretty easy. You need tables for students, classes, classSections, and studentSchedules.

For your classSection table, since the classes aren't the same time every day, if they're the same days each week, you can include fields for each day of the week (M-Sa), start time, class length (in hours,) and, of course, the classCodeID.

At a minimum:

Student
   ID
Class
   classCodeID
   description
classSection
   classCodeID
   classSectionID
   isOnM
   isOnTu
   isOnW
   isOnTh
   isOnF
   isOnSat
   startTime
   length
studentSchedule
   studentID
   classCodeID
   classSectionID

You could also normalize the days of the week instead of having them in the classSection table, but I like seeing the week mapped out in a bunch of checkboxes.

I see you have multiple start times per week, so you'll need another ID field in the classSection table.

The app you have seems ok, don't you have a data model already? Looks like you don't even need to be a student to see the class schedules.

Answer 3

This is a problem where genetic algorithms are suitable. At least, my University staff developed an algorithm based on it. Here are some of their papers where the technique is presented.

http://morgoth.zemris.fer.hr/people/Marko.Cupic/files/2009-425555.EvoCOP_2009.pdf

http://morgoth.zemris.fer.hr/people/Marko.Cupic/files/2009-422047.iti2009.pdf