\chapter{The Timetabling Problem}

\section{As a Generalized Assignment-Type Problem}

The notion of the assignment-type problem and its generalized version
appear to be powerful modeling tools. In particular, such models are
very appropriate for formulating timetabling and scheduling problems
where time periods have to be determined for activities according to
several specific constraints.

The Assignment-Type Problem (ATP) can be summarized as follows:

{\it Given $n$ items and $m$ resources, the problem is to determine an
  assignment of each item to a resource in order to optimize an
  objective function and to satisfy $K$ additional side constraints.}

The mathematical model associated with an ATP is formulated as
follows: 

{\bf (ATP)}

\be{gatp-1}
\text{Min}\;F(x)
\ee
{\it subject to}
\be{gatp-2}
G_k(x) \leq 0 \;\;\;\;\;\; 1\leq k\leq K
\ee
{\it and}
\be{gatp-3}
x \in X(1)
\ee

{\it where}

\be{gatp-4}
X(1) = \{ x : \sum_{j \in J_i} x_{ij} = 1, 1 \leq i \leq n; x{ij} = 0
\;\;\text{or}\;\; 1,\; 1 \leq i \leq b, j\in J_i \}
\ee

and $J_i \subset \{1, 2, \ldots, m\}$ is the set of admissible
resources for item $i$, $1\leq i \leq n$.

The decision variables $x_{ij}$ are such that:

\be{gatp-5}
x_{ij} =
\twoif {1} {\text{if item} i \text{assigned to resource} j}
       {0} {\text{otherwise.}}
\ee

The objective function $F$ and the side constraints $G_k$, $1 \leq k
\leq K$, are only required to be calculable.

A Generalized Assignment-Type Problem (GATP) is an ATP where each
item $i$ has to be assigned to $a_i$ resources, $a_i \geq 1$. The
mathematical model associated with a GATP is: 

{\bf (GATP)}

\be{gatp-6}
\text{Min}\;F(x)
\ee

{\it subject to}
\be{gatp-7}
G_k(x) \leq 0 \;\;\;\;\;1\leq k\leq K
\ee
{\it and}
\be{gatp-8}
x \in X(a)
\ee

{\it where}

\be{gatp-9}
X(a) = \{ x : \sum_{j \in J_i} x_{ij} = a_i, 1 \leq i \leq n; x{ij} = 0
\;\;\text{or}\;\; 1,\; 1 \leq i \leq n, j\in J_i \}
\ee

{\it and}

\be{gatp-10}
a = {[a_1, a_2, \ldots, a_n]}^T
\ee
and $a_1 \geq 1$ and integer $1 \leq i \leq n$. It is easy to see that
an ATP is a GATP where $a = {[1, 1, \ldots, 1]}^T$.

The constraints $x \in X(a)$ underly several timetabling and
scheduling problems. Furthermore, to take advantage of the simple
structure of the constraints $x \in X(a)$, a {\it penalty approach} is
used to deal with GATP. In this approach, let $V_k(x)$ denote the
violation of constraint $G_k(x) \leq 0$; i.e.

\be{gatp-11}
V_k(x) = \text{Max} \{0, G_k(x) \}.
\ee

Hence, for each $x\in X(a)$, let $V(x)$ denote the 
{\it total weighted violation}:

\be{gatp-12}
V(x) = \sum_{k=1}^K \beta_k V_k(x)
\ee

where $\beta_k \geq 0$ is proportional to the relative importance of
the {\it k}th constraint. Then, instead of solving GATP, the
solution techniques already introduced, are applied to the following
{\it penalized version} of GATP: 

{\bf (PGATP)}

\be{gatp-13}
{Min}_{x \in X(a)} P(x) = \alpha F(x) + V(x)
\ee

where $\alpha \geq 0$. The values of $\alpha$ and $\beta_k$, $1 \leq k
\leq K$, are parameters that can be adjusted according to the specific
application. For instance, larger values for $\beta_k$, $1 \leq k \leq
K$, allow putting more emphasis on feasibility.

\section{Timetabling}

\subsection{Introduction}

Timetabling is the assignment of time slots to a set of events, 
subject to constraints on these assignments. 
The NP-complete {\it professors and classes} timetabling 
problem is a constraint satisfaction problem that can
be briefly stated as follows:

For a certain school with $N_p$ professors, $N_q$ classes, $N_x$
classrooms and lecture halls, and $N_s$ students, it is required to 
schedule $N_l$ professor-class pairs within a time
limit of $N_t$ time slots producing a legal schedule. A legal schedule
needs to be found such that no professor, class, or student is in more
than one place at a time, and no room is expected to accommodate more
than one lesson at a time or more students than its capacity. 

The constraints for this problem can be hard, medium or soft. 
The medium and soft constraints have an associated cost (or penalty), 
and if they are not satisfied, the goal is to minimize this cost. 
Soft constraints have a lower priority (and thus lower cost) than medium 
constraints.
The hard constraints must be satisfied, so their associated cost must be 
reduced to zero. A feasible schedule is one that satisfies all the hard
constraints.

\subsection{Problem representation as GATP}

Consider the problem of establishing the schedule of lectures
accounting for individual student registrations, lecturers, and 
classroom availabilities. Note that this formulation allows for
lectures of different length. Hence, to formulate this problem as a
GATP, the lectures are the items and the starting times allowed are
the resources; then for each lecture $i$, $1 \leq i \leq n$, and
starting time $j \in J_i$ (the set of admissible starting times for
lecture $i$) such that $J_i = \{1,2,\ldots,m\}$:

\be{form-1}
x_{ij} =
\twoif {1} {\text{if lecture} i \text{starts at} j}
       {0} {\text{otherwise.}}
\ee

The objective function accounts for the lecturer preferences:

\be{form-2}
F(x) = \sum_{i=1}^{n} \sum_{j \in J_i} c_{ij} x_{ij}
\ee

where $c_{ij}$ is the cost of starting lecture $i$ at $j$ specified in
terms of lecturer preferences ($c_{ij} = 0$ if $j$ is the most
preferred starting time for lecture $i$).

A first set of side constraints is specified to eliminate the
conflicting situations where students or lecturers are involved in
lectures taking place simultaneously. Define:

$\Gamma_{ij} = \{(k,l)$: lectures $i$ and $k$ have students or
lecturers in common, and they overlap in time if lecture $i$ starts at
$j$ and lecture $k$ at $l$ $\}$.

The conflicting constraints are specified as follows:

\be{form-3}
x_{ij} x_{kl} \leq 0\;\;\;\;\;\;(k,l) \in \Gamma_{ij}\;,\; 1\leq i
\leq n\;,\; j\in J_i\;.
\ee

Other side constraints are introduced to account for classroom
availability. Partition the set of classrooms available into several
subsets including classrooms of the same type. Define:

$B =$ number of classroom types
$U_b =$ number of classrooms of type $b\;$,$\; 1 \leq b \leq B$.

For each lecture, a unique classroom type is specified. Define:

$K_{bt} = \{(i,j)$: lecture $i$ requires a classroom of type $b$ and
it takes place during teaching hour $t$ of the week whenever its
starting time is $j$ $\}$.

The classroom availability constraints are as follow:

\be{form-4}
\sum_{(i,j) \in K_{bt}} x_{ij} - U_b \leq 0 \;\;\;\;\;\; 1\leq
b \leq B\;,\; 1\leq t \leq T
\ee

where $T$ is the total number of teaching hours of the week.

The course timetabling problem can be summarized as follows:

\be{form-5}
Min \sum_{i=1}^n \sum_{j \in J_i} c_{ij} x_{ij}\;.
\ee

Subject to:

\be{form-6}
x_{ij} x_{kl} \leq 0 \;\;\;\;\;\; (k,l) \in \Gamma_{ij},\;\;\; 1\leq i
\leq n\;,\; j \in J_i
\ee

Next, we need to derive the associated penalized version of this
problem (i.e. the penalized GATP), with weights specified to indicate
the relative importance of violating the corresponding
constraints. For the conflicting constraints, the weights account for
the length of the conflict and the number of individuals
involved. Define:

\begin{itemize}
\item $L_{ijkl} =$ length (in number of hours) of the conflict $(k,l)
  \in \Gamma_{ij}\;$ , $1 \leq i \leq n\;$,$\; j \in J_i\;$. 

\item $\delta_{ik} =$ number of students taking both lectures $i$ and
  $k$, $1 \leq i \leq n\;$, $\;1 \leq k \leq n\;$.

\item $\gamma_{ik} = 
      \twoif {M + \delta_{ik}} {\text{if lectures} i \text{and} k
                                \text{have lecturers in common}}
             {\delta_{ik}} {\text{otherwise}}
$

For  $1 \leq i \leq n , 1 \leq k \leq n\;$.
\end{itemize}

where $M$ is a parameter to indicate the relative importance of
conflicts due to lecturers. Let $V_{kl}^{ij}(x)$ denote the violation
of the conflicting constraints:

\be{form-7}
V_{kl}^{ij}(x) = Max\{0, x_{ij} x_{kl}\} = x_{ij} x_{kl}\;\;.
\ee

Let $V_{bt}(x)$ denote the violation of the classroom availability
constraints:

\be{form-8}
V_{bt}(x) = Max\{0, \sum_{(i,j) \in K_{bt}} x_{ij} - U_b \}\;\;.
\ee

Furthermore, let the weight $\beta_{kl}^{ij}$ associated with
$V_{kl}^{ij}(x)$ be specified as follows:

\be{form-9}
\beta_{kl}^{ij} = \gamma_{ik} L_{ijkl}\;\;.
\ee

Also, let the weight $\beta_{bt}$ associated with $V_{bt}(x)$ be equal
to a scalar $\rho$ for all $1 \leq b \leq B\;$, $\; 1 \leq t \leq
T\;$. Then, the penalized GATP for this problem is as
follows:

\be{form-10}
{\displaystyle {Min}_{x \in X(1)} \sum_{i=1}^n \sum_{j \in J_i}
\left[ \alpha c_{ij} x_{ij} + \sum_{(k,l) \in \Gamma_{ij}} \gamma_{ik}
  L_{ijkl} x_{ij} x_{kl} \right] + \rho \sum_{b=1}^B \sum_{t=1}^T
Max\left\{ 0, \sum_{(i,j) \in K_{bt}} x_{ij} - U_b \right\}}\;\;. 
\ee

The weight parameters $\alpha$, $\rho$, and $M$ are selected according
to the specific context. For instance, if the priority is to reduce
the conflicts, then $\alpha$ and $\rho$ take smaller values.


\subsection{The Problem Constraints}

\noindent
{\bf Hard constraints} are usually constraints that physically cannot be
violated. This includes events that must not overlap in time, such as:
\begin{itemize}
\item classes taught by the same professor,
\item classes held in the same room,
\item a class and a recitation or a lab of the same class.
\end{itemize}
%
Another examples are space or room constraints:
\begin{itemize}
\item {\bf Room Type}: Some classes, such as laboratories, require a
certain type of room.
\item {\bf Room Size}: A class cannot be assigned to a
particular room unless the capacity of the room (denoted by $R_c$) 
is greater than or equal to the class enrollment (denoted by $C_e$). 
The smaller the difference between these two sizes, the better the
assignment.
\end{itemize}

There is a cost associated with any violation of these
constraints. For the {\bf Room Size} constraint our cost function
$C_{rs}$ computes the magnitude of the difference between the room
capacity $R_c$ and the class enrollment $C_e$ as follows:

\be{room-constraint}
C_{rs}=
\twoif{{(C_e - R_c)}^2} {\text{if} C_e > R_c\,,}
{\tanh((1.0 - {C_e \over R_c}) \beta \gamma) (R_c - C_e)}
{\text{otherwise.}}
\ee

In our experiments, the parameters $\beta$ and $\gamma$ were set to
0.4 and 0.8, respectively. When the class enrollment is larger than
the room size, this function will always yield a much higher cost
than the cost incurred from the assignment of a class with an
enrollment that is smaller than the room size. The use of $\tanh$
function is to non-linearize the cost and not to make its increase
directly proportional to the difference between room size and class
enrollment.

There is also a cost assigned to any violation to the constraint that
certain classes cannot be scheduled at the same time or have any
overlap in the scheduled times. This is called {\it exclusion cost}
$C_x$ and derived as follows:


\be{exclusion-constraint}
C_x =
\fourif{(end(c_i) - s(c_j)) Rlen(c_i,c_j)} {\text{if} (s(c_j) > s(c_i))\,
\text{and} \, (end(c_i) \geq s(c_j))\,,}
{(end(c_j) - s(c_i)) Rlen(c_i,c_j)} {\text{if} (s(c_j) < s(c_i))\,
\text{and} \, (end(c_j) \geq s(c_i))\,,}
{(end(c_j) - s(c_i)) Rlen(c_i,c_j)} {\text{if} (s(c_j) \geq s(c_i))\,
\text{and} \, (end(c_i) \geq end(c_j))\,,}
{(end(c_i) - s(c_j)) Rlen(c_i,c_j)} {\text{if} (s(c_i) \geq s(c_j))\,
\text{and} \, (end(c_j) \geq end(c_i))\,.}
\ee

where the relation between the two class durations is defined as
follows:

\be{relative-length}
Rlen(c_i,c_j)=
\twoif {len(c_i) / len(c_j)} {\text{if} len(c_i) \geq
len(c_j)\,,}
{len(c_j) / len(c_i)} {\text{otherwise.}}
\ee

The first and second choices of $C_x$ take care of any partial
overlaps between $c_i$ and $c_j$, while the third and fourth
choices take care of any complete overlaps between the two classes. 

%%-----------------
%% Add additional hard constraints of relevance to students ...
%%-----------------

\noindent
{\bf Medium constraints} are usually considered to be those
constraints that fall into the gray area between the hard and soft
constraints~\cite{49} (ref: Eiselt-Laporte-87).  
In our implementation, we define medium constraints to be constraints
such as time and space conflicts which, like hard constraints, cannot
physically be violated (for example, it is not possible for one person
to be in two different classes at the same time). However we consider
these constraints to be medium rather than hard if they can be avoided
by making adjustments to the specification of the problem. The primary
example is student preferences. We cannot expect to be able to satisfy
all student class preferences, in some cases, certain students will
have to adjust their preferences since certain classes will clash, or
will be oversubscribed.

Medium constraints have a high penalty attached to them, although not
as high as that associated with the hard constraints. In the final 
schedule the penalty of these constraints should be minimized and 
preferably reduced to zero. Some examples of medium constraints are:
\begin{itemize}
\item Avoid time conflicts for classes with students in common.
\item Eligibility criteria for the class must be met.  
\item Do not enroll athletes in classes that conflict with their sport
      practice time (of course, depending on the sport).
\item The predecessor-successor relation between the topics is
  satisfied.
\item Two courses of a same topic are scheduled on two different
  working days.
\end{itemize}

\noindent
{\bf Soft constraints} are preferences that do not deal with time
conflicts, and have a lower penalty (or cost) associated with them. We
aim to minimize the cost, but do not expect to be able to reduce it to
zero. Some examples are:
\begin{itemize}
\item For each student, balance the three-day ({\it Mon, Wed, Fri}) 
      as well as the two-day ({\it Tue, Thu}) schedules.
\item Balance or spread out the lectures over the week.
\item Classes may request contiguous time slots.
\item Balance enrollment in multi-section classes.
\item Lunch and other break times may be specified.
\item Professors may request periods in which their classes are not
  taught.
\item Professors may have preferences for specific rooms or types of
  rooms.
\item Once a class enrollment exceeds the upper limit, the class is
split into multi-sections.
\item Minimize the distance between the room where the class is
  assigned and the building housing its home department. 
\end{itemize}

Some soft constraints may have higher priority (and thus higher cost)
than others. For example, preferences involving professors will have
higher priority than the preferences of students.

We have dealt with the distance minimization constraint in the
following way. Given the various building preferences of the
departments, we have constructed a matrix $M_{IJ}$ between all the
academic departments $I$ and all the buildings involved in scheduling 
$J$. Using $M_{IJ}$ in conjunction with the (appropriately scaled)
distance between all buildings involved in the process,  a final
distance matrix $Q$ is derived and directly used in the scheduling
process. Also, unless otherwise stated, a department's home building
is always the first preference for the department classes to be
assigned.

Let $B$ denote the set of all $k$ buildings, $D$ denote the set of all
$n$ departments. Also for department $d_i$ where $1\leq i \leq n$ the
distance to all buildings $B$ is a vector denoted by $<d_i,b_j>$ where
$b_j \in B$ and $1\leq j \leq k$.  At each step of the scheduling
process and according to $d_i$ space preferences, $d_i$ courses would
be scheduled into buildings $B^{'}$ where $|B^{'}| \leq |B|$ and the
distance is denoted by the vector $\ll d_i, b_j \gg$ where $b_j \in
B^{'}$. In addition, let $|B^{'}| = k^{'}$.

Now the cost associated with the distance of department $d_i$ is
computed as follows:

\be{dist-cost}
C_{d_i}^{dist} = {{\sum_{j=1}^{k^{'}} \ll d_i, b_j \gg} \over  
{\sum_{j=1}^k <d_i, b_j>}}\;\; k^{'}
\ee

The cost function is the {\it distance ratio} of department(i)'s
buildings of preference to all available buildings multiplied by the
number of  department(i)'s preferred buildings. Notice that for a
particular department the denominator of equation \ref{dist-cost}
stays fixed the scheduling process.

Other constraints that may need to be taken into account during the
scheduling process:
\begin{itemize}
\item It is not the case, in general, that all classrooms are
  available for all subjects. In reality, many subjects require
  special purpose rooms. 
\item Some rooms may be declared unavailable during any time period.
\item Daily limits must be specified to restrict the assignment of
more than a specified number of classes per day to each professor.
\end{itemize}

$\ldots$
$\ldots$

\subsection{Cost Function}

The {\bf cost function} measures the quality of the current schedule
and generally involves the weighted sum of penalties associated with 
different types of constraint violations. The aim of the optimization
technique is to minimize the cost function. We consider the following
as part of the cost function:

\begin{itemize}
\item {\it Class cost} is the sum of costs incurred from scheduling a 
class in a particular time period, including  having a certain class
and its lab scheduled in the same time period; spreading classes over
the week and within each of the weekdays; and gluing to fill in holes
in the timetable and allow contiguous time periods for a class that
requests them.

\item {\it Professor cost} is the sum of costs associated with each
professor, including teaching two or more classes that overlap in
time; being assigned more classes than the maximum number allowed to
be taught; and not having a long enough time interval between classes
taught by the same professor.

\item {\it Student cost} is the sum of costs associated with each
student, including clashes in class times; not having the classes
evenly spread out over the week; having to schedule a class from the
list of alternates rather than the list of first preferences; or
classes that do not satisfy eligibility criteria.

\item {\it Room cost} is the sum of costs associated with each classroom, 
including the distance cost obtained from the distance constraint;
not being able to schedule a room of the specified type; and the room
size cost obtained from the room constraint.
\end{itemize}


