\chapter{Method Comparisons and Complexity Measures}

\section{Complexity of Course Scheduling}


\section{Airline Crew Scheduling}

Airline crew scheduling is classified as a resource allocation
problem, where a given flight schedule is to be covered by a set of
crew {\it rotations}. Each rotation consists of a a connected sequence
of flights or {\it legs}, each starting and ending at a given home base
or {\it hub}. Then the objective is to minimize the total waiting time 
of the crew subject to a number of constraints on the rotations. Its
topological structure and the restrictions imposed on it is quite
similar to a multi-task phone routing structure.

One particular approach in tackling this problem is first to convert
it into a {\it set covering problem}, by 
\begin{enumerate}
\item generating a large number of legal rotation templates, and
\item seeking a subset of these templates that precisely covers the
entire flight schedule.
\end{enumerate}

Then, solutions to the set covering problem are found with
conventional methods such as linear programming or other methods
such as feedback neural networks. 

This will have a big disadvantage and that is, on one hand, from a
computational point of view, an exhaustive generation of rotations is
not feasible for large real world problems; on the other hand, a
non-exhaustive generation will only cover a fraction of the solution
space. 

One other approach followed by Peterson et. al (Neural
Computation-98), proceeds in two phases:
\begin{enumerate}
\item the full solution space is narrowed down by using a reduction
method that removes a large part of the sub-optimal solutions; then
\item a mean field annealing approach is applied to handle the
topology, leg-counting, etc.
\end{enumerate}

It has been determined that the computational requirement for random
artificial problems with resemblance to real-world situations grows in 
the order of $N_f^3$ where $N_f$ is the number of flights.

So, given a schedule in terms of a set of $N_f$ flights (let say per
week), with specified times and airport departure and arrival, a crew
is to be assigned to each flight such that the total crew waiting time 
is minimized subject to the following restrictions:

\begin{itemize}
\item Each flight crew must follow a connected path, or {\it
rotation}, starting and ending at the {\it hub}.
\item The number of flight {\it legs} in a rotation must not exceed a
given upper bound, i.e. $L_{max}$.
\item The total duration (flight + waiting time) of a rotation is
similarly bounded by a maximum time, i.e. $T_{max}$.
\end{itemize}

In a real-world case there are many constraints to be
satisfied, but in general the above three are the most crucial and
difficult ones. Furthermore, without them the problem would reduce to
that of minimizing waiting times independently at each airport ---
the {\it local problems}; which can be solved exactly in polynomial
time; e.g. by pairwise connecting arrival flights with subsequent
departure flights. Therefore, without the global structural
requirements, the crew scheduling problem is not much of a challenge.


\subsection{Crew Scheduling vs. Course Scheduling}

The most noticeable difference between academic course scheduling and
crew scheduling is in the topological structures. Course scheduling
problem has a non-Euclidean global structure while the structure
(or the graphical representation of it) of crew scheduling is quite
similar to a multi-task phone routing structure. Neural networks based
methods such as the abovementioned mean field annealing approach has
been shown by several authors to be unsuited for tackling
non-Euclidean problems. (ref: Peterson90).

The other distinction is in the duration. Typically, a real-world
flight schedule has a basic period of about one week; while the
duration of a university course schedule is an academic semester or a
quarter. 

\vspace{1.5cm}
\noindent
\hrule
\noindent
\hrule
\noindent
\hrule
\vspace{1.5cm}

Some of Geoffrey's suggestions to be taken into account in the
thesis.

\begin{itemize}

\item A section (medium to large) on the relationship between airline
crew scheduling and course scheduling.

\item A section (medium to large) giving the complexity of the problem.
This would include runtime of various algorithms used, number of
variables, size of the overall problem and data, etc.

\item A chapter explaining why some optimization problems can also be
tackled by methods such as used in this thesis, particularly the
annealing approaches... While others are not suitable. For example,
Genetic Algorithms are known to be quite good in tackling certain
problems but not so good in tackling others. It would be quite useful
to shed some light on the reasons behind this. Also, it would be
interesting to have a section on the reasons why the neural net
approach does not do well on scheduling problems.

\item A section on the comparison between the type of constraints used 
in university course scheduling and those typically used for airline
or crew scheduling.

\end{itemize}



