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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\bibliographystyle{alpha}
\begin{center} 
{\LARGE\bf 
A Comparison of Annealing Techniques 
\vspace{0.2cm}
for Academic Course Scheduling
}
\vspace{1cm}

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

\vspace{1cm}
\centerline{\today}

\vspace{1.5cm}
\centerline{ABSTRACT}

In this study we have tackled the NP-hard problem of academic
class scheduling (or timetabling) at the university level.
We have investigated a variety of approaches based on simulated annealing, 
including mean-field annealing, simulated annealing with three different
cooling schedules, and the use of a rule-based preprocessor to provide a 
good initial solution for annealing.
The best results were obtained using simulated annealing with 
adaptive cooling and reheating as a function of cost, 
and a rule-based preprocessor.
This approach enabled us to obtain valid
schedules for the timetabling problem for a large university, using a 
complex cost function that includes student preferences. 
None of the other methods were able to provide a complete valid schedule.


\vspace{4cm} 
% \vfill

\noindent
Submitted to {\sl PATAT'97}, the 2nd international conference on 
the Practice and Theory of Automated Timetabling.

\vfill

\newpage
\pagestyle{empty}

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

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

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

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

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

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

We have applied the following optimization techniques to this problem: 
\begin{enumerate}
\item 
A rule-based expert system.
\item 
Mean-field annealing.
\item
Simulated annealing with geometric cooling.  
\item
Simulated annealing with adaptive cooling.  
\item
Simulated annealing with adaptive cooling and reheating as a function of cost. 
\item
Simulated annealing (using each of the three different cooling schedules) 
with a rule-based preprocessor to provide a good initial solution.
\end{enumerate}

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 moves,
we were able to generate solutions to the class scheduling problem using real
data for a large university. None of the other methods were able to provide
a complete valid solution.


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

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

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

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

\noindent
{\bf Hard constraints} are usually constraints that physically cannot be
violated. This includes events that must not overlap in time, such as:
\begin{itemize}
\item classes taught by the same professor,
\item classes held in the same room,
\item a class and a recitation or a lab of the same class.
\end{itemize}
%
Another examples are space or room constraints: 
\begin{itemize}
\item A class cannot be assigned to a
particular room unless the capacity of the room  
is greater than or equal to the class enrollment.
\item
Some classes, such as laboratories, require a certain type of room.
\end{itemize}


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

Medium constraints have a high penalty attached to them, although not as
high as that associated with the hard constraints. In the final
schedule the penalty of these constraints should be minimized and 
preferably reduced to zero. Some examples of medium constraints are:
\begin{itemize}
\item Avoid time conflicts for classes with students in common.
\item Eligibility criteria for the class must be met.  
\item Do not enroll athletes in classes that conflict with their sport
      practice time (of course, depending on the sport).
\end{itemize}

%%%%% Paul, check the following statement. Is it really clear or a
%%%%% little more need to be added ? ...
% One thing that we would like to point out
% is that these kind of constraints are considered to be medium only
% when scheduling classes, but when dealing with student scheduling we
% re-defined them to be considered as hard constraints.

\noindent
{\bf Soft constraints} are preferences that do not deal with time conflicts, 
and have a lower penalty (or cost) associated with them. We aim to 
minimize the cost, but do not expect to be able to reduce it to zero.
Some examples are:
\begin{itemize}
\item For each student, balance the three-day ({\it Mon, Wed, Fri}) 
      as well as the two-day ({\it Tue, Thu}) schedules.
\item Balance or spread out the lectures over the week.
\item Classes may request contiguous time slots.
\item Balance enrollment in multi-section classes.
\item Lunch and other break times may be specified.
\item Professors may request periods in which their classes are not taught.
\item Professors may have preferences for specific rooms or types of rooms.
\item 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.


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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Mean-Field Annealing}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
One of the potential drawbacks of using simulated annealing for hard 
optimization problems is that finding a good solution can often take an 
unacceptably long time. 
Mean-field annealing (MFA) attempts to avoid this problem by using a
deterministic approximation to simulated annealing, by attempting to average
over the statistics of the annealing process. 
The result is improved execution speed at the expense of solution quality. 
Although not strictly a continuous descent technique, MFA is closely related to
the Hopfield neural network~\cite{32}. 

Mean-field annealing has been successfully applied to high-school class 
scheduling \cite{28}. 
For scheduling, it is advantageous to use a 
Potts neural encoding to specify discrete neural variables (or neurons) 
for the problem.
This is defined in its simplest form as a mapping
of events onto space-time slots,  
for example events defined by a professor-class pair ($p,q$) are mapped onto 
space-time slots ($x,t$). 
Potts neurons $s_{pq,xt}$ are defined to be 1 if event ($p,q$) takes place in
the space-time slot ($x,t$), and 0 otherwise.
In this way, the constraints involved can be embedded in the neural net in 
terms of a Potts normalization condition such as $\sum_{x,t} S_{pq,xt} = 1$.

For a full derivation of the mean-field
annealing algorithm from its roots in statistical physics, see Peterson
{\it et al.} \cite{26.1}. 
Here we will give a brief overview, 
taking as our starting point the saddle point equations 
${\partial E^{'} \over \partial V_{ia}} = 0$ and 
${\partial E^{'} \over \partial U_{ia}} = 0$ 
which generate a set of self-consistency
equations in the mean-field (MF) variables ($E$ is the energy function):

\be{spe-1}
U_{ia} = - {1 \over T} {\partial E_{potts} \over \partial V_{ia}}
\ee

\be{spe-2}
V_{ia} = {e^{(U_{ia})} \over \sum_b e^{(U_{ib})}}
\ee

\be{tran-func}
g(u_i) = {1 \over {1 + e^{(-u_i / T)}}}
\ee

where $E_{potts}$ is the dominant energy function of the system. The
MFA algorithm involves solving equations \ref{spe-1} and \ref{spe-2} at a 
series of progressively lower temperature $T$: this process is known
as temperature annealing. The iterations of the MF dynamics over
equations \ref{spe-1} and \ref{spe-2} can either be synchronous or serial 
updating.
The solutions to \ref{spe-1} and \ref{spe-2} correspond to stable
states of the Hopfield network \cite{32} with transfer functions of
the form of equation \ref{tran-func} and $\eta = 1$, so both
techniques appear to be seeking the same solution points. 
Observe from equation \ref{spe-2} that at a MF solution the variables
respect a continuous version of the Potts condition (over all states $a$):

\be{potts-cond}
\sum_a V_{ia} = 1  \;\;\;\forall\;i 
\ee


\subsection{The Mean-Field Annealing Algorithm}

The generic MFA algorithm appears in Figure~\ref{MFA-algorithm}. 
Let $N$ denote the total number of the utilized neurons. 
At high $T$,
the mean-field solutions will tend to be states near to the
(symmetrical) maximum entropy state $V_{ia} = 1/N$. Conversely at low
$T$, finding a mean-field solution will be equivalent to using a local
optimization method on the internal energy -- a procedure highly
sensitive to the initial conditions and known to be ineffective \cite{32}.

These characteristics are similar to those of simulated annealing,
which is no surprise since both it and the mean-field method compute
thermal averages over Gibbs distributions of discrete states, the
former stochastically and the later through a deterministic
approximation. It is therefore natural to couple the mean-field method
with the concept of annealing from high to low temperatures. 

In addition to the structure of the energy function, there are three
major interdependent issues which arise in completely specifying 
a mean-field annealing algorithm for a timetabling problem:

\begin{itemize}
\item The values of the coefficients of terms in the energy function.
\item The types of dynamics used to find solutions of the mean-field
 equations at each $T$.
\item The annealing schedule details, i.e. the initial temperature
 $T(0)$, the rules for deciding when to reduce $T$ and
 by how much, and the termination criteria.
\end{itemize}

A quantity introduced by Peterson {\it et al.} \cite{28} is called 
{\it saturation}, $\Sigma$, defined as
\be{saturation}
\Sigma = {1 \over N} \sum_{ia} \nu^{2}_{ia} \;\; ,
\ee
to characterize the degree of clustering of events in time and/or
space;  clearly $\Sigma_{min} = {1 \over N}$ and $\Sigma_{max} = 1$.

\begin{figure}[htb]
\vspace{0.25cm}
\begin{center}
\begin{enumerate}
\item Choose a problem $\Longrightarrow$ (mapped into) $\{w_{ij}\}$.
\item Find the approximate phase transition temperature by linearizing
  equation (\ref{spe-2}).
\item Add a self-coupling $\beta$-term if necessary. Neural-wise, this
corresponds to a feedback connection from a neuron to itself.
\item Initialize the neurons $\nu_{ia}$ with ${1 \over N} \pm$ {\em
    random values}; and set $T(0) = T_c$.
\item Until ($\Sigma \approx {1 \over N}\sum_{ia}\nu^{2}_{ia}\geq 0.99$) do:
\begin{itemize}
  \item At each $T(n)$, update all $\nu_{ia}$ via $\upsilon_{ia}$:
  \begin{itemize}
    \item  $\upsilon_{ia} = - {1 \over T(n)} \cdot {{\partial
          E[\nu]} \over {\partial \nu_{ia}}}.$
    \item  $\nu_{ia} = {e^{\upsilon_{ia}} \over {\sum_b e^{\upsilon_{ia}}}}. \;\;\; (\equiv f_{ia})$
  \end{itemize}
  \item $T(n+1) = 0.9 \times T(n)$.
\end{itemize}
\item After $\Sigma \geq 0.99$ is reached perform a {\it greedy
 heuristics} if needed to account for possible imbalances or rule violations.
\end{enumerate}

\end{center}
\caption{The Generic Mean-Field  Annealing Algorithm}
\label{MFA-algorithm}
\vspace{0.25cm}
\end{figure}

In our implementation, at each $T_n$ the algorithm 
(Figure~\ref{MFA-algorithm}) 
performs one update per neural variable 
(defined as one sweep) 
with sequential updating using equations \ref{spe-1} and \ref{spe-2}. 
After reaching $\Sigma \equiv 0.99$ we check whether the
obtained solutions are legal, i.e. $E_{hard} = 0$. If this is not the
case the network is initialized with a different seed and is allowed to
resettle. We repeat this procedure a number of times until the best 
solution is found. 
A similar procedure was carried out on high-school
scheduling by Peterson {\it et al.} \cite{28}.

The MFA implementation was a little more complicated 
than the implementation of simulated annealing and the expert system, 
since it had many more parameters to handle, and it was 
often more difficult to find optimal values for these parameters.  
For example, one complication is the computation of the critical
temperature $T_c$, which involved an iterative procedure of a
linearized dynamic system.  On the other hand, we observed that the 
convergence time was indeed much less than any of the convergence times of
the simulated annealing using the three annealing
schedules studied. 
For more details on our MFA implementation, see Ref. \cite{SalehMFA}.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 other methods do in comparison to this standard technique. 
Secondly, a number of these rules are used to provide sensible choices for
moves in the simulated annealing algorithm, rather than choosing swaps 
completely at random.
Thirdly, we have used this system as a preprocessor for simulated
annealing, in order to provide a good initial solution.

It is a good practice, when using methods such as simulated 
annealing, to start at a good point in the search space or with a
partial solution, regardless of the difficulty or complexity of the
problem at hand. A good starting point generally provides
faster convergence and a better final solution. Our results clearly
support this rationale in this case. Simulated annealing is a very
time-consuming, computationally intensive procedure. Using an expert
system as a preprocessor is a way of quickly providing a good starting
point for the annealing algorithm, which reduces the time taken in the
annealing phase, and improves the quality of the result.

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, students 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 distances between buildings, 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.

There are many rules dealing with space and hours, type of room, and 
priority of room. Most of the rules implemented in the system are quite 
straightforward, for example, the following rule deals with time and space
conflicts for a room:

{\it IF [room(capacity) $>$ class(space-requested)] and [no time
conflict in this room]
THEN assign the room to the class.}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Simulated Annealing}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Simulated annealing (SA) has been
widely used for tackling different combinatorial optimization
problems, particularly academic scheduling \cite{39, 3, 4}. 
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 the
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 is given in \cite{57, 17}. It suffices here to say that the elementary
operation in the Metropolis method for a combinatorial problem such as
scheduling is the generation of some new candidate configuration,
which is then automatically accepted if it lowers the cost ($C$), or 
accepted with probability $\exp(-\Delta C /T)$, where $T$ is the
temperature, if it would increase the cost by $\Delta (C)$. Also, in
Figure~\ref{SA-algorithm}, $s$ is the current schedule and $s^{'}$ is
a neighboring schedule obtained from the current neighborhood  space
(${\cal N}_{s}$) by swapping two classes in time and/or space.

Thus the technique is essentially a generalization of the local optimization
strategy, where, at non-zero temperatures, thermal excitations can
facilitate 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 almost 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 heuristics, such as 
expert systems, forming quite useful hybrid methods for tackling a range of 
complex problems.
SA is a robust technique, however, it does have some drawbacks.
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.

Depending on the problem to which it is applied, 
SA appears competitive with many of the best 
%  local optimization methods, 
heuristics,
as shown in the work of Johnson {\it et al.} \cite{51}. 

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

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

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

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

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

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

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

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

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

Along with all of the necessary constraints, the simulated annealing
algorithm also takes as input data the following:  the preprocessor
output in the form of lists of scheduled and non-scheduled classes 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.

To use simulated annealing effectively, it is crucial to use a good 
cooling schedule, and a good method for choosing new trial schedules, 
in order to efficiently sample the search space. We have experimented
with both these areas, which are discussed in the following sections.

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

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

The first schedule we have 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. Our results obtained from using this standard cooling
schedule will be used as a baseline for comparison with those using
the other two schedules, which allow the rate of cooling to be varied.

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

Generally, in combinatorial optimization problems, phase transitions 
\cite{66, 8} can be observed as sub-parts of the problem are resolved. 
In some of the work dealing with the traveling salesman problem using 
annealing \cite{7}, the authors often observe that the resolution of the
overall structure of the solution occurs at high temperatures, and at
low temperatures the fine details of the solution are resolved.
As reported in \cite{2}, applying a reheating type procedure,
depending on the phase, would 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.

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 aforementioned maximum specific heat, we employ the
following steps \cite{2, 17, 60}.

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

At temperature $T$, the acceptance probability is: 
\be{T.1}
P_i(T) = {e^{-C_i \over {kT}} \over \sum_j{e^{-C_j \over {kT}}}} \,.
\ee

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

Therefore, the average square cost is: 
\be{T.3}
<C^{2}(T)> = \sum_{i \in {\cal C}} C_i^2 P_i(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 specific heat, i.e.
the standard deviation of all costs obtained at the current $T$. 
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 as follows: 

\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 large changes in the
standard deviation $\sigma$. 
We used the following standard method to provide a smoothed standard
deviation $\bar\sigma$:

\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

and set $\omega$ to $0.95$.
This smoothing function is used because it follows (from the form of the
Boltzmann distribution, see \cite{41}) 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 be used in conjunction with any cooling schedule.
We have used it with adaptive cooling.

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

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

The simplest method for choosing a move is to swap the rooms or
timeslots of two randomly selected classes. However this is extremely
inefficient, since most of the time random swapping of classes will
increase the overall cost, especially if we are already close to
obtaining a valid solution (i.e. at low temperature), and will likely
be rejected in the Metropolis procedure. This low acceptance of the
moves means this simple method is very inefficient, since a lot of
computation is required to compute the change in cost and do the
Metropolis step, only to reject the move.

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

In effect, we have embedded a simple expert system into the annealing
algorithm in order to improve the choice of moves, as well as using a more 
complex expert system as a preprocessor for the annealing step.

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

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

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


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

We spent quite some time finding optimal values for the various parameters 
for the annealing schedule, such as the initial temperature, 
the parameters controlling the rate of cooling 
($alpha$ for geometric cooling, $a$ for adaptive cooling)
and reheating ($K$), 
and the number of iterations at each temperature
(for more details, see Ref. \cite{SalehMFA}).
%
Johnson {\it et al.} \cite{51} noted in their SA implementation for the 
traveling salesman problem (TSP)
that the number of steps at each temperature (or the size of the Markov
chain) needed to be at least proportional to the ``neighborhood'' size
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. 
Furthermore, in a few tests for one semester we fixed the number of
classes and professors but varied the number of rooms and time slots, and
found that the final result improves as the number of iterations in
the Markov chain becomes
proportional to a combination of the number of classes, rooms and time slots. 
We also observed the same behavior when we fixed the number of rooms and
time slots but varied number of classes. 

Our study case involved real scheduling data covering three semesters
at Syracuse University. The size and type of the three-semester data
is shown in Table \ref{table.01}. Nine types of rooms were used:
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. Our data was 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. 

Table~\ref{table.01} lists all major components of the data we have used.
Timetabling problems can be characterized by their {\it sparseness}.
After the required number of lessons $N_l$ have been scheduled, there will be 
$N_{sp} = (N_x N_t - N_l)$ spare space-time slots, hence, the
sparseness ratio of the problem is defined as the ratio $N_{sp} / (N_x N_t)$. 
The sparser the problem, the lower the sparseness ratio, and the 
harder the problem is to solve.
Table~\ref{table-sparseness} shows the sparseness of the three-semester data.
For university scheduling, the sparseness ratio generally decreases as the
data size (particularly the number of classes) increases, 
so the problem becomes harder 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.

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. The MFA results are different only due to having different initial
conditions. 
Each simulated annealing run takes about 10-20 hours on a Unix workstation.

As expected, each of the methods did much better for the third (summer) 
semester data, which has a higher sparseness ratio. 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 (ES). 
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 valid class schedule every time.

In the case of mean-field annealing, the overall results 
are generally below those of SA and ES. In addition, we have
found in the implementation of this method that the results were quite
sensitive to the size of the data as well the type of constraints
involved. If we confine ourselves to the set of hard constraints, 
the results are as good as or even better than the other methods.
However if we take into account the medium and soft constraints, that is,
the overall cost function, this method does not perform as well.

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 $\%75$ of the student 
preferences were satisfied. This is reasonably good (particularly since 
other approaches do not deal with student preferences at all), but we are 
working to improve upon this result.


\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 simulated annealing was more effective than mean-field
annealing for this problem, and that using a preprocessor to provide a
good initial solution 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}, or it may be possible to just utilize the schedule
from the same semester for the previous year.

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 solutions to the class scheduling
problem using real data for a large university. None of the other
methods were able to provide a complete solution.

Mean-field annealing works well for small scheduling problems, but does 
not appear to scale well to large problems with many complex constraints.
It is more difficult to tune the parameters, and use a preprocessor to
take advantage of a good initial solution, than is simulated annealing.
Because of the complexity and size of the Potts neural encoding in MFA,
there seems to be no clear way of preserving the state of an initial 
configuration provided by a preprocessor when carrying out the Potts encoding. 

Our main conclusion from this work is that simulated annealing, with a 
good cooling schedule, optimized parameters, carefully selected update moves,
and a good initial solution provided by a preprocessor, can be used to 
solve the academic scheduling problem at a large university, including
student preferences. Similar approaches should prove fruitful for other
difficult scheduling.


\section*{Acknowledgments}

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. We also would like to thank Andrew
Gee and Martin Simmen for the useful comments and suggestions, and
Carsten Peterson for the pointers and comments about his
papers. 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 Prof. Ben Ware, Vice President for Research and
Computing at Syracuse University, for his support and encouragement.


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

\newpage

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

\vspace{2cm}

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


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

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

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

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l|l||c|c|c||}
\hline
Academic        &   Algorithm     & Scheduled  & highest   & lowest    \\
Time Period     &                 & (average)  & Scheduled & Scheduled \\
                &                 &    \%      &    \%     &    \%     \\ \hline\hline
First Semester  & SA (geometric)  &   65.00    &   67.50   &   56.80 \\
                          & SA (adaptive)     &   67.80    &   70.15  &  61.20 \\
                          & SA (cost-based) &   70.20    &   72.28   &   68.80 \\
                          &    ES       &      76.65   &   76.65   &  76.65\\
                          &    MFA    &       65.60  &   71.00      &   61.00            \\ \hline
Second Semester & SA (geometric)  &   65.65    &   68.00   &   57.10 \\ 
                              & SA (adaptive)     &   68.50    &  70.10   &   60.77 \\
                              & SA (cost-based) &   75.14    &   77.68   &   70.82   \\ 
                              &    ES       &      79.00   &   79.00   &  79.00\\
                              &    MFA    &       67.20           &   75.00       &  65.00             \\ \hline
Third Semester  & SA (geometric)  &   83.10      &   86.44   &   68.50 \\
                           & SA (adaptive)    &   85.80       &  89.00    &   70.75  \\
                           & SA (cost-based) &   91.20    &   95.18   &   85.00   \\ 
                           &    ES       &      96.80   &   96.80   &  96.80\\
                           &    MFA    &      88.00    &  95.00   &  82.00 \\ \hline
\end{tabular}
$$
\caption{Simulated annealing (SA) results: percentage of scheduled
  classes, averaged over 10 runs of the same initial temperature and
  other parameters for three terms.  Expert system (ES) results:
  percentage of scheduled classes is averaged over 10 runs. Mean-field
  annealing (MFA) results: percentage of scheduled classes is also
  averaged over 10 runs. {\it No preprocessor was used with the
  three methods.}}
\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||}
\hline
Academic         &   Algorithm     & Scheduled & highest   & lowest    \\
Time Period     &                 & (average) & Scheduled & Scheduled \\
                         &                 &    \%     &    \%     &    \%     \\ \hline\hline
First Semester  & SA (geometric)  &   93.90   &   95.12   &   85.20 \\
                          & SA (adaptive)     &   98.80   &  99.20  &  95.00 \\
                          & SA (cost-based) &   100.0   &   100.0  &   100.0   \\ \hline
Second Semester & SA (geometric)  &   95.00   &   98.95   &   89.40 \\
                               & SA (adaptive)    &   99.00    & 99.50  &  98.50 \\    
                              & SA (cost-based) &   100.0   &   100.0   &   100.0   \\ \hline
Third Semester  & SA (geometric)  &   97.60   &   98.88   &   90.90 \\
                            & SA (adaptive)  &  100.0    &   100.0   &  100.0  \\
                           & SA (cost-based) &   100.0   &   100.0   &   100.0   \\ \hline
\end{tabular}
$$
\caption{Percentage of scheduled classes, averaged over 10 runs of the
same initial temperature and other parameters, for three terms using 
simulated anealing {\it with an expert system as preprocessor.}}
\label{table.4.1}
\end{table}

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


\clearpage
\begin{thebibliography}{TTP}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\bibitem{SalehSA}
Elmohamed, S., P. Coddington, G.C. Fox, 
``Academic Scheduling using Simulated Annealing with a Rule-Based
Preprocessor'', 
Northeast Parallel Architectures Center technical report, 
Syracuse University, 1997.

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

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

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

% \bibitem{45}
% Gee, Andrew, private communication.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\end{thebibliography}
\end{document}

