\chapter{Airline Crew Scheduling versus Course Scheduling}

\section{Airline Crew Scheduling}

The resource planning of an airline company is a 
very complex problem, usually it is divided into four main blocks 
which then are solved more or less sequentially.
\begin{itemize}
\item {\bf Timetable construction}: Construct a timetable, optimized
with respect to market, available time slots at airports, etc.
\item {\bf Fleet assignment}: Assign a given aircraft fleet to the
timetable such that a revenue, depending on size of the aircraft, fuel 
consumption, staff requirement, etc. is maximized. An example of a
constraint is that all types of aircraft are not allowed to land on
all airports.
\item {\bf Crew scheduling}: A crew should be assigned to each flight
obeying a large number of governmental regulations, union demands and
collective agreements. This should be done so that the total expense
for the crews is minimized (utilizing the crew effectively).
\item {\bf Crew Assignment}: Assigning persons to the different crews
taking things as vacations and training into account.
\end{itemize}

For a more complete problem description see e.g. (operations research
in the airline industry, Gang Yu, editor, 1998)

Next to fuel cost the crew is the largest scheduling problem. 

In summary, the overall problem of 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}, as
generated in part (1). Each of these rotations consists of a
connected sequence of flights or {\it legs}, each starting and ending
at a given home base or {\it hub}.  The objective is to minimize the
total waiting time of the crew subject to a number of constraints on
the rotations. The problem's topological structure and the
restrictions imposed on it is quite similar to a multi-task phone
routing structure. 

Perhaps, one particular approach that has been used in tackling this
problem is first to convert it into a 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 often found with
conventional methods such as linear programming.
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 is to proceed in two phases (see \cite{LPS:airline}):
\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 fine-tune those sub-parts in an iterative manner 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 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~\cite{Sim:neural}.

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. Also, in crew scheduling, airlines restrict crew members in
spending double overnights in any of the non-{\it hub} points of the
flight; and to take a rest for a certain number of hours after each
duty period. These restrictions are considered from a constraint point
of view to be hard so it would need to be satisfied for the final
schedule. On the other hand, the analogous set of constraints dealing
with students and professors in course scheduling are generally
treated as soft or medium constraints. In general, for 
course scheduling we do not have a well defined objective function to 
optimize; there are many requirements which occur as constraints in
the problem and a collection of preferences for students and
professors, that are partially formulated as low priority constraints.

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

\section{Things To Be Done...}

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

\begin{itemize}

\item A section 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.

\end{itemize}



