%% LATEX TWICE TO GET THE REFERENCES RIGHT
%%\documentstyle[12pt]{article}
\documentstyle[11pt,epsf,psfig]{article}

\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}
\newtheorem{itlemma}{Lemma}[section] %number by section (set in \em by default)
%%%same numbering counter as itlemmas:
\newtheorem{itproposition}[itlemma]{Proposition}
\newtheorem{itcorollary}[itlemma]{Corollary}
\newtheorem{itremark}[itlemma]{Remark}
\newtheorem{itnote}[itlemma]{Note}
\newtheorem{itobservation}[itlemma]{Observation}
\newtheorem{itdefinition}[itlemma]{Definition}
\newtheorem{itexercise}[itlemma]{Exercise}
\newtheorem{itexample}[itlemma]{Example}

\newenvironment{lemma}{\begin{itlemma}\rm}{\end{itlemma}} %no-italics
\newenvironment{remark}{\begin{itremark}\rm}{\end{itremark}} %no-italics
\newenvironment{observation}{\begin{itobservation}\rm}{\end{itobservation}} %no-italics
\newenvironment{corollary}{\begin{itcorollary}\rm}{\end{itcorollary}}
\newenvironment{proposition}{\begin{itproposition}\rm}{\end{itproposition}}
\newenvironment{definition}{\begin{itdefinition}\rm}{\end{itdefinition}}
\newenvironment{exercise}{\begin{itexercise}\rm}{\end{itexercise}}
\newenvironment{example}{\begin{itexample}\rm}{\end{itexample}}

\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% These are for choices.  They take 4 or 6 args
%% (carriage returns allowed in between}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\twoif}[4]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\end{array}\right.
}
\newcommand{\threeif}[6]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\\#5&#6\end{array}\right.
}
\newcommand{\fourif}[8]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\\#5&#6\\#7&#8\end{array}\right.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\partmlab#1#2#3#4#5#6#7#8{\bordermatrix{&#1&#2\cr#3&#5&#6\cr
                                        \noalign{\medskip}#4&#7&#8\cr}}
%% For 2by2 partitioned matrices; arguments are: two labels of top, side,
%% 4 entries (row by row).  If entries are themselves matrix or pmatrix,
%% better for readability of source to define first: \def\matrix1{...} etc.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bigframebox}[1]{\framebox{\parbox{\smallerwidth}{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Warning: use \noindent before!
% AND IN TEXT, after begin doc, do:
% \newlength{\smallerwidth}  %for bigboxes
% \setlength{\smallerwidth}{\textwidth}
% \addtolength{\smallerwidth}{-8pt}        %MUST BE DONE AFTER begin doc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def \beq {\begin{eqnarray}}
\def \eeq {\end{eqnarray}}
\def \beqn {\begin{eqnarray*}}
\def \eeqn {\end{eqnarray*}}

\newcommand{\rf}[1]{[\ref{#1}]}            %bibliographical references

\newcommand{\text}[1]{\hbox{\rm \ #1\ \/}}
\newcommand{\be}[1]{\begin{equation}\label{#1}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bl}[1]{\begin{lemma}\label{#1}}
\newcommand{\ble}[1]{\begin{lemmaex}\label{#1}}
\newcommand{\br}[1]{\begin{remark}\label{#1}}
\newcommand{\bn}[1]{\begin{note}\label{#1}}
\newcommand{\bo}[1]{\begin{observation}\label{#1}}
\newcommand{\bt}[1]{\begin{theorem}\label{#1}}
\newcommand{\bd}[1]{\begin{definition}\label{#1}}
\newcommand{\bp}[1]{\begin{proposition}\label{#1}}
\newcommand{\bc}[1]{\begin{corollary}\label{#1}}
\newcommand{\bfact}[1]{\begin{fact}\label{#1}}
\newcommand{\ber}[1]{\begin{exercise}\label{#1}}
\newcommand{\bex}[1]{\begin{example}\label{#1}}
\newcommand{\bem}[1]{\begin{example}\label{#1}}    %Yes, 2 different ones :-)
\newcommand{\ec}{\mybox\end{corollary}}
\newcommand{\efact}{\mybox\end{fact}}
\newcommand{\eer}{\mybox\end{exercise}}
\newcommand{\eex}{\mybox\end{example}}
\newcommand{\eem}{\mybox\end{example}}
\newcommand{\el}{\mybox\end{lemma}}
\newcommand{\ele}{\mybox\end{lemmaex}}
\newcommand{\er}{\mybox\end{remark}}
\newcommand{\en}{\mybox\end{note}}
\newcommand{\eo}{\mybox\end{observation}}
\newcommand{\et}{\qed\end{theorem}}
\newcommand{\ed}{\mybox\end{definition}}
\newcommand{\ep}{\mybox\end{proposition}}
\newcommand{\epr}{\end{proof}}
\newcommand{\bpr}{\begin{proof}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  These are just for statements, no "qed" box is put in.
%%  (Also for when I have to finish something after a displayed equation
%%        or itemized.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ecs}{\end{corollary}}
\newcommand{\eers}{\end{exercise}}
\newcommand{\eexs}{\end{example}}
\newcommand{\eems}{\end{example}}
\newcommand{\els}{\end{lemma}}
\newcommand{\eles}{\end{lemmaex}}
\newcommand{\ers}{\end{remark}}
\newcommand{\ens}{\end{note}}
\newcommand{\eos}{\end{observation}}
\newcommand{\ets}{\end{theorem}}
\newcommand{\eds}{\end{definition}}
\newcommand{\eps}{\end{proposition}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\qed}{\hfill \halmos} %put \qed at right margin
\newcommand{\mybox}{\hfill $\Box$} %put \qed at right margin (white square)

%%%\newcommand{\pmat}[2]{\left( \begin{array}{#1} #2 \end{array} \right) }
%%%use as e.g. \pmat{cc}{ a&b\\ a &c }  Note 'cc' for 2 Centered cols
%%%can also use \pmatrix{ a&b\cr a &c \cr} for plainTeX standard construct
%%%\setcounter{page}{27} should set the CURRENT page to 27

\def \R {\bb R} % reals
\def \C {\bb C} % complexes
\def \Z {\bb Z} % integers
\def \X {\bb X} % for this paper only!
\def \inter {{\rm int \,}}
\def \rank {{\rm rank \,}}
%%%\def \inf {{\rm inf \,}}  %better in Latex -- subscripts OK!
%%%\def \min {{\rm min \,}}
\def \im {{\rm im \,}}
\def \ker {{\rm ker \,}}
\def \norm #1{\Vert #1 \Vert}
\def \ip #1\by #2{\langle #1 , #2 \rangle}
\def \Sone {{\bf S}^1} % circle
\def \wigglearrow {\sim \mkern -6mu >}

\def \today {\ifcase \month \or January\or February\or  
  March\or April\or May\or June\or July\or August\or 
  September\or October\or November\or December\fi\   
  \number \day, \number \year}                       
\newcommand{\comment}[1]{}
\newcommand{\halmos}{\rule{1ex}{1.4ex}}
%%%alternative to \qed (see below)
\newenvironment{proof}{\noindent {\em Proof}.\ }{\hspace*{\fill}$\halmos$\medskip}

%%%\def\qed{\kern 1em \vrule height .5em width .5em depth 0em}
%%%(I now use new qed: in right margin)

\def\vbar{\mathchoice{\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height4.1ptdepth-.35ptwidth.6pt\kern-.6pt}
   {\vrule height3.1ptdepth-.25ptwidth.5pt\kern-.5pt}}
\def\fudge{\mathchoice{}{}{\mkern.5mu}{\mkern.8mu}}
\def\bbc#1#2{{\rm \mkern#2mu\vbar\mkern-#2mu#1}}
\def\bbb#1{{\rm I\mkern-3.5mu #1}}
\def\bba#1#2{{\rm #1\mkern-#2mu\fudge #1}}
\def\bb#1{{\count4=`#1 \advance\count4by-64 \ifcase\count4\or\bba A{11.5}\or
   \bbb B\or\bbc C{5}\or\bbb D\or\bbb E\or\bbb F \or\bbc G{5}\or\bbb H\or
   \bbb I\or\bbc J{3}\or\bbb K\or\bbb L \or\bbb M\or\bbb N\or\bbc O{5} \or
   \bbb P\or\bbc Q{5}\or\bbb R\or\bbc S{4.2}\or\bba T{10.5}\or\bbc U{5}\or
%%%   \bbb P\or\bbc Q{5}\or\bbb R\or\bba S{8}\or\bba T{10.5}\or\bbc U{5}\or
   \bba V{12}\or\bba W{16.5}\or\bba X{11}\or\bba Y{11.7}\or\bba Z{7.5}\fi}}
%
%
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%%% read as: theFOOTNOTE (i.e. the command  executed when doing a footnote) is
%%% now to be set as a FOOTNOTESYMBOL (type of number) value of counter
%%% FOOTNOTE (Instead of Roman).  See LaTeX manual pp.91-92 as well as 175.
\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}
\def\ben{\begin{enumerate}}
\def\een{\end{enumerate}}
\def\st{\, | \,}

\newcommand{\myboxineq}{\eqno\Box} %put \qed at margin (white square) in eqn
\newcommand{\qedineq}{\eqno\halmos} %put \qed at margin in eqn

\topmargin -0.5in %default is 0.0, i.e. 1 inch from top.  Now it is 0.5
\textheight 9in
\oddsidemargin 0.25in %more reasonable margins!  (This is 1.25; can use <0 too)
\evensidemargin 0.25in %(same as above)
\textwidth 6.25in %(could use also -.5,-.5,7.5 for instance)
\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%% FROM HERE, macros special for paper
\def\mm{m}
\def\pp{p}
\def\proj{\pi _1} % projection on first group of coordinates
\def\x{u}  % vector argument
\def\SEC{(SEC)}
\def\SECo{(SEC$^0$)}
\def\INV{(INV)}
\def\Fp{{\cal F}_\pp}
\def\Fpm{{\cal F}_\pp^\mm}  %there is a 3,3 and a 2,1 in text

\def\Rm{\R^m}
\def\Rn{\R^n}
\newcommand{\ball}[2]{{\bb B}(#1,#2)}
\newcommand{\cball}[2]{\overline {\bb B} (#1,#2)}
\def\Fnm{{\cal F}_n^\mm}
\def\clos{{\rm clos\,}}
\def\inter{{\rm int\,}}

\def\CCF{compatible class of functions}
\begin{document}

\bibliographystyle{alpha}
\newpage
\begin{flushright}
{\sl NPAC technical report SCCS-777}  % Remove for submission to journal
\end{flushright}
\vspace{.75cm}
\begin{center} 

{\LARGE\bf 
Academic Scheduling using Simulated Annealing
\vspace{0.2cm}
with a Rule-Based Preprocessor
}
\vspace{1cm}

{\large
Saleh Elmohamed, Paul D. Coddington and Geoffrey C. Fox\\}
\vspace{.5cm}
Northeast Parallel Architectures Center\\
Syracuse University, Syracuse, NY 13244\\
\vspace{.25cm}
\{saleh, paulc, gcf\}@npac.syr.edu\\
\end{center}

\vspace{1cm}
\centerline{February 5, 1997}

\vspace{1.5cm}
\centerline{ABSTRACT}

In this study we tackle the NP-hard problem of academic
class scheduling, or timetabling, at the university level. 
We have used simulated annealing, 
with three different cooling schedules being implemented and compared. 
A rule-based expert system is used as a preprocessor to provide a good 
starting point for the annealing, which greatly improves the results. 
This approach enables us to obtain valid schedules for the timetabling 
problem for a large university using a complex cost function that 
includes student preferences. 

\vfill
\noindent{\bf Keywords : scheduling, timetabling, optimization, 
simulated annealing, reheating, annealing schedule, expert system.}

\newpage
\pagestyle{empty}

% Remove these???
%% \tableofcontents
\newpage
%% \listoffigures
%% \listoftables

\newpage
\pagestyle{plain}
\pagestyle{myheadings}
%% \markright{\sl SCCS report }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{page}{1}

The primary objective of this study is to derive an approximate solution
to the problem of university class scheduling, or timetabling,  
which can be summarized as follows:   
given data sets of classes and their days, enrollments, and
instructors; rooms and their capacities, types, and locations;
distances between buildings; priorities of each building for different
departments; and students and their class preferences; 
the problem is to construct a feasible class schedule satisfying all
the hard constraints and minimizing the  medium and soft constraints.
Hard constraints are space and time constraints that must be
satisfied, such as scheduling only one class at a time for any 
teacher, student, or classroom. 
Medium and soft constraints are student and teacher preferences that 
should be satisfied if possible.

The timetabling problem (TTP) is a high-dimensional, 
non-Euclidean, multi-constraint combinatorial optimization problem, 
and is consequently very difficult to solve.
This problem has been tackled by many researchers, 
mostly in the field of operations research.
A number of different heuristics have been tried on different 
instances of the problem, from high school to university course scheduling 
(see the reviews by de Werra \cite{21} and Shaerf \cite{50}).
For small to medium size problems, some of these methods work well,
however no particular method has yet been shown to produce good results for 
large-scale, real-world problems. 
Very few of these studies have used real-world data, and 
none of these methods has been used on as large and complex a problem 
as we have addressed in this work, 
which also takes into account constraints due to student preferences.

We have used data for classes at Syracuse University. 
Currently this problem is handled by the university
scheduling department in a semi-automated fashion. A scheduling program 
is used to find a partial solution, and substantial manual effort is 
required to iterate towards a final solution. Also, when scheduling a
certain semester (e.g. fall 1996), a template of a previous semester
(e.g. fall 1995) is used as part of the input data.

We tackle this problem using a multi-phase approach. First, a
rule-based expert system is used as a preprocessor to derive a partial
solution. This is used as the starting point in the second phase, which uses
a simulated annealing algorithm, for which we have tested three different
cooling schedules: standard geometric cooling, adaptive cooling, and
reheating as a function of cost. Using a preprocessor in conjunction with
simulated annealing was found to greatly improve the quality of the solution 
compared to a rule-based system and simulated annealing used separately.
Combining these two approaches, and using the best cooling schedule, 
we were able to find feasible solutions
to the complex class scheduling problem for a large university. 
Prior to this work, we also experimented with using the mean field annealing
of Peterson et al. \cite{26}, but this gave relatively poor results
\cite{SalehMFA, patat97}.

This paper is organized as follows.
In section 2 we give a brief review of the timetabling problem, and 
present the three categories of constraints along with examples of each.
Section 3 provides a background to some of the approaches used for tackling
the timetabling problem.
Sections 4 and 5 describe the two methods, a rule-based expert system
and simulated annealing, that we have used in our approach.
A discussion of the experimental results of our
method appears in section 6, and finally a summary and conclusion are
presented in section 7.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Timetabling Problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Many combinatorial optimization problems, 
such as the well-known traveling salesman problem (TSP), 
are defined in terms of minimizing an objective function.
Another class of optimization problems are constraint satisfaction problems,
which do not have a well-defined objective function.
This includes the NP-complete {\it teachers and classes} timetabling problem
\cite{2, 3, 27}. 
Briefly, the general problem is stated as follows:

For a certain school with $N_p$ teachers, $N_q$ classes, $N_x$
classrooms and lecture halls, and $N_s$ students, it is required to 
schedule $N_l$ teacher-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 teacher, 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. 
Figure \ref{relationship} sketches the approximate relationship
between the various entities of the timetabling problem.
\vspace{0.70cm}
\begin{figure}[htb]
\centerline{\psfig{figure=scheduling-net.eps,height=200pt,width=280pt}}
\vspace{0.20cm}
\caption{The relationship between various entities of the timetabling 
problem, where P is professors, C is classes, S is students, R is rooms, 
and I is time periods. 
The direction of the arrow indicates the direction of the assignment.}
\label{relationship}
\end{figure}


Constraint satisfaction problems have have been widely studied in the
artificial intelligence community \cite{9, 10, 11}.
A general constraint satisfaction problem consists of:
\begin{itemize}
\item A finite set of variables, $N_i$, where $i = 1, 2,\ldots,n\;$.
\item A domain D of possible values of $N_i\;$.
\item A set of constraints $\{C(S_1), C(S_2),\ldots, C(S_c)\;$, in
which each $S_i$ is an ordered subset of the variables, and each
constraint $C(S_i)$ is a set of tuples indicating the mutually
consistent values for the variables in $S_i\;$.
\end{itemize}

Assuming the time periods are given, a combination of a class,
a teacher, and a classroom will be considered as a tuple. Furthermore,
the length of the tuples in a given constraint will be called the 
{\it arity} of that constraint. In particular, unary constraints
specify the allowed values for a single variable, and binary
constraints specify the allowed combinations of values for a pair of
variables. 
% Note that to simplify our
% presentation, we will neglect the case of associating an arity with an
% empty set of tuples. 
%% To simplify it even further, just leave this out??

A solution to a constraint satisfaction problem is an assignment
of values to the variables that is consistent with all of the
constraints. Deciding whether or not a given problem instance has a 
solution is NP-complete in general \cite{11}, even when the
constraints are restricted to binary constraints.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Constraints of the Timetabling Problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Timetabling is the assignment of time slots to a set of events, 
subject to constraints on these assignments. Generally,
a constraint places a restriction on when and where classes may be
scheduled. 
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. 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.

In short, the three types of constraints used are:
\begin{enumerate}
\item Hard - These are constraints that must be satisfied.
\item Medium - These are constraints that should be satisfied, if
possible, but are not required for a valid solution or a legal schedule.
\item Soft - These constraints have a lower priority (and thus lower
cost) but it is preferable to minimize this cost.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Hard Constraints}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The most common and important hard constraint is what is sometimes
referred to as an {\it edge} constraint between two events, 
which simply states that a given pair of events ($e_1, e_2$) must not overlap in time. 
The name is due to the similarity of any simple timetabling problem with 
vertex coloring in graph theory \cite{21, 22}.

Events that must not overlap in time include:

\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.
% \item classes with students in common.
\end{itemize}

Other examples are space or room constraints: 
\begin{itemize}
\item
Some classes, such as laboratories, require a certain type of room.
\item 
A class cannot be assigned to a particular room unless the capacity of 
the room $R_c$ is greater than or equal to the class enrollment $C_e$. 
The smaller the difference between
these two sizes, the better the assignment. 
\end{itemize}

A cost is associated with any violation of these constraints.
The room constraint is implemented using a non-linear function for the 
cost $C_{rs}$ associated with the room size:  

\be{room-constraint}
C_{rs}=
\twoif{C_e - R_c} {\text{if} C_e > R_c\,,}
{\tanh((1.0 - {C_e \over R_c} - \beta) \gamma \pi) (R_c - C_e)}
{\text{otherwise.}}
\ee
In our experiments, the parameters $\beta$ and $\gamma$ were set 
to $0.5$ and $0.8$, respectively.

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. Here is how the exclusion cost
$C_x$ is obtained from this constraint:

$\forall i, j$ such that $i\neq j$, let $c_i$ denote class(i), $c_j$
denotes class(j), $s(c_i)$ is the starting time of $c_i$,
$end(c_i)$ is the end time of $c_i$, $len(c_i)$ is the duration
of $c_i$, $\epsilon$ is some chosen constant, and $Rlen(c_i,c_j)$ is
the relative length between $c_i$ and $c_j$ as defined below. Also,
the same notation applies to class $c_j$.

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

\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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Medium Constraints}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Medium constraints are usually considered to be those constraints that fall 
into the gray area between the hard and soft constraints \cite{49}. 
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 or postpone taking a particular class since some classes will 
have time conflicts, or will be oversubscribed.
In the problem we have studied, students specify their class preferences, 
plus a number of alternate choices. Our program attempts to satisfy a 
student's main preferences, but in many cases it will have to choose from the 
list of alternates, and in some cases will not be able to find any satisfactory 
class even from among the alternates. 

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 To sign up for a class it must be open 
      (classes can open or close depending on the class size).
\item Eligibility criteria for the class must be met.  
\item Enroll students in all parts of a class when associated sections 
(i.e. recitation, labs) are required.
\item Avoid time conflicts for classes with students in common.
\item Do not enroll athletes in classes that conflict with their sport
      practice time (of course, depending on the sport).
\end{itemize}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Soft Constraints}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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 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 teachers 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.

% FIX - what is 
% vector $\bar{m}<d_i,b_j>$   ??

Let $B$ denote the set of all $m$ buildings, and
$D$ denote the set of all $n$ departments, and $dist$
denotes distance. 
Now, for each $d_i \in D$ where $1\leq i \leq n$,
$dist(d_i)$ = vector $\bar{m}<d_i,b_j>$ for ${1 \leq j \leq m}$ of
matrix $Q$. Also, let $dist(d_i)_{min}$ = minimum of
$\bar{m}<d_i,b_j>$ for ${1 \leq j \leq m}$ of also matrix $Q$. Now
$C_{d_i}$ (the distance cost of $d_i$) is computed as follows:

\be{dist-cost}
C_{d_i} = 
\twoif {{dist(d_i)}_{min} {dist(d_i) \over {\sum_{j=1, i\neq j}^m
\bar{m} <d_i,b_j>}} + {dist(d_i)}_{min}} {\text{if} dist(d_i) >
{dist(d_i)}_{min}\,,}
{{dist(d_i)}_{min}} {\text{otherwise.}}
\ee

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Cost Function}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The cost function measures the quality of the current schedule and
generally involves the weighted sum of penalties associated with
different types of constraint violations. Summing these penalties or
costs is not strictly necessary, provided that the components
(individual costs) can be combined in some fashion to reflect the
overall quality of the schedule. 
The aim of the optimization technique is to minimize the cost function.
% 
% Let $C$ be the set of the given constraints. A {\it feasible} schedule 
% is defined as a schedule that satisfies the set of hard constraints
% $C^{'}$, where $C^{'} \subseteq C\;$.
% 
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 contigous 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; 
and eligibility criteria.

\item {\it Room cost} is the sum of costs associated with each classroom, 
including
the distance cost obtained from the distance constraint; 
and the room size cost obtained from the room constraint. 

\end{itemize}

% FIX - add section on how to chose parameters in the cost function, 
% especially for hard and medium constraints.
%
% cost = (A * hard) + (B * medium) + C * (soft)
% hard = A1 * constraint1 + A2 * constraint2 + ...
% medium = B1 * medconstraint1 + B2 * medconstraint2 + ...
% soft = C1 * cost1 + C2 * cost1 + ...
%
% ??




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Some Methods for Tackling the Timetabling Problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The timetabling problem we are studying can be summarized as follows. 
Given data sets of classes and their days, hours, enrollments, and
instructors; rooms and their capacities, types, and locations;
distances between buildings; 
priorities of each building for different departments; 
and students and their class preferences; 
the problem is to construct a feasible academic 
class schedule satisfying all the hard constraints and minimizing the 
medium and soft constraints. 

If the procedure used cannot assign certain classes to rooms and
timeslots, i.e. cannot find a feasible schedule for all classes, these
classes are left out of the final schedule and must be assigned
manually, or else the input variables must be changed. In some cases
there may be no feasible schedule for the given constraints, and the
problem must be reformulated to allow a solution. However our goal is to
provide a feasible schedule of better quality (i.e. lower cost), and in
less time, than that provided using current techniques.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Complexity of Timetabling}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Timetabling belongs to the class of constraint satisfaction problems
and is essentially an example of a resource-constrained scheduling
problem, which is NP-hard \cite{12, 58}. Here, resources
are physical entities, for example: students, rooms, overhead
projectors, and so on. Time periods can also be thought of as resources.

In general, timetabling problems are always NP-complete \cite{25}, 
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.

% is the complexity analysis OK?? yes in its brevity but will
% definitely take more than a short subsection to cover all aspects
% of it.

Traditionally, timetabling has been approached by means of linear
programming (LP) 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.

For the much simpler problem of {\it class allocation}, 
% which is??
for which there is no timetabling involved (i.e. no allocation of classes to 
time periods), 
% then why is N_t in here??
the computational load for using the LP method scales as 
$N_c N_x N_t$ \cite{5, 28},  
where $N_c$ is the number of room categories available.

% but it doesn't scale exponentially? 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Previous Approaches}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Clarify polytope stuff???

Most of the previous work in this area has addressed only a subset or 
simplified version of the problem, for example, 
examination scheduling, or dealing only with scheduling classes without 
taking into account the issue of student preferences. In addition, 
very few of the published studies actually use complex real-world data -- 
% with only a few exceptions \cite{38, 62},
most use randomly generated or artificial data sets. A number of
researchers have tackled the smaller scale (but still very difficult) 
problem of high school scheduling \cite{28}. 

Traditionally, the approach to the TTP 
in the operations research community has been to use methods such as integer 
programming and network flow \cite{21}. 
Another approach is to reduce it to
the well-known problem of graph coloring \cite{1, 21, 33}. 
More recently,
a number of non-conventional global optimization techniques such as 
neural networks \cite{27, 28}, 
simulated annealing \cite{3, 4, 18, 39}, 
genetic algorithms \cite{37}, 
tabu search \cite{29, 38, 62} 
have been used to tackle various instances of the timetabling problem,
with varying degrees of success. 


\begin{figure}[htb]
\psfig{figure=polytopes.eps,width=432pt,height=228pt}
\caption{An integral polytope AB has all its vertices at integral
points (A = 1.0 and B = 1.0), as shown in the left hand side figure,
but polytope DE in the right hand side figure is not integral since
its ends do not pass through [0-1] points.}
\label{poly}
\end{figure}


A solution from an integer programming point of view is basically to
find any integral vertex within the constraint polytope $P$, as shown
in Figure \ref{poly}. To elaborate on this, 
consider each constraint as a hyperplane in the solution space 
\cite{14, 15, 23}. 
The set of constraints define a polytope (or a bounded
polyhedron) within which the state vector must remain if it is not to
violate any constraints. The 0 or 1 solution points will lie at
some of the vertices of this polytope, and whatever annealing or other
local search method is used, it must force convergence to one of these
points. The problem with methods such as annealing 
% (certainly depends on the cooling schedule used) 
is that in this case the best one can
expect is convergence to a vertex, not necessarily a 0 or 1 vertex.

Polytopes, for example, like the one in the permutation matrix mapping
for the TSP, are integral, so there is no problem finding valid TSP
solutions (though the minimum tour length is another question
altogether). Class scheduling polytopes are a totally different story:
Gee and some of his colleagues at Cambridge University have
done some experiments on them and found that for timetabling problems
as small as five teachers, five classrooms, five classes, and five
time-slots, the proportion of 0-1 vertices is only about $1\%$ \cite{45}.  
This means that on average one has to run a descent procedure about 100
times to find a valid solution! Some of our experiments with sets of
teachers, classes, classrooms, students and time-slots of various
sizes confirm some of Gee's results and conclusions. 

Timetabling problems can be characterized by their {\it sparseness}.
After all the required lessons have been scheduled, there will be 
$N_{sp} = (N_x N_t - N_l)$ spare space-time slots, and the 
{\it sparseness ratio} of the problem is defined as $N_{sp} / (N_x N_t)$. 
Dense problems have a low sparseness ratio, since they have
relatively few spare space-time slots, 
and are thus harder to solve than sparse problems with many slots to spare.
Table \ref{table.02} shows three-semester sparseness ratios for our problem.

Gee \cite{45} has noted that for sparse problems, 
the probability of an arbitrary descent procedure converging
to an integral vertex is near one, though this falls off rapidly for harder,
less sparse problems. 
For dense problems, there is an additional
correlation involving the problem size: as the problem gets larger
(more classes, teachers, rooms, students, etc.), the proportion of
integral vertices gets smaller. From this we could deduce that a
one-time descent procedure, operating on an arbitrary ``objective function'', 
is not likely to be very successful with difficult (dense)
constraint satisfaction problems, most probably converging to a
non-integral vertex of $P$, for example. 

On the other hand, any
``partial'' or ``imperfect'' solution to a timetabling problem found
by methods such as simulated annealing 
is likely to be of some use. Since simulated annealing does
not search over the interior of the unit hypercube, but only over its
vertices,
% why???
the solution it finds will be a unique timetable, 
% what???
possibly violating few soft and/or medium constraints. As part of the
post-processing operation, for example we could at least remove some
classes to obtain a valid (or legal) timetable which fulfills most of
the teaching requirements. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Our Approach to the Timetabling Problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% FIX - add brief discussion of previous use of SA for this problem!!??

We adopted a multi-phase approach to tackle the the timetabling
problem \cite{50}. In the first phase a partial solution (a feasible
schedule for a subset of the classes) is found using a rule-based
expert system.  In the second phase this partial schedule is improved
to obtain a final schedule, using simulated annealing.

It is a good practice when using techniques such as simulated 
annealing to start at a good point in the search space or with a
partial solution, regardless of the difficulty or complexity of the
problem at hand. Simulated annealing is a very
time-consuming, computationally intensive procedure. 
A good starting point generally provides faster convergence and a better 
final solution, and our results clearly support this rationale for the
academic scheduling problem.
Using a rule-based preprocessor is a way of quickly providing such a 
starting point for the annealing process. 

To use simulated annealing effectively, it is crucial to use a good 
cooling schedule, and a good method for choosing new trial schedules, 
in order to efficiently sample the search space. We have experimented
with both these areas, which is discussed in section~\ref{SimulatedAnnealing}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Rule-Based System}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We have implemented a fairly complex
rule-based expert system for solving the timetabling
problem, for three reasons. Firstly, it gives us a benchmark as to how
well simulated annealing does in comparison to this standard technique. 
Secondly, a number of these rules are used to provide sensible choices for
moves in the annealing algorithm, rather than choosing swaps 
completely at random.
Thirdly, we have used this system as a preprocessor to provide a good 
starting point for the simulated annealing algorithm.

The rule-based expert system consists of a number of rules
(or heuristics) and conventional recursion to assist in carrying out
class assignments. We have developed this system specifically for the
problem of academic scheduling. The basic data structures or
components of the system are: 
\begin{enumerate}
\item
Distance matrix of values between each academic department and every
other building under use for scheduling. 
\item
Class data structure of each class scheduled anywhere in campus. 
These structures are capable of linking with each other. 
\item
Room data structure of each room (regardless of type) involved in the
scheduling process. Like classes, room structures are also linked with
each other. 
\item
Data structures for time periods to keep track of which hour or time
slot was occupied and which was not. 
\item
Department inclusion data structure giving department inclusion within
other larger departments or colleges. 
\item
Students structures indicating classes of various degree of
requirements and preferences for each student. 
\end{enumerate}

The basic function of the system is as follows: given data
files of classes, rooms and buildings, department-to-building distance
matrix, student data, and the inclusion data, using the
abovementioned data structures, the system builds an internal database
which in turn is used in carrying out the scheduling process. This
process involves a number of essential sub-processes such as checking
the distance given in the distance matrix, checking building, room
type and hours occupied, checking and comparing time slots for any
conflicts, checking rooms for any space conflict, and keeping track of
and updating the hours already scheduled.

When the rule-based system is used as a preprocessor, it produces a partial 
schedule as an output, since it is usually unable to legally assign all of 
the given classes to rooms and time slots. 
The output is divided into two parts: the first consists of classes,
with their associated professors and students, assigned to various
rooms; and the second is a list of classes that could not be assigned
due to constraint conflicts.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Example Rules}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Here are few examples of some of the implemented rules
dealing with space and hours, type of room, and priority of room.

\medskip
\noindent
{\bf Space and Hours}

{\it IF [room(capacity) $>$ class(space-requested)] and [no time
conflict in this room]

THEN assign the room to the class.}

\noindent
If more than one room having an identical availability time is present
in the database, then choose the one with the minimal magnitude of the
difference between room(capacity) and class(space-requested).

\medskip
\noindent
{\bf Type of Room}

{\it IF [room(capacity) $>$ class(space-requested)] and [no time
conflict in assigning this room] and 
[type(room) matches type(requested)] 

THEN
   assign the room to the class.}

\noindent
If identical rooms in type are present in the database, then choose
the one with the minimal magnitude of the difference between
room(capacity) and class(space-requested).

\medskip
\noindent
{\bf Room Priority}

Rooms are classified as either general purpose (GP), which are used by
all, or priority rooms (PR) with a usage based on certain priority of
the class or the department, or special purpose (SP) rooms which are
only assigned to specific users.

Here is a sample of rules showing how these room categories are used:

\smallskip
{\it IF [room(priority) == general] and [room(capacity) $>$
class(space-requested)] and [no time conflict in assigning this room]
and [type(room) matches type(requested)]  

THEN  assign any user to this room.}

\smallskip
{\it IF [room has a priority user] and [the user is already
assigned] and [room(capacity) $>$ class(space-requested)] and [no
time conflict in assigning this room] and [type(room) matches
type(requested)]

THEN  assign other users.}

\smallskip
{\it IF [room(priority) == special purpose] and [user belongs to
the special users of this room] and [room(capacity) $>$
class(space-requested)] and [no time conflict in assigning this room]
and [type(room) matches type(requested)]

THEN  assign the room to the user.}

\smallskip
{\it IF [room has a priority user] and [the user is already
assigned] and [room(capacity) $>$ class(space-requested)] and [no
time conflict in assigning this room] and [type(room) matches
type(requested)]

THEN  assign other users.}

\smallskip
{\it IF [room(priority) == special purpose] and [user belongs to
the special users of this room] and [room(capacity) $>$
class(space-requested)] and [no time conflict in assigning this room]
and [type(room) matches type(requested)]

THEN  assign the room to the user.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{SimulatedAnnealing}
\section{Simulated Annealing}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Simulated annealing (SA) has been widely used for tackling different 
combinatorial optimization problems, including academic scheduling 
\cite{39, 3, 4}. 
% Is this previous work discussed???
The basic algorithm is described in Figure~\ref{SA-algorithm}.
The results obtained depend heavily on the cooling schedule used. We
initially used the most commonly known and used schedule, which is 
geometric cooling, but later tried adaptive cooling, as well as the method of
geometric reheating based on cost \cite{2}.

A comprehensive discussion of the theoretical and practical details of SA 
has been given in a number of books and review articles on the subject
\cite{57, 17, 60}. 
It suffices here to say that the elementary operation is the Metropolis 
Monte Carlo update, which involves the generation of some new candidate 
configuration (in this case, a schedule),
which is then automatically accepted if it lowers the cost ($C$), 
or accepted with probability $\exp(-\Delta C /T)$, where $T$ is the
temperature parameter, if it would increase the cost by $\Delta (C)$. 
In Figure~\ref{SA-algorithm}, $s$ is the current schedule (configuration)
and $s^{'}$ is a neighboring schedule obtained from the current neighborhood 
space (${\cal N}_{s}$) by swapping two classes in time and/or space.
The annealing procedure starts at a high temperature, and then slowly 
decreases the temperature to zero, following a specified {\it cooling schedule}.
Simulated annealing is essentially a generalization of a local optimization
strategy, but improves upon it since at non-zero temperatures, 
there is a chance for the system to escape from local minima.

\begin{figure}[htb]
\vspace{0.25cm}
\begin{center}
\begin{enumerate}
\item Generate an initial schedule $s$.
\item Set the initial best schedule $s^{*} = s$.
\item Compute cost of $s$ :  $C(s)$.
\item Compute initial temperature $T_0$.
\item Set the temperature $T\; =\; T_0$.
\item While {\em stop criterion} is not satisfied do:
\begin{enumerate}
\item Repeat {\em Markov chain length} (M) times:
\begin{enumerate}
\item Select a random neighbor $s^{'}$ to the current schedule, 
$( s^{'} \subset {\cal N}_{s} )\;$.
\item Set $\Delta(C) = C(s^{'}) - C(s)\;$.
\item If ($\Delta(C) \leq 0$ $\{$downhill move$\}$):
\begin{itemize}
\item Set $s = s^{'}\;$.
\item If $C(s) < C(s^{*})$ then set $s^{*} = s$.
\end{itemize}
\item If ($\Delta(C) > 0$ $\{$uphill move$\}$):
\begin{itemize}
\item Choose a random number $r$ uniformly from $[0,1]$.
\item If $r < e^{-\Delta(C) /T}\;$ then set $s = s^{'}$.
\end{itemize}
\end{enumerate}
\item Reduce (or update) temperature $T$.
\end{enumerate}
\item Return the schedule  $s^{*}$.
\end{enumerate}
\end{center}
\caption{The Simulated Annealing Algorithm}
\label{SA-algorithm}
\vspace{0.25cm}
\end{figure}

The SA algorithm has advantages and disadvantages compared to other
global optimization techniques. 
Among its advantages are the relative ease of implementation,
the applicability to virtually any combinatorial optimization problem, 
the ability to provide reasonably good solutions for most problems
(depending on the cooling schedule and update moves used), 
and the ease with which it can be combined with other methods, such as 
expert systems and branch-and-bound techniques, forming quite useful hybrid 
methods for tackling a range of complex problems.
Some of the drawbacks of SA are that to obtain good results the update moves 
and the various tunable parameters used (such as the cooling rate) need to be 
carefully chosen, the runs often require a great deal of computer time, and 
many runs may be required.
Despite these problems, SA is a robust technique and has been successfully
applied to a wide variety of problems. 
Detailed comparisons of SA with other optimization techniques for some
well-known problems has shown that SA is competitive with many of the best 
%  local optimization methods, 
heuristics \cite{51}. 

% Is this necessary??
% Furthermore, the
% inherently serial nature of the approach in general precludes any
% obvious parallel implementation, though several attempts have been
% made to overcome this problem such as the recent work by Frost
% \cite{16}, Boissin and Lutton \cite{55}, and Verhoeven and Aarts
% \cite{56}. The most promising approach to parallelizing SA is to
% distribute the execution of the various parts of the algorithm over a
% number of communicating parallel processors which may contribute to a
% significant speedup in the overall runtime of the method. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Timetabling Using the Annealing Algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% This needs fixing??

The most obvious mapping of TTP into the SA algorithm
involves the following constructs:

\begin{enumerate}
\item a {\bf state} is a timetable containing the following sets:
\begin{itemize}
% Make sure variable names don't clash??? e.g. P, C, I?
\item $P$: a set of professors.
\item $C$: a set of classes.
\item $S$: a set of students.
\item $R$: a set of classrooms.
\item $I$: a set of time intervals.
\end{itemize}
\item a {\bf cost} or ``energy'' E($P, C, S, R, I$) such that:
\begin{itemize}

% This has already been defined in an earlier section which we can refer to.
% Why repeat it??

\item E($P$): is the cost of assigning more than maximum number of 
allowed classes $M_p$ to the same professor, 
plus scheduling one or more classes that cause a conflict
in the professor's schedule.

\item E($C$): is the cost of scheduling certain classes at/within the
same time period in violation of the exclusion constraint, for
example.

\item E($S$): is the cost of having two or more classes conflict in
time; plus cost of having in the schedule one or more classes that
really don't meet the student's major, class requested, or class
requirements; plus the cost of not having the classes evenly spread
out over the week, etc. 

\item E($R$): is the cost resulting from assigning room(s) of the wrong
size and/or type to a certain class.

\item E($I$): is the cost of having more or less time periods than
required, plus cost of an imbalanced class assignments (a certain
period will have more classes assigned to than others, etc.).
\end{itemize}

\item A {\bf swap} (or a move) is the exchange of one or more of the
following:
class $c_i$ with class $c_j$ in the set $C$ with
respect to time periods $I_i$ and $I_j$, and/or with
respect to classroom $R_i$ and $R_j$, respectively. Generally, this
step is referred to as class swapping.
\end{enumerate}

% Need to define what the input data is. Isn't this done elsewhere?

Along with all of the necessary constraints and the output of the
rule-based preprocessor, 
the simulated annealing algorithm also takes as input data the following: 
a list of classes that have not been already scheduled by the preprocessor
and their
associated professors and room types, a list of rooms provided by the
registrar's office, a department to building distance matrix, a list
of students and their class preferences, and a list of classes that
are not allowed to be scheduled simultaneously.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Annealing Schedules}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Three annealing schedules have been used in our experiments to update
the temperature of the SA algorithm:
geometric cooling, adaptive cooling, and adaptive reheating as a function of 
cost.

The first schedule we used is {\bf geometric cooling}, where the 
new temperature $T^{'}$ of the SA algorithm is computed using
\be{geometric}
T^{'} = \alpha T\; ,
\ee
where $\alpha$ ($0 < \alpha < 1$) denotes the cooling factor. 
Typically the value of $\alpha$ is chosen in the range $0.90$ to $0.99$. 
This cooling schedule has the advantage of being well understood, having
a solid theoretical foundation, and being the most widely used annealing
schedule. The results obtained from using this standard cooling
schedule can be used as a baseline for comparison with those using
the other two schedules, which allow the rate of cooling to be varied.

The second annealing schedule we used is the method of 
{\bf reheating as a function of cost} (RFC), 
which was used for timetabling by Abramson {\it et al.} \cite{2}, 
but the ideas behind it are due to Kirkpatrick {\it et al.} \cite{52, 53}
and White \cite{41}. 
Before introducing this schedule we first summarize a few relevant
points on the concept of specific heat ($C_H$). Specific heat is a
measure of the variance of the energy (or cost) values of states at a
given temperature. The higher the variance, the longer it presumably
takes to reach equilibrium, and so the longer one should spend at the
temperature, or alternatively, the slower one should lower the temperature.

Generally, in combinatorial optimization problems, phase transitions 
\cite{66, 8} can be observed as sub-parts of the problem are resolved. 
In some of the work dealing with the traveling salesman problem using 
annealing \cite{7}, the authors often observe that the resolution of the
overall structure of the solution occurs at high temperatures, and at
low temperatures the fine details of the solution are resolved.
Applying a reheating type procedure,
depending on the phase, should allow the algorithm to spend more time
in the low temperature phases, thus reducing the total amount of time
required to solve a given problem \cite{2}. 

In order to calculate the temperature at which a phase transition
occurs, it is necessary to compute the specific heat of the
system. A phase transition occurs at a temperature $T(C_H^{max})$ when
the specific heat is maximal ($C_H^{max}$), and this triggers the change in
the state ordering. If the best solution found to date has a high
energy or cost then the super-structure may require
re-arrangement. This can be done by raising the temperature to a level
which is higher than the phase transition temperature $T(C_H^{max})$.
Generally, the higher the current best cost, the higher the
temperature which is required to escape the local minimum.
To compute the maximum specific heat, we employ the
following steps \cite{2, 17, 60}.

At each temperature $T$, the annealing algorithm generates a set of 
configurations ${\cal C}(T)$. 
Let $C_i$ denote the cost of configuration $i$, $C(T)$ be the average 
cost at temperature $T$, and $\sigma(T)$ be the standard deviation of the
cost at $T$. 

At temperature $T$, the probability of being in configuration $i$ is given by
the Boltzmann distribution \cite{8, 60, 57, 41}: 
\be{T.1}
P_i(T) = {e^{-C_i \over {kT}} \over \sum_j{e^{-C_j \over {kT}}}} \,.
\ee

The average cost is thus: 
\be{T.2}
C(T) = \sum_{i \in {\cal C}} C_i P_i(T) \,.
\ee

The Metropolis Monte Carlo update used in SA generates configurations with
a Boltzmann probability distribution \cite{8, 60, 57, 41}, 
so an estimate $<C(T)>$
of the average cost can be computed from the set {\cal G} of configurations 
generated at temperature $T$ by the annealing algorithm using: 
\be{T.2}
<C(T)> \, = \, \sum_{i \in {\cal G}} C_i \,.
\ee

Similarly, the average square cost can be computed as: 
\be{T.3}
<C^{2}(T)> \, = \, \sum_{i \in {\cal G}} C_i^2 \,.
\ee

The variance of the cost is:
\be{T.4}
\sigma^{2}(T) \, = \, <C^{2}(T)> - <C(T)>^{2} \,.
\ee

Now, the specific heat is defined as: 
\be{T.5}
C_H(T) \, = \, {{\sigma^{2}(T)} \over {T^{2}}} \,.
\ee
The temperature $T(C_H^{max})$ at which the maximum specific heat
occurs, or at which the system undergoes a phase transition, can thus
be found. 

Reheating sets the new temperature to be
\be{T.6}
T = K \cdot C_b + T(C_H^{max}) \, ,
\ee
where $K$ is a tunable parameter and $C_b$ is the current best cost. 
Reheating is done when the temperature  drops below the phase
transition (the point of maximum specific heat) 
and there has been no decrease in cost for a specified number of
iterations, i.e. the system gets stuck in a local minimum. Reheating
increases the temperature above the phase transition (see equation
\ref{T.6}), in order to produce enough of a change in the configuration
to allow it to explore other minima when the temperature is reduced again.  

The third cooling schedule we have tried is {\bf adaptive cooling}. 
In this case, a new temperature is computed based on 
the standard deviation of all costs obtained at the current temperature, 
i.e. the specific heat. 
The idea here is to keep the system close to equilibrium, by cooling slower
close to the phase transition, where the specific heat is large.
There are many different ways of implementing this idea, 
we have chosen the approach taken by Huang {\it et al.} \cite{59}, 
which was shown to yield an efficient cooling schedule. 
Let $T_j$ denote the current temperature, at step $j$ of the annealing schedule.
After calculating $\sigma(T_j)$ from equation \ref{T.4}, the new temperature
$T_{j+1}$ is computed using: 
%
\be{T.6.1}
T_{j+1} = T_j \cdot e^{-{{a T_j} \over \bar\sigma(T_j)}} \, ,
\ee
%
where $a$ is a tunable parameter.
Following suggestions by Otten and van Ginneken \cite{60} and Diekmann
{\it et al.} \cite{61}, $\sigma(T_j)$ is smoothed out in order to avoid any
dependencies of the temperature decrement on statistical fluctuations in the
measurement of the standard deviation $\sigma$. 
The smoothed standard deviation $\bar\sigma$ is given by
%
\be{T.6.0}
\bar\sigma(T_{j+1}) = (1 - \omega) \sigma(T_{j+1}) + \omega \sigma(T_j) \, ,
{T_{j+1} \over T_j}
\ee
%
where we have set $\omega$ to $0.95$.
This smoothing function is used because it follows (from the form of the
Boltzmann distribution) that it preserves the key relationship
\be{T.7}
{d \over {dT}}C(T) = {\bar\sigma^{2}(T) \over T^{2}} = C_H \, .
\ee

Note that reheating can in principle be used in conjunction with any 
cooling schedule. We have used it with adaptive cooling.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Choice of Moves}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The performance of any application of simulated annealing is highly
dependent on the method used to select a new trial configuration of the
system for the Metropolis update. In order for the annealing algorithm to 
work well, it must be able to effectively sample the parameter space, 
which can only be done with efficient update moves.

Let $s$ be the current schedule and $s^{'}$ be a neighboring schedule
obtained from the current neighborhood space (${\cal N}_{s}$) by
swapping two classes in either time or/and space.
%
The simplest method for choosing a move is to swap the rooms or
timeslots of two randomly selected classes. However this is extremely
inefficient, since most of the time random swapping of classes will
increase the overall cost, especially if we are already close to
obtaining a valid solution (i.e. at low temperature), and will likely
be rejected in the Metropolis procedure. 
This simple method is therefore very inefficient, since a lot of
computation is required to compute the change in cost and do the
Metropolis step, only to reject the move.

What is needed is a strategy for choosing moves that are more likely to be
accepted. A simple example is in the choice of room. If we randomly choose
a new room from the list of all rooms, it will most likely
be rejected, since it may be too small for the class, or an auditorium 
when, for example, a laboratory is needed. One possibility is to
create a subset of all the rooms which fulfill the hard constraints on
the room for that particular class, such as the size and type of
room. Now we just make a random selection for a room for that class
only from this subset of feasible rooms, and the acceptance
probability will be much higher. In addition, each class
in our data set comes with a ``type-of-space-needed'' tag which is
used along with other information to assign the class to the right room.
This effectively separates the updates into independent sets based on
room type, so for example, laboratories are scheduled separately from
lectures. We carry out the scheduling of lectures first,
followed by scheduling of laboratories, making sure that during the
course of this process no lecture and its associated laboratory are
scheduled in the same time period.
%
In effect, we have embedded a simple expert system into the annealing
algorithm in order to improve the choice of moves, as well as using a more 
complex expert system as a preprocessor for the annealing step.

To improve further on the move strategy, we can take the subset of
possible move choices that we have created for each class, and choose
from them probabilistically rather than randomly. There may be certain
kinds of moves that are more likely to be effective, so our move
strategy is to select these moves with a higher probability.  
For example, swapping a higher level class (e.g. graduate) with a
lower level class (e.g. first or a second year) generally has a 
higher acceptance, since there is little overlap between students taking
these classes. 

% FIX THIS!!
We have also experimented with two kinds of swaps, 
those that only involve classes offered by the same department or college, 
and swaps between classes of different departments and colleges. 
As illustrated in Figure \ref{class-swaps}, swapping is 
done as follows: Given a certain college or school, school(i), 
we randomly pick a department, $A$. 
Based on the given constraints, we carry out class swapping within 
department $A$ making sure that no cycling occurs. 
The second step is to swap classes
between $A$ and another randomly selected department, $C$, within
school(i). The third step of class swapping takes place within
department $C$. This process of swapping continues within the same
school provided all room and time constraints are satisfied and also
no cycling of the same departments or classes occurs. We refer to
this phase of swapping as ``local'' since it only involves classes
either in the same department or classes of departments that belong to
the same school or college. As previously mentioned, associated with
each department a list of buildings where it assign its classes to. The
first building in the list is the home building and always the first
preference for class assignment. If the tag name ``others'' appears in
the list then the department has an option of swapping its classes
with those of any other department of not only the same school but
with others as well. This ``global'' swapping has to be done in such a
way that all constraints involved and room preferences for both
classes are satisfied. 

The plots of Figures \ref{graph.6} and \ref{graph.6.1} clearly show
that the overall rate of acceptance of swapping classes of the same 
departments or schools is higher than the overall rate of acceptance 
swapping classes of different departments of different schools. 
We could see that one of the reasons for this is that
classes of the same departments or schools are associated with the same
subset of rooms that satisfies those constraints involving distance and
department preference. Therefore, the likelihood of satisfying the
constraints of room availability, capacity, and type within that group
of rooms is much greater than if it is the otherwise case. In addition,
departments and schools in our test data always prefer to have their
classes (especially the lower and the upper level) spread out into as
many time slots as needed, in turn minimizing, if not totally
eliminating, any overlap that may occur otherwise. Consequently, the
likelihood of any time conflict occurring after any department
two-class swap is quite low. Also, as shown in Figures \ref{graph.6}
and \ref{graph.6.1}, those acceptance rates drop off with the decrease
in temperature. 

Another move strategy we have followed is that since constraints
involving capacity of rooms are hard ones, we schedule larger classes
first to try to avoid not having large enough rooms later for those
class sections with large enrollments. 

Generally, the swap methods we have taken here can be considered as 
heuristics for pruning the neighborhood or narrowing the search space,
which provides much more efficient moves and in turn an overall
improvement in the results. 

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=class-swaps.eps,height=330pt,width=330pt}}
\vspace{0.20cm}
\caption{A pictorial view of the class swaps. Three kind of swaps are
shown: first, class swapping within the same department; second, class
swapping between two departments; three, class swapping between two
departments of different schools. The first two types of swaps are
classified as (local) within the same dept/school while the last one
(global) involving different schools.}
\label{class-swaps}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experimental Results}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Our computations were done with a number of goals in mind. The main
objective was to provide a schedule which satisfied all hard
constraints and minimized the cost of medium and soft constraints, 
using real-life data sets for a large university. 
We also aimed to find an acceptable set of annealing parameters 
and move strategies for general timetabling problems of this kind,
and to study the effect of using a preprocessor to provide the annealing
program with a good starting point. Finally, we wanted to make a
comparison of the performance of the two different cooling schedules,
geometric cooling and reheating based on cost.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Timetabling Data Set}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Our study case involved real scheduling data covering three semesters
at Syracuse University. The size and type of the three-semester data
is shown in Table \ref{table.01}. Nine types of rooms were used and
they are: auditoriums, classrooms, computer clusters, conference
rooms, seminar rooms, studios, laboratories, theaters, and
un-specifies types. Staff and teaching assistants are considered part
of the set of professors. In addition, third semester (summer) data
was much smaller, however, there were additional space/time
constraints and fewer number of available rooms. Our data was quite
large in comparison to data used by other researchers, for example,
\cite{18, 27, 28}. Peterson and colleagues high school data \cite{26,
27, 28} consists of approximately 1000 students, 20 different possible
majors, and an overall periodic school schedule (over weeks). In the
case of Abramson et al. \cite{18}, their data set was created randomly
and relatively small. Also they stated that problems involving more
than 300 tuples were very difficult to solve. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental Runs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We have observed that the choice of initial
temperature poses more of a challenge. To be exact, the experimental
procedure was this: For the geometric cooling as well as the reheating
schedule, $10$ simulation runs were made from each of the following
starting temperatures: 50, 100, 150, 200, 250, 300,
350, 400, 450, 475, 485, 490, 495, 500, 505, 510, 515, 520, 525, 550, 600, 650, 700,
850, 900, 1000. The challenge stems mainly from the fact that in our simulations
we apply a preprocessor to give us a good starting point in the search
space. So using either very small or very large initial temperature
can disturb this desirable starting state leading to inferior final
solution or a solution with high cost. 
As shown in Figure \ref{graph.6.2}, the smaller values of the set
yield more inferior solutions than the higher values, and generally 
final cost is the lowest around the intermediate values of the set. In
particular, the temperature of $500$ gives the lowest final
cost. Consequently Figures \ref{graph.3}, \ref{graph.2},
\ref{graph.5}, \ref{graph.6}, and \ref{graph.6.1} are all based on an
initial temperature of $500$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Cooling Schedule - Some Analysis}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We have used two cooling schedules for our 
experiments, reheating based on cost and geometric cooling. Each 
schedule takes a set of parameters --- the initial temperature, the
temperature reduction constant ($\alpha$), and time (number of iterations)
spent at each temperature. We also needed to specify a criterion for 
stopping the procedure when it was believed that the solution was
good enough that we do not expect to obtain much improvement by
extending the run.

The temperature reduction factor $\alpha$ and the the number of moves at 
each temperature $N_T$ are related, since we expect that if $\alpha$ is 
replaced with its square root (so the number of temperatures in the
cooling schedule is doubled), and $N_T$ is halved, the solution quality is 
expected to be about the same, as long as $\alpha$ is large enough.
Usually $\alpha$ is chosen to be in the region $0 \le \alpha < 1$. 
We found only a small variation in the results for this parameter range,
and decided to arbitrarily fix $\alpha$ to be $0.95$, and use $N_T$ as
a variable with which to compare solution quality.  
In some of the runs we set this variable to be at least proportional to 
the neighborhood size, or the size of our data, and in general we observed 
that this yielded slightly better results.

In general, specifying an initial temperature for annealing is usually
a straightforward procedure. Infinite temperature means that the
changes are always accepted (i.e. the acceptance ratio is 1), which
produces random configurations. In practice the initial temperature
should not be too large, or else the cooling will take too long, and
the annealing will spend too much time at higher temperatures where
little useful work is being done. So the initial temperature is
usually chosen to be the lowest possible value that still gives a high
acceptance ratio (greater than $0.5\%$, for example). 

Choosing an initial temperature is much more difficult when we use
a preprocessor to provide a good starting configuration
rather than the usual random initial configuration. In that case,
we must be very careful that the initial temperature and the
acceptance ratio are not so high that the good initial configuration
is randomized to the point where is loses its usefulness. However the
initial temperature must be high enough so that we can still make
effective changes in the configuration. In our abovementioned chosen
sets of experimental starting temperatures we have observed (see
Figure \ref{graph.6.2}) that when using the 2 intermediate
temperatures, 500 and 650, and particularly 500 for both schedules,
the system simulation comes as close as satisfying those criteria,
more so than when other temperatures of the set are used. 

For geometric cooling as well as for the adaptive schedule, the
initial comparison was with a standard type of stopping criterion
\cite{19, 51}: the run was terminated when no moves had been accepted
for five generations (a generation is a full Markov chain at a single
temperature). 

% \subsection{The Choice of Moves} ???
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Observations and Analysis}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Johnson et al. \cite{51} noted in their SA implementation for the TSP
that the number of steps at each temperature (or the size of the Markov
chain) needed to be at least proportional to the ``neighborhood'' size
if they were to obtain worthwhile tour quality. From our experiments
we found that the above hypothesis raised in \cite{51} to also hold
eventhough the nature of our problem is different than
TSP. Furthermore, in few tests for one semester we fixed number of
classes and professors but varied number of rooms and time slots and
found that the final result improved as the size of Markov chain becomes
more proportional to a combination of number of classes, number of
rooms and number of time slots. In other words, as the ratio 
of Markov chain to the combined number of classes, rooms, and
timeslots approaches 1.0 a more improved final result is obtained. We
also observed the same behavior when we fixed the number of rooms and
time slots but varied number of classes. In regard to the relation
between the initial temperature and number of iterations per
temperature, in few runs we observed that as the number of iterations
per temperature decreases it is more preferable to start with a lower
initial temperature, and this is more so when using the geometric
cooling schedule than adaptive annealing. On this last point, from our
experiments involving the preprocessing phase, in general we have not
observed such a relationship.

Also, we observed that the efficacy of starting annealing (using either
adaptive or non-adaptive schedules) from a good solution depends not
only on the energy (or cost) of that solution, but also on how it was
obtained, that is, on its structure. For example, \cite{19, 51}
gave few thoughts and hypotheses on this subject as mentioned above
but as far as we know we have not come across any kind of analysis on
the topic.

% This is not an analysis either!!
% How does it depend on structure?? How can you tell??
% THIS DOESN'T EXPLAIN ANYTHING!!
% How does specific heat fit in?? 

Our analysis starts with Figure \ref{graph.3} which shows the
relationship between $\log_2(T)$ and cost for both the geometric
cooling and the adaptive method. The change in cost for the geometric
schedule seems to be more ``smoother'' or uniform and less steeper
than that of the adaptive schedule. Furthermore, for the adaptive
schedule after reaching a certain point around $\log_2(T)$ of $4$ it
stabilizes and the rate of change in cost becomes almost unnoticable. 

Table \ref{table.01} lists all major components of the data and Table
\ref{table.02} shows the rates of sparseness of the three-semester
data which greatly depends on number of time slots and rooms used. The
level of sparseness increases as the overall size of the data,
particularly, number of rooms, time slots, and number of classes.

Our overall results are shown in Tables (\ref{table.1}, \ref{table.2},
\ref{table.3}, and \ref{table.4}). Table \ref{table.1} gives a
percentage output of the preprocessor (the rule-based system) for a
three-semester set of data as well as the highest and lowest
percentage of scheduled data. We also can see that the size of those
scheduled classes increases as the input (number of classes)
decreases, which was not really surprising since the overall number of
rooms and time slots were kept fixed for the three semesters. So the
system does quite well for small sets of classes even when both class
and students constraints were taken into consideration. Unlike Table
\ref{table.1}, Table \ref{table.2} shows improved results and that was
mainly due to not taking students constraints into consideration and
only restricting the system to class constraints.

In the case of simulated annealing, Table \ref{table.3} shows output
in a percentage form averaged over 10 runs for three semesters 
without a preprocessor. Clearly, it shows a rather poor output which
is even lower in quality to that of the rule-based system of Table
\ref{table.1}. Also, the use of the adaptive (cost-based) schedule did
not improve the results by much and remained below those of Table
\ref{table.1}. Furthermore, the adaptive annealing gave an overall 
better average result than that of the geometric schedule for the
three semester.

In contrast to the first three tables, Table \ref{table.4} shows quite
improved and high quality averaged results for both annealing
schedules. Such excellent results were mainly due to the use of
preprocessed input (output of the rule-based system) to the SA
processor. Also the figures were averaged over 10 runs of annealing
and for the cost-based schedule $6$ out of those runs for the third
semester set yielded a perfect schedule, that is, all classes of the 
input set were scheduled satisfying the given class and students 
constraints.

Clearly, this tells us that the use of preprocessing was not only
helpful but quite essential when using methods such as simulated
annealing to deal with complex timetabling  problems. Furthermore,
these high quality averaged results state in an unambiguous terms that
a multi-phase approach, one as explained above, gives a much better
results to TTP then a single-phase approach. 


\subsection{Code and Simulation Times}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The annealing programs were written in ANSI C, and all the simulations 
were run on a number of IBM RS/6000 workstations, and on a 12-processor 
IBM SP2, which uses RS/6000 processors.  % specify CPU???
For the SP2, individual jobs were run separately on different nodes
using different sets of parameters, or different cooling schedules, or
just different random numbers. 
The average time for running the preprocessor (the expert system) for
the first and second semester data was about two hours, and the average
time for each simulated annealing run was approximately 20 hours for
the geometric cooling schedule and about 14 hours using the reheating
schedule. 

These runtimes are much faster than
the 30 days or so time period it usually takes for Syracuse University to
produce a final schedule (not including student preferences) for a single
semester, using a semi-automated procedure which involves substantial 
manual effort to iterate to a solution. 

\section{Conclusions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We have successfully applied simulated annealing to the difficult
problem of academic scheduling for a large university. Feasible
schedules were obtained for real data sets without requiring 
enormous computational effort.

We found that we could only obtain successful results by using 
a preprocessor to provide a good initial schedule to the annealing
program. We used a fairly complex rule-based system for the 
preprocessor, however the type of preprocessor may not be crucial.
Other fast heuristics could possibly be used, for example a graph
coloring approach, or it may be possible to just utilize the schedule
from the same semester for the previous year.

Another critical part of the annealing program was the choice of moves.
We used techniques that drew from our work on the rule-based system in
order to carefully select good moves that have a relatively high
probability of acceptance, rather than wasting computational effort on
randomly chosen moves, most of which would be rejected. 
We tested two types of cooling schedules: the standard geometric
cooling, and a cost-based annealing method. This former method
outperformed the former for the larger sets but didn't do as well
smaller one.

\section{Future Work}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In order to avoid dealing with a rather complex expert system, we
will try to use graph coloring heuristics as worked out in \cite{1}
as a preprocessor. Also, as a preprocessor, we will investigate the
possible use of previous year's templates. For the processor, we would
like to try other methods, particularly tabu search, genetic
algorithms, and other methods outlined in Johnson et
al. \cite{51}. Furthermore, using the same set of data we plan to
carry an intensive comparative study on these and perhaps other
methods exploring the various characteristics and constraints of the
timetabling problem. We are investigating these possibilities.

\section*{Acknowledgments}

% FIX??

The authors are very grateful for the valuable help of Robert
Irwin in converting and formatting the registration data prior to the
scheduling process. We would like to thank Seong-Joon Yoo for the useful
discussion on the preprocessing phase and Hon Yau for  the  useful 
comments and suggestions contributing to the improvement of the presentation 
of the contents. Also, we sincerely thank Karen Bedard for providing us with the 
data and answering so many questions we had about it, Meg Cortese for providing us 
with a set of building constraints for various departments, and Ben Ware, Vice President for
Research and Computing at Syracuse University, for his support and 
encouragement.

%%%%%%%%%%%%
% TABLES
%%%%%%%%%%%%

\newpage

\begin{table}[htb]
\vspace{0.1cm}
$$
\begin{tabular}{|l||c|c|c||}
\hline
                  & First Semester & Second Semester & Third Semester \\ \hline\hline
Rooms             &     509        &      509        &     120        \\ \hline
Classes            &     3839       &      3590       &     687        \\ \hline
Professors        &     1190       &      1200       &     334        \\ \hline
Students          &     13653      &      13653      &     2600       \\ \hline
Buildings         &     43         &      43         &     11         \\ \hline
Schools/Colleges  &     20         &      21         &     17         \\ \hline
Departments/      &     143        &      141        &     108        \\
Course Prefix     &                &                 &                \\ \hline
\end{tabular}
$$
\caption{Size of a three-semester data.}
\label{table.01}
\vspace{0.25cm}
\end{table}

\begin{table}[htb]
\vspace{0.1cm}
$$
\begin{tabular}{|l||c||}
\hline
Academic               & sparseness \\ 
Time Period           &    ratio   \\
                               &            \\ \hline\hline 
First Semester       &    0.50    \\ \hline
Second Semester &    0.53    \\ \hline
Third Semester      &    0.62    \\ \hline
\end{tabular}
$$
\caption{A three-semester sparseness ratio each computed as
$N_{sp}/(N_x N_t)$ is shown. The smaller the ratio, the less sparse
the problem is. Refer to section (3) for more details. Here, the ratio
is based on $N_t$ = 15 time slots each with a duration of 55 minutes. The
first slot starts at 8:00 am and the last slot ends at 9:45 pm.}
\label{table.02}
\vspace{0.25cm}
\end{table}

\begin{table}[htb]
\vspace{0.1cm}
$$
\begin{tabular}{|l||c|c|c|c||}
\hline
Academic        &  Total     & Scheduled  & highest       & lowest    \\ 
Time Period     & Classes & (average) & Scheduled & Scheduled \\
                         &               &    \%         &   \%             &   \%      \\ \hline\hline 
First Semester  &  3839    &   69.20      &   74.90       &   66.60   \\ \hline
Second Semester &  3590   &   70.85   &   76.15   &   68.55   \\ \hline
Third Semester  &  687    &   90.35   &   93.77   &   86.45   \\ \hline
\end{tabular}
$$
\caption{Percentage of scheduled classes, averaged over 10 runs,
for three terms using a {\it rule-based system} only. 
Both class and student constraints are used.}
\label{table.1}
\vspace{0.25cm}
\end{table}

\begin{table}[htb]
\vspace{0.1cm}
$$
\begin{tabular}{|l||c|c|c|c||}
\hline
Academic        &  Total  & Scheduled & highest   & lowest    \\ 
Time Period     & Classes & (average) & Scheduled & Scheduled \\
                &         &    \%     &   \%      &   \%      \\ \hline\hline 
First Semester  &  3839   &   73.19   &   76.65   &   70.23   \\ \hline
Second Semester &  3590   &   76.00   &   79.00   &   72.80   \\ \hline
Third Semester  &  687    &   93.70   &   96.80   &   91.00   \\ \hline
\end{tabular}
$$
\caption{Percentage of scheduled classes, averaged over 10 runs,
for three terms using a {\it rule-based system} only. 
Only class constraints are used.}
\label{table.2}
\end{table}

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l|l||c|c|c||}
\hline
Academic        &   Algorithm     & Scheduled  & highest   & lowest    \\
Time Period     &                 & (average)  & Scheduled & Scheduled \\
                &                 &    \%      &    \%     &    \%     \\ \hline\hline
First Semester  & SA (geometric)  &   60.55    &   65.50   &   52.80   \\
                & SA (cost-based) &   66.85    &   70.40   &   61.30   \\ \hline
Second Semester & SA (geometric)  &   61.65    &   66.72   &   56.00   \\ 
                & SA (cost-based) &   67.84    &   71.68   &   63.91   \\ \hline
Third Semester  & SA (geometric)  &   84.12    &   88.50   &   68.00   \\
                & SA (cost-based) &   89.14    &   92.87   &   70.25   \\ \hline
\end{tabular}
$$
\caption{Percentage of scheduled classes, averaged over 10 runs of the
same initial temperature and other parameters, for three terms using
{\it simulated anealing} only, with no preprocessor and a random
initial configuration. Both class and student constraints are used.}
\label{table.3}
\end{table}

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l|l||c|c|c||}
\hline
Academic        &   Algorithm     & Scheduled & highest   & lowest    \\
Time Period     &                 & (average) & Scheduled & Scheduled \\
                         &                 &    \%     &    \%     &    \%     \\ \hline\hline
First Semester  & SA (geometric)  &   91.90   &   95.92   &   80.00   \\
                          & SA (cost-based) &   98.17   &   98.97  &   90.66   \\ \hline
Second Semester & SA (geometric)  &   92.85   &   95.95   &   80.40   \\
                              & SA (cost-based) &   98.90   &   99.70   &   91.40   \\ \hline
Third Semester  & SA (geometric)  &   96.51   &   99.89   &   88.90   \\
                           & SA (cost-based) &   100.0   &   100.0   &   100.0   \\ \hline
\end{tabular}
$$
\caption{Percentage of scheduled classes, averaged over 10 runs of the
same initial temperature and other parameters, for three terms using 
{\it simulated anealing with a rule-based preprocessor.} Both class
and student constraints are used.} 
\label{table.4}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% FIGURES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=adaptive-and-geometric.TempLog2.vs.Cost.ps,height=280pt,width=280pt,angle=-90}}
\caption{Cost vs. temperature (log to the base of 2) for the geometric and
adaptive (RFC) schedules.}
\label{graph.3}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=Temp_log2.vs.Cost-after-cooling.ps,height=280pt,width=280pt,angle=-90}}
\caption{Cost after cooling vs. temperature (log base 2) for the reheating based on cost
schedule.}
\label{graph.2}
\end{figure}

%%\vspace{0.25cm}
%%\begin{figure}[htb]
%%\centerline{\psfig{figure=geomtric.Cost.vs.Steps.ps,height=280pt,width=280pt,angle=-90}}
%%\caption{Cost vs. number of steps for the geometric annealing.}
%%\label{graph.4}
%%\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=non-geom.geom.Steps.vs.Cost.ps,height=280pt,width=280pt,angle=-90}}
\caption{Cost vs. number of steps for the adaptive (RFC) and the
geometric schedules. As shown the range of steps is relatively small
in comparison to the Markov chain which is about a factor 20 as large
as the intermediate value of the range.}
\label{graph.5}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=Adaptive.log_T.vs.same-diff-avg.ps,height=280pt,width=280pt,angle=-90}}
\caption{Temperature vs. rate of acceptance when classes of
different schools/depts and the same schools/depts are swapped. This is
using the adaptive (RFC) schedule. As shown, the figure includes the
average rate as well.} 
\label{graph.6}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=Geometric.log_T.vs.same-diff-avg.ps,height=280pt,width=280pt,angle=-90}}
\vspace{1.0cm}
\caption{Temperature vs. rate of acceptance when classes of different
and same schools or depts are swapped. This is using the geometric
schedule. As shown, the figure includes the average rate as well.} 
\label{graph.6.1}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=Log-initial_T.vs.Final_cost.ps,height=280pt,width=280pt,angle=-90}}
\vspace{1.0cm}
\caption{Initial temperature vs. final cost for both schedules: the geometric
annealing and the adaptive (RFC). Each of the final costs is an
average of a 10-run at the given initial temperature. Furthermore, the
category of class swaps in these runs is either local or global or both.}
\label{graph.6.2}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=K.vs.Final-Cost.ps,height=280pt,width=280pt,angle=-90}}
\vspace{1.0cm}
\caption{Final cost vs. the value of ``K'' in the reheating equation. K is multiplied by the best
cost found so far.}
\label{graph.6.3}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=a.vs.Final-Cost.ps,height=280pt,width=280pt,angle=-90}}
\vspace{1.0cm}
\caption{Final cost vs. the value of the parameter (a) in adaptive cooling schedule.}
\label{graph.6.4}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% REFERENCES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\clearpage
\begin{thebibliography}{TTP}

\bibitem{57}
Aarts, E. H,  J. Korst, and P. J. van Laarhoven, ``Simulated
annealing,'' in Local Search in Combinatorial Optimization,
E. H. Aarts and J. K. Lenstra (eds.), John Wiley and Sons. (to
appear in 1997)

\bibitem{18}
Abramson, D,
``Constructing school timetables using simulated annealing: 
sequential and parallel algorithms,'' {\it Management Science}, 37(1), 98-113,
1991.

\bibitem{2}
Abramson, D., H. Dang, and M. Krishnamoorthy,
``An Empirical Study of Simulated Annealing Cooling Schedules,''
Griffith Univ. report, Nathan, Qld, Aus. 1994. Another version:
``Simulated Annealing Cooling Schedules for the School Timetabling
Problem,'' submitted to Asia Pacific Journal of Operations Research,
1996.

\bibitem{39}
Applied Simulated Annealing, Rene Vidal (ed), Lecture
Notes in Economics and Mathematical Systems no. 396, Springer-Verlag,
1993.

% \bibitem{55}
% Boissin, N, and J.-L. Lutton, ``A parallel simulated annealing
% algorithm,'' {\it Parallel Computing} 19, 859-872, 1993.

% \bibitem{54}
% Carter, M,  ``A Lagrangian Relaxation Approach to The Classroom
% Assignment Problem,'' {\it INFOR} vol. 27, no.2, 230-246, May 1989.

\bibitem{58}
Carter, M, and C. Tovey, ``When is the classroom assignment problem
hard?,'' Working Paper 89-03, Dept. of Industrial Engineering,
Univ. of Toronto, 1989. (submitted to Operations Research).
% ?? This needs updating

\bibitem{37}
Colorni, A,  M. Dorigo, and V. Maniezzo, 
``On the use of genetic algorithms to solve the timetable problem,''
report 90-060, Dipartimento Di Elettronica E Informazione, 
Politecnico Di Milano, Milan, Italy.
% published??

\bibitem{62}
Costa, D,  ``A Tabu Search algorithm for computing an operational
timetable,'' European Journal of Operational Research, 76 (1994),
98-110. 

\bibitem{21}
de Werra, D,
``An introduction to timetabling,'' {\it European Journal of
Operational Research}, 19, 151-162, 1985.

\bibitem{22}
de Werra, D,
``Extensions of coloring models for scheduling purposes,'' {\it
European Journal of Operational Research}, to appear 1996.

\bibitem{61}
Diekmann, R, R. L\"{u}ling, and J. Simon, ``Problem independent
distributed simulated annealing and its applications,'' in Applied
Simulated Annealing, R. V. Vidal (ed), Lecture Notes in Economics and
Mathematical Systems, Springer 1993.

\bibitem{3}
Dowsland, K., Using Simulated Annealing for Efficient Allocation of
Students to Practical Classes. Stat and OR Group, EBMS, Univ College
of Swansea, UK, 1993.

\bibitem{4}
Dowsland, K. and J. Thompson, 
``Variants of Simulated Annealing for
the Examination Timetabling Problem,'' Working Paper, Statistics and
OR Group, European Business Management School, Swansea SA2 8PP,
UK. (1994) 

\bibitem{49}
Eiselt H. A, and G. Laporte, ``Combinatorial Optimization Problems
with Soft and Hard Requirements,'' {\it J. Operational Research Society},
vol. 38, No. 9, pp. 785-795, 1987.

\bibitem{SalehMFA}
Elmohamed, S., G. C. Fox, P. Coddington, ``Course Scheduling using 
Mean-Field Annealing, Part I: algorithm and Part II: implementation,'' 
Northeast Parallel Architectures Center technical report, 
Syracuse University, 1996.

\bibitem{patat97}
S. Elmohammed, P.D. Coddington and G.C Fox, 
``A comparison of annealing techniques for academic course scheduling'',
Northeast Parallel Architectures Center technical report SCCS-777, 
submitted to {\sl PATAT'97}, the 2nd international conference on 
the Practice and Theory of Automated Timetabling.

% \bibitem{16}
% Forest, W
% {\it Ensemble of Simulated Annealing}, SDSC, San Diego, California, 1994.

% \bibitem{65}
% Fox, G. C, M. Johnson, G. Lyzenga, S. Otto, J. Salmon, and D. Walker, 
% Solving Problems on Concurrent Processors, vol. 1, Prentice-Hall 1988.

\bibitem{25}
Even, S,  A. Itai, and A. Shamir,
``On the complexity of the timetable and multicommodity flow problems,'' 
% {\it SIAM Jr. Computing} 5 (76), 691-703.  %??
{\it SIAM J. Computing} 5 (76), 691-703.

\bibitem{12}
Gary, M. and Johnson, D.
Computers and Intractability: A guide to the theory of
NP-completeness. Freeman, San Francisco (1979).

\bibitem{23}
Gee, A. H. and  R. W. Prager,
``Polyhedral combinations and neural nets,'' (May 1992),
CUED/F-INFENG/TR-100, Cambridge Univ. Engineering Dept, Cambridge
University, UK.
%  published??

\bibitem{45}
Gee, Andrew, private communication.
% Is there any preprint for this work yet?

\bibitem{27}
Gisl$\acute{e}$n, L, Bo S$\ddot{o}$derberg, C. Peterson, 
``Teachers and Classes with Neural Nets,'' 
{\it Inter. Jr. of Neural Systems} 1, 167 (1989).

\bibitem{28}
Gisl$\acute{e}$n, L, Bo S$\ddot{o}$derberg, C. Peterson, 
``Scheduling High Schools with Neural Nets,'' Lund 
University Preprint LU-TP-91-9, Lund, Sweden (1991),
(appeared in Neural Computation 1992).

\bibitem{5}
Gosselin and M. Truchon, ``Allocation of Classrooms by Linear
Programming,'' {\it Journal of Operational Research Society} 37, 561
(1986).

\bibitem{29}
Hertz, A,
``Tabu search for large scale timetabling problems,'' {\it European
Journal of Operational Research} 54, 39-47, 1991.

\bibitem{38}
Hertz, A, ``Finding a feasible course schedule using Tabu search,''
{\it Discrete Applied Mathematics} 35, 255-270, 1992.

\bibitem{66}
Hogg, T,  B. Huberman, and C. Williams (editors), Artificial
Intelligence, special issue on {\it Phase transitions and the search
space}, 81, 1996.

\bibitem{32}
Hopfield, J. J, and D. W. Tank, 
``Neural Computation of Decisions in Optimization Problems,''
{\it Biological Cybernetics} 52, 141 (1985).

\bibitem{59}
Huang, M,  F. Romeo, and A. Sangiovanni-Vincentelli, ``An efficient
general cooling schedule for simulated annealing,'' IEEE International
Conf. on Computer Aided Design (ICCAD), 1986, pp. 381-384.

% \bibitem{20}
% Johnson, D,
% ``Local Optimization and the TSP,'' {\it Springer Lecture Notes in
% Computer Science} 443, 446-461, Springer-Verlag, 1990.

\bibitem{19}
Johnson, D, C. Aragon, L. McGeoch, and C. Schevon,
``Optimization by Simulated Annealing: an Experimental Evaluation, Part
I (Graph Partitioning),'' {\it Operations Research} 37, 865-892 (1989).

\bibitem{42}
Johnson, D, C. Aragon, L. McGeoch, and C. Schevon,
``Optimization by Simulated Annealing: an Experimental Evaluation, Part
II (Graph Coloring and number partitioning),'' {\it Operations
Research} 39, No. 3, 865-892 (1991).

\bibitem{51}
Johnson, D, and L. McGeoch, ``The Traveling Salesman
Problem: A Case Study in Local Optimization,'' in Local Search in 
Combinatorial Optimization, E. H. Aarts and J. K. Lenstra (eds.), 
Wiley and Sons. (to appear in 1997).

\bibitem{52}
Kirkpatrick, S, C. D. Gelatt, Jr., and M. P. Vecchi, ``Optimization by
Simulated Annealing,'' {\it Science} 220 (13 May 1983), 671-680.

\bibitem{53}
Kirkpatrick, S, ``Optimization by simulated annealing: Quantitative
studies,'' {\it J. Stat. Physics} 34 (1984), 976-986.

\bibitem{10}
Ladkin, P. and R. Maddux,
``On binary constraint problems,'' {\it Journal of the ACM} 41 (1994),
pp. 435-469.

\bibitem{33}
Leighton, F. T,
``A graph coloring algorithm for large scheduling problems,'' {\it
Journal of Research of the National Bureau of Standards} 84, 1979,
489-506.

% \bibitem{48}
% Lin, S, and B. Kernighan, ``An effective heuristic algorithm for the
% traveling salesman problem,'' {\it Operations Research}, 21 (1973),
% 498-516.

\bibitem{7}
Lister, R.,''Annealing Networks and Fractal Landscapes,''  {\it Proc. IEEE
Int. Conf. on Neural Nets}, March 1993, Vol. I, pp 257-262.

% \bibitem{63}
% Lundy, M, and A. Mees, ``Convergence of the annealing algorithm,''
% Mathematical Programming, 34, 111-124, 1986.

\bibitem{11}
Mackworth, A. K,
``Consistency in networks of relations,'' {\it Artificial
Intelligence} 8 (1977) pp. 99-118.

\bibitem{1}
Miner, S., S. Elmohamed, and H. W. Yau, ``Optimizing Timetabling
Solutions Using Graph Coloring,'' 1995 NPAC REU program, NPAC, 
Syracuse University, 1995.

\bibitem{9}
Montanari, U., ``Networks of constraints: fundamental properties and
applications to picture processing,'' {\it Information Sciences} 7
(1974), pp. 95-132. 

\bibitem{8}
Mouritsen, O. G., Computer Studies of Phase Transitions and Critical
Phenomena, Springer-Verlag, Berlin, 1984.

\bibitem{60}
Otten, R, and  L. van Ginneken, The Annealing Algorithm, 
Kluwer Academic Publishers, 1989.

\bibitem{26}
Peterson, C, and Bo S$\ddot{o}$derberg,
``Artificial Neural Networks and Combinatorial Optimization
Problems,'' To appear in {\it Local Search in Combinatorial
Optimization,} E.H.L. Aarts and J.K. Lenstra, eds. Wiley and
Sons. (to appear 1997)

\bibitem{26.1}
Peterson, C, and Bo S$\ddot{o}$derberg,
``A New Method for Mapping Optimization Problems onto Neural Nets'',
International Jr. of Neural Systems 1, 3 (1989).

\bibitem{50}
Schaerf, A, ``A survey of automated timetabling,'' Department of
Software Technology, Report CS-R9567, CWI, Amsterdam, The Netherlands.

\bibitem{14}
Shrijver, A,
Theory of Linear and Integer Programming, John Wiley and Sons, 
Chichester, UK, 1986.

\bibitem{15}
Shrijver, A,
A Course in Combinatorial Optimization, to appear in 1997.
% details??

\bibitem{64}
Thompson, J, and K. Dowsland, ``General Cooling Schedules for
Simulated Annealing Based Timetabling Systems,'' Proceedings of the
1st International Conf. on the Practice and Theory of Automated
Timetabling, Napier Univ., Edinburgh 1995.

\bibitem{17}
van Laarhoven, P. J. and E. H. Aarts,
Simulated Annealing: Theory and Applications. D. Reidel,
Dordrecht (1987).

% \bibitem{56}
% Verhoeven, M. G. A, and E. H. L. Aarts, ``Parallel local search
% techniques,'' Manuscript, Philips Research Laboratories, Eindhoven,
% The Netherlands, 1994.

\bibitem{41}
White, S. R, ``Concepts of scale in simulated annealing,''
{\it Proceedings of the IEEE Int. Conference on Circuit Design}, pp 646-651,
(1984). 


\end{thebibliography}
\end{document}

