how to tackle this combinatorial algorithm problem

Posted by Andrew Bullock on Stack Overflow See other posts from Stack Overflow or by Andrew Bullock
Published on 2010-05-04T14:38:29Z Indexed on 2010/05/04 14:58 UTC
Read the original article Hit count: 804

I have N people who must each take T exams. Each exam takes "some" time, e.g. 30 min (no such thing as finishing early). Exams must be performed in front of an examiner.

I need to schedule each person to take each exam in front of an examiner within an overall time period, using the minimum number of examiners for the minimum amount of time (i.e. no examiners idle)

There are the following restrictions:

  • No person can be in 2 places at once
  • each person must take each exam once
  • noone should be examined by the same examiner twice

I realise that an optimal solution is probably NP-Complete, and that I'm probably best off using a genetic algorithm to obtain a best estimate (similar to this? http://stackoverflow.com/questions/184195/seating-plan-software-recommendations-does-such-a-beast-even-exist).

I'm comfortable with how genetic algorithms work, what i'm struggling with is how to model the problem programatically such that i CAN manipulate the parameters genetically..

If each exam took the same amount of time, then i'd divide the time period up into these lengths, and simply create a matrix of time slots vs examiners and drop the candidates in. However because the times of each test are not necessarily the same, i'm a bit lost on how to approach this.

currently im doing this:

  • make a list of all "tests" which need to take place, between every candidate and exam
  • start with as many examiners as there are tests
  • repeatedly loop over all examiners, for each one: find an unscheduled test which is eligible for the examiner (based on the restrictions)
  • continue until all tests that can be scheduled, are
  • if there are any unscheduled tests, increment the number of examiners and start again.

i'm looking for better suggestions on how to approach this, as it feels rather crude currently.

© Stack Overflow or respective owner

Related posts about genetic-algorithm

Related posts about algorithm-design