We’ve now entered the “Miscellaneous” section of the Sequencing and Scheduling chapter.

**The problem: **Timetable Design. This is problem SS19 in the appendix.

**The description: **(I’m using the description in the paper by Even, Itai, and Shamir, because I think it’s clearer than G&J’s definition): We’re given a set H (of hours to schedule), a collection of N “teachers”, each teacher is available for some subset of the H hours. We’re also given a collection of M “Classes”, each class is available to be taught for some subset of the H hours. We’re also given an NxM matrix R of requirements: R_{ij} is the number of hours teacher i needs to teach class j for. Can create a function f: TxCxH->{0,1} such that f(t,c,h) is 1 if teacher T is teaching class c at time h (and 0 otherwise)? The function needs to respect the following rules:

- If f(i,j,h) is 1, then h is in T
_{i}and C_{j}(we only schedule teachers and classes when they’re available) - The sum of f(i,j,h) over all h = R
_{ij}(Each teacher teaches each class the number of hours they’re supposed to - The sum of f(i,j,h) over all i <= 1 (Each class has at most 1 teacher in each time period)
- The sum of (i,j,h) over all i <= 1 (Each teacher can only teach 1 class per time slot).

**Example: **Suppose H was {1,2,3,4,5}

We have 3 teachers:

- T
_{1}is available at {1,2,3} - T
_{2}is available at {3,4,5} - T
_{3}is available at {1,3,5}

..and 3 classes:

- C
_{1}is available at {2,4} - C
_{2}is available at {1,5} - C
_{3}is available at {2,3}

If R was:

1 | 1 | 0 |

1 | 0 | 1 |

0 | 1 | 1 |

(Teachers are rows, so T_{1} needs 1 hour of C_{1}, 1 hour of C_{2}, and none of C_{3}, this won’t be satisfiable, since neither T_{2} nor T_{3} can teach C_{3} during hour 2, and someone has to. If we change C_{3} to be available at {2,3,5}, then this becomes satisfiable:

- T
_{1}can only teach C_{1}at time 2, and C_{2}at time 1 - T
_{2}can only teach C_{1}at time 4, and C_{3}can be either time 3 or 5. Let’s pick 5. - T
_{3}can teach C_{2}at times 1 or 5, but time 1 is taken by T_{1}, so we schedule it at time 5. Similarly, C_{3}is available at times 2 and 3, and T_{3}is also available at time 3, so we can schedule that class then.

**Reduction: **Even, Itai, and Shamir use 3SAT. So we’re given a set X of literals (x_{1} through x_{l}, and the negation ~x_{1} through ~x_{l}), and a set D of k clauses (D_{1} through D_{k}). Define p_{i} to be the number of times variable i (so the literal x_{i} or the literal ~x_{i}) shows up in the formula. Each variable i will get 5*p_{i} classes denoted C^{i}_{ab}, where a runs from 1 to p_{i}, and b runs from 1 to 5. There will be 3 hours to schedule the classes. They organize the teachers for the classes in a widget that looks like this (from the paper, p. 693):

The idea is that the diagonal lines are teachers who have to teach the 2 classes connected by the line (So, C_{12} and C_{13} for example) and the crosses are the 2 ways they can teach it (so h_{2} and h_{3}). The bottom arrows are teachers who can have 3 hours of availability and 3 classes to teach. Each variable gets p_{i} teachers who teach C_{q3} and C_{q4} (where q runs from 1 to p_{i}) during h_{1} and h_{2}. If C_{q3} is taught at time h_{1}, the variable is treated as being set to positive, otherwise, it’s negative.

We then need to add more jobs to make sure that we make one literal true in each clause. This is done by creating a teacher with 3 classes (one for each literal in the clause). If the literal is the qth occurrence of literal x_{i}, the teacher is assigned to class C^{i}_{q2 }if the literal is true, and C^{i}_{q5} if the literal is false.

If there is a satisfiable solution to the SAT instance, the literal that makes each clause true will define a way to set the teacher at time h_{1} and h_{2}, and that starts a chain reaction that schedules everything.

If there is a feasible timetable, we look at the C^{i}_{q3} and C^{i}_{q4} classes to see how we have allocated the teachers to those tasks, which tells us how to set the variables to make each clause true.

**Difficulty: **9. I’m having a hard time following all of the classes and teachers here. I wonder if there is a much easier way to do this if we reduce from some other problem.