The two classes of solutions that I considered where optimization solvers (see Gurobi Optimization for example), and meta-heuristics (see the book Metahueristics: From Design to Implementation). If I remember correctly, the people at Gurobi started at a previous company which was spun out of an airline, but I might be confused. All the algorithms in both classes of solutions are so nuanced that it can take years to begin to grasp how their strengths and weaknesses interact with your particular scheduling challenge, and how the way you formulate the problem interacts with the ability of the algorithm to solve it.
All that said, the real problem for me was a human one: If you produce a viable schedule X, the organization involved will always want to alter the rules to stretch the available resources to cover more, and simultaneously all the schedule staff will want more flexibility and nuance in expressing their preferences. You, as the author of scheduling software, are caught between them. Neither side is ever happy with the result.
I occasionally daydream about revisiting resident scheduling (I don't recommend it, the people who use your software leave every year, are not business oriented, and don't understand the complexity of the task until they've tried it on their own their first and only attempt). If I did, I would focus less on algorithms, and more on incentives to reconcile the tension between the organization, which wants to cover the most shifts with the fewest people at the cost of flexibility and preferences, and the staff, who want more flexibility and more preferences satisfied. I think that is the core problem at a business level.