2
$\begingroup$

I have a problem where mentors need to paired with courses, this is similar to the marriage problem or the hospitals/residents problem except that it isn't. The current solution is terribly written and needs to be expanded, plus it's a monte-carlo algorithm. I want to change it to something deterministic

(I'm using weird terminology with "mentor" because my university is weird think of a mentor as a T.A.)

Courses don't "care" which mentor is assigned. All courses must be assigned a mentor. All mentors must be assigned one course. No mentor may be assigned to more than 2 courses. A mentor may not be assigned 2 courses with identical or overlapping time-slots. Courses have 3 attributes: time-slots (may be web-only or hybrid web/classroom) theme professor faculty and/or time-slot may be TBD (too be decided)

Mentors are asked a series of questions: rank your top 5 time-slots rate (weight) the value of various themes from 1-7 or dont' care (don't care is the same as a 4 in the current algorithm) rate (weight) faculty you'd like to work with from 1-7 or don't care (don't care is the same as a 4 as above) Are you willing to mentor two courses? yes/no Are you willing to mentor an online or hybrid course? yes/no Are you trained to mentor an online/hybrid course.

Current system assigns a "score" to each assignment using the questions above and tries to minimize the score.

When combining assignments into a schedule, no extra weightings are added. However, some schedules are considered invalid (as above): assigning a mentor to more than 2 courses or more than 1 if they didn't select "yes" to "I'm willing to mentor 2 courses" and time-slots aren't allowed to overlap.

More complications/edge cases: certain mentors may be pre-assigned courses. This doesn't take the mentor out of the running but it does take the course out. A mentor may be assigned to multiple courses, so there first one might be pre-assigned, but there second one cannot. Also, some mentors are "owned" by a certain department, and so may only be allowed to teach "urban studies" courses.

Thoughts on an algorithm I should use?

Edit: for clarity and to answer some questions. The current solution (monte-carlo) has a function that generates a cost based on your options 1st choice is 0.0 cost, 2nd choice is .33, etc. 7th choice is 4.0. Then the weights for all parameters are summed and the algorithm has to optimize for the lowest score. There are also some other parameters like untrained (0.0 if web and trained, +2.0 to cost if web course and untrained, +2.0 to cost if unwilling to teach web course and web course)

$\endgroup$
  • 1
    $\begingroup$ As a question in algorithms, this question is underspecified. You have only specified what a feasible solution is and which information is available, but you have not specified the objective function. In other words, you have to model the question to reduce it to an algorithmic question. $\endgroup$ – Tsuyoshi Ito Mar 15 '11 at 14:26
  • $\begingroup$ I think that this should be considered as a question of how to model the problem, which is allowed. See the meta discussion for more information on this. $\endgroup$ – Tsuyoshi Ito Mar 15 '11 at 14:35
  • $\begingroup$ Mark, I think you need to clarify (at least informally) what you want to find, i.e. you should specify when a solution is better than another one, and then we can talk about finding an optimum/optimal solution or approximate solution. An unknown scoring function used by current system is not very helpful. If they really don't care about this and just want an acceptable answer then you can ignore all those extra detailed information. (IMHO, your question is underspecified even for a modeling question and it is not clear what would be an acceptable answer to your question. (more) $\endgroup$ – Kaveh Mar 16 '11 at 5:26
  • $\begingroup$ You probably need a software engineer first to speak with them to find what they are trying to achieve.) Abstracting the details a little bit will also help, most of the details just tell which mentor can be assigned to which course, and how much the mentor is willing to accept that appointment. (I don't see the point of asking mentors both for the course and the instructor, it just complicates things, one number should suffice). $\endgroup$ – Kaveh Mar 16 '11 at 5:32
3
$\begingroup$

While the entire problem seems under-defined, I believe it's fairly clear that you're dealing with a Multi-Objective Optimization problem, with scheduling simply being the backdrop for this problem. Most new effort in this field seems to be concentrated on Evolution Algorithms as solutions to these problems.

I personally do quite a bit of work with Particle Swarms in this area mostly because they provide very simple method of visualization in a complicated space. Other algorithms would include Non-dominated Sorting Genetic Algorithm-II (NSGA-II), or Multiple-objective Bayesian Optimization Algorithm (mBOA).

I would agree with Tsuyoshi in that you may want to spend more time on the problem definition as well.

$\endgroup$
3
$\begingroup$

It seems to me that a better approach is to frame this as a large optimization problem and throw it into CPLEX or something like that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.