Complex sort (I think!)

[girish]

Hi folks - I have a problem that I just can't get my head around and was hoping that I might get some assistance here. Hopefully I can explain this clearly!

Firstly, let me set the scene (this is an academic scenario, running FM Pro 6 unlimited) :

Say I have 3 different academic courses (C1, C2, C3). Each course runs a number of tutorial sessions at different times per week (T1, T2, T3, T4, etc). A student who enrols in any of the courses must also sign up for one tutorial time for that course. Each tutorial lasts 3 hours, and can accommodate a maximum 20 students (it can have less than 20).

I have a total student population of 200. Every student is enrolled in at least one of the courses, but may also enrol in multiple courses (e.g. they can be enrolled in C1 and C2; or C1, C2, and C3; or just C3; etc.).

So, in summary I might have something like this :

C1 (100 enrolled students)

T1 - Monday 9.00am-12.00pm

T2 - Monday 2.00-5.00pm

T3 - Tuesday 12.00-3.00pm

T4 - Wednesday 9.00am-12.00pm

T5 - Thursday 2.00-5.00pm

T6 - Thursday 6.00-9.00pm

C2 (60 enrolled students)

T1 - Monday 12.00-3.00pm

T2 - Tuesday 3.00-6.00pm

T3 - Thursday 9.00am-12.00pm

T4 - Thursday 6.00-9.00pm

C3 (100 enrolled students)

T1 - Monday 1.00-4.00pm

T2 - Tuesday 9.00am-12.00pm

T3 - Wednesday 6.00-9.00pm

T4 - Thursday 9.00am-12.00pm

T5 - Thursday 3.00-6.00pm

T6 - Friday 10.00am-1.00pm

I want to be able to set up a web-based system where students can nominate a number of tutorials that they can attend for each course they are enrolled in (say students have to nominate 4 tutorials per course). They should be able to rank the tutorials in the order of preference that they would like to attend. For example, for C1, a student might make the following selection :

Preference 1 - T2

Preference 2 - T5

Preference 3 - T1

Preference 4 - T3

Once all students have made their selections for all of their courses, I want to sort the selections so that students are distributed across tutorials that they can all attend and, if they are enrolled in multiple courses, none of their tutorials clash.

In fact, I think that the initial database side of this is relatively straight forward. I can set up a database that contains all of the courses and tutorials and share it through the web companion. I can then create a web page on which students can see all tutorials and make their selections in order of preference. Each preference might be coded by course and tutorial number, e.g. C1T4 would equal tutorial four of course one, etc.

So far so good - but then what?

Once I've got all students' tutorial selections and preferences, is there any way that I can manipulate that data so that every student ends up in a tutorial that was one of their four selections, but that also doesn't clash with the tutorial time that they may have been sorted in to for any other course they have signed up for?

Further, is it possible to do this so that as many students as possible get sorted in to the tutorial they nominated as their first preference (or if not then their second preference, then their third and, finally, as few as possible get their fourth preference).

Does that make sense? Is it possible?!

Thanks

Girish..

[girish]

Hi folks - I have a problem that I just can't get my head around and was hoping that I might get some assistance here. Hopefully I can explain this clearly!

Firstly, let me set the scene (this is an academic scenario, running FM Pro 6 unlimited) :

Say I have 3 different academic courses (C1, C2, C3). Each course runs a number of tutorial sessions at different times per week (T1, T2, T3, T4, etc). A student who enrols in any of the courses must also sign up for one tutorial time for that course. Each tutorial lasts 3 hours, and can accommodate a maximum 20 students (it can have less than 20).

I have a total student population of 200. Every student is enrolled in at least one of the courses, but may also enrol in multiple courses (e.g. they can be enrolled in C1 and C2; or C1, C2, and C3; or just C3; etc.).

So, in summary I might have something like this :

C1 (100 enrolled students)

T1 - Monday 9.00am-12.00pm

T2 - Monday 2.00-5.00pm

T3 - Tuesday 12.00-3.00pm

T4 - Wednesday 9.00am-12.00pm

T5 - Thursday 2.00-5.00pm

T6 - Thursday 6.00-9.00pm

C2 (60 enrolled students)

T1 - Monday 12.00-3.00pm

T2 - Tuesday 3.00-6.00pm

T3 - Thursday 9.00am-12.00pm

T4 - Thursday 6.00-9.00pm

C3 (100 enrolled students)

T1 - Monday 1.00-4.00pm

T2 - Tuesday 9.00am-12.00pm

T3 - Wednesday 6.00-9.00pm

T4 - Thursday 9.00am-12.00pm

T5 - Thursday 3.00-6.00pm

T6 - Friday 10.00am-1.00pm

I want to be able to set up a web-based system where students can nominate a number of tutorials that they can attend for each course they are enrolled in (say students have to nominate 4 tutorials per course). They should be able to rank the tutorials in the order of preference that they would like to attend. For example, for C1, a student might make the following selection :

Preference 1 - T2

Preference 2 - T5

Preference 3 - T1

Preference 4 - T3

Once all students have made their selections for all of their courses, I want to sort the selections so that students are distributed across tutorials that they can all attend and, if they are enrolled in multiple courses, none of their tutorials clash.

In fact, I think that the initial database side of this is relatively straight forward. I can set up a database that contains all of the courses and tutorials and share it through the web companion. I can then create a web page on which students can see all tutorials and make their selections in order of preference. Each preference might be coded by course and tutorial number, e.g. C1T4 would equal tutorial four of course one, etc.

So far so good - but then what?

Once I've got all students' tutorial selections and preferences, is there any way that I can manipulate that data so that every student ends up in a tutorial that was one of their four selections, but that also doesn't clash with the tutorial time that they may have been sorted in to for any other course they have signed up for?

Further, is it possible to do this so that as many students as possible get sorted in to the tutorial they nominated as their first preference (or if not then their second preference, then their third and, finally, as few as possible get their fourth preference).

Does that make sense? Is it possible?!

Thanks

Girish..

[girish]

Hi folks - I have a problem that I just can't get my head around and was hoping that I might get some assistance here. Hopefully I can explain this clearly!

Firstly, let me set the scene (this is an academic scenario, running FM Pro 6 unlimited) :

Say I have 3 different academic courses (C1, C2, C3). Each course runs a number of tutorial sessions at different times per week (T1, T2, T3, T4, etc). A student who enrols in any of the courses must also sign up for one tutorial time for that course. Each tutorial lasts 3 hours, and can accommodate a maximum 20 students (it can have less than 20).

I have a total student population of 200. Every student is enrolled in at least one of the courses, but may also enrol in multiple courses (e.g. they can be enrolled in C1 and C2; or C1, C2, and C3; or just C3; etc.).

So, in summary I might have something like this :

C1 (100 enrolled students)

T1 - Monday 9.00am-12.00pm

T2 - Monday 2.00-5.00pm

T3 - Tuesday 12.00-3.00pm

T4 - Wednesday 9.00am-12.00pm

T5 - Thursday 2.00-5.00pm

T6 - Thursday 6.00-9.00pm

C2 (60 enrolled students)

T1 - Monday 12.00-3.00pm

T2 - Tuesday 3.00-6.00pm

T3 - Thursday 9.00am-12.00pm

T4 - Thursday 6.00-9.00pm

C3 (100 enrolled students)

T1 - Monday 1.00-4.00pm

T2 - Tuesday 9.00am-12.00pm

T3 - Wednesday 6.00-9.00pm

T4 - Thursday 9.00am-12.00pm

T5 - Thursday 3.00-6.00pm

T6 - Friday 10.00am-1.00pm

I want to be able to set up a web-based system where students can nominate a number of tutorials that they can attend for each course they are enrolled in (say students have to nominate 4 tutorials per course). They should be able to rank the tutorials in the order of preference that they would like to attend. For example, for C1, a student might make the following selection :

Preference 1 - T2

Preference 2 - T5

Preference 3 - T1

Preference 4 - T3

Once all students have made their selections for all of their courses, I want to sort the selections so that students are distributed across tutorials that they can all attend and, if they are enrolled in multiple courses, none of their tutorials clash.

In fact, I think that the initial database side of this is relatively straight forward. I can set up a database that contains all of the courses and tutorials and share it through the web companion. I can then create a web page on which students can see all tutorials and make their selections in order of preference. Each preference might be coded by course and tutorial number, e.g. C1T4 would equal tutorial four of course one, etc.

So far so good - but then what?

Once I've got all students' tutorial selections and preferences, is there any way that I can manipulate that data so that every student ends up in a tutorial that was one of their four selections, but that also doesn't clash with the tutorial time that they may have been sorted in to for any other course they have signed up for?

Further, is it possible to do this so that as many students as possible get sorted in to the tutorial they nominated as their first preference (or if not then their second preference, then their third and, finally, as few as possible get their fourth preference).

Does that make sense? Is it possible?!

Thanks

Girish..

[Ender]

I think you're on the right track. Scheduling algorithms are fairly complex. I'll do my best to explain the two approaches I have tried. First, I use a Course_Choice file that has a record for each Student-Course pair. Students choose from the list of available Course_Choices, by marking the Course_Choice records in a portal. There is also a Course file (one course per record,) a Course_Section file (for each time slot that the course is offered,) and a Student_Section file (one record for each successful assignment of a student to a section.) See the attached ER diagram.

Once the students have all marked their choices in the Course_Choice records, I run a scheduling script that does this:

Algorithm 1: More fair

1. In the course file, find all courses that have unassigned course requests.

2. Sort the records by duration (descending) and the average number of seats available per section (descending). This puts those courses with a longer duration first, as these are harder to fill otherwise. Then it gives preference to those courses with the most openings, so that they fill up evenly.

3. Go to the first course.

4. Start at a random section for that course.

5. Checking that section's time slot, see if the first related Course_Request (sorted by preference and date chosen) could be used for filling the current section's slot. If there is a conflict with the student's previously scheduled classes, then go to the next section (starting at 1 if the counter is higher than the number of sections.)

6a. If there is a section that fits the student's schedule, add a Student_Section record for the current section and student, then mark the Course_Request as assigned.

6b. If there is not a section that fits, mark the Course_Request as a conflict.

7. Go to the next Course_Request, repeating steps 4 through 7 until all Course_Requests for this Course have been marked.

8. Go to the next Course, repeating steps 4 through 8 until all Courses have been scheduled.

9. Find those Students that do not have enough class time.

10. Fill the holes in their schedules with an available Course_Section.

Algorithm 2: Faster

1. Go to the Course_Choice file.

2. Find all records that are marked as a preference for the student, have a duration of 4 hours (or whatever your longest class is,) and are not yet assigned.

3. If there are records found, go to a random Course_Choice record, and attempt to assign the student to a related section (see A below.)

A. For the current course, go to a random section.

B1. If there's space in this section, slot the student and mark the Course_Choice as assigned.

B2. If there's no space, go to the next section and try again (go back to section 1 if the counter is over the number of sections.) If none of them have space, mark the Course_Choice as a confilct.

C. Omit the Course_Choice.

4. Repeat steps 2 through 4, decreasing the duration to find each time.

5. Find those Students that do not have enough class time.

6. Fill the holes in their schedules with an available Course_Section.

In testing, Algorithm 2 is faster by about 1/3. However, it does not give preference to those that marked their Course_Choices with a higher preference, nor those that registered earlier. The reason is it only looks at each Course_Choice once, whereas Algorithm 1 may look at it several times as it tries to fit it into a section.

You may be able to build on Algorithm 2 by finding for the highest preference first, then the second highest, etc., in the same manner that I have the longest courses go first.

Hopefully that gives you some ideas.

[Ender]

I think you're on the right track. Scheduling algorithms are fairly complex. I'll do my best to explain the two approaches I have tried. First, I use a Course_Choice file that has a record for each Student-Course pair. Students choose from the list of available Course_Choices, by marking the Course_Choice records in a portal. There is also a Course file (one course per record,) a Course_Section file (for each time slot that the course is offered,) and a Student_Section file (one record for each successful assignment of a student to a section.) See the attached ER diagram.

Once the students have all marked their choices in the Course_Choice records, I run a scheduling script that does this:

Algorithm 1: More fair

1. In the course file, find all courses that have unassigned course requests.

2. Sort the records by duration (descending) and the average number of seats available per section (descending). This puts those courses with a longer duration first, as these are harder to fill otherwise. Then it gives preference to those courses with the most openings, so that they fill up evenly.

3. Go to the first course.

4. Start at a random section for that course.

5. Checking that section's time slot, see if the first related Course_Request (sorted by preference and date chosen) could be used for filling the current section's slot. If there is a conflict with the student's previously scheduled classes, then go to the next section (starting at 1 if the counter is higher than the number of sections.)

6a. If there is a section that fits the student's schedule, add a Student_Section record for the current section and student, then mark the Course_Request as assigned.

6b. If there is not a section that fits, mark the Course_Request as a conflict.

7. Go to the next Course_Request, repeating steps 4 through 7 until all Course_Requests for this Course have been marked.

8. Go to the next Course, repeating steps 4 through 8 until all Courses have been scheduled.

9. Find those Students that do not have enough class time.

10. Fill the holes in their schedules with an available Course_Section.

Algorithm 2: Faster

1. Go to the Course_Choice file.

2. Find all records that are marked as a preference for the student, have a duration of 4 hours (or whatever your longest class is,) and are not yet assigned.

3. If there are records found, go to a random Course_Choice record, and attempt to assign the student to a related section (see A below.)

A. For the current course, go to a random section.

B1. If there's space in this section, slot the student and mark the Course_Choice as assigned.

B2. If there's no space, go to the next section and try again (go back to section 1 if the counter is over the number of sections.) If none of them have space, mark the Course_Choice as a confilct.

C. Omit the Course_Choice.

4. Repeat steps 2 through 4, decreasing the duration to find each time.

5. Find those Students that do not have enough class time.

6. Fill the holes in their schedules with an available Course_Section.

In testing, Algorithm 2 is faster by about 1/3. However, it does not give preference to those that marked their Course_Choices with a higher preference, nor those that registered earlier. The reason is it only looks at each Course_Choice once, whereas Algorithm 1 may look at it several times as it tries to fit it into a section.

You may be able to build on Algorithm 2 by finding for the highest preference first, then the second highest, etc., in the same manner that I have the longest courses go first.

Hopefully that gives you some ideas.

[Ender]

I think you're on the right track. Scheduling algorithms are fairly complex. I'll do my best to explain the two approaches I have tried. First, I use a Course_Choice file that has a record for each Student-Course pair. Students choose from the list of available Course_Choices, by marking the Course_Choice records in a portal. There is also a Course file (one course per record,) a Course_Section file (for each time slot that the course is offered,) and a Student_Section file (one record for each successful assignment of a student to a section.) See the attached ER diagram.

Once the students have all marked their choices in the Course_Choice records, I run a scheduling script that does this:

Algorithm 1: More fair

1. In the course file, find all courses that have unassigned course requests.

2. Sort the records by duration (descending) and the average number of seats available per section (descending). This puts those courses with a longer duration first, as these are harder to fill otherwise. Then it gives preference to those courses with the most openings, so that they fill up evenly.

3. Go to the first course.

4. Start at a random section for that course.

5. Checking that section's time slot, see if the first related Course_Request (sorted by preference and date chosen) could be used for filling the current section's slot. If there is a conflict with the student's previously scheduled classes, then go to the next section (starting at 1 if the counter is higher than the number of sections.)

6a. If there is a section that fits the student's schedule, add a Student_Section record for the current section and student, then mark the Course_Request as assigned.

6b. If there is not a section that fits, mark the Course_Request as a conflict.

7. Go to the next Course_Request, repeating steps 4 through 7 until all Course_Requests for this Course have been marked.

8. Go to the next Course, repeating steps 4 through 8 until all Courses have been scheduled.

9. Find those Students that do not have enough class time.

10. Fill the holes in their schedules with an available Course_Section.

Algorithm 2: Faster

1. Go to the Course_Choice file.

2. Find all records that are marked as a preference for the student, have a duration of 4 hours (or whatever your longest class is,) and are not yet assigned.

3. If there are records found, go to a random Course_Choice record, and attempt to assign the student to a related section (see A below.)

A. For the current course, go to a random section.

B1. If there's space in this section, slot the student and mark the Course_Choice as assigned.

B2. If there's no space, go to the next section and try again (go back to section 1 if the counter is over the number of sections.) If none of them have space, mark the Course_Choice as a confilct.

C. Omit the Course_Choice.

4. Repeat steps 2 through 4, decreasing the duration to find each time.

5. Find those Students that do not have enough class time.

6. Fill the holes in their schedules with an available Course_Section.

In testing, Algorithm 2 is faster by about 1/3. However, it does not give preference to those that marked their Course_Choices with a higher preference, nor those that registered earlier. The reason is it only looks at each Course_Choice once, whereas Algorithm 1 may look at it several times as it tries to fit it into a section.

You may be able to build on Algorithm 2 by finding for the highest preference first, then the second highest, etc., in the same manner that I have the longest courses go first.

Hopefully that gives you some ideas.

[girish]

Wow! - thanks for these suggestions Ender. At first blush I'm not sure I fully grasp this, but I'll work through the options and see where I get :-)

Girish..

[girish]

Wow! - thanks for these suggestions Ender. At first blush I'm not sure I fully grasp this, but I'll work through the options and see where I get :-)

Girish..

[girish]

Wow! - thanks for these suggestions Ender. At first blush I'm not sure I fully grasp this, but I'll work through the options and see where I get :-)

Girish..