We run into this for customer support (www.assembled.com) and one of the things we've learned is that the ability to solve the fully constrained problem in the real world is not quite enough, at least for our customers.
Quite often, people are looking for the right set of constraints to apply so they're kind of running a meta problem on top of the NSP. How many back-to-back shifts should I allow? Should people's shifts always start at the same time? Can I give some people regular 9-5 schedules? All of the above questions will decrease the strict optimality of the solution, but increase the happiness and long term retention of your workforce. Thus, the question really become, how much do each of these cost in terms of optimality and what are the tradeoffs.
We've found that developing a very fast heuristic algorithm for the NSP allows people to iterate quickly on these types of questions (even though it's not quite as optimal as a SAT solver). We use a greedy algorithm with a heuristic that is relatively specific to our problem domain to ensure that we have a reasonable combination of speed and optimality.
Quite often, people are looking for the right set of constraints to apply so they're kind of running a meta problem on top of the NSP. How many back-to-back shifts should I allow? Should people's shifts always start at the same time? Can I give some people regular 9-5 schedules? All of the above questions will decrease the strict optimality of the solution, but increase the happiness and long term retention of your workforce. Thus, the question really become, how much do each of these cost in terms of optimality and what are the tradeoffs.
We've found that developing a very fast heuristic algorithm for the NSP allows people to iterate quickly on these types of questions (even though it's not quite as optimal as a SAT solver). We use a greedy algorithm with a heuristic that is relatively specific to our problem domain to ensure that we have a reasonable combination of speed and optimality.