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)