\chapter{Introduction}

In this dissertation we try to answer the following question: How do
we go about solving optimization problems\footnote{The terms ``search
problem'' and ``optimization problem'' are considered synonymous. The
search for the best feasible solution is the optimization problem.},
in general, and academic course scheduling (or timetabling) at the
university level in particular? we give a detailed answer to the
latter part, and shed some light on the case of tackling optimization
problems in general.

Combinatorial optimization problems involve choosing the best solution 
from a finite set of mutually exclusive outcomes and are often
deceptively difficult to solve. 

To summarize, we have investigated a variety of optimization
algorithms, in particular, random search, hill climbing,
knowledge-based systems (or rule-based expert systems), mean-field
(feedback neural net-based) annealing, and simulated annealing methods
to solve a large scale optimization problem, namely university
academic course scheduling, represented as generalized assignment-type
problems. The core heuristics of our approach are annealing-based 
and it includes mean-field annealing, simulated annealing with three
different cooling schedules, and the use of two types of
preprocessors, namely rule-based and graph coloring. Moreover, 
preprocessors are only used with simulated annealing to provide
a good starting point for the algorithm. 

Along with the use of preprocessing we also have investigated a number 
of techniques to accelerate (i.e. 'speed up') the convergence of
annealing to a good quality solution. These techniques include the
selection of appropriate annealing schedules and its subsequent
parameter fine-tuning, as well as recording the best solution
encountered in an annealing run. Others that we have not investigated
such as approximate random number generation and the implementation of 
a local search trigger. Also, in this thesis we have not investigated
other more arduous to implement techniques such parallel, nested, and
two-stage simulated annealing. 

Most of these acceleration techniques are not mutually exclusive and,
as our investigations have shown, that several can often be used in
combination to produce time savings of a magnitude greater than those
available through the use of individual acceleration techniques. 

In terms of convergence speedup as well as solution quality, 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
we have investigated were able to provide a complete valid schedule. The
same processing method using a graph-coloring preprocessor did
quite well but not as good as the approach with the rule-based
preprocessor. 

\section{Objectives}

The primary objective of this dissertation is to shed light on how we
go about solving optimization problems in general, and to present
detailed analysis on deriving an approximate solution to the problem
of university course scheduling in particular. Such analysis would
involve the determination of how varying the parameters of the
method(s) used would affect the quality of the results.

The optimization problem we have closely tackled is university course
scheduling, and 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. 

\section{Outline}

Chapter 2 is an introduction to combinatorial optimization along with 
discussion of the inherent difficulty of many combinatorial problems,
as well as look at some tailored and generally applicable
heuristics. We introduce the problem of course scheduling in chapter 3,
giving a definition and associated three types of constraints. Also,
the chapter outlines the general form of an assignment-type problem
and outlines a representation of course scheduling as a generalized
assignment type.

In chapter 4 we look into the structure of the preprocessor used,
namely the rule-based expert system giving a sample of of some of the
rules that were used. Then we start the discussion about the core processor 
in chapter 5; including important discussion and analysis of energy
landscapes and annealing schedules. Chapter 6 looks into our
multi-phase (or hybrid) approach and its main components, discussing
strategies on the choice of moves during the simulation followed by
set of experimental results.

Our approach to mean field annealing is given in some details in
chapter 7. Followed by discussion in chapter 8 on the use of graph
coloring as a tool for course scheduling. We have used the
graph-coloring approach as another preprocessor in our multi-phase
approach. Finally, in chapter 9 we outline common characteristics
between the two problems of airline crew scheduling and course
scheduling, and discussion on performance of local search algorithms
in chapter 10. We conclude with glossary chapter of definitions and
terms.
