StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>As <strong>julienaubert</strong> proposed, a solution (which I will call <em>schedule</em>) is a sequence of tuples (date, student, examiner, test) that covers all relevant student-test combinations (do all N students take all T tests?). I understand that a single examiner may test several students at once. Otherwise, a huge number of examiners will be required (at least one per student), which I really doubt.</p> <p>Two tuples A and B conflict if</p> <ul> <li>the student is the same, the test is different, and the time-period overlaps</li> <li>the examiner is the same, the test is different, and the time-period overlaps</li> <li>the student has already worked with the examiner on another test</li> </ul> <p>Notice that <em>tuple</em> conflicts are different from <em>schedule</em> conflicts (which must additionally check for the repeated examiner problem).</p> <p>Lower bounds:</p> <ul> <li>the number E of examiners must be >= the total number of the tests of the most overworked student</li> <li>total time must be greater than the total length of the tests of the most overworked student.</li> </ul> <p>A simple, greedy schedule can be constructed by the following method:</p> <ol> <li>Take the most overworked student and assigning tests in random order, each with a different examiner. Some bin-packing can be used to reorder the tests so that the lunch hour is kept free. This will be a happy student: he will finish in the minimum possible time.</li> <li>For each other student, if the student must take any test already scheduled, share time, place and examiner with the previously-scheduled test.</li> <li>Take the most overworked student (as in: highest number of unscheduled tests), and assign tuples so that no constraints are violated, adding more time and examiners if necessary</li> <li>If any students have unscheduled tests, goto 2.</li> </ol> <p>Improving the choices made in step 2 above is critical to improvement; this choice can form the basis for heuristic search. The above algorithm tries to minimize the number of examiners required, at the expense of student time (students may end up with one exam early on and another last thing in the day, nothing in between). However, it is guaranteed to yield legal solutions. Running it with different students can be used to generate "starting" solutions to a GA that sticks to legal answers.</p> <p>In general, I believe there is no "perfect answer" to a problem like this one, because there are so many factors that must be taken into account: students would like to minimize their total time spent examining themselves, as would examiners; we would like to minimize the number of examiners, but there are also practical limitations to how many students we can stack in a room with a single examiner. Also, we would like to make the scheduling "fair", so nobody is clearly getting much worse than others. So the best you can hope to do is to allow these knobs to be fiddled with, the results to be known (total time, per-student happiness, per-examiner happiness, exam sizes, perceived fairness) and allow the user to explore the parameter space and make an informed choice.</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