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.
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.