We have a discipline dedicated to solve problems we don't know how to solve: Artificial Intelligence. Let us give it a try.

First of all, let us come up with an utility function. The idea is that we should be able to feed a possible solution to the problem to the utility function, and it will return a value that tells us an estimation of how good that solution is.

We will have an agent try to maximize this utility function. If you want to imagine it as if we were designing a video game for people to do it, that works too.

Coming up with a good utility function is about understanding the problem space. So, let us see…

A mentor should have the skills necessary to provide proper mentorship

The solution will have pairings of mentors and mentees. The mentee has a list of skills, and so does the mentor. For each skill that overlaps in a pair, grant some points. The utility function is the sum of the points.

Mentors and mentees time slots should overlap (once everything is converted to UTC)

Similarly, they have time slots. When they overlap grant some points.

How does this interact with the above rule? The mentor skills are of no use if the mentor can't interact with mentee. Similarly - at least, in this model - the mentor that has none of the skills the mentee is looking for, is no use, even if their time overlap.

Thus, I suggest to grant points proportional the overlapped time times the overlapped skills.

If there is like a deadlock situation => order mentors and mentees by their questionnaire submission times

Instead of an utility function, we can work with relative utility. That is, we would have a function that compares solutions and tells you which is best. We still need to worry about making sure the order does not result in a strange loop or similar. This deadlock rule can be used with that.

Yet, I think there is a simpler solutions: add points for good questionnaire submission time. However, more time is worst, right? I suggest to avoid penalties, so don't do it by removing points. Add the multiplicative inverse of the time, by some factor q. I don't know what the factor q is, but it should be small, given that this is meant to untie solutions, it should result in fractions of a point.

Thus, our utility function would look like this:

f(p) = p.overlapping_skills * p.overlapping_time + q/p.total_q_time
utility(s) = sum i=1->n {f(s[n])}

Now, we can design our agent. Remember that we must not exceed the maximum number of mentees per mentor, nor the maximum number of mentors per mentee. Thus, every time we pick a pair, it must be validated. Also, every time we pick a mentor or a mentee (or loop over them), we have a chance to prioritize by questionnaire time.

We can follow a deterministic approach: loop over every mentee, for each one pick the mentor that would give the most utility, and assign it. Loop until no mentor can take more mentees, or no mentee can take more mentors.

We can try something similar to simulated annealing: Starting with no pair assigned, pick a mentor an mentee at random. If the mentor is at capacity, we are considering replacing the mentee that contributes less utility. Similarly, if the mentee is at capacity, we are considering replacing the mentor that contributes less utility. See if the assigment results in more utility that before, if it does, keep it, otherwise drop it. Loop until you are done a large amount of iterations (or a large ammount of iterations with no improvement).

We can try a generic algorithm. The list of pairs is the genome. We can start with a random population, cross them, mutate them, select the best, and repeat. Until we have done a large amount of iterations, or we see no improvement form a generation to the next.

We can try path finding. Use the inverse of the utility as heuristic of the distance. The better the solution, it would have better utility. And thus, the heuristic will be smaller. Which means it is closer to "the solution". Implement A* or similar heuristic path finder algorithm, where the nodes are the solution, and the vertex are each possible pairing you can do. This graph has a large branching factor, thus you will run into memory problems with A*, consider Iterative Deepening A* or Memory bounded A*.

Oh, and who said these agents have to be artificial? You could start by having people do it by hand, see what patterns emerge from what they do, automate those, repeat. You would end up with an expert system that can solve most of the case automatically, and let the humans handle the outliers.

Look, we can throw plenty of different kinds of agents to this problem. We have gone from "we have this problem with these restrictions" to "here is a bunch of things we can try to solve it". You can even imagine coming up with a large dataset, and testing which performs better.

Plus we probably can improve the utility function. I remind you that coming up with a good utility function is about knowing the problem space. And you know that better than me. For example: should we prefer that a mentor interacts with a mentee one at a time? Should we prefer only one mentor per skill the mentee wants? Should we prefer more or less mentors per mentee? Or should we prefer more or less mentees per mentor? I don't know.