%% 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 PATAT97 paper}
\end{flushright}
\vspace{.75cm}
\begin{center} 
{\LARGE\bf 
A Comparison of Annealing Techniques 
for Academic Course Scheduling
}
\vspace{1cm}

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

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

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

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.
% Check this. Do any take into account 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, 
most of them being variants of simulated annealing:
\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.
\item
\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 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.


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

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

{\bf Hard constraints} include 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,
\item classes with students in common.
\end{itemize}

Another example of a hard constraint is: 
\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. 
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Redefine medium constraints to be hard student preferences??
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\bf Medium constraints} fall into the shaded region between the
%%%%%%%%%%%%%%%%%%%%%%%%
hard and 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
schedule the penalty of these constraints should be minimized and 
preferably reduced to zero.

% Also, there are medium 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}

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 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). Also constraints involving students preferences
fall in this category.

{\bf Soft constraints} are preferences that do not deal with time conflicts, 
%%%%%%%%%%%%%%%%%%%%%%
and have a low penalty (or cost) associated with them. 
Some examples are:

\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 Minimize the distance between the room where the class is assigned and 
the building housing its home department. 
\end{itemize}

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. 


Timetabling problems can be characterized by their {\it sparseness}.
After all the required lessons have been scheduled, there will be 
$N_{sp} = (N_x N_t - N_l)$ spare space-time slots, hence, the
sparseness of 
the problem is defined as the ratio $N_{sp} / (N_x N_t)$. The sparseness
decreases as  $N_{sp} / (N_x N_t)$ goes to zero or as $N_{sp}$ becomes
smaller and smaller. 
Table \ref{table.02} shows a three-semester
ratio of sparseness of our problem.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Mean-Field Annealing}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




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

We have implemented a 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 relatively simple 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 the 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 
straigtforward, 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 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), see Figure~\ref{SA-algorithm}, has been
widely used for tackling different combinatorial optimization
problems, particularly academic scheduling \cite{39, 3, 4}. 
% 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 adaptive 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 either time or/and 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 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 expert systems, forming quite
useful hybrid methods for tackling a range of complex problems.
SA is a robust technique, however, to obtain good results the annealing
runs often require a great deal of computer time which is one of the
major drawbacks of the algorithm.

In summary, depending on the given problem, SA appears competitive
with many of the best local %??  
optimization methods.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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
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, geometric cooling, computes the new temperature 
($T^{'}$) of the SA algorithm 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 reheating as a
function of cost (RFC), which was used 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 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
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, reheating based on cost and adaptive cooling.

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
un-specifies types. Staff and teaching assistants are considered part
of the set of professors. In addition, third semester (summer) data
was much smaller, however, there were additional space/time
constraints and fewer 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. 

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.

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

Table \ref{table.01} lists all major components of the data and Tables
\ref{table.02} and {\ref{table.03} show the rates of sparseness of the three-semester
data which greatly depends on number of time slots and rooms used. The
level of sparseness increases as the overall size of the data,
particularly, number of rooms, time slots, and number of
classes. Also, after scheduling all the classes, there will be about
$N_{sp} = (N_x N_t - N_l )$ spare space-time slots, hence, the
sparseness of the problem is defined as as the ratio $N_{sp} / (N_x
N_t)$. As we can see that Table \ref{table.03} degree of sparseness is
less than that of Table \ref{table.02} and the reason is the presence
of the students' preferences. 

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

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

In contrast to the the numbers in Table \ref{table.3}, Table
\ref{table.3.1} shows higher percentages of the three annealing
schedules and it is mainly due to the exclusion of students'
preferences/constraints and only dealing with class constraints.

Table \ref{table.4} shows quite improved and high quality averaged
results for the three schedules. Such excellent results can only be
attributed to the use of  preprocessed input (output of the rule-based
preprocessor)  Also the figures were averaged over 10 runs of annealing
and for the cost-based schedule all those runs for the third
semester set yielded a perfect schedule, that is, all classes of the 
input set were scheduled satisfying the given class and students 
constraints. However, as we can see in Table \ref{table.01} that the
size of classes of the third semester is quite small relative to the
first two semesters so achieving a perfect schedule for it was not
too difficult.

Furthermore, we obtained even better results for the three semesters
when the class constraints were disjoined from the students
preferences and first dealt with the class constraints. As shown in
Table \ref{table.4.1} we achieved perfect schedules for the three
semesters using the cost-based reheating schedule and also a perfect
schedule for the third semester using the adaptive annealing. Students
data and preferences are dealt with in the second stage with respect
to the class schedule obtained in the first stage.

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

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

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. As expected, 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.

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 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, or it may be possible to just utilize the schedule
from the same semester for the previous year.

Another critical part of the annealing program was the choice of moves.
We used techniques that drew from our work on the preprocessor 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 three types of cooling schedules: the standard geometric
cooling, adaptive annealing, and reheating based on cost method. The
third schedule outperformed the other two on all data sets we dealt with.

\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. 
Also, we would to 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 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 a three-semester data.}
\label{table.01}
\vspace{0.25cm}
\end{table}

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

\begin{table}[htb]
\vspace{0.1cm}
$$
\begin{tabular}{|l||c||}
\hline
Academic               & sparseness \\ 
Time Period           &    ratio   \\
                               &           \\ \hline\hline 
First Semester       &    0.35  \\ \hline
Second Semester &    0.38    \\ \hline
Third Semester     &    0.50    \\ \hline
\end{tabular}
$$
\caption{A three-semester sparseness ratio (\underline{including
students}) computed by ${\cal R}(N_{sp}/(N_x N_t)$, ((majors  *  max classes
taken per students) / number of students)). The smaller the ratio, the
less sparse the problem is and for this problem the ratio is based on
$N_t$ = 15 time slots each with a duration of 55 minutes. The first
slot starts at 8:00 am and the last slot ends at 9:45 pm.}
\label{table.03}
\vspace{0.25cm}
\end{table}


\begin{table}[htb]
\vspace{0.1cm}
$$
\begin{tabular}{|l||c|c|c|c||}
\hline
Academic        &  Total     & Scheduled  & highest       & lowest    \\ 
Time Period     & Classes & (average) & Scheduled & Scheduled \\
                         &               &    \%         &   \%             &   \%      \\ \hline\hline 
First Semester  &  3839    &   69.20      &   74.90       &   66.60   \\ \hline
Second Semester &  3590   &   70.85   &   76.15   &   68.55   \\ \hline
Third Semester  &  687    &   90.35   &   93.77   &   86.45   \\ \hline
\end{tabular}
$$
\caption{Percentage of scheduled classes, averaged over 10 runs,
for three terms using 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{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{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   \\ \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   \\ \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   \\ \hline
\end{tabular}
$$
\caption{Percentage of scheduled classes, averaged over 10 runs of the
same initial temperature and other parameters, for three terms using
{\it simulated anealing} only, with {\it no preprocessor and a random
initial configuration}. \underline{Only class constraints are used.}}
\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{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 
{\it simulated anealing with an expert system as preprocessor.}
\underline{Only class constraints are used.}}
\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{6}
Elmohamed, S., G. C. Fox, P. Coddington, ``Course Scheduling using Mean
Field Annealing, Part I: algorithm and Part II: implementation,'' 
unpublished report, NPAC preprint, Syracuse Univ. 1996.

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

