Nurse Scheduling Problem and Optimization

I had an interview on Friday, and one of the questions has been on my mind, because I didn't really like how vague my answer was. It was presented as a design problem, but really it's a software engineering problem.  And it's a problem that I might be working on, if hired.

It turns out that it's something of an instance of the Nurse Scheduling Problem.  Nurses need to work a certain number of shifts, shouldn't have back to back shifts, should work about equally each week, then you have to consider different skill levels, shift preferences etc.

This isn't the exact question, of course... I'm not getting hired at a hospital.  But considering I've been scheduling a lot of interviews, it strikes me that having software engineers do technical interviews of candidates is something of the same problem.  Less busy, but still, a structure lots of people in tech can understand.

It's easy to think of additional constraints, either hard constraints which if violated make a schedule invalid, and soft constraints which can be used to rate valid solutions.  Maybe you have an open office, and two people shouldn't interview simultaneously if they work next to each other.  Soft constraint. Some people can interview for front end, some for back end, some for mobile, some for embedded, some for multiple.  Maybe you have all of those at your company, and need to assign individuals to particular candidates.  You may not give a good interview if you assign the embedded guy to interview someone to see if they actually know android development.  Hard Constraint.

Let's say we have d developers who can interview, i individuals interviewing, and t  time slots that a candidate says they are available and lets say we want to organize based on week.

 Even with just d and i  and the hard constraints, the naive solution will be in polynomial time. Now finding the optimal solution, with the soft constraints, the time slot issue... this is the nurse scheduling problem, and it's NP hard.

Imagine you are a manager assigning people, that's a lot of things to keep track of.  Add in sick days, projects that are priorities, and a manual system is going to be pretty stressful and complicated.

So obviously I'm not looking for an optimal solution.   But I've been thinking on heuristics that might be helpful.

Time slots where only one person is scheduled are easier to sub for.
Everyone may be equal, but multiple certifications can sub for more people, and can interview more people.

It strikes me that there are a variety of ways to simplify the problem.   So I'll try to solve the general problem programmatically and handle corner cases in an adhoc manner.
list available time slots in a calendar.  Have the the Candidates pick one time slot to commit to, then reschedule if needed. If a time slot overlaps, have a rough indication of interviewers available.  Green for multiple interviewers, red for 1, disabled for 0.

Limit time slots. A morning slot and an afternoon slot.  If none of the time slots work, the candidate can inform the company of when they are available by emailing.

Keep track of how many interviews a person does in a week, and when randomly selecting individuals, prefer selecting people who have done less.

I don't need to have an optimal solution, just a reasonably good one that makes finding workable solutions easier.   And it's okay that I didn't have perfect answers.  I don't need to design a perfect system, just one better then what they have currently.  Optimization isn't always about finding the optimum way to do things.  As long as you can make something better, you have improved it.