Planning Tool Algorithm

Question

I am writing a small software application that should serve as a simple planning tool for a local school. The “problem” to be solved is quite simple. Namely, teachers need to talk with the parents of all the children. However, some children, of course, are brothers and sisters in different groups, so these negotiations should be planned next to each other in order to avoid situations when parents talked at 18:00, and the other at 10 o’clock in the evening. In short, given the collection of Russian children in which some children have 1 or more brothers or sisters, create a schedule where all of these children’s conversations are planned next to each other.

Now, maybe the problem can be solved very easily, but on the other hand I have the feeling that it can be a rather complicated problem that needs and can be solved using some kind of algorithm. Elegantly. But right? Here? I reviewed Hungarian alorithm, but this is not entirely applicable to this particular problem.

Edit: I forgot to mention that all conversations take the same amount of time.

Thanks!

Answer 1

I think this is pretty easy.

The first group of children that belong to each other because they share parents. Plan the children within the group sequentially, assign the rest as random.

Another way to abstract it and ease the task is to look from the parent's point of view, see the brothers and sister as a “child” and give them more time. Then you can simply plan your parents at random, but some need more time (because they have several speakers).

Answer 2

One approach to identifying a problem in a language of declarative constraints, and then solving this problem for you. The last time I did this, I used ECLiPSe , which is a great little language in which you define your problem space by constraints, and then let you find valid values ​​that satisfy these constraints.

For example, I believe that you have two classes of restrictions:

• A teacher can have only one conference at a time
• All students in the same family must have consecutive slots.

Once you define them in ECLiPSe, it will calculate the values ​​for each student who meets the requirements. If you go this way, you can also easily add restrictions as you need. For example, it is easy to say that teaching is not available for slot Y, or that teachers must take turns performing administrative work, etc.

Answer 3

This type is similar to a backpack algorithm type problem. You need to group family members and then fill in the slots correctly.

If you use Google’s backpack algorithm, you’ll see enough records to make your head spin, as well as some good coded solutions.

Answer 4

I think that if each conversation could be reduced to “actions”, when each action has a start time and an end time, you can use the activity selection algorithm studied in the field of computer science. It is based on a greedy approach and can be solved in O (n) (where n is the number of activities). You can find more information here . I am sure that you will need to do the preprocessing here to be able to reduce the sibling problem as one type of activity.