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.
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.
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.
http://healthysleep.med.harvard.edu/need-sleep/success-stori...
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.
So... you're saying soldiers are like girls in high school?
"I thought this high school bullshit was over!" is one of the most depressingly funny phrases I've ever heard eighteen-year-olds repeatedly utter.
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.
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
EDIT: A sibling comment pointed out Simulated Annealing also, which provides a more analogous means to discuss the 'reheat' stage here.
I don't think tinkering with the weights is quite the same thing. That happens when the algorithm is doing a good job of optimizing the scoring function, but the scoring function isn't doing a good job of representing what people want.
It does remind me of another thing I occasionally do when I don't quite get the results I want, which is to manually change one of the assignments and then have it climb the hill from there. Sometimes I'll just clear some assignments and re-run, which is pretty much a manual, ad-hoc version of what you describe.
Even though I did research on it, I found that the field is subject to a lot of colloquialisms (for lack of a better term) when it comes to different research cliques, and therefore the terminology I use isn't any more of less correct as a result.
It seems like you've got as good a handle on it as anyone.
My research was mainly involving investigating parallelism of the above algorithm (not very friendly to parallelism without work).
Nowadays, there's so many academic open source optimizers, as well as commerical, that I would usually tell people if you're solving for a business case, it's often more cost effective to frame your problem in a format digestible by the solvers and let them at it than writing the solvers yourself.
Of course, where's the fun in that? I'm jealous that you got to use this for a problem that you had, rather than in my approach which was for a problem I didn't need solved myself. I bet that was satisfying.
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.
https://en.wikipedia.org/wiki/Hill_climbing#Mathematical_des...
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!
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.
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).
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.