6 ms·

I have a miniature version of this, as I'm in charge of the duty schedule at my flying club and I wrote a program to generate the schedules for me. There's a f

I have a miniature version of this, as I'm in charge of the duty schedule at my flying club and I wrote a program to generate the schedules for me. There's a function which takes a schedule and generates a score. Leaving a spot unfilled or scheduling someone who isn't available subtracts lots of points. Scheduling someone much more or less often than the median subtracts points based on how much of a difference there is. Scheduling someone on a day they prefer adds points, and so forth. Then it's a simple hill-climbing algorithm starting from an empty schedule. I get people's availability and preferences into the program, hit run, and out pops a schedule. I learned early on that I must check the result before publishing it. The algorithm itself works fine. Hill climbing probably isn't finding the absolute optimal schedule, but it does a good job. The problem, of course, is the scoring function. Sometimes it turns out to be missing some important constraint. Much more often, I need to tinker with the weights assigned to various conditions. People assign too much agency and intelligence to computers. They are, of course, just tools. A nail gun will put a nail into whatever you point it at, whether it's drywall or flooring or feet. Likewise, a computer optimization system will optimize whatever function you tell it to, and will probably do an excellent job, but it's up to you to make sure the function accurately describes what the humans want.

snerbles 8y ago
Back when I was enlisted, my sergeant had a bit of a conundrum. Troops were grumbling about being repeatedly assigned to the same posts, and we didn't have enough time during the shift to scramble the roster while ensuring adequate manning. I wrote a simple Excel macro which randomly assigned security personnel to posts they held qualifications for. Since it didn't have any knowledge of personality conflicts or preferences of the troops getting assignments, the results generated by the Rosternator 3000 were generally hated by all involved. In the end the tool was still useful - the mere threat of a randomized roster was enough to get everyone to quit grumbling.
- mikeash 8y ago
  Nice one. The key to effective use of computers is knowing exactly what problem you want to solve.
- WhompingWindows 8y ago
  How many personnel/posts were you assigning, out of curiosity? I've seen a similar problem, not automated yet, with around 20 staff members, who have varying conditionals which would have to be accounted for. It's not necessarily worth my time to automate for such a small # of people, then again it's a fun puzzle. The current approach is a 2-month rotating schedule. Since there are day/evening/overnight shifts, with overnight being the least desirable and evening the most desirable, it was deemed most equitable to simply rotate members through different 2-month schedules. This way, everyone across the year will be doing the same sets/timings of shifts in different months. This becomes very important for evening shifts, in particular, since transitioning to/from that schedule requires time to overcome the jet-lag induced.
  - snerbles 8y ago
    Roughly seventy personnel to about half as many posts. This was during the surge in Iraq, so half (or more) of our garrison was out in the sandbox at any given time anyway. This was a shift-specific tool, so it only had to account for certifications (e.g. a Response Force Member wouldn't be put into a Controller/Dispatch position). From what I recall, the post listing itself was on one sheet with personnel/qualifications on another. Posts were iterated by priority, so critical manning positions were always appropriately staffed from the source roster.
    - ghrifter 8y ago
      What did you do as an enlisted guy?
  - Spooky23 8y ago
    Make sure to rotate forward. http://healthysleep.med.harvard.edu/need-sleep/success-stories/lou-killer-shift http://healthysleep.med.harvard.edu/need-sleep/success-stori...
- pkaye 8y ago
  I wonder if you could augment this further. Assign a scoring system for various conflicts and preferences. Start with the randomly assigned roster and swap random people as long as it improves the overall score.
  - dantheman0207 8y ago
    This is probably pretty close to how the roster originally came to be, except organically and without any computers.
  - snerbles 8y ago
    This thought did occur to me, but I didn't have the time to continue iteration past the first revision. Police blotters don't write themselves, as it turns out. If I had to do it today, I'd probably put the list of pair scores on one sheet (e.g. Snuffy/Smith at +5, Smith/Jones at -3) and perform iterative swapping as you suggested.
    - ThrustVectoring 8y ago
      Note that this is the "stable roommates problem" and does not necessarily have an "optimal" solution (where "optimal" means "no unmatched pair of people would've rather been matched together". Eg, if Albert prefers Bob over Charles, Bob prefers Charles over Albert, and Charles prefers Albert over Bob, and all three prefer being matched with the last person over anyone else).
  - jpfed 8y ago
    I did something very similar to this for my wedding seating assignments.
  - jschwartzi 8y ago
    The problem here is that these conflicts and preferences are constantly shifting. Two people can be good friends one week and decide they hate each others' guts the next week. And then they can go back to being friends again the week after. The Rosternator 3000 can't keep up with this so you're always going to be generating bad schedules for a certain portion of your people. This is one of the reasons good retail managers ignore the advice of their time-keeping systems and give peoples' requests preference. The time-keeping system ignores all of the human aspects of the problem to focus on the least-important aspect of keeping a store running--making sure there are warm bodies in it.
nradov 8y ago
Is a simple hill-climbing algorithm really effective for problems like this? I've found that you usually have to add some randomization plus simulated annealing to avoid issues caused by falling into local maximums or always iterating through entries in the same order.
- mikeash 8y ago
  The simplest version where you just choose the single change that produces the best score isn't quite good enough for my purposes. I modified that slightly to run that to completion, then switch to choosing the two changes that produce the best score until that can't improve anymore either, which works a lot better. Fortunately my membership list is small enough that this is still computationally feasible.
- deong 8y ago
  Even local optima are often pretty good in practice. Also, it's a very good practice to iterate through the neighbors in a random order (if you're doing next descent, for steepest descent obviously it doesn't matter).
ac2u 8y ago
Hi, I did my masters research into this very problem. A lot of research here does just simply revolve around iterations of hill climbing [1] One thing which has been done quite a lot (and that's not to say you don't already do this), is to measure the gradient of improvement of your fitness function, and if it's been flat for too long, to relax the conditions/weights by X percent (X becomes another thing to tinker here, but I start with 10%). The flatness here suggests that you may be in a local optimum in the candidate space. This will allow worse solutions for many more iteration, (and a graph tracking the fitness will go the wrong direction), but in the end, you might find that you end up with a solution that is much 'fitter' than before the algorithm relaxed the conditions. (In the academic papers I read at the time, various words were used for this, sometimes it was called 'reheat') It seems that even if you don't do this, you know about it intuitively anyway since you talked about tinkering with the weights, just thought I'd chime in to mention that the tinkering part is often automated now. [1] https://en.wikipedia.org/wiki/Great_Deluge_algorithm https://en.wikipedia.org/wiki/Great_Deluge_algorithm EDIT: A sibling comment pointed out Simulated Annealing also, which provides a more analogous means to discuss the 'reheat' stage here.
- lodrein 8y ago
  That's interesting. Our approach is based on Mixed Integer Programming and Generalized Quadratic Assignment.
  - ac2u 8y ago
    I'm sure other approaches can be much more effective, my research was almost 8 years ago and was framed around trying to parallelise one of the algorithms. So my focus was half on the theory behind these solution search algorithms and half on parallelism and the associated theory. I've a gut feeling that a superior algorithm often gets you better ROI than parallelising an existing solution. The TLDR of my findings was that for the algorithm in question, it wasn't greatly suited to parallelism. Performance didn't scale linearly with cores due to too much shared state, and the best you could hope for was seeding each parallel run of the algorithm with different randomisation seeds and it's own state and bank on certain runs not getting caught in local optimum. So it got you better performance, but not so much that you'd jump right in to doing work to parallelise. Probably better to use algorithms that are built to be embarrassingly parallel from the ground up.
dba7dba 8y ago
Reading about scheduling reminded of a conversation I heard about involving an ER doctor. In that ER center, the scheduling of ER Doctors was done manually, by one of the ER doctors. Of course not the most senior doctor. But not the most junior doctor either, cause that doctor will be bullied into giving someone a preferred schedule. So the job was given to one of the junior doctors, like 3rd or 4th newest doctor out of about 15 ER doctors. These are doctors with big egos and with family, and all have legitimate reasons not to work certain days/nights/shifts. And this new, young ER doctor starting out his career confessed coming up with the weekly schedule to satisfy as many of the doctors as possible was the MOST stressful aspect of his job. And this is an ER doctor we are talking about. Granted he worked in a hospital in a suburb so not as many shootings/etc. I thought that was hilarious to hear.
- mikeash 8y ago
  Ouch. I will say that the moment when I hit “send” on a new schedule is pretty stressful. Thankfully everybody is very understanding of mistakes, and nobody’s being forced to work a night shift in this case.
twic 8y ago
FWIW, this is a classic genre of problem to tackle with integer programming - usually in the specific form of nurse rostering, for some reason: https://pdfs.semanticscholar.org/9d0b/5eb5749a6699a4c43bf8084d02113454b40b.pdf https://pdfs.semanticscholar.org/9d0b/5eb5749a6699a4c43bf808... It's entirely possible that your particular case has constraints you can't easily express as a linear program. But if you can, go ahead and use the nuclear option!
CJefferson 8y ago
This is my research area, and this is exactly the problem. While technically these kinds of problems are np complete, they are usually easy in practice. Getting people's requirements is much, much, much harder.
- mikeash 8y ago
  Exactly. It took me a couple of weeks, working in my leisure time, to get the solver to work well. It took me a couple of years of feedback from my victims to give it a set of rules and weights that didn’t need constant tweaking.
jpeg_hero 8y ago
market-based approach? sequential rounds of bidding with limited trading?
contravariant 8y ago
Simulated annealing is also great for solving problems like that, without getting stuck in the (many) local maxima.

snerbles 8y ago

Back when I was enlisted, my sergeant had a bit of a conundrum. Troops were grumbling about being repeatedly assigned to the same posts, and we didn't have enough time during the shift to scramble the roster while ensuring adequate manning. I wrote a simple Excel macro which randomly assigned security personnel to posts they held qualifications for. Since it didn't have any knowledge of personality conflicts or preferences of the troops getting assignments, the results generated by the Rosternator 3000 were generally hated by all involved. In the end the tool was still useful - the mere threat of a randomized roster was enough to get everyone to quit grumbling.

mikeash 8y ago
Nice one. The key to effective use of computers is knowing exactly what problem you want to solve.
WhompingWindows 8y ago
How many personnel/posts were you assigning, out of curiosity? I've seen a similar problem, not automated yet, with around 20 staff members, who have varying conditionals which would have to be accounted for. It's not necessarily worth my time to automate for such a small # of people, then again it's a fun puzzle. The current approach is a 2-month rotating schedule. Since there are day/evening/overnight shifts, with overnight being the least desirable and evening the most desirable, it was deemed most equitable to simply rotate members through different 2-month schedules. This way, everyone across the year will be doing the same sets/timings of shifts in different months. This becomes very important for evening shifts, in particular, since transitioning to/from that schedule requires time to overcome the jet-lag induced.
- snerbles 8y ago
  Roughly seventy personnel to about half as many posts. This was during the surge in Iraq, so half (or more) of our garrison was out in the sandbox at any given time anyway. This was a shift-specific tool, so it only had to account for certifications (e.g. a Response Force Member wouldn't be put into a Controller/Dispatch position). From what I recall, the post listing itself was on one sheet with personnel/qualifications on another. Posts were iterated by priority, so critical manning positions were always appropriately staffed from the source roster.
  - ghrifter 8y ago
    What did you do as an enlisted guy?
- Spooky23 8y ago
  Make sure to rotate forward. http://healthysleep.med.harvard.edu/need-sleep/success-stories/lou-killer-shift http://healthysleep.med.harvard.edu/need-sleep/success-stori...
pkaye 8y ago
I wonder if you could augment this further. Assign a scoring system for various conflicts and preferences. Start with the randomly assigned roster and swap random people as long as it improves the overall score.
- dantheman0207 8y ago
  This is probably pretty close to how the roster originally came to be, except organically and without any computers.
- snerbles 8y ago
  This thought did occur to me, but I didn't have the time to continue iteration past the first revision. Police blotters don't write themselves, as it turns out. If I had to do it today, I'd probably put the list of pair scores on one sheet (e.g. Snuffy/Smith at +5, Smith/Jones at -3) and perform iterative swapping as you suggested.
  - ThrustVectoring 8y ago
    Note that this is the "stable roommates problem" and does not necessarily have an "optimal" solution (where "optimal" means "no unmatched pair of people would've rather been matched together". Eg, if Albert prefers Bob over Charles, Bob prefers Charles over Albert, and Charles prefers Albert over Bob, and all three prefer being matched with the last person over anyone else).
- jpfed 8y ago
  I did something very similar to this for my wedding seating assignments.
- jschwartzi 8y ago
  The problem here is that these conflicts and preferences are constantly shifting. Two people can be good friends one week and decide they hate each others' guts the next week. And then they can go back to being friends again the week after. The Rosternator 3000 can't keep up with this so you're always going to be generating bad schedules for a certain portion of your people. This is one of the reasons good retail managers ignore the advice of their time-keeping systems and give peoples' requests preference. The time-keeping system ignores all of the human aspects of the problem to focus on the least-important aspect of keeping a store running--making sure there are warm bodies in it.

nradov 8y ago

Is a simple hill-climbing algorithm really effective for problems like this? I've found that you usually have to add some randomization plus simulated annealing to avoid issues caused by falling into local maximums or always iterating through entries in the same order.

mikeash 8y ago
The simplest version where you just choose the single change that produces the best score isn't quite good enough for my purposes. I modified that slightly to run that to completion, then switch to choosing the two changes that produce the best score until that can't improve anymore either, which works a lot better. Fortunately my membership list is small enough that this is still computationally feasible.
deong 8y ago
Even local optima are often pretty good in practice. Also, it's a very good practice to iterate through the neighbors in a random order (if you're doing next descent, for steepest descent obviously it doesn't matter).

ac2u 8y ago

Hi, I did my masters research into this very problem. A lot of research here does just simply revolve around iterations of hill climbing [1] One thing which has been done quite a lot (and that's not to say you don't already do this), is to measure the gradient of improvement of your fitness function, and if it's been flat for too long, to relax the conditions/weights by X percent (X becomes another thing to tinker here, but I start with 10%). The flatness here suggests that you may be in a local optimum in the candidate space. This will allow worse solutions for many more iteration, (and a graph tracking the fitness will go the wrong direction), but in the end, you might find that you end up with a solution that is much 'fitter' than before the algorithm relaxed the conditions. (In the academic papers I read at the time, various words were used for this, sometimes it was called 'reheat') It seems that even if you don't do this, you know about it intuitively anyway since you talked about tinkering with the weights, just thought I'd chime in to mention that the tinkering part is often automated now. [1] https://en.wikipedia.org/wiki/Great_Deluge_algorithm https://en.wikipedia.org/wiki/Great_Deluge_algorithm EDIT: A sibling comment pointed out Simulated Annealing also, which provides a more analogous means to discuss the 'reheat' stage here.

lodrein 8y ago
That's interesting. Our approach is based on Mixed Integer Programming and Generalized Quadratic Assignment.
- ac2u 8y ago
  I'm sure other approaches can be much more effective, my research was almost 8 years ago and was framed around trying to parallelise one of the algorithms. So my focus was half on the theory behind these solution search algorithms and half on parallelism and the associated theory. I've a gut feeling that a superior algorithm often gets you better ROI than parallelising an existing solution. The TLDR of my findings was that for the algorithm in question, it wasn't greatly suited to parallelism. Performance didn't scale linearly with cores due to too much shared state, and the best you could hope for was seeding each parallel run of the algorithm with different randomisation seeds and it's own state and bank on certain runs not getting caught in local optimum. So it got you better performance, but not so much that you'd jump right in to doing work to parallelise. Probably better to use algorithms that are built to be embarrassingly parallel from the ground up.

dba7dba 8y ago

Reading about scheduling reminded of a conversation I heard about involving an ER doctor. In that ER center, the scheduling of ER Doctors was done manually, by one of the ER doctors. Of course not the most senior doctor. But not the most junior doctor either, cause that doctor will be bullied into giving someone a preferred schedule. So the job was given to one of the junior doctors, like 3rd or 4th newest doctor out of about 15 ER doctors. These are doctors with big egos and with family, and all have legitimate reasons not to work certain days/nights/shifts. And this new, young ER doctor starting out his career confessed coming up with the weekly schedule to satisfy as many of the doctors as possible was the MOST stressful aspect of his job. And this is an ER doctor we are talking about. Granted he worked in a hospital in a suburb so not as many shootings/etc. I thought that was hilarious to hear.

mikeash 8y ago
Ouch. I will say that the moment when I hit “send” on a new schedule is pretty stressful. Thankfully everybody is very understanding of mistakes, and nobody’s being forced to work a night shift in this case.

twic 8y ago

FWIW, this is a classic genre of problem to tackle with integer programming - usually in the specific form of nurse rostering, for some reason: https://pdfs.semanticscholar.org/9d0b/5eb5749a6699a4c43bf8084d02113454b40b.pdf https://pdfs.semanticscholar.org/9d0b/5eb5749a6699a4c43bf808... It's entirely possible that your particular case has constraints you can't easily express as a linear program. But if you can, go ahead and use the nuclear option!

CJefferson 8y ago

This is my research area, and this is exactly the problem. While technically these kinds of problems are np complete, they are usually easy in practice. Getting people's requirements is much, much, much harder.

mikeash 8y ago
Exactly. It took me a couple of weeks, working in my leisure time, to get the solver to work well. It took me a couple of years of feedback from my victims to give it a set of rules and weights that didn’t need constant tweaking.

jpeg_hero 8y ago

market-based approach? sequential rounds of bidding with limited trading?

contravariant 8y ago

Simulated annealing is also great for solving problems like that, without getting stuck in the (many) local maxima.