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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\bibliographystyle{alpha}
\newpage
\begin{flushright}
{\sl DRAFT SCCS report ???}  % Get an SCCS number
\end{flushright}
\vspace{.75cm}
\begin{center} 
{\Large\bf 
Academic Scheduling using Simulated Annealing \\
with a Rule-Based Preprocessor
}
\vspace{1cm}

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

\vspace{1.5cm}
\centerline{ABSTRACT}

In this study we tackle the complex problem of academic class scheduling
(or timetabling) at the university level. The method used is simulated
annealing, with two different cooling schedules being implemented and
compared.   An expert system is used as a preprocessor before the
annealing, and this multi-phase approach greatly improved the results.
This enabled us to obtain valid schedules for the timetabling problem
for a large university using a complex cost function that includes
student preferences. 

\vfill
\noindent{\bf Key words : scheduling, timetabling, optimization, 
simulated annealing, reheating, cost functions, annealing schedule,
phase transition, rule-based system.}
% IS there a list of standard words to be used?? no.

\vfill
\centerline{\today}
\vfill

\newpage
\pagestyle{empty}

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

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

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

% EXPAND THIS???

The primary objective of this study is to derive an approximate solution
to a high-dimensional and non-geometric combinatorial optimization 
problem, namely academic scheduling at the university level. 

The academic scheduling or timetabling problem (TTP) has been tackled 
by many researchers \cite{54}, mostly in the field of operations
research. This is a very difficult problem due to its nature as a
multi-constraint satisfaction non-Euclidean combinatorial optimization
problem for which no particular heuristic or method has been shown to
produce good results for large-scale problems.

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. 
Hard constraints are physical 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.

Recently there have been a number of {\it non-conventional} (or novel)
methods utilized to tackle this problem from different angles.
Among them are neural networks \cite{32}, simulated annealing
\cite{39, 2}, genetic algorithms \cite{37}, tabu search \cite{38, 62}, and
various combinations of two or more of these techniques. 
None of these methods has been used on as large and complex a problem 
as we have addressed in this work, and with the exception of 
Refs \cite{32, 38}, none have used real-world academic scheduling data. 

We used data for classes at Syracuse University, which has over 
13000 students, 1000 professors, 400 classrooms, and 2500 classes to be 
scheduled each semester.
Currently this problem is handled by the university admissions office
in a semi-automated way. 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.

Our method for tackling this problem is simulated
annealing using two different cooling schedules: the standard
geometric cooling, and geometric reheating as a function of cost.
In addition, a rule-based (or expert) system
is used as a preprocessor in the application of each of these
schedules, which was found to greatly improve the quality of the solution. 
Using this method, we were able to find feasible solutions to the
complex academic scheduling problem for a large university.

% Check this ??
This paper is organized as follows.
In section 2 we give a brief review of the timetabling problem, and 
present the three categories of constraints along with examples of each.
Section 3 outlines
an approach to carry out optimization of the problem over integral
polytopes and in section 4 we describe our approach to deal with
the timetabling problem. 
Section 5 is on simulated annealing and the
mapping of the different TTP components onto the annealing cost
function. 
We describe the cooling schedules in section 6 and then discuss
our experimental results in section 7. Finally, in section 8 we
present a summary and conclusions.


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

A problem that does not have a well-defined objective
function (as in the traveling salesman problem (TSP), for example) to
optimize and belongs to the class of constraint satisfaction problems
is the NP-complete {\it teachers and classes} timetabling problem
\cite{2, 3, 27}. Briefly, the problem is stated as follows:

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Constraint Satisfaction Problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We now briefly describe the general constraint satisfaction problem
which has been widely studied in the Artificial Intelligence
community \cite{9, 10, 11}.

An instance of a constraint satisfaction problem consists of:
\begin{itemize}
\item A finite set of variables, $N_i$, where $i = 1, 2,\ldots,n\;$.
\item A domain D of possible values of $N_i\;$.
\item A set of constraints $\{C(S_1), C(S_2),\ldots, C(S_c)\;$, in
which each $S_i$ is an ordered subset of the variables, and each
constraint $C(S_i)$ is a set of tuples indicating the mutually
consistent values for the variables in $S_i\;$.
\end{itemize}

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

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

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

In a nutshell, 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. 
A constraint can be hard, medium or soft \cite{49}. 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.
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 {\it vertex coloring} in graph theory.
% Reference ??
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 of hard constraints are 
\begin{itemize}
\item {\it Room constraint}: 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. This 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.

\item {\it Exclusion constraint}: deals with any violation to the
given list of classes that 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:

% SIMPLIFY ??? 

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

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

\be{relative-length}
Rlen(c_i,c_j)=
\twoif {len(c_i) / len(c_j)} {\text{if} len(c_i) \geq
len(c_j)\,,}
{len(c_j) / len(c_i)} {\text{otherwise.}}
\ee
\end{itemize}

Also, there are hard constraints of relevance to students, such as:
\begin{itemize}
\item To sign up for a class it must be open.
\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}
These constraints have to be respected at all costs.

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

These kinds of constraints fall into the shaded region between the
{\it hard} and {\it soft} constraints in the sense that they do not
directly deal with time conflicts as do the hard type, but nonetheless
have a high penalty attached to them (though not as
high as that associated with the hard constraints). In the final
(legal) schedule the penalty of these constraints should be minimized and 
preferably reduced to zero.

In short, these kind of constraints should be satisfied but are
nevertheless relaxable. Some examples of medium constraints:

\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 Classes may be grouped with other classes.
\item The overall schedule should have as few ``holes'' as possible;
that is lessons should be glued together or the separating intervals
are as short as possible.
\item It is not the case, in general, that all classrooms are
available for all subjects. In reality, many subjects require a
special purpose rooms.
\end{itemize}

Constraints involving
classes that are not available during certain time period(s) due to the
unavailability of their instructors at those times are harder than
constraints of no overlapping classes involving common student(s). 


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

Like medium constraints, they also do not deal with time conflicts at
all but unlike the medium constraints, have a low penalty (or cost)
associated with them. Furthermore, this cost is lower than that of the
medium constraints and much lower than that of the hard ones. In
addition, in the final schedule, this cost is minimized but does not
often approach zero. Here are few examples of soft constraints:

\begin{itemize}
\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 groups of rooms.
\item {\it Distance constraint}: deals with the distance between where the
class is assigned and the building which is housing its home
department. Before actually stating what this constraint is we
will first outline how we have dealt with the aspect of distance. 

% CLARIFY???

Given the various building preferences of the departments, we
have constructed a matrix $M[I,J]$ between all the academic
departments $[I]$ and all the buildings involved in scheduling
$[J]$. Using this matrix in conjunction with the real -- appropriately
scaled -- distance, a final state matrix is derived and directly used
in the scheduling process. Therefore, unless otherwise indicated, for
a certain department the home building is always the first preference
where the department classes to be assigned.

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \subsection{Cost Function and the Solution Space}
\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. 

Let $C$ be the set of the given constraints. A {\it feasible} schedule 
is defined as a schedule that satisfies the set of hard constraints
$C^{'}$, where $C^{'} \subseteq C\;$.

% This is confusing and unnecessary
% On the question of determining whether a given constraint
% belongs to the set $C^{'}$ or not, roughly we follow this rule and
% that is, a class should never be assigned to a time period if such an
% assignment induces only class schedules that do not satisfy all of the
% hard constraints.

We consider the following as part of the abovementioned cost function:
\begin{itemize}

\item {\it Time period cost} includes the 
cost of class or classes assigned to that period, (for example, the
cost that result from having a certain class and its lab scheduled in
the same time period); cost of class spreading over the week and
within each of the weekdays; and cost of class glueing  % Define???
and filling in any holes of the timetable.

\item {\it Professor cost} includes the cost
incurred from  assigning more classes than the maximum number taught
by that professor;  cost from not having a long enough time interval
between classes taught by the same professor; and cost of assigning
to the same professor two or more classes that overlap in time. 

\item {\it Student cost} is the sum of various costs associated with
each student, such as eligibility criteria and number of classes taken
by the student.
% Clash of class times???

\item {\it Distance cost} is obtained from the distance constraint.

\item {\it Room size cost} is obtained from the room constraint. 
\end{itemize}

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

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

In general, scheduling problems are almost always NP-complete, which
means there exists no known polynomially bound algorithm for solving
them optimally. As a result, these problems are often solved by means
of {\it heuristics} -- solution procedures that focus on finding
a feasible schedule of ``good'' (as opposed to optimal) quality
within an acceptable amount of time.

% is the complexity analysis OK??
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 which represent the problem, and 
$2^{6000}$ possible states. The problem quickly becomes intractible as
the number of variables increases.

For the much simpler problem of {\it class allocation}, for which there
is no timetabling involved (i.e. no allocation of classes to time 
periods), the computational load ($n_c$) from tackling this problem
using the LP method scales as follows \cite{5, 28}: 

\be{complexity}
n_c \propto N_c N_x N_t\;\;,
\ee

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Some Methods of Tackling Timetabling}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Previous Work}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% ADD MORE ON PREVIOUS WORK???

% Clarify polytope stuff???

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

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

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

Timetabling problems can be characterized by their {\it sparseness}.
After all the required lessons have been scheduled, there will be $N_s
= (N_x N_t - N_l)$ spare space-time slots, hence, the sparseness of
the problem is defined as the ratio $N_s / (N_x N_t)$. The sparseness
decreases as  $N_s / (N_x N_t)$ goes to zero or as $N_s$ becomes
smaller and smaller. Furthermore, Gee \cite{45} notes that for sparse
problems, the probability of an arbitrary descent procedure converging
to an integral vertex is near one, though this falls off rapidly for
less sparse problems. For dense problems, there is an additional
correlation involving the problem size: as the problem gets larger
(more classes, teachers, rooms, students, etc.), the proportion of
integral vertices gets smaller. From this we could deduce that a
one-shot descent procedure, operating on an arbitrary ``objective
function'', is not likely to be very successful with difficult
constraint satisfaction problems, most probably converging to a
non-integral vertex of $P$, for example. On the other hand, any
``partial'' or ``imperfect'' solution to a timetabling problem found
by methods such as simulated annealing (using some good adaptive
schedules) is likely to be of some use. Since simulated annealing does
not search over the interior of the unit hypercube, but only over its
vertices, the solution it finds will be a unique timetable, possibly
violating few soft and/or medium constraints. As part of the
post-processing operation, for example we could at least remove some
lessons to obtain a valid (or legal) timetable which fulfills most of
the teaching requirements. 


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

We adopted a multi-phase approach to tackle the complex academic
scheduling problem \cite{49}.   % What is the reference???
In the first phase a partial solution (a feasible schedule for a subset 
of the classes) is found using a rule-based system. 
In the second phase this partial schedule is improved to obtain a
final feasible schedule, using simulated annealing. 

It is a good practice, when using techniques such as simulated 
annealing, to start at a good point in the search space or with a
partial solution, regardless of the difficulty or complexity of the
problem at hand. 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 a rule-based preprocessor is a way of quickly providing
a good starting point for the annealing process, which reduces the time
taken in the annealing process, and improves the quality of the result.

To use simulated anealing 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 these two areas, which is discussed in the following sections.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Rule-Based Preprocessor}
\label{preprocessor}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In the first phase, the preprocessing phase, we used a rule-based
system giving a partial feasible sschedule as an output. A
partial sschedule in the sense that due to constraint conflicts not all 
of the given classes were assigned to rooms and times slots. 
The preprocessor output was divided into two parts. The first part
consisted of classes, with their associated professors and students,
assigned to various rooms; and the second part was a list of classes
which could not be assigned due to time and/or space conflict. 

As mentioned above, this was an expert (rule-based) system consisting
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: first, distance
matrix of integer values between each academic department and every
other building under use for scheduling. Second, class data structure
of each class scheduled anywhere in campus. Also, these structures
are capable of linking with each other. Third, room data structure of each
room (regardless of type) involved in the scheduling process. Like
classes, room structures are also linked with each other. Fourth, data
structures for time periods to keep track of which hour or time slot
was occupied and which was not. Fifth, department inclusion data
structure giving department inclusion within other larger departments
or colleges.  

The basic function of the system is as follows: given data
files of classes, rooms and buildings, department-to-building distance
matrix, 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.


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

\noindent
{\bf Space and Hours}

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

THEN assign the room to the class.}

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

\noindent
{\bf Type of Room}

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

THEN
   assign the room to the class.}

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


{\bf Room Priority}

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

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

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

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

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

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

\item {\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{itemize}

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

Simulated annealing (SA), see Figure~\ref{SA-algorithm}, has been
widely used for tackling different combinatorial optimization
problems, particularly academic scheduling \cite{3, 4, 39}. 
% Is this previous work discussed???
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 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{17, 57}. 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)$ 
(see Figure~\ref{SA-algorithm}).
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 some advantages as well as some
disadvantages. Among its advantages are the relative ease of
implementation, the applicability to almost any combinatorial
optimization problem, depending on the cooling schedule(s) used it
usually provides reasonable solutions, and it can easily be combined
with other heuristics, such as rule-based systems, forming quite
useful hybrid methods for tackling a range of complex problems.
One major drawback of the algorithm is the requirement for long run
times.

SA is a robust technique and has been applied with success to a wide
variety of problems. However, to obtain good results the annealing
runs often require a great deal of computer time. Johnson et
al. \cite{19} criticized much of the earlier research for only 
comparing SA with the simpler local optimization
heuristics (i.e. those using r-Optimization, or r-Opt, style moves)
and not with the more competitive Lin-Kernighan (LK) heuristics
\cite{48}. They undertook a systematic comparison of the performance
of the above three methods on the graph bisection problem, for low
degree random and random geometric graphs. 
When assessed using equivalent amounts of computer time, SA emerged a
clear winner over simple local optimization for both types of
graph. Against the LK-style algorithm however, SA was only slightly
better for random graphs and worse for the random geometrical class. A
similar investigation was carried  out for the TSP \cite{20, 51}
and the results suggest that, matched for run-time, SA beats 3-opt,
also can be quite competitive with LK, but not as good as a
well-designed and implemented LK or the Iterated Lin-Kernighan (ILK)
heuristics \cite{20}.

In summary, depending on the given problem, SA appears competitive
with many of the best local optimization methods. 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{Mapping the Problem Components onto Time Periods}
%% 
%% The two sketches in Figure \ref{components-mapping} show roughly how the
%% various main components of the timetabling system are mapped onto the
%% desired time periods.
%% 
%% \begin{figure}[htb]
%% \begin{center}
%% \begin{picture}(380,380)
%% \psfig{figure=tuples-periods.ps,height=350pt,width=370pt}
%% \end{picture}
%% \end{center}
%% \caption{Mapping the problem components onto the time slots.}
%% \label{components-mapping}
%% \end{figure}


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

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

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

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


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

Two annealing schedules have been used in our experiments to update
the temperature of the SA algorithm in Figure~\ref{SA-algorithm}:
geometric cooling and adaptive reheating as a function of cost. 
The latter schedule was presented in Abramson et al. \cite{2}
but the ideas behind it are due to Kirkpatrick et
al. \cite{52, 53} and White \cite{41}.

Let $\alpha$ ($0 < \alpha < 1$) denote the cooling factor. The first
schedule, geometric cooling, computes the new temperature ($T^{'}$) of
the SA algorithm using $T^{'} = \alpha T$.
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 second method.

%% 
%% {\bf \underline{Disadvantages}}:
%% 
%% The state of the system is not taken into account in any way, and
%% thus can not adapt the intensity of the search depending on the
%% complexity of the problem.

The second annealing schedule we used to update the temperature of the
SA algorithm is the method of reheating as a function of cost
(RFC). 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{8} can be observed as sub-parts of the problem are resolved. 
In some of the work dealing with the TSP using annealing,
e.g. \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 is poor
(i.e. 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.
Now, to compute the aforementioned maximum specific heat we employ the
following steps which we refer to as the RFC schedule.

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

The average cost at temperature $T$ can be computed as: 
\be{T.2}
<C(T)> = \sum_{i \in {\cal C}} C_i \,.
\ee
The average square cost is: 
\be{T.3}
<C^{2}(T)> = \sum_{i \in {\cal C}} C_i^2 \,.
\ee
The variance of the cost is:
\be{T.4}
\sigma^{2}(T) = <C^{2}(T)> - <C(T)>^{2}\,.
\ee
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 constant and $C_b$ is the current best cost. 

Also, we have used another variant of equation
\ref{T.6} to compute a new temperature based on not the best cost
found so far, but rather on the standard deviation of costs at the
current $T$. A similar approach was taken by Huang et al. \cite{59}
yielding 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 $T$ which is denoted as
$T_{j+1}$ is 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 parameter that we have set to $0.0001$.
Following suggestions by Otten and van Ginneken \cite{60} and Diekmann
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, 13}) that it preserves the key 
relationship:
\be{T.7}
{d \over {dT}}C(T) = {\bar\sigma^{2}(T) \over T^{2}} = C_H
\ee

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. 


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

Let $s$ be the current schedule and
$s^{'}$ be a neighboring schedule obtained from the current neighborhood 
space (${\cal N}_{s}$) by swapping two classes in
either time or space (i.e. classroom), or time and space. 

The simplest method for choosing a move is to just randomly select a 
class, and then randomly select a new timeslot or room for that class,
and swap with the class already scheduled for that
timeslot or room (if there is one).
However this is extremely inefficient, since most of the time swapping 
the classes randomly will increase the 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 large list of all rooms, it will most likely
be rejected, since it may be too small for the class, or an auditorium 
when we need a laboratory. We can instead 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 make a random selection 
of rooms for that class only from this subset of feasible rooms, 
and the acceptance probability is much higher. 
%% ?? is this right? This assumes labs and lectures are assigned to the 
%% right type of room by the preprocessor. But what about the unscheduled
%% classes???
This effectively separates the updates into 
independent sets based on room type, so that laboratories are scheduled
separately from lectures, for example.
We carry out the scheduling of lectures first, followed by scheduling of
laboratories, however we still need to ensure that 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, and our move strategy is to 
select these 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.  

% Why ?? 

%%%% This whole section needs clarification!! ??
% Saleh has done this the wrong way. These updates have a high
% change in cost, not low.

Also, we have assumed that swapping classes that
belong to different academic departments always involve lower costs
than swapping classes belonging to the same department. The
justification for this assumption is that classes that belong to the
same department often tend to have students and instructors in
common. In addition, they usually are scheduled in the same set of
rooms allocated to or chosen by that department. Therefore, part of our
strategy of moves is to limit as much as possible the interdepartmental
class swaps. 
% Why ??



Another strategy we have used is to schedule the larger classrooms and 
auditoriums firstm to try to avoid not having large enough rooms later for
those classes with large enrollments.


Generally, the techniques we have taken here can be considered as 
heuristics for pruning the neighborhood or narrowing or limiting the
search space, which provides much more efficient moves
and improved overall results.



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

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


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

Our study case involved real scheduling data covering three semesters
at Syracuse University. 
The data for first and second semester were roughly of the same size:
around 13600 students, 1100 professors, staff, and teaching
assistants, 400 rooms (classrooms, seminar rooms, laboratories and 
auditoriums), and 2500 classes. 
The third (summer) semester data was much smaller, around 700 classes. 
However for this semester there were a lot of additional constraints,
particularly on the availability of rooms.

Our data was quite large in comparison to that 
used by Peterson et al. \cite{28}. The largest case they
dealt with involved around 1000 students, 20 different possible
majors, and an overall periodic schedule (over weeks). In the case of
Abramson et al. \cite{2}, their data set was quite small
and they stated that problems involving more than 300 tuples were very
difficult to solve. 


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

%% THIS IS VERY CONFUSING!! WHAT ARE THE ACTUAL VALUES???
We have observed that the choice of initial
temperature poses more of a challenge. To be exact, the experimental
procedure was this: Two data sets were obtained for both
schedules. For the geometric cooling, its set consists of ten runs
made from each of ten starting temperatures anywhere between $100$ and
$500$ with increments of $10$'s. For the reheating schedule, ten
choices of the initial $T$ were used anywhere between $128$ and $500$
also with increments of $10$'s.

To summarize, there were two data sets, each having $10$ samples for
each of their $10$ parameter combinations. For each combination the
{\it mean run time} as well as the {\it mean final energy} (cost) over
the $10$ sample runs were computed. If one parameter combination
yielded a longer run time and higher final energy than another, it was
discarded. The remaining combinations were those that were most
efficient, that is, by construction they had the property that as 
time increases, the energy decreases. 


\subsection{The Cooling Schedule}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

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

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

Choosing an initial temperature is much more difficult when we use
a preprocessor to provide a good starting configuration
rather than the usual random initial configuration. In that case,
we must be very careful that the initial temperature and the acceptance ratio
are not so high that the good initial configuration is randomized to the 
point where is loses its usefulness. However the initial temperature must
be high enough so that we can still make effective changes in the 
configuration.

% IMPORTANT
% Explain how initial temperature was chosen???
% Saleh to get data on T_0 dependence.

For geometric cooling, the initial comparison was with a standard type 
of stopping criterion \cite{19, 51}: the run was terminated when no
moves had been accepted for three generations (a generation is
a full Markov chain at a single temperature).
Other stopping criteria were also considered.   % AND????
% WHat about reheating??



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





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



We also observed that the efficacy of starting annealing (using either
adaptive or non-adaptive schedules) from a good solution depends not
only on the energy (or cost) of that solution, but also on how it was
obtained, that is, on its structure. For example, \cite{19, 51}
give few thoughts on this subject but as far as we know we have not
come across any kind of analysis on the topic.
% This is not an analysis either!!
% How does it depend on structure?? How can you tell??


% THIS DOESN'T EXPLAIN ANYTHING!!
% How does specific heat fit in?? (temperatures in the two figures
% don't seem to match up).
Our analysis starts with Figure \ref{graph.3} which shows the
relationship between $\log_2(T)$ and cost for the geometric cooling
and the RFC method. The interesting thing to notice is
that the cost begins to decrease rapidly around $\log_2(T)$ of $3.5$
and continue decreasing picking up speed approximately at
$0$. Figure \ref{graph.2} shows the range of the
maximum specific heat which is between $0$ and $1$. As can be seen,
after some fluctuation the specific heat climbs up above 0.4 and
reaching a maximum just below $0.45$. Unlike the relationship between
$\log_2(T)$ and the RFC cost, we could see that this relationship is
very much typical for the geometric cooling. The cost continues to
decrease, albeit slowly, beyond the point shown in the plot till
reaching close to 3000. After that the rate of change 
becomes even slower with either taking very short upward moves or
slightly going down but no sharp downward moves, as partly shown
in Figure \ref{graph.4}. This pattern continues for at least 10000
more iterations till termination or reaching a stopping point. Also,
as shown in Figure \ref{graph.5}, in the first 300 or so iterations
very little reheating was done since the cost is a bit high. Reheating
becomes more frequent as it is shown between steps $400$ and
$800$. As the decrease in cost becomes less and less or no noticeable
decrease at all, the frequency of reheating increases sharply as
observed around the $1100$ iteration step.


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

In the case of simulated annealing, Table \ref{table.3} shows output
in a percentage form averaged over 10 runs for only the first semester
input and without a preprocessor. Clearly, it shows a rather poor
output which is even lower in quality to that of the rule-based
system. Also, the use of the RCF schedule did not improve the results
by much and remained below those of Table \ref{table.1}. 

In contrast to the first three tables, Table \ref{table.4} shows quite
improved and high quality averaged results for both annealing
schedules. Such excellent results were mainly due to the use of
preprocessed input (output of the rule-based system) to the SA
processor. Also the figures were averaged over 10 runs of annealing
and one out of those runs yielded a perfect schedule, that is, all
classes of the input set were scheduled subject to the given students
and class constraints. Clearly, this tells us that the use of
preprocessing was not only helpful but quite essential when using
methods such as simulated annealing to deal with complex timetabling 
problems. Furthermore, these high quality averaged results state in an 
unambiguous terms that a multi-phase approach, as we explained above,
gives a much better results to TTP then a single-phase approach.


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

The annealing programs were written in ANSI C, and all the simulations 
were run on a number of IBM RS/6000 workstations, and on a 12-processor 
IBM SP2, which uses RS/6000 processors.  % specify CPU???
For the SP2, individual jobs were
run separately on different nodes using different sets of parameters, 
or different cooling schedules, or just different random numbers.

The average time for running the preprocessor (the expert system) for
the first and second semester data was about two hours, and the average
time for each simulated annealing run was 
approximately 20 hours for the geometric cooling schedule and 
about 15 hours using the reheating schedule. It took just a few runs of
the reheating schedule to produce a feasible solution to the scheduling
problem, and these runs
could be done concurrently on a multiprocessor computer such as the IBM
SP2, which would allow the scheduling to be completed overnight.

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



\section{Conclusions}

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

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

Another critical part of the annealing program was the choice of moves.
We used techniques that drew from our work on the rule-based system in
order to carefully select good moves that have a relatively high
probability of acceptance, 
rather than wasting computational effort on randomly chosen
moves, most of which would be rejected.

We tested two types of cooling schedules: the standard geometric
cooling, and the more recent technique of reheating based on cost.
The reheating method clearly improved the quality of the solution,
even with a smaller runtime.


% FUTURE WORK??


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Acknowledgments}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The authors are very grateful for the valuable help of Robert
Irwin in converting and formatting the registration data prior to the
scheduling process. We also would like to sincerely thank Karen Bedard
for providing us with the data and answering so many questions we had
about it, Meg Cortese for providing us with a set of building
constraints for various departments, and Ben Ware, Vice President for
Research and Computing at Syracuse University, for his support and 
encouragement.


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

\newpage

\begin{table}[htb]
\vspace{0.1cm}
$$
\begin{tabular}{|l||c|c|c|c|c|c||}
\hline
                &  Total  & Scheduled & highest   & lowest    \\ 
                & Classes & (average) & Scheduled & Scheduled \\
                &         &    \%     &   \%      &   \%      \\ \hline\hline 
First Semester  &  2482   &   68.00   &   71.75   &   66.95   \\ \hline
Second Semester &  2164   &   70.57   &   72.85   &   68.50   \\ \hline
Third Semester  &  709    &   80.25   &   85.35   &   77.95   \\ \hline
\end{tabular}
$$
\caption{Percentage of scheduled classes, averaged over 10 runs,
for three terms using a {\it rule-based system} only. 
Both class and student constraints are used.}
\label{table.1}
\vspace{0.25cm}
\end{table}
\begin{table}[htb]
\vspace{0.1cm}
$$
\begin{tabular}{|l||c|c|c|c|c|c||}
\hline
                &  Total  & Scheduled & highest   & lowest    \\ 
                & Classes & (average) & Scheduled & Scheduled \\
                &         &    \%     &   \%      &   \%      \\ \hline\hline 
First Semester  &  2482   &   72.00   &  75.15    &  69.55    \\ \hline
Second Semester &  2164   &   78.12   &  81.10    &  75.00    \\ \hline
Third Semester  &  709    &   92.00   &  96.45    &  88.90    \\ \hline
\end{tabular}
$$
\caption{Percentage of scheduled classes, averaged over 10 runs,
for three terms using a {\it rule-based system} only. 
Only class constraints are used.}
\label{table.2}
\end{table}

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c|c|c||}
\hline
                &  Scheduled & highest   & lowest    \\
                &  (average) & Scheduled & Scheduled \\
                &     \%     &    \%     &   \%      \\ \hline\hline
SA (geometric)  &    60.70   &   67.95   &  55.28    \\ \hline
SA (cost-based) &    66.22   &   70.47   &  61.12    \\ \hline
SA (geometric)  &    62.55   &   69.85   &  60.28    \\ \hline
SA (cost-based) &    69.25   &   72.15   &  66.52    \\ \hline
\end{tabular}
%% ??? ! FIX THIS TABLE SO IT HAS ALL 3 SEMESTERS DATA ! ???
$$
\caption{Percentage of scheduled classes, averaged over 10 runs,
for three terms using {\it simulated anealing} only, with no
preprocessor and a random initial configuration. 
Both class and student constraints are used.}
\label{table.3}
\end{table}

\begin{table}[htb]
\vspace{0.25cm}
$$
\begin{tabular}{|l||c|c|c|c|c||}
\hline
                &  Scheduled & highest   & lowest    \\
                &  (average) & Scheduled & Scheduled \\
                &     \%     &    \%     &   \%      \\ \hline\hline
SA (geometric)  &   97.27    &  98.25    &  94.45    \\ \hline
SA (cost-based) &   98.80    &  100.0    &  95.10    \\ \hline
\end{tabular}
%% ??? ! FIX THIS TABLE SO IT HAS ALL 3 SEMESTERS DATA ! ???
$$
\caption{Percentage of scheduled classes, averaged over 10 runs,
for three terms using {\it simulated anealing with a rule-based
preprocessor}.
Both class and student constraints are used.}
\label{table.4}
\end{table}


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

\newpage

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=Temperature.vs.Specific-heat-gnuplot.ps,height=320pt,width=320pt,angle=-90}}
\caption{Specific Heat vs. Temperature for the reheating based on cost schedule}
\label{graph.2}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=Adaptive_Geometric.TempLog2.vs.Cost-gnuplot.ps,height=320pt,width=320pt,angle=-90}}
\caption{Cost vs. Temperature (log base 2) for the geometric annealing
and the reheating based on cost schedules}
\label{graph.3}
\end{figure}

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

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=Non-geometric.steps.vs.cost-gnuplot.ps,height=320pt,width=320pt,angle=-90}}
\caption{Cost vs. Number of Steps for the reheating based on cost schedule}
\label{graph.5}
\end{figure}

\vspace{0.25cm}
\begin{figure}[htb]
\centerline{\psfig{figure=Temp_vs_Accept.adaptive_schedule.ps,height=320pt,width=320pt,angle=-90}}
\caption{Percentage of Acceptance vs. Temperature for the reheating
based on cost schedule}
\label{graph.6}
\end{figure}


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

\clearpage
\begin{thebibliography}{TTP}

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

\bibitem{4}
J. Thompson, and K. Dowsland, ``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{5}
K. Gosselin and M. Truchon, ``Allocation of Classrooms by Linear
Programming,'' {\it Journal of Operational Research Society} 37, 561
(1986).

\bibitem{2}
D. Abramson, H. Dang, and M. Krishnamoorthy,
{\it An Empirical Study of Simulated Annealing Cooling Schedules},
Griffith Univ. report, Nathan, Qld, Aus. 1994.

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

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

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

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

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

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

\bibitem{13}
G. Sorkin,
{\it Theory and Practice of Simulated Annealing on Special Energy
Landscapes}. PhD Thesis, UC-Berkeley, California, 1992.

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

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

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

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

\bibitem{19}
D. Johnson, 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{20}
D. Johnson,
``Local Optimization and the TSP,'' {\it Springer Lecture Notes in
Computer Science} 443, 446-461, Springer-Verlag, 1990.

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

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

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

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

\bibitem{37}
A. Colorni, 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, Italia.

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

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

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

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

\bibitem{49}
H. A. Eiselt 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{51}
D. Johnson 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.), John
Wiley and Sons, UK (to appear in 1996).

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

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

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

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

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

\bibitem{57}
E. H. Aarts, 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, UK (to
appear in 1996).

\bibitem{58}
M. Carter, 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{59}
M. Huang, 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{60}
R. Otten, L. van Ginneken, The Annealing Algorithm. Kluwer Academic
Publishers, 1989.

\bibitem{61}
R. Diekmann, 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{62}
D. Costa, ``A Tabu Search algorithm for computing an operational
timetable,'' European Journal of Operational Research, 76 (1994),
98-110. 

\bibitem{45}
Andrew Gee, private communication.

\end{thebibliography}
\end{document}

