\section{The Nature of the Problem}
A combinatorial optimization problem tackled by methods such as
simulated annealing, mean field annealing, genetic algorithms, and
expert systems among others.

\section{The Timetabling Problem}
One of the problems that has no single objective to minimize, but is
rather a purely constraint satisfaction problem (CSP) is the
$NP$-complete ``teachers and classes'' timetabling problem.
Briefly, the problem is defined as follows:

For a certain school having $N_p$ teachers, $N_q$ classes, $N_x$
classrooms or lecture halls, and $N_s$ students; it is required to
schedule $N_l$ lessons (defined as teacher-class pairs) within a time
limit of $N_t$ lesson periods (or time slots). 

A schedule needs to be found satisfying a set of constraints, some are
${\bf hard}$, some are ${\bf medium}$, and some are ${\bf soft}$.
A schedule that does not violate any of the ${\bf hard}$
constraints is a legal schedule, and it is the kind of schedule that
need to be produced.

\section{Constraints of Timetabling}

In a nutshell, timetabling is the assignment of time slots to a set of
events, ${\bf subject to}$ constraints on these assignments. 
These constraints are divided into three types: hard, medium, and
soft.

\subsection{Hard Constraints}

All need to be satisfied, that is, their associated cost to be driven
to zero.  Here is a sample of few [can go up to 10 or 15 constraints]:
\begin{itemize}
\item Two or more classes taught by the same professor can not be
scheduled at the same time.
\item A class and its recitation or/and lab can not be scheduled at
the same time.
\item A class can not be assigned to a particular room unless
size(room) $\ge$ enrollment(class).
\end{itemize}

\subsection{Medium Constraints}

These kinds of constraints do not deal with time conflicts but
do have a high cost attached to them. Also, this cost is not as
high as that associated with the hard constraints. In the final
(legal) schedule the cost of these constraints is minimized and it is
quite preferable to reduce it to $0$.  Here is a sample of few [can go
up to 20 or 25 constraints]:
\begin{itemize}
\item For each student, balance {\it MWF} and {\it TuTh} sections.
\item Balance or spread out the lectures over the week.
\item Classes may request contiguous time slots.
\item Classes may be grouped with other classes.
\item The overall schedule should have as few ``holes'' as possible;
that is lessons should be glued together, etc.
\end{itemize}

\subsection{Soft Constraints}

These do not deal with time conflicts and have a low cost associated 
with them. Also, in the final schedule, this cost is minimized
but does not often approach zero. Here is a sample of few [can go up
to 30 or 40 constraints]:
\begin{itemize}
\item Balance enrollment in multi-section courses.
\item Lunch and other break times may be specified.
\item Teachers may request periods in which their classes are not taught.
\item Do not enroll athletes in courses that conflict with their sport
practice time, etc.
\end{itemize}

\section{Some Methods for Tackling Timetabling}

Academic scheduling or timetabling has been tackled by many
researchers, mostly in the field of operations research. 
Lately, there have been a number of ``non-conventional'' (or novel)
methods utilized to tackle this problem from different angles. Chief 
among them are neural networks, simulated annealing, genetic
algorithms, tabu search, and various combinations of two or more of these 
techniques. Among these techniques we have used the following two:

\subsection{Neural Networks}
From the various categories of artificial neural systems (ANS),
the most suitable for the problem at hand is the family
of feed-back ANS based on multi-state neurons with mean field theory
(MFT) equations controlling the dynamics. This system is usually known
as mean field annealing (MFA). The MFT equations are used in place of
the CPU demanding stochastic updating procedures often used to avoid
getting stuck in local minima.

\subsection{Simulated Annealing (SA)}
This approach depends heavily on the annealing schedule. The most
widely used one is the geometric cooling schedule. Others, such as
geometric re-heating as a function of cost can also be used.

\subsection{Rule-based System (ES)} 
This system is used with a number of heuristics and conventional
recursion to assist in carrying out course assignments. 
Those heuristics are implemented to take care of various cases that
arise when carrying out the scheduling. 

\section{The Nature of the Following two Problem}
A combinatorial optimization problem tackled by methods such as
simulated annealing, mean field annealing, genetic algorithms, and
expert systems among others.

\subsection{Graph Matching (GM)}
The graph matching problem is to find out if two graph have the same
topology (the way its nodes are linked together), that is, if the two
graphs are in fact the same. For simple graphs, this is not difficult
to determine but for more complicated graphs, this becomes quite
difficult. It is not known whether this problem is in the NP-complete
class or not, but, except for some special cases, no polynomial
algorithm is known.

A quite useful class of matching problems are those described by
specifying $n$ points in the plane to match so as to minimize the
distance between the pairs. In term of graphs, this basically means we
have the complete graph on $n$ nodes with the weight of each edge
being the distance between its end points (under some metric).

\subsection{Graph Coloring (GC)}
Briefly, given a graph $G=(V,E)$ we have to find a coloring of its
vertices with as few colors as possible. The main constraint is that
two vertices linked by an edge should not receive the same color (such
coloring are called feasible coloring). One could define the set $S$
of feasible solutions as the set of feasible coloring which do not use
more than a given number of colors; for example, this upper bound may
be the number of colors used in the initial solution. For more
information, take a look at Mike Trick's
http://mat.gsia.cmu.edu/resource.html.

\subsection{A Mapping Sketch of Timetabling onto Graph Coloring}

\begin{enumerate}
\item The courses are the vertices of a graph.
\item The time periods correspond to the colors.
\item Two vertices are linked by an edge if the corresponding courses
cannot be given at the same time.
\item Additional constraints have to be taken into account and mapped
onto the graph.
\end{enumerate}

\section{What need to be done}
\subsection{Tasks}
\begin{enumerate}
\item Carry out timetabling using SA. 
\item Carry out timetabling using MFA.
\item Tackle GC or GM using SA with different cooling schedules.
\item Tackle GC or GM using MFA and investigate parallelism and scaling.
\end{enumerate}

\subsection{Furtherwork}
\begin{itemize}
\item Experiment with different cooling schedules for task [1] and
compare the results.
\item Use more constraints for tasks [1] and [2].
\item Investigate the issues of parallelism and scaling for task [2]. 
\item Tackle timetabling or (and) either GC or GM  using ES and
  compare results with those obtained from SA or MFA.

\end{itemize}

\section{Requirements}
The student ought to be quite knowledgeable (and have already done a
at least one medium to large size project) in using a programming
language, such as C (the preference here is C but Fortran is ok). Any
mathematical knowledge (calculus and beyond) and perhaps knowing some
awk or perl is a plus.

\end{document}

