Best algorithm for scheduling interviews

Question

I posted the same question on stackoverflow and immediately referred to post it here.

I want to think about the best algorithm which let the interviewer meet maximum number of candidates. Suppose that there are n candidates and one interviewer. Each of interview will be held for a fixed time, so we can consider that each interview to be given a time slot. Number of time slots are given as m. All candidates are asked to submit whether they are available for each time slots. If I put it in table format, it looks like this.

1: available
0: not available

         Aoi   Banri  ...   Nami
slot 1    1      1    ...    0
slot 2    0      1    ...    1
 .        .      .    .      .
 .        .      .     .     .
 .        .      .      .    .
slot m    0      1    ...    0

• Possible approaches 1: solve as a matrix problem

If I interpret this as a matrix problem, it would be reduced to find the Matrix X, expressed as a product of matrices with only one-to-one column exchange, that maximizes trace(AX). A is the schedule table.

Is there any good way to do that?

• Possible approaches 2: solve as a algorithm problem

If one can think about the best algorithm which always produces best result, it does not necessarily be a matrix problem One that comes to my mind will be something like that:

1. Find the candidate A which has minimum number of available time slots.
2. Among the time slots when A is available, find the slot a which has minimum number of candidates who are possible to attend.
3. Place A on slot a. Remove both from the table.
4. Repeat above procedure for each candidates.

In the Python code format, it may look like this.

d=[[Aoi, 1, 0, ..., 0
Banri, 1, 1, ..., 1
.
.
.
Nami,  0, 1, ..., 0
]]

d_reserved=[]

d_return=reserve_each(d, d_reserved)


def reserve_each(d, _reserved):
  d_summed = cal_sums(d) # add summ on rows and columns as the outermost row/column.
  d=d[np.argsort(d_summed[-1, :])]

  for i in range(n):
    di=d[i,1:]
    if np.max(di) < 0.1:
      if i > 1:
        researve_each(d[i-1:, :], d[:i-1,:])
      else:
        # alert!!! perhaps goes random?

    di=di[np.argmax(d[-1,1:]*d[i,1:])]

    first = 1
    for dij in di:
      if dij == 1:
        dij = dij*first
        first = 0        

    d[i,1:]=di

  return np.concatenate(d_reserved, d, axis=1))    


def cal_sums(d):
  d=np.concatenate(d, np.sum(d[:, 1:], axis=1))
  d_summed=np.concatenate(d_sorted, [0, np.sum(d[1, 1:], axis=0)])
  return d_summed

However, I can think many ways this algorithm would fail or may not be provide the best answers. I would be happy if anyone facing similar problem knows better ways to do that.

Answer 1

You can model your problem as ILP and implement it e.g., in Pythons PuLP library and solve it with commercial solvers (e.g., GUROBI or CPLEX) or non-commercial solvers such as COIN-OR. However, you would need to see how this approach would scale.

Let $i \in I$ be the set of interviewers, $j \in J$ the set of interviewees and $t \in T$ the set of slots. We now define variable $x_{ijt}$ to be a binary variable that is 1 if interviewer $i$ interviews interviewee $j$ at slot $t$. Further, let $y_{jt}$ be the parameter that shows if interviewee $j$ is available in slot $t$.

Linear Program \begin{align} \ & \max z = \sum_{i\in I}\sum_{j\in J}\sum_{t\in T} x_{ijt} \\ \\\textit{S.t.}\\ \\ & \sum_{i\in I} \sum_{t\in T} x_{ijt} \leq 1 \quad \forall j \in J & \tag1 \\ & \sum_{i\in I} x_{ijt} \leq y_{jt} \quad \forall j \in J; t \in T & \tag2 \\ & \sum_{j\in J} x_{ijt} \leq 1 \quad \forall i \in I; t \in T & \tag3 \\ & x_{ijt} \in \{0,1\} \quad \forall i \in I; j \in J; t \in T\tag4 \end{align}

The objective is to maximize the number of interviews held. Equation (1) makes sure that an interviewee is only interviewed at most once. Equation (2) makes sure that an interviewee is interviewed in a slot he is available in. Equation (3) makes sure that an interviewer interviews at most one interviewee in a slot.

Answer 2

Someone with a handlename MBo told me this problem is called Maximum Bipartite Matching problem and there is an algorithm to solve it on my stackoverflow post.

Khun's Algorithm: https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html#proof

I may try implementing one of the variation.

As I commented, I think I can expand this problem for more than one interviewer. In that case, just set the number of total time slots to be equal to the sum of time slots each of iterviewers is available. So that the variables can be represented in 2D array and can be solved in the same manner.