Welcome to an old and important topic in 'operations research'.

Such scheduling problems, and 'constraint satisfaction' problems more generally, have been attacked seriously for decades.

A fundamental point is what is wanted is a 'feasible' solution to an integer linear programming problem (ILP). That is, what ILP looks for is an 'optimal' solution but you want only a 'feasible' solution.

What is 'linear programming' (LP)? Remember a high school algebra system of linear equations. Linear programming asks for a solution to such a system but also asks that one more such equation -- called the 'objective function', e.g., cost -- be as small as possible. A solution to the linear equations is 'feasible'. If a feasible solution also makes the value of the objective function as small as possible, then that solution is 'optimal'.

If we also ask that the solution be integers, then we have 'integer linear programming' (ILP).

Or, for an example, a 'feasible' solution is a path that will get you to your date's house, and an optimal solution will get you there in least time.

Fundamentally in LP and ILP, although not necessarily always in practice, looking for a feasible solution is no easier than looking for an optimal solution. That is, fundamentally constraint satisfaction is no easier than optimization. So, really, in both theory and much of practice, constraint satisfaction problems end up in the world of optimization (i.e., linear programming and ILP).

So, one approach to such scheduling and constraint satisfaction problems is ILP, and for that there is C-PLEX done by R. Bixby of Rice University and the Optimization Subroutine Library (OSL) done at IBM's Yorktown Heights lab and as in

Ming S. Hung, Walter O. Rom, Allan D. Waren, 'Optimization with IBM OSL', ISBN 0-89426-244-0, Boyd & Fraser Publishing, Danvers, MA, 1994.

And there are several more collections of LP and ILP software.

ILOG was a French company heavily interested in constraint satisfaction problems and worked with SAP and made use of C-PLEX. Apparently now ILOG and C-PLEX are sold by IBM.

For academics, ILP, constraint satisfaction, etc. are in operations research, the mathematical sciences, and selected parts of engineering. Computer science also gets interested. Schools to consider include Georgia Tech, Rice, and Waterloo. E.g., Georgia Tech was the origin of

George L. Nemhauser and Laurence A. Wolsey, 'Integer and Combinatorial Optimization', ISBN 0-471-35943-2, John Wiley & Sons, Inc., New York, 1999.

ILP was one of the primary sources of motivation for the theory of NP completeness in computational complexity, e.g., as in

Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979.

We should note: Practical ILP problems vary enormously in difficulty. If we only ask for feasible solutions that save nearly all the money instead of necessarily the last tiny fraction of a penny exactly, then in practice the variation in difficulty is even larger. By "vary", I mean that for finding solutions some ILP problems are really easy and others are really difficult.

So, with this variation, it may be that your actual, practical problems are easy enough and can give you many happy trips to the bank.

But the theory of NP completeness asks for more: It wants an algorithm (and so far no one knows if such an algorithm can exist) that will solve any ILP problems, including the worst cases that can exist, even in theory, to exact optimality (when an optimal solution exists), in computer execution time that grows no faster than a polynomial in the size of the input data for the problem. It turns out, that's asking a lot, asks for a very strong guarantee, and asks for much more than is commonly sufficient for nice trips to the bank in practice. To be clear, many practical ILP problems are quite doable, but the worst case problems are much, much worse. To be more clear, it has long been known that your scheduling problems are in the challenging class NP-complete, but that does not mean that the instances of those problems you encounter in your practice are difficult.

There is a good chance that your problem is just linear programming on networks, i.e., minimum cost network flows, and where the arc capacities are integers. Then, if there is a feasible solution, there is a feasible integer solution, and the iterations of the ordinary LP simplex algorithm will, automatically with no extra effort, maintain feasible, integer solutions and produce an optimal integer solution (if an optimal solution exists). Specializing the data handling of the simplex algorithm to such network problems yields the 'network simplex method'. See papers of W. Cunningham long at Waterloo. So, in practice, linear programming on such network flow problems gives integer programming for no extra cost. Cute, and sometimes valuable.

Programming the network simplex algorithm is surprisingly easy. On a current PC processor with all the data in main memory, the algorithm is shockingly fast.

D. Bertsekas long at MIT has an algorithm for minimum cost network flows that is guaranteed polynomial (in the sense of the theory of NP completeness).

H. Kushner, long at the Division of Applied Math at Brown, long ago attacked nurse scheduling problems.

Welcome to operations research.