Is there an efficient algorithm to distribute resources in a way that both avoids conflict and allows bias?
- by Steve V.
Background
(Skip this if you only care about the algorithm)
At the university where I work, one of the biggest hassles in our department is classroom scheduling. For illustration purposes and to lay out the scope of the problem, here's how we do scheduling now:
Professors give us a list of the classes they're teaching with the time slots they'd prefer to teach, ranked in order of priority (most desired to least desired).
Administration gives us a list of the rooms we may assign along with the times those rooms are available for our department's use.
We start assigning professors to rooms trying (at first) to take into account the preferences of the various professors.
Inevitably, conflicts arise, professors start asking for changes, and the plan falls to pieces somewhere around professor number 30, at which point we start assigning rooms basically wherever we can fit them in, crumpled pieces of paper are everywhere, and nobody's happy. (If you've ever wondered why your class was at 9.30 in the morning on Thursday but 4 pm every other day, now you know)
I have been asked to quietly investigate whether software could do this more optimally.
The Actual Question
Is there an algorithm to efficiently schedule a set of resources such that the following criteria are met:
The algorithm must never assign two professors to the same room at the same time.
The task is not complete until every professor has been assigned a room / time.
The algorithm need not worry about having too many professors for the amount of time slots available. (We're not that well funded.)
As much as is possible the algorithm should respect the scheduling preferences of the individual professors.
I feel like I can't be the first one to ask this. Is there a efficient algorithm for this, or is this the sort of problem that can only be brute-forced?
