\chapter{Introduction}

In this dissertation we try to answer the following question: 
How do we go about solving the problem of academic scheduling at the
university level, in particular? we give a detailed answer to this
question, 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
annealing, and simulated annealing methods 
to solve a large scale optimization problem, namely university
academic course scheduling, represented as a generalized assignment-type
problem. The core heuristics of our approach are annealing-based 
and include 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. 

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 combination of
graph-coloring and rule-based expert system preprocessor did quite
well but not as good as the approach of using only the rule-based
expert system as a preprocessor.

\section{Objectives}

The primary objective of this dissertation is to present
a detailed analysis on deriving an approximate solution to the problem
of university course scheduling, and also to shed some
light on how we go about solving similar optimization problems, in
general. Particularly, we briefly discuss airline scheduling
by comparing it to academic course scheduling and 
how our problem solving approach can be used to tackle
the airline crew pairing problem. Our analysis would also involve the
determination of how varying the parameters of the method(s) used
would affect the quality of the results obtained.

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 cost associated with
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 
a discussion of the inherent difficulty of many combinatorial problems,
as well as a look at some tailored and generally applicable
heuristics. We introduce the problem of course scheduling in chapter 3,
giving a definition and the 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 problem.

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 detail 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 a part of the preprocessing stage in
our multi-phase approach. In chapter 9 we outline common
characteristics between the two problems of airline crew scheduling
and course scheduling, briefly sketching how our approach can also be
used to tackle the airline crew scheduling problem. Chapter 10 is a
discussion on the complexity of course scheduling and its components.
Finally, in chapter 11 we summarize our approach and the results obtained
from tackling the problem using our method, followed a section on what
we have learned from dealing with the problem of academic scheduling and
another section on possible future work.
A number of key terms used throughout the thesis are
defined in an appendix A.

