1

I have this problem but not sure what algorithm it belongs to.

We are trying to make a scheduling system where the users can choose the time preferences and then they are grouped into classes with their most preferred time.

Let say I have 100 users. Those users have their time preferences. We want to divide them into 4 -> 6 class with about 20 -> 25 students in each class. My question is

  • How to schedule them into the class time that they most preferred with the least amount of classes used ?

(Another constraint factor we have is the amount of teachers we have and the maximum hours a week they can teach. Also we want to be able to have makeup class. For eg: students who miss class this week can be reschedule for next week. )

Improve this question
3
  • You say "that they most preferred", but it could be their second or third choice, right? If I understand you correctly, you are balancing potentially conflicting constraints. How do you weigh the cost of departing from the ideal choice for a particular constraint? Commented May 2, 2013 at 21:27
  • Yes it could be their second or third choice. It is kinda like the stable marriage problem. Except for we are grouping 25 people in 1 class instead of matching only 2 people Commented May 2, 2013 at 21:38
  • Is this what you mean? 'student scheduling' unitime.org/uct_students.php Commented May 4, 2013 at 17:52

1 Answer 1

Reset to default
2

One way to go about a multi-objective optimization problem like this is to find a solution that satisfies one objective, and then use local search to attempt to satisfy the remaining constraints.

For example, if you ignore the constraint that you would like to minimize the number of classes used, then you can treat this as a variant on the Stable Marriage Problem (or weighted bipartite graph matching problem) - this has the nice property that it can be solved in polynomial time. Your variant on the problem is most similar to the "hospitals/residents" problem (assigning many residents to a few hospitals based on preference).

This will leave you with several classes with only a few students in them, so you next perform a local search to satisfy the "minimize the number of classes" constraint (if you formulated the Stable Marriage algorithm correctly then you should have already satisfied the "no class exceeds 25 students" constraint) - from there you have two options:

  1. Sort the classes from fewest to most students and close the classes with the fewest students, reassigning the evicted students to the remaining classes

  2. Continue to take the students' preferences into account and sort the classes from least-preferred to most-preferred (so if you have 5 students in a class who assigned it a weight of 10 then you would first close a class with 10 students who assigned it a weight of 2).

You would then perform another local search to satisfy the teachers' hours constraints - you would perform the "teachers can't teach more than X hours" search after you perform the "minimize the number of classes" search, since the latter optimization will make it easier to perform the former optimization.

If the resulting algorithm is fast enough then you can randomize it and run it a few dozen times, saving the best result. For example, rather than closing the class with the fewest students first, randomly select a class to close (weight the selection so that it usually selects the smallest class - a completely random search won't perform well)

It's possible that you'll find that one of your constraints is causing a lot of conflicts, e.g. when satisfying the teachers' hours constraint you discover that you're having to rearrange a large percentage of the students. If this occurs then change the constraint ordering, so that satisfying the teachers' hours is done on the second or even the first pass rather than on the third pass.

The makeup-class-constraint might actually belong at the top of the constraint list (even though it's got a low priority), depending on its specifications. For example, you may have the requirement that the makeup class occur before any other class (so that e.g. a student with class on Tuesday can have the makeup class on Monday and get caught up prior to his regular class); even though the makeup class constraint has a low priority, it has the tightest requirements, and so it needs to get ordered first.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thank you. The stable marriage problem has the same amount of male and female to match. Over here we have to match and group students to fewer time slots. Will the algorithm be slightly different then ?
That's correct, the algorithm will need to be slightly different; according to Wikipedia your variant is called the "hospitals/residents" problem - here's a description of an algorithm to solve it
Thats great. Thank you. However in both examples, both the residents and the programs have preference for each other. In this case, the time slot doesnt have preferences thouhg. So Im wondering should it be FIFO (First come first served?). I also edited more requirements above like allowing the ability to reschedule & makeup class
@hvu89 I edited my answer to account for the new constraints in your question

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.