\chapter{Conclusion}\label{ch:conc}

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. For example, other
type of scheduling problems are production scheduling, workforce
scheduling, sport scheduling, and airline crew scheduling. 
We have chosen academic
course scheduling 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 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 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 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.

\section{Other Scheduling Problems}
Many scheduling problems share some features with the timetabling problem. 
For example, the {\it sport leagues games scheduling} \cite{FF:sports} and the 
{\it service timetable problem for transportation networks} \cite{O:periodic} also
account to the creation of a timetable. In that cases, though, the type of 
the constraints are different. The latter, for example, takes into
account also the order of execution of the activities. 

Another scheduling problem that has been largely investigated in the 
literature is the {\it job shop scheduling} which can be summarized as
follows: A job consists of a sequence of operations, each of which must
be processed on a specific machine. The operations of a job must be
processed in the order specified by the sequence, and each machine can
process at most one job at a time. The problem is to produce a schedule
of $n$ jobs on $m$ machines that minimizes the time when all jobs have
completed processing.

The job shop scheduling is NP-hard (\cite{GJ:candi}, category SS18, p. 242). 
Several algorithms have been proposed for this problem (see e.g. 
\cite{SSW:approximation, HSSW:scheduling}). In addition, there are several
approximability results for these algorithms. The ideas for the solution of the
job shop scheduling might be profitably exploited for the timetabling 
problem.

\section{Lessons Learned}

There are a number of lessons to be drawn from our study.
\begin{enumerate}
\item When dealing with combinatorial optimization type problems, 
particularly the non-Euclidean type such as those of scheduling, 
it is quite unlikely that a single algorithm would be able to fully 
tackle the problem and yield a solution
that is not only `good' but if possible close to `optimal'. In addition,
this is even more true as the problem being dealt with is large
scale (in data and constraints) real-world problem. 
\item The application of a particular method would generally depend on
the structure of the problem. But as we have shown, there are heuristics
that are more generally applicable to different classes of problems. One
particular example is annealing-based heuristics.
\item Neural-based approaches are generally not quite suitable for
tackling hard, combinatorial optimization type problems, as we have 
shown for the case of academic scheduling, and as has been shown in 
numerous studies of the traveling salesman problem.
\item As we have demonstrated, a number of different heuristics can
be coupled together forming an efficient problem solving hybrid approach
that can be used in tackling a host of constraint satisfaction
or combinatorial type problems, such as airline scheduling, academic
scheduling, and sports scheduling.
\item We would like to acknowledge that some aspects of our experiments and
the problem formulation do not correspond to current practice at institutions
such as Syracuse University. They also do not correspond to wishes of many 
faculty and students.
\end{enumerate}

\section{Future Work and Research Directions}

\subsection{Investigation of specific technique}
The application of search and optimization techniques, developed in various 
fields, to the course scheduling problem probably will continue to go on in
the future.

Other techniques may need to be explored for tackling this or other related
scheduling problems as well. For example, GSAT~\cite{SLM:sat} has been applied
also to graph coloring and other problems, suitably transformed into SAT problems.
It might be interesting to try to formulate the course scheduling problem
as a SAT problem and then apply the GSAT algorithm to it.

\subsection{Design of a powerful constraint language}
The constraints of a timetabling problem can be very different in nature. Some
of them can be easily formulated in a mathematical form, whereas some others
are well expressed in some logical formulation. In addition, in some cases,
the informal definition of the constraint, given in some papers, is not clear
enough for the reader. For these reasons, we envision the definition of
a constraint language, semantically well-founded, that can express all the types
of constraints usually considered in the literature.

\subsection{Compare and combine different approaches}
The comparison of different approaches to the solution of a specific problem
can give an insight on the quality of a specific method. The comparison can also
provide information about which approach works best in different situations.
In addition, it can also help for the development of combined methods that
hopefully exploit the good qualities of these various techniques, as we have
done in this thesis.

