Checking for timetable clashes

S

SteveWalker

Hi,

Quite a complicated problem here, hopefully someone's been doing this kind
of thing before...

I'm writing a system for a college that checks whether the course requests a
student has made are valid, or if they result in timetable clashes. The data
starts off as a list of courses, which I then convert into a table of the form

AdmissionNumber - Index - C1 - C2 - C3 - C4 - C5 - C6 - C7 - C8

where index is a unique integer, and C1-8 are class IDs where the selected
course is taught. This works fine so far. The class IDs are then linked to
PeriodIDs, which describe a timetable period in which the class is taught.

I need to be able to tell the user if there is a valid combination of
classes - i.e. a combination of classes where no two classes are taught in
the same period, and it has to be done as quickly as possible. At the moment
I've got some queries that can do it, but they're taking way to long (over 2
minutes) to check a single student, so I need to cut that time down a lot.
The main problem is the amount of data I'm working with - there can be many
thousands of possible combinations for a student - so any aggregate functions
tend to be very slow. If necessary work can be done on the server in SQL
Server, but I'd prefer to do it locally as many people will be doing this at
once.

Thanks,

Steve Walker
 
M

Michel Walsh

Hi,


I would try a total query, group by on student and physical time slots. Any
total HAVING a COUNT > 1 is a conflict.

===================================
SELECT i.studentID, c.PeriodID
FROM Inscriptions As i INNER JOIN CoursesPeriods As c
ON i.CourseID = c.CourseID

GROUP BY i.studentID, c.PeriodID
HAVING COUNT(*) > 1
====================================

Fields in Inscriptions are assumed like

StudentID, CourseID

where a given student may take one course per record, by may take different
course by being mentioned many times (in multiple records)

Fields in CoursesPeriods are assumed like:

CourseID, PeriodID

where each record give ONE period where the course is given



Ideally, you should also have a constraint unique on the couple StudentID,
CourseID, in table inscriptions, so that a student is not registered to the
SAME course TWICE.



Hoping it may help,
Vanderghast, Access MVP
 
S

SteveWalker

Thanks, but it's not quite that simple. There is a table like

StudentID, CourseID

but a course may be taught in multiple classes, so there's then a table

CourseClassID, CourseID, ClassID

and finally

ClassID, PeriodID.

Therefore counting the occurences of a period isn't enough, as while a
period may appear many times, that doesn't necessarily mean a clash since
there may be another combination of classes that works. Picture this:
StudentID, CourseID
1, 1
1, 2

CourseClassID, CourseID, ClassID
1, 1, 1
2, 1, 2
3, 2, 3

Class 1 is taught in periods 1 and 4, Class 2 in periods 2 and 5, and Class
3 in periods 4 and 6. Then

StudentID, PeriodID, Count
1 1 1
1 2 1
1 4 2
1 6 1

Period 4 has a count > 1, but this is still a valid combination if the
student is put in Class 2 and Class 3.

I hope that makes things a bit clearer - the Course-Class system can be
difficult to get your head around! The counting approach is essentially what
I've been using and it's far too slow one combinations are considered - the
sample data gives 4,950 possible combinations of classes, with each class in
5 periods, which is a lot of counting to do!

Thanks,

Steve Walker
 
D

Dale Fye

Steve,

From your second description, it sounds like what you want the application
to do is select the appropriate class IDs to ensure there is no overlap.
From your first post, it sounded as if the student was selecting the
specific Course/Class combination they wanted and you just wanted to check
to make sure that these did not overlap.

Which is it?

How do you handle the case where the course meets for a regular period twice
a week and for an extended lab once a week? Do the students have to sign up
for the lab separately? You indicate that ClassID's are tied to PeriodIDs,
I assume that these PeriodIDs are tied to a table with day of the week and
start and end times. If all you are trying to do is confirm that the
students picks do not cause a conflict, I think I'd just run some code to
loop through the students selections and compare the class periods to make
sure they don't overlap. My guess is that this will be a much quicker
process than the query route.

HTH
Dale
 
S

SteveWalker

Dale:

The student selects a only a courseID. The application then needs to find a
set of classIDs that match the requested courses, and do not overlap.

"> How do you handle the case where the course meets for a regular period
twice
a week and for an extended lab once a week?"
Click to expand...

This isn't an issue - classes are placed in a well-structured timetable.
Periods are defined by start and end times, but no two different periods
overlap. The system is being used by colleges with timetables that are
consistent across the curriculum. In the case of an extended lesson, it would
simply be assigned to multiple PeriodIDs to cover the different periods that
it covers. This means that only I only need to compare periodIDs against each
other, there will be no clashes with other periods.

I've tried doing it all in code and it was much slower than running via
queries. (Doing it in code is indeed quicker when you already know the
classes as you mentioned, which is done somewhere else in the application,
but it's too slow with many combinations to search through.) I'm now
experimenting with mixing the two but I suspect the time it takes to import
data into recordsets will mean it's quicker staying with queries.

Thanks,

Steve
 
D

Dale Fye

Good luck.

I'm assuming that 8 is the maximum number of classes for a student. If each
course had 4 possible time slots, that is over 65000 combinations of
possible class schedules. I just don't see an easy way to accomplish this.
How are you doing it now?

Dale
 
S

SteveWalker

At the moment I use queries to put the data into a list of class
combinations, then a list of period combinations, with a "Clash" bit
indicating if a period is used twice in any record. I was then "Clash"
summing over each combination, and if the sum of Clash = 0 then it's a valid
combination, but that was very slow. I'm now trying loading this table of
Periods/combinations into VB and looping through it myself, which seems to be
quicker in most cases as it doesn't have to check all the combinations, only
the ones up to the point where/if a valid one is found.

Looks like this is as quick as I'll get it in Access, maybe the best method
is to write an external program to do this for me...

Thanks for your help

Steve
 
Top