\documentclass[11pt]{article}
\usepackage[dvips]{epsfig}

\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}

\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 Discussion Notes}  % Remove for submission to journal
\end{flushright}
\vspace{1cm}

\begin{center} 

{\LARGE\bf 
Notes on Parallel and Distributed Computing
}
\vspace{5cm}

{\large
Saleh Elmohamed\\}
\vspace{.5cm}
Northeast Parallel Architectures Center\\
Syracuse University, Syracuse, NY 13244-4100\\
\vspace{.25cm}
saleh@npac.syr.edu\\
\end{center}

%%\vspace{1cm}
%%\centerline{March 11, 1997}

%%\vspace{1.5cm}
%%\centerline{ABSTRACT}
%%A set of notes on programming models as well as various theoretical
%%and practical aspects of parallel and distributed computing.

\newpage
\pagestyle{empty}

\tableofcontents
\newpage
%% \listoffigures
%% \listoftables

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{On Parallelism}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{page}{1}

\subsection{Principles}

Principles of parallel computing are as follows:
\begin{itemize}
\item Parallelism and Amdahl's Law. 
\item Granularity. 
\item Locality. 
\item Load balance. 
\item Coordination and synchronization. 
\item Performance modeling. 
\end{itemize}

\subsection{Motivations}

Here are few of the main reasons for looking into parallelism: 
\begin{itemize}
\item It provides an interesting alternative computing paradigm. 
\item It applies at all levels of system design. 
\item It is an interesting perspective from which to view
  architecture.
\item It is becoming increasingly central in information processing.
\end{itemize}

Parallelism is exploited at several levels: 
\begin{enumerate}
\item Instruction-level parallelism.
\item Multiprocessor servers.
\item Large-scale multiprocessors (MPPs).
\end{enumerate}

Our focus in these notes is on the multiprocessor level of
parallelism.

\subsection{Limits on Performance}

It is well-known that the performance of any parallel program is
limited by the following factors:
\begin{itemize}
\item Available parallelism. 
\item Load balance: This basically means that some processors work
  while others wait due to insufficient parallelism or unequal size 
  tasks. Few examples of unequal size tasks are:
\begin{enumerate}
\item The problems are fundamentally unstructured. 
\item Adapting to only the "interesting parts of the domain". 
\item Dealing with trees-structured computations. 
\end{enumerate}
\item Extra work of managing parallelism and dealing with redundant
  computation.
\item Communication.
\end{itemize}

\newpage

\subsection{Parallel Machines and Programming Models}

The key three models are:
\begin{enumerate}
\item {\bf Hardware-based}: Shared Memory Architecture. {\bf
    Software-based}: Shared Address Space.
\item {\bf Hardware-based}: Distributed Memory Architecture. {\bf
    Software-based}: Message Passing.
\item {\bf Hardware-based}: SIMD (Single Instruction Multiple Data)
  Architecture. {\bf Software-Based}: Data Parallel.
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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: 

\begin{quote}
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.
\end{quote}

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 solution to a
given 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}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.

% Why is this??
% EXPLAIN this, that you are penalizing for assigning small classes to
% large auditoriums. But this penalty should be MUCH SMALLER than the
% penalty for exceeding the room size. Is it?
% Explain choice of parameters.

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), 
$s(c_i)$ the starting time of $c_i$,
$end(c_i)$ the end time of $c_i$, $len(c_i)$ 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. 

\be{exclusion-constraint}
C_x =
\fourif {0.0} {\text{if} (s(c_i) > s(c_j))\, \text{and} \, (end(c_i) + \epsilon \geq
s(c_j))\,,}
{0.0} {\text{if} (s(c_j) > s(c_i))\, \text{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

% FIX??
% cases for setting to 0 make no sense.
% EXPLAIN what epsilon is
% is the penalty a large constant plus or times Cx? If not, why not? 

% ADD something based on the following??

%% In regard to the overlap: the schedule or the distribution of the
%% classes in the schedule or at least over a single day is not
%% completely glued with each but have various free or break
%% periods. These periods are generlly short, much shorter than the
%% least class duration but long enough to at least allow students and
%% profs to go from scheduled class to another. Also allow students to
%% vacate  a room before the start of another scheduled class in the
%% same room. So if for class1 and class2 there is an overlap and this
%% overlap is only a fraction of the break period that is prior to
%% class1 and the break period that is immediately following class2
%% (or can be some of fraction of the combined length of the two
%% periods), then class1 could start a little earlier or the second a
%% little later or maybe both, the first earlier and the seond
%% later. Doing it this way there won't be any need in swapping
%% classes over different time slots which will affect other
%% classes which in turn affecting others, etc. throughout the
%% schedule.   ... This kind of small shifting is actually done by our
%% simulation.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 a student to be in two
different classes at the same time). However we consider these
constraints  to be medium rather than hard if it is possible to relax
the constraints by 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 schedule the
number of classes requested, even using the list of 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 Avoid time conflicts for classes with students in common.
\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 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 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 Balance or spread out the lectures over the week.
\item For each student, balance the three-day ({\it Mon, Wed, Fri}) 
      as well as the two-day ({\it Tue, Thu}) schedules.
\item Classes may request contiguous time slots.
\item Balance enrollment in multi-section classes.
\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.

% CHECK
% FIX?? This is still bogus notation - Saleh and Paul to fix
% EXPLAIN why is the cost defined like this??

% % Let $B$ denote the set of all $k$ buildings, 
% $D$ denote the set of all $n$ departments, $\bar{m}<x,y>$ is the
% distance  between department $x$ and building $y$, and $dist$
% denotes distance. 
% Now, for each $d_i \in D$ where $1\leq i \leq n$,
% $dist(d_i)$ = $\bar{m}<d_i,b_j>$ for ${1 \leq j \leq k}$ of
% $Q$. Also, let $dist(d_i)_{min}$ = minimum of
% $\bar{m}<d_i,b_j>$ for ${1 \leq j \leq k}$, $i \neq j$ of $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}^k
% \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


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

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

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

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

Note that throughout the scheduling process, the denominator of equation
\ref{dist-cost} stays fixed while the numerator may change.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \subsection{Cost Function and the Solution Space}
\label{CostFunction}
\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.
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; not having the classes evenly spread
out over the week; having to schedule a class from the list of
alternates rather than the list of first preferences; or classes that
do not satisfy eligibility criteria.

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

\end{itemize}

Each of the terms in the cost function are assigned different 
weights~\cite{64}, % CHECK - is this the right paper?? 
in order to quantify the relative importance of the corresponding constraints.
For example, hard constraints should be weighted so that their cost is much
greater than the medium constraints, which should similarly be weighted to have 
higher costs than the soft constraints.
The values of each of the terms for the constraint costs need to be 
taken into account when specifying the weights. 
For example, soft constraints involving the students
require summing the cost over all students, which will usually be much larger 
than the equivalent sum over all professors, since the number of professors
is much smaller than the number of students. However, constraints involving
professors are usually given a higher cost than constraints involving 
students, in which case the weights for the professor costs will need to be 
much larger than the weights for the student costs.

What we have done is to select individual weights based on the relative 
importance of the various constraints of a particular type (hard, medium, 
and soft), and then included an additional overall weighting factor for each 
type of constraint, with the weighting factor for hard constraints being much 
larger than for medium constraints, which in turn is much larger than for soft 
constraints.


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

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 is no known algorithm that can find an optimal solution
in a time that is bounded by a polynomial of the problem size.
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. 

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. Clearly the problem becomes intractable even for very small
numbers of variables.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{PreviousApproaches}
\subsection{Previous Approaches}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Most of the previous work on academic scheduling has addressed only a
subset  or simplified version of the problem, such as examination
scheduling,  or the smaller scale (but still very difficult) problem
of high school class scheduling, which does not require dealing with
student preferences (for more information, see the reviews by de
Werra~\cite{21} and Shaerf~\cite{50}).

Traditionally, the approach to the timetabling problem 
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, JohnsonExam, Dige, Eglese},  
genetic algorithms \cite{37}, and tabu search \cite{29, 38, 62} 
have been used to tackle various instances of the timetabling problem,
with varying degrees of success. 
% ADD more refs here??

Simulated annealing has been successfully used for scheduling examinations
\cite{4, JohnsonExam}, laboratories \cite{3}, conference seminars \cite{Eglese}
and high school classes \cite{18, Dige}, but not to our knowlege for
the more complex problem of  university class scheduling.

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

The timetabling problem we have studied 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.

We have adopted a multi-phase approach to tackle the the timetabling
problem \cite{50,64}. 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.
Simulated annealing is a very time-consuming, computationally intensive 
procedure, so it is a good practice to start at a good point in the search 
space or with a partial solution. 
A good starting point allows the annealing to begin at a lower temperature, 
provides faster convergence, and usually a better final solution.
Using a rule-based preprocessor is a way of quickly providing such a 
starting point for the annealing process. 

% Is this OK?? DO they use a rule-based system in the first phase??
Our multi-phase approach is similar to that of Thomson and Dowsland \cite{64} 
to the problem of exam scheduling, in which they use a rule-based system to 
solve the hard constraints, and then use simulated annealing to minimize the 
cost of the soft constraints, while continuing to satisfy the hard constraints. 
Solving the hard constraints is much more difficult for the course scheduling
problem, and we are only able to obtain a partial solution using the rule-based 
system in the initial phase (the preprocessor).
We have also used a variant of the rule-based system to choose the new trial 
states for the annealing algorithm. This rule-based system only selects trial 
states that satisfy the hard constraints, while the annealing algorithm takes 
care of the optimization of the medium and soft constraints. In effect, we are
continuing the multi-phase approach at each iteration of the annealing 
algorithm.

To use simulated annealing effectively, it is crucial to use a good 
cooling schedule, to allow the temperature to be reduced as quickly as 
possible while keeping the system close to equilibrium, and also to
use a good method for choosing new trial states,  in order to
efficiently sample the search space.  We have experimented with
different approaches in both these areas,  and these are discussed in
section~\ref{SimulatedAnnealing}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{Rule-BasedSystem}
\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 modified version of this
system us used to provide sensible  choices for moves in the annealing
algorithm, rather than choosing the moves 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.

% CHECK - is this a good description of how it works??
%%%% yes ...
The rule-based system uses an iterative approach. The basic procedure for
each iteration is as follows. 
The scheduling of classes is done by department, so each iteration consists 
of a loop over all departments. The departments are chosen in order of size,
with those having the most classes being scheduled first.
The system first loops over all the currently unscheduled classes,
and attempts to assign them to the first unoccupied room and timeslot that 
satisfies all the rules governing the constraints.  The classes are
chosen in a specific order. We chose to separate 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.
Also, since constraints involving capacity of rooms are very difficult to 
satisy, larger classes are scheduled first, to try to avoid not having
large enough rooms later for those class sections with large enrollments. 

In some cases the only rooms and timeslots that satisfy all the rules will
already by occupied by previously scheduled classes. In that case, the 
system attempts to move one of these classes into a free room and timeslot,
to allow the unscheduled class to be scheduled.
% CHECK - Do you ever swap unscheduled with scheduled classes??
%         What about 3-way swaps?? How do they work??
%%%
%  Yes, swapping is done between two already scheduled classes as well as
%  scheduled and unscheduled classes. Swapping between
% unscheduled and scheduled classes was done based mainly on two
% conditions or criteria: first, if the size of the unscheduled
% class would match more closely to the size of the assigned
% room. Second, there is more match or correspondence between the
% desired time of the unscheduled  class and those occupied time
% slot(s) ... That is if the room is  occupied by a class with a
% requested time falling in another time  period or off by a number of
% time slots then it preferrable to swap it with perhaps unscheduled
% class  that would go into that period, and then see if a suitable room
% would become available within the correct time period for the
% swapped out class ... If course, not every course would be scheduled
% exactly in its requested time period due to lack of rooms, etc. 
% There are many classes in the data that have no desired or rquested
% time period so this gives us a bit of leaway or flexibilty during the
% swapping process.
% I'm not quite clear about your question regarding 3-way swap.

Next, the system searches through all the scheduled classes, and selects 
those that have a high cost, by checking the medium and soft constraints 
such as how closely the room size matches the class size, how many students 
have time conflicts, whether the class is in a preferred time period or a
preferred building, and so on. Selecting threshold values for defining what is 
considered a ``high'' cost in each case is a subjective procedure, but it is
straightforward to choose reasonable values. When a poorly scheduled 
class is identified, the system searches for a class to swap it with, so 
that the hard constraints are still satisfied, but the overall cost of the 
medium and soft constraints is reduced.
% CHECK - Do you actually compute the cost, or is it just done by
% rules??
% No `cost''  -as in the case of SA- is computed ... Things that are
% computed, for example, differences between distances of depts and
% buildings, or differences between size of room and class enrollments
% and the ratio between two sets of sizes and enrollments, etc. Also
% differences between requested times and available time periods or
% slots and whether one ratio is smaller 
% or larger for one class than for another (the two would be involved
% in the swap...) 
% So, yes, all this is computed in the context of rules, that is if
% certain condition(s) are met then certain things would be inferred,
% etc.

% CHECK - Does it try to allocate classes to unscheduled slots, or
% just swap them??
% Initially, at the start of the scheduling process, classes would be
% allocated to time slots corresponding to their ``requested'' times
% ... Later, for example, if a large class need to be scheduled and no
% room is available for it, then swapping might take place between it
% and a class that is occuping a room within the same time period
% ... Of course, whether swapping or no swapping would take place 
% very much depends on those two conditions I mentioned above about
% the class size vs. room size and the correlation between any
% requested time those occupied time slots, etc.

% An observation: If at the beginning we start with a much fewer
% rooms and time slots but have the same number of classes, then it
% may become necessary to ``allocate'' as well as ``swap'' from the
% very start of the process ... That is ``optimization'' would take
% place much sooner than later. I guess we could afford to wait a
% little if we initially have more time slots as well as room of various sizes
% to deal with. 

Our strategy is to first try to swap a class with another class in the same 
department. If this cannot be achieved within the rules, we attempt to swap
classes within different departments in the same school, and finally we try
swaps between classes in different schools.
We refer to the first two types of swaps as local, 
while the third is considered global. Local swaps have the advantage that 
classes in the same departments or schools are associated with the same
subset of rooms that will usually satisfy constraints involving distance and
department preference, however global swaps are less likely to have students 
and professors in common, which may help alleviate time conflicts.
A department may specify that they do not want any classes scheduled outside 
their home buildings, so global swaps will not be used on their classes.

This process of swapping rooms continues provided all the rules
are satisfied and no ``cycling'' (swapping of the same classes) occurs. 
Once all the departments have been considered, this completes one iteration. 
The system continues to follow this iterative procedure until a complete 
iteration produces no changes to the schedule.


The rule-based system is usually unable to legally assign all of the classes,
and thus produces a partial schedule as an output, which is 
divided into two parts: 
a list of scheduled classes and their assigned rooms and timeslots; 
and a list of classes that could not be assigned due to constraint conflicts.
This is what is used as input for the simulated annealing program.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}
%
\begin{quote}
{\it IF [room(capacity) $>$ class(space-requested)] and [no time
conflict in this room]

THEN assign the room to the class.}
\end{quote}

\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}
%
\begin{quote}
{\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.}
\end{quote}

\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, which are used by
all, or priority rooms with a usage based on certain priority of
the class or the department, or special purpose rooms which are
only assigned to specific users.
Here is a sample of rules showing how these room categories are used:

\begin{quote}
{\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.}

\medskip
{\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.}

\medskip
{\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.}

\medskip
{\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.}

\medskip
{\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.}
\end{quote}



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

Simulated annealing (SA) has been widely used for tackling different 
combinatorial optimization problems, including academic timetabling problems 
\cite{3, 4, 18, 39, JohnsonExam, Dige, Eglese}, 
% ADD more refs here?? 
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 assigning a class to a timeslot and room or
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}. 

% 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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The mapping of timetabling problem into the SA algorithm
involves the following constructs:

\begin{enumerate}
\item a {\bf state} (or configuration) is a timetable with 
the following sets of variables:
\begin{itemize}
% CHECK that variable names don't clash??? 
% - C clashes (classes and cost) - change C for cost to E for energy??
% - P clashes (probability and professors)
% but classes and professors are not used except here, so this is OK?
% How do other papers deal with variable name clashes??
\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) function $E(P,C,S,R,I)$, 
as outlined in Section~\ref{CostFunction}.

\item a {\bf move} is the assignment of a class to a time period and a room, 
or swapping two classes $C_i$ and $C_j$, by exchanging their 
time periods $I_i$ and $I_j$ and/or classrooms $R_i$ and $R_j$.
\end{enumerate}

% ADD something like this, but extend to define exactly what the input data is. 
% Should this done elsewhere?? Perhaps in section 6.1??
%% What you mean? you mean the format of the input files? I don't
%% think that would be necessary. Why do that? we have a table giving
%% the size of all data that we have dealt with so I guess that should
%% do.

% FIX?? - instead of this, just say that annealing takes input data plus
% list of rooms that have not been scheduled by the preprocessor (if one
% is used).

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.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{AnnealingSchedule}
\subsection{The Annealing Schedule}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The effectiveness of simulated annealing depends greatly upon
the rate at which the temperature is changed, which is known as the
annealing (or cooling) schedule.
Three annealing schedules have been used in our experiments to 
update the temperature of the SA algorithm:
geometric cooling, adaptive cooling, and reheating as a function of cost.

The first annealing 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 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$), which are taken from the 
principles of statistical mechanics that are the foundation of the
simulated annealing technique. 
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 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}$.
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$. The average cost is just:
\be{T.2}
C(T) = \sum_{i} C_i P_i(T) \,,
\ee
where $P_i(T)$ is the probability of obtaining configuration $i$ at 
temperature $T$, and the sum is over all possible configurations. 
The Metropolis Monte Carlo update used in SA generates configurations with
a Boltzmann probability distribution \cite{Binder, 8, 60, 57, 41}: 
\be{T.1}
P_i(T) = {e^{-C_i \over {T}} \over \sum_j{e^{-C_j \over {T}}}} \,.
\ee
A particular run of the annealing program will generate (with probability 
$P_i(T)$) a set $\cal C$ of $N_T$ configurations $i$ at temperature $T$, 
from which an estimate $<C(T)>$ of the average cost can be computed using: 
\be{T.2b}
<C(T)> \, = \, \sum_{i \in {\cal C}} C_i / N_T \,.
\ee
Similarly, the average square cost can be computed as: 
\be{T.3}
<C^{2}(T)> \, = \, \sum_{i \in {\cal C}} C_i^2 / N_T \,.
\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 use efficient update moves that can sample the parameter 
space effectively, and have a reasonably high probability of being accepted. 

In our implementation, we have used a sophisticated rule-based system for 
choosing the moves, which is a modified version of the rule-based expert 
system used as the preprocessor for annealing, which is described in 
Section~\ref{Rule-BasedSystem}. 
Using the rule-based system ensures that all the trial moves satisfy the hard 
constraints, while the Metropolis update used in the annealing algorithm
takes care of minimizing the costs of the medium and soft constraints.

One of the main modifications to the rule-based system
is that while the version used in the 
preprocessor is completely deterministic, the version used in choosing the 
moves for annealing selects at random from multiple possibilities that 
satisfy the rules equally well.
Also, some of the rules dealing with the medium and soft constraints are
softened or eliminated here, since reducing the cost of these constraints 
is done using the annealing algorithm.   % CHECK - is this true??

% Well, what we do here is that we have many rule, some classifed to
% be ``hard'' rules or rules dealing with only hard constraints and
% others are ``medium'' rules or ``soft'' rules. So the system would
% have to satisfy all those conditions related to or dealt with by the
% hard rules and violation is not acceptable. In regard to those
% ``medium'' and ``soft'' rules: during the process of swapping not
% all or many of the ``conditions'' or premises of these rules may not
% be satisfied ... So here is an example for the soft rules:
% Each rule would involve looking at (n) things to be met in order for
% it to fire, so if the majority (> half) of these (n) conditions are
% not satisfied then no firing will occur. But if ``most'' of these
% conditions are satisfied then firing would go ahead ..
% Also, various ``tags'' of  weights would be associated with these
% rules so the higher the value of the tag is the ``harder'' the rule
% becomes and therefore the less likely that it would fire if one or
% more of its premises is violated. So, we could adjust up or down
% these tags to vary the ``hardness'' or ``softness'' of the rule.
% This works to certain extent but the drawback is that more and more
% rules are needed to count of all of the various combinations of
% conditions or ``premises'' possible ... It really is pretty
% complicated and easily we could write a full paper on it.
% The more time slots and rooms available the better the results are
% ... Well, I guess the same applies when using other systems ...

This extra freedom in choosing new schedules, plus the extra degree of 
randomness inherent in the annealing update, helps prevent the system getting
trapped in a local minimum before it can reach a valid schedule, which is the
problem with the standard deterministic rule-based system.

For class scheduling, a move involves assigning a class to an unused 
timeslot and room, or swapping two classes in time (timeslots) 
and/or space (rooms).
The simplest method for doing this is to choose the classes, timeslots and
rooms at random.
However this is impractical, since random allocation or swapping of classes 
will almost always violate one of the hard constraints or greatly increase the 
cost of the medium and soft constraints (especially if we already have a 
fairly good schedule), and will thus almost always be rejected in the 
Metropolis procedure. 
This simple method is therefore extremely inefficient, since a lot of
computation is required to compute the change in cost and do the
Metropolis step, only to reject the move in the vast majority of cases.

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 a new room is 
randomly chosen 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. A more effective strategy 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. 
A candidate new room for that class can then be chosen from this subset of 
feasible rooms, and the acceptance probability will be much higher, saving
time that would otherwise be wasted on moves that would just have been 
rejected by the Metropolis algorithm. This is precisely what is done by our
rule-based system (see Section~\ref{Rule-BasedSystem}), although 
rather than choosing at random from a list of feasible rooms that
obey the hard constraints, it goes a step further and attempts to chose 
the ``best'' available room, for example by selecting the room that most 
closely matches the size requirement, and preferentially selecting rooms from 
the home building of the department.

Using the rule-based system to select the moves means that 
the classes to be moved are chosen not at random, but following the
same rules used for the preprocessor, for example, unscheduled classes are
handled first, and classes are selected in order based on size. 
Since the classes are not chosen at random, it is very unlikely that the 
detailed balance criterion 
is satisfied for the Metropolis updates, which means that the
configurations produced at each temperature will not have a Boltzmann 
probability distribution \cite{Binder,8}.  % CHECK the references??
However we will assume that the actual distribution approximates a Boltzmann 
distribution well enough that certain standard annealing techniques that 
assume a Boltzmann distribution, such as adaptive cooling, will still be
effective.  
% CHECK - Refer to Otto and Williams work on simulated annealing??
% don't have this ref. Do you mean Otto and Martin's ??
%
% CHECK - is this a reasonable description??
% quite good and well-written.
Many of the rules used in the rule-based system address the medium and soft
constraints, in an effort to reduce the overall cost. In some cases these 
are relaxed in choosing trial moves for annealing, in order to allow a wider
selection of moves.  % CHECK - is this true??
% yes.
However most of them are still included (although sometimes in modified form),
since they generally improve the acceptance 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. 
We have done a few experiments to test modifications of these ``soft'' rules 
to try to improve the acceptance and the final results. 
For example, we found that
at high temperatures there is not much difference in the acceptance rate
between local (within the same school) and global (between different schools)
class swaps, and that most swaps are accepted. 
At low temperatures the acceptance is much lower, but about the same for 
local and global swaps. In the mid-range temperatures, local swaps have a 
slightly higher acceptance rate. Thus the rule of first attempting local
class swaps, then global swaps, works well with annealing.

% CHECK - any other tricks we should mention??

% I think this should be sufficient. We didn't cover every little base
% in details but certainly we covered all of the major ``bases'' and most of the
% associated ``sub-bases''. I guess we really need to direct our to
% the experimental results and put as much details there as possible 
% after I manage to get all those plots :-)

Generally, the rules used to choose the moves can be considered 
as heuristics for pruning the neighborhood or narrowing the search space,
which provides much more efficient moves, as demonstrated by the good
acceptance rates as shown in Figure~\ref{acceptance.vs.T}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 three different cooling schedules,
geometric cooling, adaptive cooling, and reheating based on cost.


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

% FIX - Explain exactly what the input data set was??
Our study case involved real scheduling data covering three semesters
at Syracuse University.
The size and type of the three-semester data set
is shown in Table~\ref{data.size}. 
Nine types of rooms were used:
auditoriums, classrooms, computer clusters, conference
rooms, seminar rooms, studios, laboratories, theaters, and
unspecified types. 
Staff and teaching assistants are considered part
of the set of professors. 
Third semester (summer) data was much smaller than other semesters, however 
there were additional space and time constraints and fewer available rooms. 

% CHECK - More examples??
Our data set is quite large in comparison to data used by other researchers. 
For example, high school data used by Peterson and colleagues \cite{27, 28} 
consists of approximately 1000 students, 20 different possible 
majors, and an overall periodic school schedule (over weeks). In the
case of Abramson {\it et al.} \cite{18}, their data set was created randomly
and was relatively small, and they stated that problems involving more
than 300 tuples were very difficult to solve. 
% FIX - don't use tuples, since definition has been removed??

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{sparseness.ratio} shows the sparseness ratio 
(see section~\ref{PreviousApproaches})
of the data for each of the three semesters.
For university scheduling, the sparseness ratio generally decreases as the
data size (particularly the number of classes) increases, 
so the problem becomes more difficult.
The first two semesters are of similar difficulty, whereas the third 
semester has fewer classes, and is sparser and relatively easier to solve.

Including student preferences makes the problem much harder, but these are
viewed as medium constraints and thus are not necessarily satisfied in a
valid solution.
% CHECK - How can sparseness by defined when student constraints are included?? 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Analysis of the Cooling Schedules}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The three cooling schedules used each have a number of tunable parameters,
such as the initial temperature, the rate of cooling and reheating, 
and the number of iterations at each temperature. 
We spent quite some time attempting to find optimal values for these
parameters. 

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. The initial temperature is
usually chosen to be the lowest possible value that still gives an 
acceptance ratio that is fairly close to 1. 
White~\cite{41} has suggested that a good value for the starting temperature
is the standard deviation in the cost at infinite temperature. 
% In our case, this gives a starting temperature of $T_{max}=???$. 

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. 
Figure~\ref{T0.vs.cost} shows the results of various runs using different
initial temperatures for geometric cooling and for adaptive cooling with 
reheating.
In both cases there is an optimal value of the initial temperature,
although using the optimal value appears to have much greater effect 
in the latter case.
% CHECK - Why is initial T so much more crucial for adaptive than geometric??
We have used this initial temperature value of $T_{max}=497$, 
for all of our runs. 
% CHECK - that use a preprocessor! Otherwise, what is used? White's value??
The acceptance ratio at this temperature value is approximately 0.6. 
%CHECK this value??
%ADD - comparison with value from White, which should correspond to 
% acceptance close to 1?? Note that acceptance is still pretty high?

We also need to specify a criterion for stopping the annealing procedure,
when it is believed that the solution is good enough that we do not expect 
to obtain much improvement by further cooling.
We used a standard stopping criterion \cite{19, 51}, whereby the run was 
terminated when no moves had been accepted for five steps 
(a step is a full Markov chain at a single temperature). 


The goal in choosing an annealing schedule is to reduce the temperature as
rapidly as possible while still keeping the system close to equilibrium at
each temperature. This is easy to do at high temperatures, where the system
equilibrates very rapidly, but near the phase transition the number of
iterations required to equilibrate increases dramatically. For an infinite 
system it actually diverges at the phase transition, while for a finite system
it increases as a power of the specific heat near the phase transition,
and as a power of the system size at the phase transition 
(this is referred to as ``critical slowing down'') \cite{Binder, 8}.
Johnson {\it et al.} \cite{51} noted in their SA implementation for the 
traveling salesman problem (TSP) that the number of iterations $N_T$
(or the size of the Markov chain) at each temperature 
needed to be at least proportional to the ``neighborhood'' size
in order to maintain a high-quality result. From our experiments
we found the same to be true for the scheduling problem, even though it is
very different from the TSP. In our case the neighborhood size can be taken
to be the number of classes.

A number of techniques have been suggested for dynamically determining when 
the system has reached equilibrium at a given temperature during annealing 
\cite{59,60}. 
% ADD - other refs??
However, for large systems such as we have used,
and particularly for temperatures near or below the phase transition, 
which are the most crucial, it is extremely difficult to determine when the 
system has equilibrated. We have therefore adopted an empirical approach.
The rate at which the temperature is decreased, and the number of iterations
at each temperature, are closely interrelated. For example, 
if we halve the number of iterations at each temperature value, 
but use twice as many temperature values, the results will be very similar.
We have attempted to find values for the combination of these two variables 
that keep the system close to equilibrium, and produce near-optimal results. 

For geometric cooling, the temperature reduction factor $\alpha$ 
is usually chosen to be in the region 0.9 to 0.99. 
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.  
We found good results if we set $N_T$ to be 
% proportional to??
the product of the number of classes (the system size) and the 
variance of the cost values.
% CHECK - should this be the specific heat ???
% ADD - Give approx number of iterations per temperature value??

For adaptive cooling, we set $N_T$ to be the same as for geometric cooling,
and did a number of runs with different values of the
parameter $a$, which controls the rate of cooling (see equation~\ref{T.6.1}).
Slower cooling (smaller $a$) should give better results, but there should
be a point at which further reduction of $a$ does not markedly improve the
result. Our aim is to identify this point, i.e. the largest value of $a$ 
(the fastest cooling) which still gives near-optimal results. 
Figure~\ref{a.vs.cost} shows the results of these runs, indicating a plateau
for $a$ less than about 0.0001. For our adaptive cooling runs we used 
$a=0.00011$. 

% CHECK - should this paragraph be included??
Some time could probably be saved at high temperatures by specifying $N_T$
using an adaptive approach based on one of the techniques for determining 
when the system has reached equilibrium \cite{59,60}. However when we use a
preprocessor, we do not start at a very high temperature, so this would not
be a great reduction in the overall simulation time.

The adaptive cooling and reheating methods both rely on the measurement of 
the specific heat, which is shown in Figure~\ref{CH.vs.T}. 
There is a clear maximum, indicating a phase transition. 
Reheating increases the temperature so that it is above the phase transition, 
which gives the system a better chance to change the structure of the schedule
and thus escape local minima. 

If the temperature increase used in reheating is very small or very large, 
the reheating should have little effect, so we expect to be able to find an
optimal value somewhere in between.
Figure~\ref{K.vs.cost} shows that there is indeed a clear optimum value
of the parameter $K$, which controls the amount of reheating 
(see equation~\ref{T.6}), and we have used this value in our reheating runs. 
% This value of $K$ corresponds to reheating to about ${1.?? T(C_H^{max}}$.
% ADD the correct number??

The cost as a function of temperature is shown in Figure~\ref{graph.3} 
for individual annealing runs using geometric and adaptive cooling.
The results are fairly similar, apart from the expected fluctuations in the 
region of the phase transition (maximum of the specific heat) at 
$log_2(T) \approx 3.5$,  %??
but on average the adaptive cooling gives better results, and is also faster. 

Figure~\ref{graph.5} shows the cost as a function of the number of steps
(temperature values),
this time for annealing runs using geometric cooling and adaptive cooling 
with reheating. 
Again, the two are quite similar, until we get towards the end of the runs,
at low temperature. Here the cost using geometric cooling reaches a plateau,
while the cost for adaptive cooling continues to decrease slightly,  
until the reheating kicks in, causing the procession of spikes. 
Note that the reheating phase results in a further reduction in the lowest 
cost, without substantially more computational effort.



\subsection{Scheduling Results}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% FIX this in light of new results??

Our overall results are shown in Tables~\ref{table.3.1} and \ref{table.4.1}. 
These tables show the percentage of classes that could be scheduled in 
accordance with the hard constraints.
In each case (apart from the expert system, which is purely deterministic),
we have done 10 runs with the same parameters (just different random numbers),
and the tables show the average of the 10 runs, as well as the best and worst 
results. 

As expected, each of the methods did much better for the third (summer) 
semester data, which is much sparser. Our results also confirm
what we expected for the different cooling schedules for simulated annealing, 
in that adaptive cooling performs better than geometric cooling, and 
reheating improves the result even further.

When a random initial configuration is used, simulated annealing performs
very poorly, even worse than the expert system. However, there is a dramatic
improvement in performance when a preprocessor is used to provide a good 
starting point for the annealing. In that case, using the best cooling
schedule of adaptive cooling with reheating as a function of cost, we are
able to find a feasible class schedule every time. None of the other cooling
schedules were able to consistently produce feasible schedules.

Student preferences are included only as medium constraints in our 
implementation, meaning that these do not have to be satisfied for a valid
solution, but they have a high priority. 
For the valid schedules we have produced, approximately $80\%$ of the student 
preferences were satisfied for the first two semesters, and $94\%$ for the
third semester.
This is quite a good result, particularly since other automated approaches do
not deal with student preferences at all, but we are aiming to improve upon it.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% FIX - explain or support this statement, or remove it??
% Also, we observed that the efficacy of starting annealing 
% from a good solution depends not only on the cost of that solution, 
% but also on how it was obtained, that is, on its structure. 
% For example, Johnson {\it et al}~\cite{19, 51}
% gave some thoughts and hypotheses on this subject,  
% but as far as we know we have not come across any kind of analysis on
% the topic.


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

The programs were all written in ANSI C, and the simulations 
were run on a number of IBM RS/6000 workstations, and on a 12-processor 
IBM SP2, which uses RS/6000 processors. 
For the SP2, individual jobs were run separately on different processors
using different sets of parameters, or different cooling schedules, or
just different random numbers. Note that with multiple processors, it is
possible to do many different annealing runs (using different random numbers)
and then chose the result with the lowest cost. 
In this way, parallel processing is used
not to speed up the time to obtain a result, but to obtain a better result
in the same amount of time.

For the first and second semester data,
the average time for running the preprocessor (the expert system) 
was about three hours, and the average
time for each simulated annealing run was approximately 22 hours for
geometric cooling and about 15 hours using adaptive cooling with reheating,
which means the program could be run overnight.
This is much faster than the current semi-automated procedure used at 
Syracuse University to produce a produce a final schedule for a semester, 
which involves substantial manual effort to iterate to a solution, and 
can take a few weeks.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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, including student preferences,
without requiring enormous computational effort.

We found that using a preprocessor to provide a good starting point for 
simulated annealing greatly improved the quality of the results. 
We used a fairly complex rule-based expert 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 \cite{1}, 
and just utilizing the schedule from the same semester for the previous year
should provide good results.

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. 
The rule-based system ensured that all the moves satisfied the hard
constraints, while the annealing process took care of minimizing the cost
of the medium and soft constraints.

As expected, for the simulated annealing, adaptive cooling performed better 
than geometric cooling, and using reheating improved the results even further.
The best results were obtained using simulated annealing with 
adaptive cooling and reheating as a function of cost, 
and with a rule-based preprocessor to provide a good initial solution.
Using this method, and with careful selection of parameters and update
steps, we were able to generate feasible solutions to the class scheduling
problem using real data for a large university. None of the other
methods were able to provide a complete feasible solution.

Our main conclusion from this work is that simulated annealing, in combination 
with a rule-based system, can be used to solve the complex class scheduling
problem at a large university, including student preferences. 
A similar approach should prove fruitful for other hard scheduling problems.
However, finding a valid schedule requires a good cooling schedule, 
optimized parameters, carefully selected update moves, 
and a good initial solution provided by a preprocessor. 
A poor implementation in any one of these areas could be the difference 
between the success and failure of this method.


\section*{Acknowledgments}

We would like to thank Andrew Gee and Martin Simmen 
for helpful comments and suggestions,
Seong-Joon Yoo for useful discussions on the preprocessing phase,
and Hon Yau for comments and suggestions on the paper.
The first author is very grateful for the valuable discussion and help
of Robert Irwin in converting and formatting the registration data
prior to the scheduling process. 
Many thanks go to 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
%%%%%%%%%%%%

% ADD results for no student preferences, to show how much easier the 
% problem is??


\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 the data set for each of the three semesters.}
\label{data.size}
\vspace{0.25cm}
\end{table}

\vspace{2.0cm}

\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{Sparseness ratios for the data sets for each of
the three semesters. Lower values indicate a harder problem.}
\label{sparseness.ratio}
\vspace{0.25cm}
\end{table}


\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l|l||c|c|c||c||}
\hline
           &             & Classes   & Classes   & Classes   & Preferences \\
 Academic  &  Algorithm  & Scheduled & Scheduled & Scheduled & Satisfied \\
 Semester  &             & (average) & (highest) & (lowest)  & (average)\\
           &             &    \%     &    \%     &    \%     &    \%  \\ 
\hline\hline
First  & SA (geometric)  &   65.0    &   67.5    &   56.8    &  48.7 \\
       & SA (adaptive)   &   67.8    &   70.1    &   61.2    &  56.0 \\
       & SA (reheating)  &   70.2    &   72.3    &   68.8    &  59.2 \\
       & Expert System   &   76.6    &   76.6    &   76.6    &  58.0 \\ 
\hline
Second & SA (geometric)  &   65.6    &   68.0    &   57.1    &  49.0 \\ 
       & SA (adaptive)   &   68.5    &   70.1    &   60.8    &  57.5 \\
       & SA (reheating)  &   75.1    &   77.7    &   70.8    &  60.0 \\ 
       & Expert System   &   79.0    &   79.0    &   79.0    &  59.5 \\ 
\hline
Third  & SA (geometric)  &   83.1    &   86.4    &   68.5    &  55.2 \\
       & SA (adaptive)   &   85.8    &   89.0    &   70.7    &  61.0 \\
       & SA (reheating)  &   91.2    &   95.2    &   85.0    &  65.1 \\ 
       & Expert System   &   96.8    &   96.8    &   96.8    &  64.5 \\ 
\hline
\end{tabular}
$$
\caption{Percentage of classes scheduled and student preferences satisfied. 
The averages and highest and lowest values for simulated annealing 
were obtained using 10 independent runs.
No preprocessor was used for simulated annealing.} 
\label{table.3.1}
\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 (adaptive)     &   92.80   &  94.20  &  85.00 \\
%                          & SA (cost-based) &   98.17   &   98.97  &   90.66   \\ \hline
% Second Semester & SA (geometric)  &   92.85   &   95.95   &   80.40 \\
%                               & SA (adaptive)    &   94.15    & 96.00  &  85.30 \\    
%                              & SA (cost-based) &   98.90   &   99.70   &   91.40   \\ \hline
% Third Semester  & SA (geometric)  &   96.51   &   97.90   &   88.90 \\
%                            & SA (adaptive)  &  98.00    &    99.00   &  92.00  \\
%                           & SA (cost-based) &   100.0   &   100.0   &   100.0   \\ \hline
% \end{tabular}
% $$
% \caption{[5] Percentage of scheduled classes, averaged over 10 runs of the
% same initial temperature and other parameters, for three terms using 
% {\it simulated anealing with an expert system as preprocessor.}
% \underline{both class and student constraints are used.}}
% \label{table.4}
% \end{table}

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l|l||c|c|c||c||}
\hline
           &             & Classes   & Classes   & Classes   & Preferences \\
 Academic  &  Algorithm  & Scheduled & Scheduled & Scheduled & Satisfied \\
 Semester  &             & (average) & (highest) & (lowest)  & (average)\\
           &             &    \%     &    \%     &    \%     &    \%  \\ 
\hline\hline
First  & SA (geometric)  &   93.9    &   95.1    &   85.2    &  69.0  \\
       & SA (adaptive)   &   98.8    &   99.2    &   95.0    &  77.0  \\
       & SA (reheating)  &  100.0    &  100.0    &  100.0    &  77.95  \\ \hline
Second & SA (geometric)  &   95.0    &   98.9    &   89.4    &  68.6  \\
       & SA (adaptive)   &   99.0    &   99.5    &   98.5    &  77.5  \\    
       & SA (reheating)  &  100.0    &  100.0    &  100.0    &  79.6  \\ \hline
Third  & SA (geometric)  &   97.6    &   98.9    &   90.9    &  79.0  \\
       & SA (adaptive)   &  100.0    &  100.0    &  100.0    &  93.7  \\
       & SA (reheating)  &  100.0    &  100.0    &  100.0    &  94.1  \\ \hline
\end{tabular}
$$
\caption{Percentage of classes scheduled and student preferences satisfied. 
The averages and highest and lowest values 
were obtained using 10 independent runs.
An expert system was used as a preprocessor for the simulated annealing.}
\label{table.4.1}
\end{table}


% FIX - Order the figures based on the order they are mentioned in the text??

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

\newpage
\vspace{0.25cm}
\begin{figure}[htb]
{\centerline{\epsfig{file=adaptive-and-geometric.TempLog2.vs.Cost.ps,height=280pt,width=280pt,angle=-90}}}
\vspace{1.0cm}
\caption{Cost vs. log (base 2) of temperature for simulated annealing using
geometric and adaptive cooling.}
% CHECK - should not include reheating, or it will skew the results. 
% OK
\label{graph.3}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
{\centerline{\epsfig{file=reheating-geom-Steps.vs.Cost.ps,height=280pt,width=280pt,angle=-90}}}
\vspace{1.0cm}
\caption{Cost vs. number of annealing steps for 
adaptive cooling with reheating and geometric cooling.}
% FIX - what's this next bit mean??
% 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{\epsfig{file=Log-T.vs.sigma_T-of-Cost.ps,height=280pt,width=280pt,angle=-90}}}
\vspace{1.0cm}
\caption{Average specific heat vs. log (base 2) of temperature.}
% CHECK - is this averaged over 10 runs??
% CHECK - should not include reheating, or it will skew the results.
% CHECK - is this standard deviation, or variance, or specific heat??
% are these computed correctly?? why isn't std dev at high temp = good
% initial starting temp???
\label{CH.vs.T}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
{\centerline{\psfig{file=reheating-log-T.vs.avg-acceptance.ps,height=280pt,width=280pt,angle=-90}}}
% {\centerline{\epsfig{file=Adaptive.log_T.vs.same-diff-avg.ps,height=280pt,width=280pt,angle=-90}}}
\vspace{1.0cm}
\caption{Average rate of acceptance vs. log (base 2) of temperature 
for annealing using adaptive cooling.}
% CHECK - should not include reheating, or it will skew the results.
% OK
\label{acceptance.vs.T}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
{\centerline{\epsfig{file=Log-initial_T.vs.Final_cost.ps,height=280pt,width=280pt,angle=-90}}}
\vspace{1.0cm}
\caption{Initial annealing temperature vs. average final cost for 
adaptive cooling with reheating and geometric cooling.}
% Each of the final costs is an
% average of 10 runs at the given initial temperature.}  
\label{T0.vs.cost}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
{\centerline{\epsfig{file=a.vs.Final-Cost.ps,height=280pt,width=280pt,angle=-90}}}
\vspace{1.0cm}
\caption{Final cost vs. the value of the parameter {\it a}, which governs the 
rate of cooling in the adaptive cooling schedule.}
\label{a.vs.cost}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
{\centerline{\epsfig{file=K.vs.Final-Cost.ps,height=280pt,width=280pt,angle=-90}}}
\vspace{1.0cm}
\caption{Final cost vs. the value of {\it K}, which governs the amount of
reheating when using reheating as a function of cost.}
% CHECK value??
\label{K.vs.cost}
\end{figure}


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

% FIX - put references into the correct format for whatever journal
% we submit this to. Which journal??
% Virtually all these entries need fixing, either for formatting, or
% they are incomplete, or need updating (check for publication details 
% of all tech reports)


\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; 
``Simulated Annealing Cooling Schedules for the School Timetabling
Problem,'' submitted to Asia Pacific Journal of Operations Research,
1996.

\bibitem{Binder}
Binder, K. ed., 
Monte Carlo Methods in Statistical Physics, 
Springer-Verlag, Berlin, 1986.

% \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).
% CHECK - published??

\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.
% CHECK - published??

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

\bibitem{Dige}
Dige, P., Carlos Lund and Hans F. Ravn,
``Timetabling by Simulated Annealing,''
in Applied Simulated Annealing, R.V. Vidal ed., 
Lecture Notes in Economics and Mathematical Systems, Springer, 1993.

\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.
% Fix this?? Is it published??

% WHat about Dowsland's paper referenced in Schaerf??

\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) 
% Fix this?? Is it published??

\bibitem{Eglese}
Eglese, R.W. and Rand, G.K.,
``Conference seminar timetabling,'' 
{\it Journal of the Operational Research Society}, {\bf 38}, 591-598 (1987).

\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 SCCS-782, 
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{27}
Gisl$\acute{e}$n, L, Bo S$\ddot{o}$derberg, C. Peterson, 
% can you put ddots and acutes without making the letter be italizized??
``Teachers and Classes with Neural Nets,'' 
{\it Inter. J. 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).
% FIX -  WHat is the correct reference??

\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{JohnsonExam}
Johnson, D., 
``Timetabling university examinations,''
{\it Journal of the Operational Research Society} {\bf 41}, 39-47 (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.

% CHECK - is this used now?? What is the proper reference??
\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.
% FIX - 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{39}
Rene Vidal (ed), Applied Simulated Annealing, Lecture
Notes in Economics and Mathematical Systems no. 396, Springer-Verlag,
1993.

\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}

