CODEWITHSUNDEEP
algorithm
Steve V.
Steve V.

Reputation: 453

Is there an efficient algorithm to distribute resources in a way that both avoids conflict and allows bias?

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:

  1. 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).
  2. Administration gives us a list of the rooms we may assign along with the times those rooms are available for our department's use.
  3. We start assigning professors to rooms trying (at first) to take into account the preferences of the various professors.
  4. 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:

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?

Upvotes: 3

Views: 387

Answers (1)

mcdowella
mcdowella

Reputation: 19601

There have been papers written on timetabling and scheduling problems for some time. A web search on the two words "timetabling package" turns up commercial and other packages for this.

I know of a problem domain where, despite spasmodic attempts to seek sophisticated solutions, people have ended up writing pretty basic programs implementing ad-hoc solutions - there has been no obvious sign of institutional learning in this field. The stated reason for this is that the users need to understand why the program makes its decisions, especially if it fails to solve the problem and they need to relax the constraints.

It sounds possible that your particular problem - if it is as simple as it at first sounds - could be solved by using the http://en.wikipedia.org/wiki/Assignment_problem, where you assign particular courses to particular room time-slots instead of agents to tasks.

It is possible that a program or algorithm will be influenced by the relative order of constraints in its input, especially if it encounters ties, where two solutions come out as equally good. I would be included to check for this, and, if so, to randomly re-order the input before presenting it to the program or algorithm in an attempt to at least turn bias into random luck.

Upvotes: 1

Related Questions