Algorithm for calculating the schedule of specified constraints

Question

I consider a hypothetical problem and seek guidance on how to approach the solution of the problem, from an algorithmic point of view.

Problem:

Consider a university. You have the following objects:

• Teaching Staff. Each employee teaches one or more documents.
• Students. Each student accepts one or more documents.
• The rooms. The rooms accommodate a certain number of students and contain certain types of equipment.
• Papers. Require a specific type of equipment and a certain amount of time each week.

Information on enrollment provided (for example, how many students are recorded in each document and which employees are allocated for each document), how can I calculate a schedule that is subject to the following restrictions:

• Staff can only learn one thing at a time.
• Students can attend only one document at a time.
• Numbers can contain only a certain number of students.
• Papers requiring a certain type of equipment can only be stored in a room that provides this type of equipment.
• Opening hours: Monday to Friday, 8-12 and 1-5.

Discussion:

In fact, I'm not too concerned about the situation described above - this is a general class of problems that interests me. At first glance it seems to me that this is well suited for a genetic algorithm, but the suitability function for such an algorithm will be incredibly complex.

What is a good approach to solve this constrained problem?

I think that there is probably no way to solve this problem, since students can take a combination of papers, which leads to impossible situations, especially as the number of students and documents grows.

Answer 1

Remaining on genetic algorithms, I do not think that the fitness function for this would be very difficult, quite the opposite.

Basically, you just check your candidate’s decision (regardless of encoding) for each of the restrictions (you only have 5) and assign weight to them, so when the restriction is not met, the weight is added to the overall score, which can be fitness.

In such a scenario, you simply turn off the fitness function (because the best fitness is 0, that is, all restrictions are met), and let GA crunch the numbers.

The encoding will be a little understandable, but as soon as this is done, it will be simple, unless, of course, I missed something :)

Answer 2

A very limited version of this problem is NP-Complete.

Consider the case when exactly one student can take the paper.

Now for a given time interval (say, paper is taught all day), you can build a three-part graph with numbers, documents and students with an edge between the paper and the student if this student wants to accept it. Also add edges between the paper and possible rooms.

Now we see that Problem 3 of the size matching issue is an example of your problem: you need to select non-overlapping (student, document, room) for this particular time interval.

You are probably better off with some heuristics for a common problem. Sorry, I can’t help you.

Hope this helps.