\chapter{Complexity of Course Scheduling}\label{ch:complex}

\section{Notes on Complexity of the Problem}

Course scheduling belongs to the class of non-Euclidean constraint
satisfaction problems and it is essentially an example of a
resource-constrained scheduling problem, which is an NP-hard
\cite{CT:hard, GJ:candi}. Here, resources are physical entities, such
as students, rooms, overhead projectors, etc. Also time periods can be
thought of as resources.

Assume we are given a set $S$ of time slots, and graph $G(V,E)$ 
of $V$ set of vertices and $E$ set of edges. 

The course scheduling problem is NP-complete.
This can be shown by a reduction from graph coloring, since any 
non-trivial instance ($G(V,E)$, $S$) of the coloring problem can be 
mapped into an instance of the course scheduling problem with $|V|$ 
vertices, a list of $|E|$ student schedules (each schedule selects the 
two courses corresponding to an edge of the graph $G$). Setting the 
section bound $B$ = $|V|$, we can create a timetable of size $S$ with 
no conflicts if and only if we can color $G$ with $S$ colors.

Also, the timetabling problem with teachers constraints was shown to be 
NP-complete in 1976 \cite{EIS:complex}, which means there exists no known 
polynomially bound algorithm for solving them optimally. As a result, 
these problems are often solved by means of {\it heuristics} -- 
solution procedures that focus on finding a feasible schedule of 
``good'' (as opposed to optimal) quality within an acceptable amount of 
time. In addition to being NP-complete, timetabling problems are also
characterized by their {\it sparseness} (see
definition~\ref{sparse-df} and observation~\ref{sparse-ob}).

\bd{sparse-df}$\;\;$ Let $N_p$ denotes professors (or teaching
staff), $N_q$ denotes classes, $N_x$ denotes rooms (including classrooms,
auditoriums, seminar rooms, etc.), $N_s$ denotes students, $N_l$ denotes
the pairing between a professor and class (professor-class pairs), and 
$N_t$ denotes the time slots.

Then after the required number of classes $N_l$ have been
scheduled, there will be $N_{sp} = (N_x N_t - N_l)$ spare space-time
slots, hence, the sparseness ratio of the problem is defined as the
ratio $N_{sp} / (N_x N_t)$.
\ed

\bo{sparse-ob}$\;\;$ The denser the timetabling problem, the lower
the sparseness ratio, and the harder the problem is to solve. Also,
for dense problems, there is an additional correlation involving the
problem size.
\eo

Traditionally, timetabling has been approached by means of linear
programming (LP)~\cite{Sh:linear} with binary variables plus some
heuristics. For example, if $i$ identifies a teacher, $j$ identifies a
time interval and $k$ identifies a class then the binary variable
$X_{ijk}$ $=$ $1$ if teacher $i$ has class $k$ at time-interval $j$;
$X_{ijk}$ $=$ $0$ , otherwise. Suppose we have a set of data as small
as 20 teachers, 30 time intervals, and 10 classes. If we use the LP
approach to obtain a feasible schedule out of this data, then we need
to deal with over 6000 variables to represent the problem, and  
$2^{6000}$ possible states. The problem quickly becomes intractable as
the number of variables increases. The overall complexity of
timetabling is in the order of $2^{{(N_c N_x N_t)}^a}$, for $a \geq
1$. For problems with a linear objective, the LP-relaxation solution
is potentially of some use. However, for pure-constraint satisfaction
problems, with arbitrary and large number of objectives, the LP
approach is not very promising.

For the much simpler problem of {\it class allocation}, for which there
is no timetabling involved (i.e. no allocation of classes to time 
periods), the computational load ($n_c$) from tackling this problem
using the LP method scales as follows \cite{GSP:complex,
GT:allocation}: 
\be{complexity}
n_c \propto N_c^3 N_x^2 N_t^3\;\;,
\ee

where $N_c$ is the number of room categories available
(i.e. classroom, auditorium, etc.).

In regard to the graph coloring approach,
Morgenstern~\cite{Morg:coloring} has given a $\Theta(m)$
implementation of {\it DSatur}, where $m$ is the number of the edges
in the graph. Also, the most efficient implementation of the RLF
algorithm runs at $O(km)$, where $k$ is the number of colors needed by 
the algorithm to properly color the graph and $m$ is the number of
edges in the graph.

\section{Complexity of Section Assignment Problem}

This is a decision problem and can be stated as follows: Given $N$
student schedules, section bound $B$, can the students be assigned to
sections of their desired courses so that no section has more than $B$
students and, from a graph point of view, the number of edges in the
section conflict graph is no more than $J > 0$ ?  

This problem is commonly referred to as the minimal density section
assignment problem. It is an NP-complete by reduction from the Graph
Bisection problem on fixed degree d-regular graphs (GB). This latter
problem was shown to be NP-complete by Bui et al. ~\cite{BCLS:graph}. 

The overall decision problem of course
scheduling with section assignment is also NP-complete for
metrics of edge conflicts, student conflicts, and course conflicts. It 
is stated as follows: Given $N$ student schedules, a timetable for
sections of the courses, a bound $B$ on the number of students per
section, and a goal $J > 0$, can the students be assigned to sections
of their desired courses in such a way that the number of conflicts,
as measured by some metric, is no more than $J$ ?

Again, this problem is clearly in NP since given an assignment, we can 
count the number of conflicts and compare against $J$. The proof is by 
reduction from the 3-dimensional matching (3DM) problem. (See Garey
and Johnson~\cite{GJ:candi} for a proof that 3DM is NP-complete.)

\section{Constraint Satisfaction}

A constraint satisfaction problem (CSP) is a way of expressing
simultaneous requirements for values of variables. In other words, CSP
consists of a set of $n$ variables, a domain of values for each
variable, and a set of constraints each of which restricts the
allowable assignments of values to some of the variables. 

The study of constraint satisfaction problems was initiated by
Montanari in 1974 \cite{M:network}, when he used them as a way of
describing certain combinatorial problems arising in
image-processing. It was quickly realized that the same general
framework was applicable to a much wider class of problems, and the
general problem has since been intensively studied, both theoretically
and experimentally (for example, see~\cite{M:network, LM:binary,
M:consistency}). One of the most practical examples is the problem of
{\it academic course scheduling}, studied in this thesis, which is
scheduling a collection of tasks or activities with respect to a
specified set of constraints. (A good introduction to the general
problem of scheduling as a constraint satisfaction problem can be
found in~\cite{vBeek:reasoning}.) 

\subsection{Basic definitions}

First, we will only be considering constraint satisfaction problems in 
which there are a finite number of variables, and each variable has a
finite number of possible values.

\bd{CSP-def-1}$\;$
A constraint satisfaction problem, $P$, is specified by a tuple, 
$P = (V, D, R_1(S_1),\ldots,R_n(S_n))$, where
\begin{itemize}
\item $V$ is a finite set of variables;
\item $D$ is a finite set of values (this set is called the domain of
$P$);
\item Each pair $R_i(S_i)$ is a constraint. In each constraint
$R_i(S_i)$
\begin{itemize}
\item $S_i$ is an ordered list of $k_i$ variables, called the scope of 
the constraint; 
\item $R_i$ is a relation\footnote{A relation is simply a set of
tuples of some fixed length. The length of the tuples is called the
arity of the relation.} over $D$ of arity $k_i$, called the relation
of the constraint. 
\end{itemize}
\end{itemize}
\ed

\bd{CSP-def-2}$\;$
A solution to $P = (V, D, R_1(S_1),\ldots,R_n(S_n))$ is an assignment
of values from $D$ to each of the variables in $V$, which satisfies
all of the constraints simultaneously.

Formally, a solution is a map $h : V \rightarrow D$ such that 
$h(S_i) \in R_i$, for all $i$, where the expression $h(S_i)$ denotes
the result of applying $h$ to the tuple $S_i$, coordinate-wise (in
other words, if $S_i = < v_1, v_2, \ldots, v_k >$, then 
$h(S_i) = < h(v_1), h(v_2), \ldots , h(v_k) >$).
\ed

We will occasionally make use of the notion of a {\it partial
solution} in this thesis. This may be defined in a number of different
ways, depending on the stringency of the requirements we wish to
impose. To be consistent with the majority of the literature, we use
the following definition.

\bd{CSP-3}$\;$
A partial solution to a constraint satisfaction problem 
$P = (V, D, R_1(S_1),\ldots, R_n(S_n))$ is a mapping $h$ from some
subset, say $W$, of $V$ to $D$, such that for each $S_i$ contained in
$W$, $h(S_i) \in R_i$.
\ed

\br{CSP-remark}$\;$
\begin{itemize}
\item In the context of course scheduling, a tuple is a combination of a
class, teacher, and a classroom. The time periods are assumed to be
given.
\item Unary constraints specify the allowed values for a single
variable, and binary constraints specify the allowed combinations of
values for a pair of variables. 
\item Deciding whether or not a given instance of constraint
satisfaction problem has a solution is NP-complete in general
\cite{M:consistency}, even when the  constraints are restricted to
binary constraints. 
\end{itemize}
\er


