Algorithm for a planning tool

Question

I'm writing a small software application that needs to serve as a simple planning tool for a local school. The 'problem' it needs to solve is fairly basic. Namely, the teachers need to talk with the parents of all children. However, some children have, of course, brothers and sisters in different groups, so these talks need to be scheduled next to eachother, to avoid the situations were parents have a talk at 6 pm and another one at 10 pm. Thus in short, given a collection of n children, where some children have 1 or more brothers or sisters, generate a schedule where all the talks of these children are planned next to each other.

Now, maybe the problem can be solved extremely easy, but on the other I have a feeling this can be a pretty complicated problem, that needs and can be solved with some sort of algorithm. Elegantly. But am I right? Is there? I've looked at the Hungarian alorithm but it doesn't quite apply to this particular problem.

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

Thanks!

Answer 1

I think it is quite easy.

First group the kids which belong together because they share parents. Schedule the children inside a group consecutively, schedule the rest as random.

Another way to abstract it and make the problem easier is to look from the parent perspective, see brothers and sister as "child" and give them more time. Then you can just schedule the parents at random, but some need more time (because they have multiple childeren).

Answer 2

This sorts feels like a "backpack algorithm" type of problem. You need to group the family members together then fill slots appropriately.

If you google "backpack algorithm", you'll see enough write-ups to make your head spin and also some good coded solutions.

Answer 3

I think if each talk could be reduced to "activities" where each activity has a start time and an end time you could use the activity-selection algorithm studied in computer science. It is based on a greedy approach and could be solved in O(n) (where n is the number of activities). You could find more information here. I am sure you will need to have to do a pre-processing here to be able to reduce the brother/sister issue as activities of the same type.

Answer 4

One approach woul dbe to define the problem in a declarative constraint language and then let it solve the problem for you. The last time I did this, I used ECLiPSe, which is a nifty little language where you define your problem space by constraints, and then let it find allowable values that satisfy those constraints.

For example, I believe you have two classes of constraints:

1. A teacher may only have one conference at a time
2. All students in the same family must have consecutive slots

Once you define these in ECLiPSe, it will calculate values for each student that satisfy the requirements. If you go this way, you can also easily add constraints as you need to. For example, it's easy to say that a teach is unavailable for slot Y, or teachers must take turns doing administrative work, etc.