Tag Archives: Timetable Design

Timetable Design

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:  Rij 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 Ti and Cj  (we only schedule teachers and classes when they’re available)
  • The sum of f(i,j,h) over all h = Rij  (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:

  • T1 is available at {1,2,3}
  • T2 is available at {3,4,5}
  • T3 is available at {1,3,5}

..and 3 classes:

  • C1 is available at {2,4}
  • C2 is available at {1,5}
  • C3 is available at {2,3}

If R was:

1 1 0
1 0 1
0 1 1

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

  • T1 can only teach C1 at time 2, and C2 at time 1
  • T2 can only teach C1 at time 4, and C3 can be either time 3 or 5.  Let’s pick 5.
  • T3 can teach C2 at times 1 or 5, but time 1 is taken by T1, so we schedule it at time 5.  Similarly, C3 is available at times 2 and 3, and T3 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 (x1 through xl, and the negation ~x1 through ~xl), and a set D of k clauses (D1 through Dk).  Define pi to be the number of times variable i (so the literal xi or the literal ~xi)  shows up in the formula.  Each variable i will get 5*pi classes denoted Ciab, where a runs from 1 to pi, 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, C12 and C13 for example) and the crosses are the 2 ways they can teach it (so h2 and h3).  The bottom arrows are teachers who can have 3 hours of availability and 3 classes to teach.  Each variable gets pi teachers who teach Cq3 and Cq4 (where q runs from 1 to pi) during h1 and h2.  If Cq3 is taught at time h1, 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 xi, the teacher is assigned to class Ciq2 if the literal is true, and Ciq5 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 h1 and h2, and that starts a chain reaction that schedules everything.

If there is a feasible timetable, we look at the Ciq3 and Ciq4 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.