The requirements set is totally rewritten by the requirement analyst.

Here is the new version.

In this problem, stakeholders are:

Each actor individually owns some constraints that must be (best) fulfilled.

A teacher has some constraints about:

A students group must take a particular teaching made up of a certain number of time slots for a certain number of teaching topics (X time slots for a topic 1, Y time slots for a topic 2, ...).

A lecture room is equipped or not with specific materials (an overhead projector, a video projector, materials for practical works, ...) and can be occupied or not during a given time slot, on a certain day.

For each stakeholder, constraints are given using an ordered list. The order of a constraint in the list gives its relative importance; therefore the first given constraint is, if possible, more easily relaxed than the last one.

Solving the problem consists in reconciling (combining) all the constraints to suggest a timetable for a certain duration.

In order to compare the various solutions implemented to solve this problem, a typical scenario is suggested. Three variants are proposed to gradually make the problem more complex; to realize a more and more complex timetable.

For each one of the variants proposed below, we give a possible solution which is certainly not unique but this is a means to try to slightly clarify the problem.

Variant #1: basic case, solving is possible without relaxing constraints

In this first version, the problem is simplified by the facts that only two-hour time slots are managed: 8:00-10:00, 10:00-12:00, 14:00-16:00 and 16:00-18:00 and that a timetable must be given for a two-day period.

We suppose that three teachers t1, t2 and t3 can lecture, each one on a specific topic. Each one has constraints and cannot give a course during some time slots. Therefore:

Three students group are considered: g1, g2 and g3. Each of them must follow, on these two days, two two-hour courses and each one of the courses must be given by each of the teachers (i.e. each group must have a total of twelve hours).

In this version, the system has not to manage the availability of the lecture rooms: a room exists for each group. Furthermore, actors cannot relax constraints in this variant. A possible solution for this example could be:
 
A possible solution for the first variant of ETTO problem

Variant #2: additional constraints on the lecture rooms, possible solving by relaxing a certain number of constraints

Constraints are added on the lecture rooms. Three rooms (r1, r2 and r3) are supposed to be available. Only the rooms r1 and r2 are equipped with overhead projectors.

All the teachers want to use the overhead projector at least once for each group of students during the two-day period.

To find a solution one or more actor(s) can relax one or more constraint(s).

In this variant, a possible solution could be:
 
A possible solution for the second variant of ETTO problem

This solution is possible if the constraint "the room r1 is not available on the day d1 from 10:00 to 12:00" is relaxed to put t1/r1 in this time slot and if the constraint "the room r2 is not available on the day d2 from 16:00 to 18:00" is also relaxed to put t3/r2 in this time slot (the constraint on t3 "not available from 8:00 to 10:00 on the second day could also be relaxed to find a solution).

Variant #3: constraints can change as the time goes by, adaptability to a dynamic environment

The possibility of modifying or adding constraints in a real time manner (using a graphical interface, for example) is now given. Thus a teacher is able to notify his availability for a time slot, a room can be freed or it can become occupied...

Constraints being able to dynamically evolve, the (multi-agent) system to be build must be able to adapt to the changes without any "hard" restart.

For example, during the search for a solution to the above timetable, the teacher t1 notifies his unavailability from 10:00 to 12:00 on the day d1 but, instead, he can lecture from 16:00 to 18:00 on the very same day.

How can the system solve this problem without interrupting the search for the solution and restarting from scratch?

One solution would be to ask the teacher t3 to give a course to the group g3 on the day d1 from 14:00 to 16:00 and to put in the freed time slot, t1/r1 from the 10:00-12:00 time slot on the same day. 3.4.
 

Variant #4: actors can dynamically appear or disappear, openness of the system

A potential variant number 4 could be proposed to test the adaptability of the system to the fact that the system becomes open. New actors (teachers, students groups or lecture rooms) can appear or disappear in a real time manner and the system must be able to adapt to these new "unexpected" events.