StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Okay, I don't know about a particular algorithm, but here is what I would take into consideration.</p> <p><strong>Evaluation</strong> </p> <p>Whatever the method you will need a function to evaluate how much your solution is satisfying the constraints. You may take the 'comparison' approach (no global score but a way to compare two solutions), but I would recommend evaluation.</p> <p>What would be real good is if you could obtain a score for a shorter timespan, for example daily, it is really helpful with algorithms if you can 'predict' the range of the final score from a partial solution (eg, just the first 3 days out of 7). This way you can interrupt the computation based on this partial solution if it's already too low to meet your expectations.</p> <p><strong>Symmetry</strong></p> <p>It is likely that among those 200 people you have similar profiles: ie people sharing the same characteristics (availability, experience, willingness, ...). If you take two persons with the same profile, they are going to be interchangeable:</p> <ul> <li>Solution 1: (shift 1: Joe)(shift 2: Jim) ...other workers only...</li> <li>Solution 2: (shift 1: Jim)(shift 2: Joe) ...other workers only...</li> </ul> <p>are actually the same solution from your point of view.</p> <p>The good thing is that usually, you have less profiles than persons, which helps tremendously with the time spent in computation!</p> <p>For example, imagine that you generated all the solutions based on Solution 1, then there is no need to compute anything based on Solution 2.</p> <p><strong>Iterative</strong></p> <p>Instead of generating the whole schedule at once, you may consider generating it incrementally (say 1 week at a time). The net gain is that the complexity for a week is reduced (there are less possibilities).</p> <p>Then, once you have this week, you compute the second one, being careful of taking the first into account the first for your constraints of course.</p> <p>The advantage is that you explicitly design you algorithm to take into account an already used solution, this way for the next schedule generation it will make sure not to make a person work 24hours straight!</p> <p><strong>Serialization</strong></p> <p>You should consider the serialization of your solution objects (pick up your choice, pickle is quite good for Python). You will need the previous schedule when generating a new one, and I bet you'd rather not enter it manually for the 200 people.</p> <p><strong>Exhaustive</strong></p> <p>Now, after all that, I would actually favor an exhaustive search since using symmetry and evaluation the possibilities might not be so numerous (the problem remains NP-complete though, there is no silver bullet).</p> <p>You may be willing to try your hand at the <a href="http://en.wikipedia.org/wiki/Backtracking" rel="nofollow noreferrer">Backtracking Algorithm</a>.</p> <p>Also, you should take a look at the following links which deal with similar kind of problems:</p> <ul> <li><a href="http://norvig.com/sudoku.html" rel="nofollow noreferrer">Python Sudoku Solver</a></li> <li><a href="http://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html" rel="nofollow noreferrer">Java Sudoku Solver using Knuth Dancing Links</a> (uses the backtracking algorithm)</li> </ul> <p>Both discuss the problems encountered during the implementation, so checking them out should help you.</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