
In this dissertation we try to answer the following question: How do
we go about solving optimization problems, 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 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 investigated were able to provide a complete valid schedule. The
same processing method using a graph-coloring preprocessor did
extremely well but not as good as the approach with the rule-based
preprocessor. 
