algorithm - Class Scheduling to Boolean satisfiability [Polynomial-time reduction] part 2

Question

I asked few days ago, a question about how to transform a University Class Scheduling Problem into a Boolean Satisfiability Problem.

(Class Scheduling to Boolean satisfiability [Polynomial-time reduction])

I got an answer by @Amit who was very elegant and easy to code. Basically, his answer was like this : instead of considering courses, he considered time-intervals.

So for the i-th course, he just indicted all the possible intervals for this course. And we obtain a solution when there is at least 1 true-interval for every course and when no interval overlap an other.

This methods works very well when we consider only courses and nothing else. I generalize it by encoding the room inside the interval.

for example, instead of [8-10] to say that a course can happen between 8am and 10am.

I used [0.00801 - 0.01001] to say that a course can happen between 8am and 10am in the room 1.

I'm sure that you are currently wandering "why use double ?" well, because here come my problem :

To continue to generalize this method, I encode also the n° of the teacher in this interval.

I used [1.00801 - 1.01001] to say that a course can happen between 8am and 10am in the room 1 and be taught by the teacher n°1.

Here is what I got for now :

like this [1.008XX - 1.010XX] can happen in the same time as [2.008YY - 2.010YY], which is true, if the teacher 1 is teaching in the room X between 8am and 10am, the teacher 2 can teach also in Y between 8am and 10am, if and only if the room is available.

The problem is : with this method I cannot assure that XX and YY will be different and that YY will be available, because [1.008XX - 1.010XX] don't overlap [2.008XX - 2.010XX], so for now, the solver consider this possible.

And I still don't have any clue on how to assure this, by using this interval-method... I need a way to encode {Interval, room and teacher-id}?in order that :

• a teacher cannot be in 2 places in the same interval.
• there cannot be 2 teachers in the same room for the same interval.
• there is a least 1 interval true by course.

Thanks in advance for your help, Best regards !

---

Follow up question: Class Scheduling to Boolean satisfiability [Polynomial-time reduction] Final Part

Answer 1

This answer is extension of Part 1's answer, and uses the same notations when possible.

Ok, assume each interval is assigned to one teacher (if more than one teacher can take the interval, just have multiple instances of it, with different teachers per instance), so to indicate teacher t teaches in a classroom p at time x to y, we can use the old variable that this class is given - V_{i,j} - for the class and interval.

For each teacher t , and for each pair of intervals c=(x1,y1), d=(x2,y2) in classes (a,b) the teacher might participate in, add the clause:

Q_{t,i,j} = Not(V_ac) OR Not(V_bd) OR Smaller(y1,x2) OR Smaller(y2,x1)

Intuitively, the above clause guarantees a teacher cannot be in the same time in two places - no intervals overlap that the same teacher is assigned to them.

By chaining each pair (i,j) for each teacher t with AND to the original formula, it satisfies your first constraint - a teacher cannot be in 2 places in the same interval. - since each teacher cannot be in two places at the same time.

Your second constraint there cannot be 2 teachers in the same room for the same interval. is also satisfied by the fact that there cannot be two classes that overlap the time and class.

The 3rd constraint there is a least 1 interval true by course. is satisfied by the F1 clause, since you have to choose at least one interval (with one teacher assigned) for each course.