Scheduling interview algorithm to minimize number of applicants in an interview

Question

My organization guarantees every applicant an interview and we always receive more applicants than all the time slots among all the interviewers combined. So we sometimes need to double or triple-up applicants in an interview.

I want to find an algorithm that

Matches the availabilities of applicants to an interviewer
Doubles-up the applicants as little as possible

I already tried using the Ford-Fulkerson algorithm for maximum network flow as suggested in this answer: Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction), but it immediately doubles-up applicants.

I've also thought of approaching the problem as a constraints problem, but I'm unsure how to model having a variable number of interviewers available at each time slot in addition to the occasional doubling up of applicants.

Does anyone know of an appropriate algorithm or way to model the problem? Or if this is the wrong direction, can you point me towards the correct terminology?

Do interviewers and applicants have attributes, or can any applicant meet with any interviewer? — user3386109, Jun 04 '19 at 03:36
@user3386109 There is a set of applicants and a set of interviewers. Each applicant and interviewer has a set of time slots when they are available. — DHerls, Jun 04 '19 at 03:44
I would apply the [greedy algorithm from the set cover problem](https://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm). — user3386109, Jun 04 '19 at 04:19
I don't have much experience with set cover problems, sorry. How do you recommend I represent the data to be covered? — DHerls, Jun 04 '19 at 04:34
@Yola I prefer 2 double ups. Smallest number of people per interview — DHerls, Jun 04 '19 at 19:55

score 0 · Answer 1 · answered Jun 04 '19 at 04:33

If you apply an algorithm for the https://en.wikipedia.org/wiki/Assignment_problem to the original data, it will find a full match only if the problem can be solved without any doubling-up at all. If you create N copies of all the interviewers when posing the assignment problem, it will match all of the applicants only if the problem can be solved with every interviewer handling at most N applicants at a time. So you can binary chop on N to find the value of N when you can just solve the problem, with every interviewer handling at most N applicants, and know that no smaller N will do.

Scheduling interview algorithm to minimize number of applicants in an interview

1 Answers1