Is this optimal schedule task NPC?

Question

I volunteered to write a program to schedule parent-teacher conferences. The principal wants parents to select 3 possible datetimes to visit their english and math teacher (at the same time).

Once all the parents have selected 3 datetimes, I'm supposed to figure out the optimal way to schedule the parent-teacher conferences so the greatest number of parents can meet with both teachers.

(If there is a time conflict and the math teacher can't be at the conference, a parent will only meet with the english teacher)

I don't know much about NP type problems, but when I hear the word "optimal" and "schedule" together, I start to wonder...

I already told the principal I couldn't do that, but I wanted to know if it was NP complete. And if it is, assuming there are:

• 500 parents
• 15 english teachers
• 5 math teachers
• 25 datetimes to pick from

could this be solved correctly in a few seconds, minutes or hours on your grandma's computer?

Answer 1

Well I have a partial answer to your question and a simulation that allows me to attempt different scenarios. Here are my working (but mutable) assumptions:

• The parameters are as you list them
• The choices of session times by parents follow a power law (Benford's Distribution) as this models the expected non-uniformity of preferrences
• Depending upon the run, there were ~20 parents who were 'intransigent' and could only come at one session.
• Each English teacher has one and only one corresponding Math teacher, as their correlation is presumed high but I don't know how high. The code can handle any correlation coefficient from 0 to 1.
• The whole shebang from generating plausible simulated parents ('smith' .. 'atkins'), teachers, time selections, and satisfying results took 300 milliseconds on a midling machine (5300 BogoMIPS).

My second order optimizations didn't even kick in as the first pass allowed every parent's first choice to be accommodated with a maximum of 11 parents in one session. This result was sub-optimal for the teachers who had to attend about half the time slots with a mean parent group of ~3.

Given any expressed interest I can make the code available, as it is about 125 lines.