\chapter{Multi-Phase (Hybrid) Approach to Scheduling}\label{ch:scheduling}

\vspace{0.1cm}
\begin{figure}[tbp]
\begin{center}
\begin{picture}(345,325)
\psfig{figure=sys-architecture.eps,height=345pt,width=325pt,angle=-90}
\end{picture}
\end{center}
\caption{A schematic view of the system three-phase architecture.}
\label{three-phase-arch}
\end{figure}

Figure~\ref{three-phase-arch} illustrates the multi-phase
approach~\cite{ECF:scheduling} we have taken to tackle a large scale 
course scheduling problem. The second phase of this method can be 
viewed as an improvement phase to the quality of the initial schedule 
produced in the first phase. 
This is accomplished by solving three different assignment-type
problems (ATPs), namely, timetabling, grouping, and the classroom 
assignment. The first ATP tries to decrease the total number of 
overlapping situations by modifying the starting times of the
classes. The second ATP improves the grouping of the students by
moving them from one course section to another section of the same
course, with an objective of minimizing the total number of
overlapping situations involving students. The third ATP improves the
classroom assignment.

\section{The Structure of Our Method}

\subsection{The Preprocessor Phase}
As is schematically illustrated in Figure~\ref{three-phase-arch}, the
preprocessor is either a graph coloring, a rule-based expert system,
or a combination of both. Since the test problem we have tackled is
quite large in the size of data and number of constraints involved, it 
was quite difficult to represent or encode it graphically in
its entirety for the graph coloring approach. Instead, we partitioned
it into two sets: the first set is of science and engineering data and its
associated constraints, and the second set is the rest of the data and 
also its associated constraints.

Our graph coloring approach is only for the science and engineering
set, while the second set was tackled via a rule-based expert system
approach. Furthermore, we took a second approach at preprocessing by
tackling the entire problem using a single method and in this case was
also a rule-based expert system.

\subsection{The Core Heuristics}
Annealing-based heuristics consisting of simulated annealing using
three different kind of annealing schedules working in conjunction with 
micro expert systems to manage and direct the choice of moves
throughout the search space. Moreover, these embedded micro rule-based
expert systems generally act in ways to ``cluster'' the search space
into various ``sub-spaces'' representing the relationships and
dependencies between the different components of the problem. More on
this aspect in the experimental results sections.

\subsection{The Postprocessor}

It consists of decision modules to determine whether the semi-final
solution for the three ATPs of timetabling, grouping, and classroom
assignment constitute a final solution satisfying all the required
criteria. If it is determined that there are still a few more gaps to be
filled in the schedule, or maybe in spite of the solution's low cost 
it still doesn't quite fit to be a final schedule, then each decision 
module using the information given by the user would have to decide on
any further course of action to be taken regarding the results.

\vspace{0.1cm}
\begin{figure}[tbp]
\begin{center}
\begin{picture}(340,410)
\psfig{figure=college-buildings.eps,height=340pt,width=410pt}
\end{picture}
\end{center}
\caption{A schematic view of some of the main components of the
system, colleges with their associated departments and a list of buildings.
$r_1 \ldots r_n$ denote rooms, $c_1 \ldots c_n$ denote classes, and each of 
the dotted arrows denotes the building choice of the shown department.}
\label{college-dept-buildings}
\end{figure}

\vspace{0.1cm}
\begin{figure}[tbp]
\begin{center}
\begin{picture}(350,330)
\psfig{figure=dept-building.eps,height=330pt,width=350pt,angle=-90}
\end{picture}
\end{center}
\caption{A schematic view of department(s) and their buildings. Here, it
indicates that the home building for the CIS department is building C, 
and its classes can be scheduled in buildings A, B, and D, as well as C.}
\label{dept-buildings}
\end{figure}

\vspace{0.1cm}
\begin{figure}[tbp]
\begin{center}
\begin{picture}(330,350)
\psfig{figure=class-swaps.eps,height=330pt,width=350pt}
\end{picture}
\end{center}
\caption{A schematic view of four different colleges (or schools) and
their associated departments. The sketch shows class swapping between
individual departments within the same school and others outside
it. The dotted arrows denote swaps either within the same department
or between two departments belonging to two different schools; while
the solid arrows denote swaps between departments within the same
school.}
\label{dept-swaps}
\end{figure}

%%\subsection{Attributes of the Data}
%%
%% Briefly outlining the varies attributes of the data involved in the
%% scheduling problem.
%%
%% \subsubsection{Room Attributes}
%% \subsubsection{Scheduling Domains}
%% \subsubsection{Start Times}
%% \subsubsection{Global Parameters}
%% \subsubsection{Campuses, Buildings and Rooms}
%% \subsubsection{Day-Time Combinations}
%% \subsubsection{Common Start Times}
%% \subsubsection{Faculty}
%% \subsubsection{Courses}
%% \subsubsection{Campus Distances}
%% Distances between main campus and other branches, if any exists.
%% 
%% \subsubsection{Building Distances}
%% \subsubsection{Courses to Spread Out}
%% \subsubsection{Join-Listed Courses}
%% \subsubsection{Same-Day Courses}
%% \subsubsection{Simultaneous Courses}
%%

\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.
When used to choose the moves for annealing, the main function of the 
rule-based system is to ensure that all the trial moves satisfy the 
hard constraints.
Many of the rules dealing with the medium and soft constraints are
softened or eliminated, since reducing the cost of these constraints 
is done using the Metropolis update in the annealing algorithm.

Another one of the modifications to the rule-based system
is that while the version used in the 
preprocessor is completely deterministic, the version used in choosing the 
moves for annealing selects at random from multiple possibilities that 
satisfy the rules equally well.
This extra freedom in choosing new schedules, plus the extra degree of 
randomness inherent in the annealing update, helps prevent the system from
getting trapped in a local minimum before it can reach a valid schedule, 
which is the problem with the standard deterministic rule-based system.

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, as illustrated in Figure~\ref{dept-swaps}.

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. 

Also, the abovementioned embedded micro expert systems act on the
search space by ``clustering'' it into various sub-spaces or
constraint-based dependencies between classes, time slots, students,
departments, and buildings. Thus, giving the core annealing process a
better looking and a much easier to search space landscape
representing the configuration of the scheduling problem.  
%% include GCF work here...


\section{More Analysis of the Simulation}

Our computations were done with a number of goals in mind. The main
objective was to provide a schedule which satisfies all hard
constraints and minimizes the cost of medium and soft constraints, 
using real-life data sets for a ``large'' U.S. 
university~\cite{ECF:scheduling}. 
We also aimed to find an acceptable set of annealing parameters 
and move strategies for general class scheduling problems of this kind,
and to study the effects of using a preprocessor to provide the
annealing program with a good starting point. Finally, we wanted to
make a comparison of the performance of the three different cooling
schedules, geometric cooling, adaptive cooling, and reheating based on
cost. 

We spent quite some time finding optimal values for the various
parameters for the annealing schedule, such as the initial
temperature, the parameters controlling the rate of cooling 
($\alpha$ for geometric cooling, $a$ for adaptive cooling)
and reheating ($K$), and the number of iterations at each temperature.
%
Johnson {\it et al.}~\cite{JM:traveling} noted in their SA 
implementation for the traveling salesman problem (TSP)
that the number of steps at each temperature (or the size of the Markov
chain) needed to be at least proportional to the ``neighborhood'' size
in order to maintain a high-quality result. From our experiments
we found the same to be true for the scheduling problem, even though it is
very different from the TSP. 
Furthermore, in a few tests for one semester we fixed the number of
classes and professors but varied the number of rooms and time slots, and
found that the final result improves as the number of iterations in
the Markov chain becomes
proportional to a combination of the number of classes, rooms and time
slots. We also observed the same behavior when we fixed the number of
rooms and time slots but varied number of classes. 

Our study case involved real scheduling data covering three 
semesters at Syracuse University. The size and type of the
three-semester data 
is shown in Table~\ref{table.01}. Nine types of rooms were used:
auditoriums, classrooms, computer clusters, conference
rooms, seminar rooms, studios, laboratories, theaters, and
unspecified types. Staff and teaching assistants are considered part
of the set of professors. Third semester (summer) data was much smaller
than other semesters, however, there were additional space and time
constraints and fewer available rooms. Our data was quite
large in comparison to data used by other researchers. For example,
high school data used by Peterson and colleagues~\cite{GSP:teachers,
GSP:complex} 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{A:timetable}, their
data set was created randomly and was relatively small, and they
stated that problems involving more than 300 tuples were very
difficult to solve.  

Table~\ref{table.01} lists all major components of the data we have used.
Timetabling problems can be characterized by their {\it sparseness}. 
Table~\ref{table-sparseness-1} shows the sparseness (see
definition~\ref{sparse-df}) of the three-semester
data. Table~\ref{table-sparseness-2} is also a three-semester
sparseness ratio when the students are factored in, and closely
correlated with that of Table~\ref{table-sparseness-1}. For 
university scheduling, the sparseness ratio generally decreases as the
data size (particularly the number of classes) increases, so the
problem becomes harder to solve. 
Including student preferences makes the problem much harder, but these
are viewed as medium and soft constraints and thus are not necessarily
satisfied in a valid solution.

Our overall results are shown in Tables~\ref{table.3.1},
\ref{table.4.1} and \ref{table.5.1}. These tables show the percentage
of classes that could be scheduled in accordance with the hard
constraints. In each case (apart from the expert system, which is
purely deterministic), we have done 10 runs (with the same parameters,
just different random numbers), and the tables show the average of the
10 runs, as well as the best and worst results. The MFA results are 
different only due to having different initial conditions. 
Each simulated annealing run takes about 10 to 20 hours on a Unix
workstation, while a single MFA run takes approximately an hour
and an expert system run takes close to two hours.

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

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

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

Student preferences are included as medium and soft constraints
in our implementation, meaning that these do not have to be satisfied
for a valid solution, but they have a high priority.   
For the valid schedules we have produced, approximately $75\%$ of the
student preferences were satisfied. This is reasonably good
(particularly since  other approaches do not deal with student
preferences at all), but we are working to improve upon this result. 

\subsection{Preprocessing and the Problem's Structure}

As shown in Tables~\ref{table.4.1} and \ref{table.5.1}, the two
different preprocessors used gave different final results for the
three semesters. As it is shown, the approach of using a single method
to deal with the entire problem yielded a much better results than the
approach of using a mix of two different methods, rule-based expert
system and graph-coloring~\cite{MEY:coloring}, as in
Table~\ref{table.5.1}. 

This brings us to the question of what are the
reasons behind the difference in percentages appearing in the
Tables~\ref{table.4.1} and \ref{table.5.1}?

The main components of the problem are represented by the departments,
each with its own set of data consisting of courses, professors,
timeslots, preferred set of rooms to schedule to, etc. In spite of
that, there are global interactions or ``dependencies'' between these
departments, particularly when it comes to the issue of space
allocation and our final schedules seem to show that. We find
that in order to get not only an overall feasible schedule but one with
the least possible cost, a number of science and engineering
departments need to schedule some of their courses in buildings other
than their original space preferences. The same was true for the
non-science and non-engineering departments. In other words, there was
a necessity for the two sets of departments to go outside their
initial sets of space preferences in order to satisfy the global
criterion of producing an overall schedule with the least cost
possible. Therefore, dealing with the problem in partitions and solving
each with a particular set of heuristics would definitely not allow 
the science and engineering set to schedule anything outside its original 
set of space preferences. Certainly, the same is true for other involved 
partitions. The two approaches or sets of heuristics work in two separate 
partitions that have no influence or effects whatsoever on each other 
during preprocessing. While a single approach was able to deal with and 
look at the overall global structure of the problem and handle those arising 
dependencies in a better way. 
That single preprocessing approach we have used is a rule-based 
expert system; and again, it was mainly due to the issue of problem
representation that influnced our choice to use a rule-based system
rather than a graph-coloring approach to tackle the whole problem.

In summary, the point here is ``sub-optimization''; and to put it more succinctly, 
there are decent, though sub-optimal, solutions when optimizing jointly and
ther are not when partitioning and optimizing separately.


%% \subsection{Experimental Results -- Part II}
%%
%% analysis for all plots included, etc.
%%
%%
%% $\ldots$
%%
%% \subsection{Experimental Results -- Part III}
%% $\ldots$
%%
%% analysis for all plots, etc. i.e how parameters K and a  values
%% affect temperature, etc...
%%
%% $\ldots$
%%
%% \section{Conclusions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Academic course scheduling is only one example 
%% of a difficult planning problem; there are many similar problems
%% occurring in the industry and the public sector. We have chosen this
%% particular application since we feel that the problem is
%% representative enough for this class of problems and also because real
%% data were available to us.
%%
%% Our successful approach is the application of simulated annealing as a 
%% core processing method to the the abovementioned problem of academic
%% scheduling for a large university. Feasible schedules were obtained
%% for real data sets, including student preferences, without requiring
%% enormous computational effort.
%%
%% Mean-field annealing\footnote{See chapter~\ref{ch:ON} for more details on
%% this method.} works well for small scheduling problems, but does 
%% not appear to scale well to large problems with many complex constraints.
%% For this problem, both simulated annealing and the rule-based system 
%% were more effective than MFA. 
%% It is more difficult to tune the parameters for MFA than for
%% simulated annealing, and 
%% because of the complexity and size of the Potts neural encoding,
%% there seems to be no clear way of preserving the state of a good initial 
%% configuration provided by a preprocessor when using MFA.
%%
%% Using a preprocessor to provide a good initial state greatly improved
%% the quality of the results for simulated annealing. 
%% In theory, using a good initial state should not be necessary, 
%% and any initial state should give a good result, however in practice, 
%% we do not have an ideal cooling schedule for annealing, or an
%% ideal method for choosing trial moves and efficiently exploring the
%% search space, and there are restrictions on how long the simulation
%% can take. In general, for very hard problems with large parameter
%% spaces that can be difficult to search efficiently, and for which very
%% slow cooling would be much too time-consuming, we might expect that a
%% good initial solution would be helpful.
%% We used a fairly complex rule-based expert system for the
%% preprocessor, however the type of preprocessor may not be crucial. 
%% Other fast heuristics could possibly be used, for example a graph
%% coloring approach~\cite{MEY:coloring} which we also have used. Other
%% possible option is to just use the schedule from the same semester for
%% the previous year. A modified version of the rule-based system was
%% used to choose the trial moves for the simulated annealing, and the
%% high acceptance rate provided by this system was crucial to obtaining
%% good results.
%%
%% As expected, for the simulated annealing, adaptive cooling performed
%% better than geometric cooling, and using reheating improved the
%% results even further. The best results were obtained using simulated
%% annealing with adaptive cooling and reheating as a function of cost,
%% and with a rule-based preprocessor to provide a good initial
%% solution. Using this method, and with careful selection of parameters
%% and update steps, we were able to generate solutions to the course
%% scheduling problem, with student section assignment and preferences,
%% using real data for a large university. None of the 
%% other methods were able to provide a complete solution.
%%
%% Our main conclusion from this work is that simulated annealing, with a 
%% good cooling schedule, optimized parameters, carefully selected update
%% moves, and a good initial solution provided by a preprocessor, can be
%% used to solve the academic scheduling problem at a large university,
%% including student preferences. Similar approaches should prove
%% fruitful for other difficult scheduling problems.

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


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

\begin{table}[tbp]
\begin{center}
\begin{tabular}{|l||c||}
\hline
Academic           & Sparseness \\ [2pt]
Time Period        &    ratio   \\ [2pt]
                   &            \\ [2pt] \hline\hline
First Semester     &    0.50    \\ [2pt]\hline
Second Semester    &    0.53    \\ [2pt]\hline
Third Semester     &    0.62    \\ [2pt]\hline
\end{tabular}
\vspace{10pt}
\caption{The sparseness ratios of the problem for the data sets for
each of the three semesters. Lower values indicate a harder problem.}
\label{table-sparseness-1}
\end{center}
\end{table}

\begin{table}[tbp]
\begin{center}

\begin{tabular}{|l||c||}
\hline
Academic               & sparseness \\ [2pt] 
Time Period            &    ratio   \\ [2pt]
                       &            \\ [2pt] \hline\hline 
First Semester         &    0.35    \\ [2pt] \hline
Second Semester        &    0.38    \\ [2pt] \hline
Third Semester         &    0.50    \\ [2pt] \hline
\end{tabular}
\vspace{10pt}
\caption{A three-semester sparseness ratio ({\it including
students}) computed by ${\cal R}(N_{sp}/(N_x N_t)$, ((number majors  *
average number of 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 10:55 pm.} 
\label{table-sparseness-2}
\end{center}
\end{table}


\begin{table}[tbp]
\begin{center}
\begin{tabular}{|l|l||c|c|c||}
\hline
Academic        &   Algorithm     & Scheduled  & Highest   & Lowest
\\ [2pt]
Time Period     &                 & (average)  & Scheduled & Scheduled
\\ [2pt]
                &                 &    \%      &    \%     &    \%  \\ [2pt] \hline\hline
First Semester  & SA (geometric)  &   65.00    &   67.50   &  56.80 \\
                & SA (adaptive)   &   67.80    &   70.15   &  61.20 \\
                & SA (cost-based) &   70.20    &   72.28   &  68.80 \\
                & ES              &   76.65    &   76.65   &  76.65 \\
                & MFA             &   65.60    &   71.00   &  61.00 \\[2pt]\hline 
Second Semester & SA (geometric)  &   65.65    &   68.00   &  57.10 \\ 
                & SA (adaptive)   &   68.50    &   70.10   &  60.77 \\
                & SA (cost-based) &   75.14    &   77.68   &  70.82 \\ 
                & ES              &   79.00    &   79.00   &  79.00 \\
                & MFA             &   67.20    &   75.00   &  65.00 \\[2pt]\hline
Third Semester  & SA (geometric)  &   83.10    &   86.44   &  68.50 \\
                & SA (adaptive)   &   85.80    &   89.00   &  70.75 \\
                & SA (cost-based) &   91.20    &   95.18   &  85.00 \\ 
                & ES              &   96.80    &   96.80   &  96.80 \\
                & MFA             &   88.00    &   95.00   &  82.00 \\[2pt]\hline 
\end{tabular}
\vspace{10pt}
\caption{Percentage of classes scheduled using the different methods.
The averages and highest and lowest values were obtained using 10
independent runs for simulated annealing (SA) and mean-field annealing
(MFA). The expert system (ES) is deterministic so the results are from
a single run. {\it No preprocessor was used with the three methods.}}
\label{table.3.1}
\end{center}
\end{table}


\begin{table}[tbp]
\begin{center}
\begin{tabular}{|l|l||c|c|c||}
\hline
Academic        &   Algorithm     & Scheduled & Highest   & Lowest    \\
Time Period     &                 & (average) & Scheduled & Scheduled \\
                         &                 &    \%     &    \%     &
                         \%     \\ [2pt] \hline\hline
First Semester  & SA (geometric)  &   84.50   &   88.00  &  81.00 \\
                & SA (adaptive)   &   92.25   &   95.00  &  89.50 \\
                & SA (cost-based) &   94.87   &   97.75  &  92.00 \\[2pt]\hline

Second Semester & SA (geometric)  &   85.67   &   90.95  &  80.40 \\
                & SA (adaptive)   &   93.00   &   95.00  &  91.00 \\    
                & SA (cost-based) &   96.35   &   97.50  &  95.20 \\[2pt]\hline

Third Semester  & SA (geometric)  &   96.00   &   97.00  &  95.00 \\
                & SA (adaptive)   &   98.00   &   99.00  &  97.00 \\
                & SA (cost-based) &   99.00   &   99.50  &  98.50 \\[2pt]\hline
\end{tabular}
\vspace{10pt}
\caption{Percentage of scheduled classes, averaged over 10 runs for the
same initial temperature and other parameters, for three terms using 
simulated annealing {\it with a graph-coloring preprocessor for the
set of science and engineering data, and an expert system preprocessor
for the rest of the data.}} 
\label{table.5.1}
\end{center}
\end{table}


\begin{table}[tbp]
\begin{center}
\begin{tabular}{|l|l||c|c|c||}
\hline
Academic        &   Algorithm     & Scheduled & Highest   & Lowest    \\
Time Period     &                 & (average) & Scheduled & Scheduled \\
                         &                 &    \%     &    \%     &
                         \%     \\ [2pt] \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 \\ [2pt]\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 \\ [2pt]\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 \\ [2pt] \hline
\end{tabular}
\vspace{10pt}
\caption{Percentage of scheduled classes, averaged over 10 runs for the
same initial temperature and other parameters, for three terms using 
simulated annealing {\it with an expert system as preprocessor.}}
\label{table.4.1}
\end{center}
\end{table}

%%%%%%%%%%%%
% Plots
%%%%%%%%%%%%
