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 generalized assignment-type
problems. 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 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 course scheduling 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 approach using a graph-coloring
preprocessor did extremely well but not as well as the approach with
the rule-based preprocessor. 
