Databases
StackOverflow2013
Postsdbo
POhow to tackle this combinatorial algorithm problem
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POhow to tackle this combinatorial algorithm problem
    text
    copied!<p>I have <code>N</code> people who must each take <code>T</code> 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.</p> <p>I need to schedule each person to take each exam in front of an examiner within an overall time period but avoiding a lunch break, using the minimum number of examiners for the minimum amount of time (i.e. no/minimum examiners idle)</p> <p>There are the following restrictions:</p> <ul> <li>No person can be in 2 places at once</li> <li>each person must take each exam once</li> <li>noone should be examined by the same examiner twice</li> </ul> <p>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? <a href="https://stackoverflow.com/questions/184195/seating-plan-software-recommendations-does-such-a-beast-even-exist">Seating plan software recommendations (does such a beast even exist?)</a>).</p> <p>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..</p> <p>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.</p> <p>currently im doing this:</p> <ul> <li>make a list of all "tests" which need to take place, between every candidate and exam</li> <li>start with as many examiners as there are tests</li> <li>repeatedly loop over all examiners, for each one: find an unscheduled test which is eligible for the examiner (based on the restrictions)</li> <li>continue until all tests that can be scheduled, are</li> <li>if there are any unscheduled tests, increment the number of examiners and start again.</li> </ul> <p>i'm looking for better suggestions on how to approach this, as it feels rather crude currently.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload