%% LATEX TWICE TO GET THE REFERENCES RIGHT
%%\documentstyle[12pt]{article}
\documentstyle[12pt,epsf,psfig]{article}

\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}
\newtheorem{itlemma}{Lemma}[section] %number by section (set in \em by default)
%%%same numbering counter as itlemmas:
\newtheorem{itproposition}[itlemma]{Proposition}
\newtheorem{itcorollary}[itlemma]{Corollary}
\newtheorem{itremark}[itlemma]{Remark}
\newtheorem{itnote}[itlemma]{Note}
\newtheorem{itobservation}[itlemma]{Observation}
\newtheorem{itdefinition}[itlemma]{Definition}
\newtheorem{itexercise}[itlemma]{Exercise}
\newtheorem{itexample}[itlemma]{Example}

\newenvironment{lemma}{\begin{itlemma}\rm}{\end{itlemma}} %no-italics
\newenvironment{remark}{\begin{itremark}\rm}{\end{itremark}} %no-italics
\newenvironment{observation}{\begin{itobservation}\rm}{\end{itobservation}} %no-italics
\newenvironment{corollary}{\begin{itcorollary}\rm}{\end{itcorollary}}
\newenvironment{proposition}{\begin{itproposition}\rm}{\end{itproposition}}
\newenvironment{definition}{\begin{itdefinition}\rm}{\end{itdefinition}}
\newenvironment{exercise}{\begin{itexercise}\rm}{\end{itexercise}}
\newenvironment{example}{\begin{itexample}\rm}{\end{itexample}}

\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This are for choices.  They take 4 or 6 args
%% (carriage returns allowed in between}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\twoif}[4]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\end{array}\right.
}
\newcommand{\threeif}[6]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\\#5&#6\end{array}\right.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\partmlab#1#2#3#4#5#6#7#8{\bordermatrix{&#1&#2\cr#3&#5&#6\cr
					\noalign{\medskip}#4&#7&#8\cr}}
%% For 2by2 partitioned matrices; arguments are: two labels of top, side,
%% 4 entries (row by row).  If entries are themselves matrix or pmatrix,
%% better for readability of source to define first: \def\matrix1{...} etc.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bigframebox}[1]{\framebox{\parbox{\smallerwidth}{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Warning: use \noindent before!
% AND IN TEXT, after begin doc, do:
% \newlength{\smallerwidth}  %for bigboxes
% \setlength{\smallerwidth}{\textwidth}
% \addtolength{\smallerwidth}{-8pt}        %MUST BE DONE AFTER begin doc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def \beq {\begin{eqnarray}}
\def \eeq {\end{eqnarray}}
\def \beqn {\begin{eqnarray*}}
\def \eeqn {\end{eqnarray*}}

\newcommand{\rf}[1]{[\ref{#1}]}            %bibliographical references

\newcommand{\text}[1]{\hbox{\rm \ #1\ \/}}
\newcommand{\be}[1]{\begin{equation}\label{#1}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bl}[1]{\begin{lemma}\label{#1}}
\newcommand{\ble}[1]{\begin{lemmaex}\label{#1}}
\newcommand{\br}[1]{\begin{remark}\label{#1}}
\newcommand{\bn}[1]{\begin{note}\label{#1}}
\newcommand{\bo}[1]{\begin{observation}\label{#1}}
\newcommand{\bt}[1]{\begin{theorem}\label{#1}}
\newcommand{\bd}[1]{\begin{definition}\label{#1}}
\newcommand{\bp}[1]{\begin{proposition}\label{#1}}
\newcommand{\bc}[1]{\begin{corollary}\label{#1}}
\newcommand{\bfact}[1]{\begin{fact}\label{#1}}
\newcommand{\ber}[1]{\begin{exercise}\label{#1}}
\newcommand{\bex}[1]{\begin{example}\label{#1}}
\newcommand{\bem}[1]{\begin{example}\label{#1}}    %Yes, 2 different ones...
\newcommand{\ec}{\mybox\end{corollary}}
\newcommand{\efact}{\mybox\end{fact}}
\newcommand{\eer}{\mybox\end{exercise}}
\newcommand{\eex}{\mybox\end{example}}
\newcommand{\eem}{\mybox\end{example}}
\newcommand{\el}{\mybox\end{lemma}}
\newcommand{\ele}{\mybox\end{lemmaex}}
\newcommand{\er}{\mybox\end{remark}}
\newcommand{\en}{\mybox\end{note}}
\newcommand{\eo}{\mybox\end{observation}}
\newcommand{\et}{\qed\end{theorem}}
\newcommand{\ed}{\mybox\end{definition}}
\newcommand{\ep}{\mybox\end{proposition}}
\newcommand{\epr}{\end{proof}}
\newcommand{\bpr}{\begin{proof}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  These are just for statements, no "qed" box is put in.
%%  (Also for when I have to finish something after a displayed equation
%%        or itemized.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ecs}{\end{corollary}}
\newcommand{\eers}{\end{exercise}}
\newcommand{\eexs}{\end{example}}
\newcommand{\eems}{\end{example}}
\newcommand{\els}{\end{lemma}}
\newcommand{\eles}{\end{lemmaex}}
\newcommand{\ers}{\end{remark}}
\newcommand{\ens}{\end{note}}
\newcommand{\eos}{\end{observation}}
\newcommand{\ets}{\end{theorem}}
\newcommand{\eds}{\end{definition}}
\newcommand{\eps}{\end{proposition}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\qed}{\hfill \halmos} %put \qed at right margin
\newcommand{\mybox}{\hfill $\Box$} %put \qed at right margin (white square)

%%%\newcommand{\pmat}[2]{\left( \begin{array}{#1} #2 \end{array} \right) }
%%%use as e.g. \pmat{cc}{ a&b\\ a &c }  Note 'cc' for 2 Centered cols
%%%can also use \pmatrix{ a&b\cr a &c \cr} for plainTeX standard construct
%%%\setcounter{page}{27} should set the CURRENT page to 27

\def \R {\bb R} % reals
\def \C {\bb C} % complexes
\def \Z {\bb Z} % integers
\def \X {\bb X} % for this paper only!
\def \inter {{\rm int \,}}
\def \rank {{\rm rank \,}}
%%%\def \inf {{\rm inf \,}}  %better in Latex -- subscripts OK!
%%%\def \min {{\rm min \,}}
\def \im {{\rm im \,}}
\def \ker {{\rm ker \,}}
\def \norm #1{\Vert #1 \Vert}
\def \ip #1\by #2{\langle #1 , #2 \rangle}
\def \Sone {{\bf S}^1} % circle
\def \wigglearrow {\sim \mkern -6mu >}

\def \today {\ifcase \month \or January\or February\or  
  March\or April\or May\or June\or July\or August\or 
  September\or October\or November\or December\fi\   
  \number \day, \number \year}                       
\newcommand{\comment}[1]{}
\newcommand{\halmos}{\rule{1ex}{1.4ex}}
%%%alternative to \qed (see below)
\newenvironment{proof}{\noindent {\em Proof}.\ }{\hspace*{\fill}$\halmos$\medskip}

%%%\def\qed{\kern 1em \vrule height .5em width .5em depth 0em}
%%%(I now use new qed: in right margin)

\def\vbar{\mathchoice{\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height4.1ptdepth-.35ptwidth.6pt\kern-.6pt}
   {\vrule height3.1ptdepth-.25ptwidth.5pt\kern-.5pt}}
\def\fudge{\mathchoice{}{}{\mkern.5mu}{\mkern.8mu}}
\def\bbc#1#2{{\rm \mkern#2mu\vbar\mkern-#2mu#1}}
\def\bbb#1{{\rm I\mkern-3.5mu #1}}
\def\bba#1#2{{\rm #1\mkern-#2mu\fudge #1}}
\def\bb#1{{\count4=`#1 \advance\count4by-64 \ifcase\count4\or\bba A{11.5}\or
   \bbb B\or\bbc C{5}\or\bbb D\or\bbb E\or\bbb F \or\bbc G{5}\or\bbb H\or
   \bbb I\or\bbc J{3}\or\bbb K\or\bbb L \or\bbb M\or\bbb N\or\bbc O{5} \or
   \bbb P\or\bbc Q{5}\or\bbb R\or\bbc S{4.2}\or\bba T{10.5}\or\bbc U{5}\or
%%%   \bbb P\or\bbc Q{5}\or\bbb R\or\bba S{8}\or\bba T{10.5}\or\bbc U{5}\or
   \bba V{12}\or\bba W{16.5}\or\bba X{11}\or\bba Y{11.7}\or\bba Z{7.5}\fi}}
%
%
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%%% read as: theFOOTNOTE (i.e. the command  executed when doing a footnote) is
%%% now to be set as a FOOTNOTESYMBOL (type of number) value of counter
%%% FOOTNOTE (Instead of Roman).  See LaTeX manual pp.91-92 as well as 175.
\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}
\def\ben{\begin{enumerate}}
\def\een{\end{enumerate}}
\def\st{\, | \,}

\newcommand{\myboxineq}{\eqno\Box} %put \qed at margin (white square) in eqn
\newcommand{\qedineq}{\eqno\halmos} %put \qed at margin in eqn

\topmargin -0.5in %default is 0.0, i.e. 1 inch from top.  Now it is 0.5
\textheight 9in
\oddsidemargin 0.25in %more reasonable margins!  (This is 1.25; can use <0 too)
\evensidemargin 0.25in %(same as above)
\textwidth 6.25in %(could use also -.5,-.5,7.5 for instance)
\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%% FROM HERE, macros special for paper
\def\mm{m}
\def\pp{p}
\def\proj{\pi _1} % projection on first group of coordinates
\def\x{u}  % vector argument
\def\SEC{(SEC)}
\def\SECo{(SEC$^0$)}
\def\INV{(INV)}
\def\Fp{{\cal F}_\pp}
\def\Fpm{{\cal F}_\pp^\mm}  %there is a 3,3 and a 2,1 in text

\def\Rm{\R^m}
\def\Rn{\R^n}
\newcommand{\ball}[2]{{\bb B}(#1,#2)}
\newcommand{\cball}[2]{\overline {\bb B} (#1,#2)}
\def\Fnm{{\cal F}_n^\mm}
\def\clos{{\rm clos\,}}
\def\inter{{\rm int\,}}

\def\CCF{compatible class of functions}
\begin{document}

\pagestyle{empty}
\begin{flushright}
{\sl DRAFT-Report.2}
\end{flushright}

\vspace{1cm}
\begin{center}
\thicklines
\setlength{\unitlength}{0.6cm}
\begin{picture}(14.5,12)(-7.25,-6)

\multiput(-5.5,-1.45)(0,1.75){2}{\framebox(11,1.15){}}

\multiput(-1.45,-5.5)(1.75,0){2}{\framebox(1.15,11){}}

\multiput(-3.75,-2.35)(6.35,0){2}{\framebox(1.15,4.7){}}

\multiput(-2.35,-3.75)(0,6.35){2}{\framebox(4.7,1.15){}}

\multiput(-2.9,0)(2.9,-2.9){2}{\line(1,1){2.9}}

\multiput(-2.9,0)(2.9,2.9){2}{\line(1,-1){2.9}}

\end{picture}

\vspace{1cm}

\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{.05cm}
\hrule
\vspace{.25cm}
{\bf 
Academic Course Scheduling: Its Constraints and
Mapping into Graph Coloring
}
\vspace{.25cm}
\hrule
\vspace{.05cm}
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{1cm}

Saleh Elmohamed\\
Hon W Yau\\
Geoffrey Fox\\
Paul Coddington\\
Dept. of Computer Science, and\\
Northeast Parallel Architectures Center,\\
Syracuse University\\
Syracuse, NY 13244\\
\{saleh, hwyau, gcf, paulc\}@npac.syr.edu\\
\end{center}

\newpage
\begin{flushright}
{\sl DRAFT-Report.2}
\end{flushright}
\vspace{.5cm}
\begin{center} 
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{.05cm}
\hrule
\vspace{.25cm}
{\bf
Academic Course Scheduling: Its Constraints and
Mapping into Graph Coloring
}
\vspace{.25cm}
\hrule
\vspace{.05cm}
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{1cm}

Saleh Elmohamed\\
Hon W Yau\\
Geoffrey Fox\\
Paul Coddington\\
Dept. of Computer Science, and\\
Northeast Parallel Architectures Center,\\
Syracuse University\\
Syracuse, NY 13244-4100\\
\{saleh, hwyau, gcf, paulc\}@npac.syr.edu\\
\end{center}

\vspace{1.5cm}
\centerline{ABSTRACT}
In this paper we list most of the constraints that are dealt with
while handling the timetabling problem. Also, a brief description of
how timetabling can be mapped into graph coloring is given along with
an example.

\vfill
\noindent{\bf Key words : constraints, events, legal schedule,
timetabling, graph coloring, bipartite graph.}

%% \vfill
%% \centerline{\today}
%% \vfill

\newpage
\pagestyle{empty}
\tableofcontents

\newpage

\pagestyle{plain}
\pagestyle{myheadings}
\markright{\sl DRAFT-Report.2}


\section{Constraints of the Timetabling Problem}

\bd{general-TTS}\ \
Given $N_p$ professors, $N_q$ classes and $N_x$ classrooms or lecture
halls, and $N_s$ students; it is required to schedule $N_l$ lessons
(defined as teacher-class pairs) within a time limit of $N_t$ lesson
periods (or time slots).  

Event-wise, $(p,q)$ event -- denoting a professor $p$ giving a class
$q$ -- takes place in the space-time slot $(x,t)$ -- denoting
classroom $x$ at time $t$. 


A legal schedule needs to be found such that no (teacher, class,
student) is in more than one place at a time, and no lecture hall is
expected to accommodate more than one lesson at a time or more
students than its capacity. 
Let $N_s$ to stand for students.
\ed

In a nutshell, timetabling is the assignment of time slots to a set of
events, {\bf subject to} constraints on these assignments.

The study case we have dealt with is {\it course scheduling} at the
university level for both graduate and undergraduate students. A host
of constraints need to be satisfied for any successful scheduling of this
kind. These constraints are divided into three types:
\begin{enumerate}
\item Hard.
\item Medium.
\item Soft.
\end{enumerate}

\subsection{Hard Constraints}

The most common and important hard constraint is what is sometimes
referred to as an {\it edge} constraint between two events. This
reference is due to the similarity of any {\bf simple} timetabling
problem with {\it vertex coloring} in graph theory; which simply
states that any given pair of events ${\bf e_1}$ and ${\bf e_2}$ must
not overlap in time. For example:

\begin{itemize}
\item Events ${\bf e_1}$ and ${\bf e_2}$ can be viewed as two classes
taught by the same professor, or one is a class and the other is a
recitation or lab of the same class, etc.

\item Events ${\bf e_1}$ and ${\bf e_2}$ are directly connected if
their associated classes do not overlap in time.
\end{itemize}

These constraints have to be respected at all costs.

\subsubsection{A list of hard constraints}

\begin{itemize}

\item A class can not be assigned to a particular room unless {\it
size of the room} $\geq$ {\it the class enrollment}. The smaller the
difference between these two sizes the better the assignment is.

\item If teachers are allocated automatically, specific weekly limits
are enforced, as well as limits of how many times various types of
classes are taught.

\item For a student to sign up for a class or section, it must be open.

\item Eligibility criteria for the class or section must be met, etc.

\item Section meeting time may not conflict with other ``enrolled''
sections.

\item For each student, balance $MWF$ and $TuTh$ sections.

\item Do not enroll athletes in courses that conflict with their sport
practice time. (may be {\it hard} or {\it soft}, depending on the
sport)

\item Enroll students in ALL parts of a course when associated sections 
(i.e. recitation, labs) are required.

\item A student with mapping status of {\it Req} should occupy a class
seat over a student with a status of priority ($\chi$).

\item It is not the case, in general, that all classrooms are
available for all subjects. In reality, many subjects require a
special purpose rooms.

\item Some classes are taught for two or more hours in a row, so may
request contiguous time slots.

\item The predecessor-successor relation between the subjects/topics
is satisfied.

\item Classes may be designated as clashing with other classes because
of common students between them.

\item Student with a ``required'' mapping status should occupy a class
seat over a student with other status.

\item Daily limits must be specified to restrict professors from
taking more than a specified number of classes per day.

\end{itemize}

\subsection{Medium Constraints}

These kinds of constraints do not deal with time conflicts but
do have a high cost attached to them. Also, this cost is not as
high as that associated with the hard constraints. In the final
(legal) schedule the cost of these constraints is minimized and it is
quite preferable to reduce it to $0$. 
In short, these kind of constraints should be satisfied but are
nevertheless relaxable.

\subsubsection{Examples of medium constraints}
\begin{itemize}
\item Balance or spread out the lectures over the week.
\item Classes may be grouped with other classes.
\item The overall schedule should have as few ``holes'' as possible;
that is lessons should be glued together, etc. 
\item Distance/building preference or department-to-building distance.
\end{itemize}

\subsection{Soft Constraints}

Do not deal with time  conflicts and have a low cost associated
with them. Also, in the final schedule, this cost is minimized
but does not often approach zero.

\subsubsection{Examples of soft constraints}

\begin{itemize}
\item Balance enrollment in multi-section courses.
\item Lunch and other break times may be specified.
\item Teachers may request periods in which their classes are not taught.
\item Do not enroll athletes in courses that conflict with their sport
practice time, etc.
\item An enrollment balance by gender should be obtained in Honors
seminar sections.
\item Optimize 1st choice course enrollments by attempting all 1st
choice courses for all students before attempting 2nd and 3rd
choices.
\item Various preferences of students or/and professors have to be
considered.
\item Group formation: for some subjects the classes are broken up
into option groups temporarily forming new classes.
\item The schedule should have as few ``holes'' as possible; that is
classes should be ``glued'' together.
\item Two courses of the same topic are scheduled on two different
working days.
\item The timetable may consist of an arbitrary number of periods per
day.
\item Some rooms may be declared unavailable during any time period.
\item Class subject combinations may request a preference for certain
periods.
\item Individual professor and class preferences may be specified for
specific rooms even if they are taken from a group or rooms.
\item Some classes may be grouped with others.
\item In order to schedule a number of classes at the same time, it is
possible to link class tuples together. In this way, the cost of a
move is the sum of the individual costs of each class tuple, however,
they are all moved at the same time.
\end{itemize}


\subsection{Getting around a hard constraint}

Consider two classes $c_1$ and $c_2$ involving common students. If
$c_1$ can not be scheduled at period $p$ for some reason (i.e the
teacher is perhaps not available at that time), then we shall never
visit a solution where $c_1$ is given at time $p$.

\subsubsection{Exception}
Suppose this constraint does not exist, and $c_2$ is scheduled at
period $p$, then we are allowed to schedule $c_1$ at period $p$ also,
even if this violates the constraint of {\it no overlapping of classes
involving common students}.

\subsubsection{Handling the Exception}
It is possible that $c_1$ is given at period $p$ in an optimal
schedule, so the violation of the constraint (overlapping of 
classes involving common students, etc.) can be canceled by moving
$c_2$ from $p$ to another period.


\section{Some Notation and Definitions}

\bd{const-dfn.2}\ \
Here, we define a number of {\bf hard constraints} dealing with
professors, classes, classrooms, and time periods.

\begin{itemize}
\item An event $(p,q)$ should occupy precisely one space-time slot
$(x,t)$.
\item Different events $(p_1,q_1)$ and $(p_2,q_2)$ should not occupy
the same space-time slot $(x,t)$.
\item A teacher $p$ should have at most one class at a time.
\item A class $q$ should have at most one teacher at a time.
\end{itemize}


\bd{dfn-3.9.2}\ \
One soft constraint of importance is that of {\it group
formation}. Briefly, it can be stated as follows: for some optional 
subjects the classes are broken up into option groups temporarily
forming new classes. In order to account for this, we need a formalism
that allows for the breaking up of these primordial classes and
subsequent recombinations into {\it quasi}-classes. This is a common
practice with those classes where the students have many choices.
\ed

\bd{dfn-5}\ \
Two important soft to medium constraints are:
\begin{itemize}
\item {\em Spreading}: different classes in a particular area
(i.e. computer science) should be spread over the week in a (MWF) and
(TuTh) type of spread.
\item {\em Glueing}: The schedule should have as few ``holes'' as
possible; that is lessons should be glued together.
\end{itemize}
\ed

\section{Mapping of TTS onto Graph Coloring Problem}

\subsection{Graph Coloring}

Briefly, given a graph $G=(V,E)$ we have to find a coloring of its vertices
with as few colors as possible. The main constraint is that two vertices
linked by an edge should not receive the same color (such coloring are
called feasible coloring). One could define the set $S$ of feasible
solutions as the set of feasible coloring which do not use more than a
given number of colors; for example, this upper bound may be the
number of colors used in the initial solution.

\subsection{The Mapping}

\begin{enumerate}
\item The courses are the vertices of a graph.
\item The time periods correspond to the colors.
\item Two vertices are linked by an edge if the corresponding courses
cannot be given at the same time.
\item Additional constraints have to be taken into account and mapped
onto the graph.
\end{enumerate}

\subsection{A Mapping Example}

Suppose we have $n$ classes and $m$ professors. In Table
(\ref{mapping-table}) it is indicated by an $X$ which classes should be
taught by which professor (one class of one hour a day).

Now, the question is : What is the minimum timespan in which all
classes can be scheduled?

\bt{coloring-thm}\ \
(K\H{o}nig's edge coloring theorem). For any bipartite graph G
= (V,E) one has
\be{coloring-eq}
\chi(G) = \Delta(G)\;.
\ee
That is, the edge coloring number of a bipartite graph is equal to its
maximum degree.
\et
Theorem (\ref{coloring-thm}) tells us that all classes can be
scheduled within a timespan of four hours. To see this, make a
bipartite graph G with color classes; let $T =$ set of professors, and
$C =$ set of classes, where $t \in T$ and $c \in C$ are connected if
and only if professor $t$ should teach class $c$; that is, if there is
an $X$ in position $(t,c)$ in Table (\ref{mapping-table}).

This example tells us that $G$ will have a maximum degree $\Delta(G)$
equal to four. Therefore, according to Theorem (\ref{coloring-thm}),
the edge coloring number $\chi(G)$ of $G$ is also equal to four. So we
can color the edges of $G$ by four colors so that no two edges of the
same color have a vertex in common. That is, we can color the $X$'s in
Table (\ref{mapping-table}) by four colors so that there are no two
$X$s of the same color in any row or column. If every color represent
one hour, we obtain a schedule spanning four hours.

This example can be extended to the case where professors can give
more than one class a day. In that case, we obtain a bipartite graph
with multiple edges.


\begin{table}[htb]
$$
\vspace{0.25cm}
\begin{tabular}{|l||c|c|c|c|c|c||}
\hline
class:       &  1  &  2  &  3  &  4  &  5  &  6 \\ \hline\hline
professor: a &  X  &  X  &  -  &  X  &  -  &  - \\ \hline
           b &  X  &  -  &  X  &  X  &  X  &  - \\ \hline
           c &  -  &  X  &  -  &  X  &  X  &  - \\ \hline
           d &  -  &  X  &  -  &  -  &  -  &  X \\ \hline
           e &  X  &  -  &  X  &  -  &  X  &  X \\ \hline
           f &  X  &  -  &  X  &  X  &  -  &  X \\ \hline
           g &  -  &  X  &  X  &  -  &  X  &  X \\ \hline
\end{tabular}
$$
\caption{Professor/class scheduling table.}
\vspace{0.25cm}
\label{mapping-table}
\end{table}


\subsection{Interpretation of the Solution Space}

After setting up or mapping the problem we need to determine the
following: 
\begin{itemize}
\item {\underline{A feasible solution}} is defined as a schedule that 
satisfies a subset ($C^{'}$) of constraints ($C$) : $C^{'} \subseteq C\;$;
provided that all hard constraints are part of $C^{'}\;$.

\item A neighboring solution is obtained by modifying the current
solution space (i.e. swapping two or more classes in time).

\item Here are two guidelines in determining whether a given
constraint to be included in $C^{'}$ or not:
\begin{enumerate}
\item A class should never be assigned to a time period if such an
assignment induces only class schedules that do not satisfy all the
constraints (specifically the hard constraints).
\item A conflict between two or more classes should not be a
sufficient condition for hindering an assignment.
\item If all courses last one time period, this is equivalent to
changing the color of a vertex, for example.
\end{enumerate}
\end{itemize}


\clearpage
\newpage
\begin{thebibliography}{HSW}

\bibitem[HKP-91]{Hertz-91}
Hertz, Krogh, and Palmer,
{\it Introduction to the theory of neural computation}, 
Addison-Wesley, Redwood City, 1991.

\bibitem[Abramson-94]{Abramson-94}
Abramson, Dang, and Krishnamoorthy,
{\it An Empirical Study of Simulated Annealing Cooling Schedules},
Griffith Univ. report, Nathan, Qld, Aus. 1994.

\bibitem[Dowsland-93]{Dowsland-93}
Dowsland, Kat,
Using Simulated Annealing for Efficient Allocation of Students to
Practical Classes. Stat and OR Group, EBMS, Univ College of Swansea,
UK, 1993.

\bibitem[TD-94]{TD-94}
J. Thompson, and K. Dowsland, ``Variants of Simulated Annealing for
the Examination Timetabling Problem'', Working Paper, Statistics and
OR Group, European Business Management School, Swansea SA2 8PP,
UK. (1994)

\bibitem[GT-86]{Gosselin-86}
K. Gosselin and M. Truchon, ``Allocation of Classrooms by Linear
Programming'', Journal of Operational Research Society 37, 561 (1986).

\bibitem[Abramson-94]{Abramson-94}
Abramson, Dang, and Krishnamoorthy,
``An Empirical Study of Simulated Annealing Cooling Schedules'',
Griffith Univ. report, Nathan, Qld, Aus. (1994).

\bibitem[Lister-93]{Lister-93}
R. Lister,''Annealing Networks and Fractal Landscapes'', Proc. IEEE
Int. Conf. on Neural Nets, March 1993, Vol. I, pp 257-262.

\bibitem[Mouritsen-84]{Mouritsen-84}
Mouritsen, O. G,
Computer Studies of Phase Transitions and Critical Phenomena.
Springer-Verlag, Berlin, 1984.

\bibitem[Montanari]{Montanari-74}
Montanari, U,
``Networks of constraints: fundamental properties and applications to
picture processing'', {\it Information Sciences} 7 (1974), pp. 95-132.

\bibitem[Ladkin-Maddux]{LM-94}
Ladkin, P.B., and Maddux, R.D.,
``On binary constraint problems'', {\it Journal of the ACM} 41 (1994),
pp. 435-469.

\bibitem[Mackworth]{Mackworth-77}
Mackworth, A. K.,
``Consistency in networks of relations'', {\it Artificial
Intelligence} 8 (1977) pp. 99-118.

\bibitem[GJ-79]{GJ-79}
Gary and Johnson,
{\it Computers and Intractability: A guide to the theory of
NP-completeness}. Freeman, San Francisco (1979).

\bibitem[GS-92]{Sorkin-92}
Sorkin, Gregory,
{\it Theory and Practice of Simulated Annealing on Special Energy
Landscapes}. PhD Thesis, UC-Berkeley, Dept of EE and CS, 1992.

\bibitem[Shrijver-86]{Shrijver-86}
Shrijver, A,
{\it Theory of Linear and Integer Programming}, John Wiley and Sons,
Chichester, UK, 1986.

\bibitem[Shrijver-95]{Shrijver-95}
Shrijver, A,
{\it A Course in Combinatorial Optimization}, to be published in 1995.

\bibitem[Frost-94]{Frost-94}
Forest, Richard,
{\it Ensemble of Simulated Annealing}, SDSC, California, 1994.

\bibitem[van.Laarhoven-87]{van.Laarhoven-Aarts.87}
Van Laarhoven, and Aarts,
{\it Simulated Annealing: Theory and Applications}. D. Reidel,
Dordrecht (1987).

\bibitem[van-den-Bout.90]{Van-den-Bout.90}
Van den Bout, D. E, and T. K. Miller III. Graph partationing using
annealed neural networks. {\it IEEE Transactions on Neural Networks},
1(2):192-203, June 1990.

\bibitem[Johnson-89]{Johnson-89}
Johnson, Aragon, McGeoch, and Schevon,
Optimization by Simulated Annealing: an Experimental Evaluation, Part
I (Graph Partitioning). OR 37, 865-892 (1989).

\bibitem[Johnson-90]{Johnson-90}
David Johnson,
Local Optimization and the TSP, Springer Lecture Notes in CS 443,
446-461, Springer-Verlag, 1990.

\bibitem[Johnson-92]{Johnson-92}
Johnson, Aragon, McGeoch, and Schevon,
Optimization by Simulated Annealing: an Experimental Evaluation, Part
III (TSP). Work in progress.

\bibitem[Johnson-94]{Johnson-94}
David Johnson,
Data Structures for the TSP, to appear in the Jr. of Algorithms.

\bibitem[PS-88]{Shamos-88}
F. Praparata, M. Shamos, 
{\it Computational Geometry}, Springer-Verlag, 1988.

\bibitem[Min-88]{Minsky}
Minsky, Marvin and S Papert, {\it Perceptron} , 1988 edition.

\bibitem[EIS-76]{EIS-76}
Even, Itai, and Shamir,
``On the complexity of the timetable and multicommodity flow
problems'', SIAM Jr. Computing 5 (76), 691-703.

\bibitem[PS-89]{Peterson-89.1}
Peterson, S$\ddot{o}$derberg,
``A New Method for Mapping Optimization Problems onto Neural Nets'',
International Jr. of Neural Systems 1, 3 (1989).

\bibitem[GSP-89.1]{Peterson-89.2}
Gisl$\acute{e}$n, S$\ddot{o}$derberg, Peterson, 
``Teachers and Classes with Neural Nets'', 
Inter. Jr. of Neural Systems 1, 167 (1989).

\bibitem[GSP-91]{Peterson-91}
Gisl$\acute{e}$n, S$\ddot{o}$derberg, Peterson, 
``Scheduling High Schools with Neural Nets'', Lund 
University Preprint LU-TP-91-9, Lund, Sweden (1991).

\bibitem[Peterson-90]{Peterson-90}
Carsten Peterson, 
``Parallel Distributed Approaches to Combinatorial Optimization
Problems - Benchmark Studies on TSP'', Neural Computation 2, 261 (1990).

\bibitem[PS-92]{Peterson-92}
Peterson, S$\ddot{o}$derberg, 
``Artificial neural Nets and Combinatorial Optimization Problems'',
To appear in 
{\it Local Search in Combinatorial Optimization}, edited by Aarts and
Lenstra , second half of 1993.

\bibitem[S-91]{Stolorz}
Paul Stolorz, 
``Abusing Statistical Mechanics to do Adaptive Learning and
Combinatorial Optimization'', Preprint, Santa Fe Institute, Santa Fe,
New Mexico, Dec 1991.

\bibitem[HT-85]{Hop-85}
J. J. Hopfield and D. W. Tank, 
``Neural Computation of Decisions in Optimization Problems'',
Biological Cybernetics 52, 141 (1985).

\bibitem[Hopfield-84]{Hop-84}
J. J. Hopfield, ``Neurons with graded response have collective
computational properties like those of two-state neurons''.
Proceedings of the National Academy of Science USA 81, 3088-3092
(1984).

\bibitem[Simic-90]{simic-90}
P. Simic, ``Statistical mechanics as the underlying theory of
'elastic' and 'neural' optimizations'', Network 1, 89-103 (1990).

\bibitem[Simic-91]{simic-91}
P. Simic, ``Constrained Nets for Graph Matching and Other Quadratic
Assignment Problems'', Neural Computation, v.3, n.2, 268-281 (1991).

\bibitem[Wu-82]{Wu-82}
F. Y. Wu, ``The Potts model'', {\it Reviews of Modern Physics} 54,
235-268 (1982).

\bibitem[CDM-92]{Colorni-92}
A. Colorni, M. Dorigo, and V. Maniezzo, 
``On the use of genetic algorithms to solve the timetable problem'', 
report 90-060, Dipartimento Di Elettronica E Informazione, 
Politecnico Di Milano, Milano, Italia.

\bibitem[Hertz-92]{Hertz-92}
Alain Hertz, ``Finding a feasible course schedule using Tabu search'',
Discrete Applied Mathematics 35, 255-270, 1992.

\bibitem[Vidal-93]{Vidal-93}
{\it Applied Simulated Annealing}, edited by Rene Vidal, Lecture
Notes in Economics and Mathematical Systems no. 396, Springer-Verlag,
1993.

\bibitem[Gee-93.1]{Gee-93}
Andrew Gee,
Problem Solving with Optimization Networks, PhD Thesis, The Univ. of
Cambridge, Dept. of Engineering, Cambridge, UK, July 1993.

\bibitem[White-84]{White-84}
S. R. White, ``Concepts of scale in simulated annealing''. In
Proceedings of the IEEE Int. Conference on Circuit Design, pp 646-651,
1984. 

\bibitem[Simmen-93.1]{Simmen-93}
Martin Simmen,
PhD Thesis, Univ. of Edinburgh, Edinburgh, Scotland, UK, 1993.

\bibitem[Simic-93]{PC.1}
P. Simic, private communication.

\bibitem[Simmen-93.2]{PC.2}
Martin Simmen, private communication.

\bibitem[Gee-93.2]{PC.3}
Andrew Gee, private communication.

\bibitem[Peterson-92-93]{PC.4}
Carsten Peterson, private communications.

\bibitem[Carter-93]{Carter-93}
Mike Carter, private communications.


\end{thebibliography}
\end{document}

%% \appendix
%% \newpage
%% \renewcommand{\thesection}{Appendix A}
%% \renewcommand{\theequation}{\mbox{A}\arabic{equation}}
%% \pagestyle{myheadings}
%% \markright{Listing - Algorithm + Data Structures}
%% \setcounter{equation}{0}
%% \section{}
%% \appendix
%% \newpage
%% \renewcommand{\thesection}{Appendix B}
%% \renewcommand{\theequation}{\mbox{A}\arabic{equation}}
%% \pagestyle{myheadings}
%% \markright{Listing - the source code}
%% \setcounter{equation}{0}
%% \section{}



