\chapter{Scheduling as a Graph Coloring Problem}
\section{introduction}
Many scheduling problems involve allowing for a number of pairwise
restrictions on which jobs can be done simultaneously. For instance,
in attempting to schedule classes at a university, two courses taught
by the same faculty member cannot be scheduled for the same time
slot. Similarly, two courses that are required by the same group of
students also should not conflict. The problem of determining the
minimum number of time slots needed subject to these restrictions is a
graph coloring problem (GC).

GC has considerable application to a large variety of complex problems
involving optimization. Among those problems is the one we have dealt
with, which is a large scale academic class scheduling. Constraints
for these kind of problems --class scheduling or timetabling-- are
usually expressible in the form of pairs of incompatible objects
(e.g., pairs of classes that cannot be assigned to the same room at
the same time period). Such incompatibilities are usefully embodied
through the structure of a graph. Each object (e.g. class) is
represented by a node and each incompatibility is
represented by an edge joining the two nodes. A coloring of this graph 
is then simply a partitioning of the objects into blocks (or colors) 
such that no two incompatible objects end up in the same block. Thus,
optimal solutions to such problems may be found by determining minimal
coloring for the corresponding graphs. Unfortunately, this may not
always be accomplished in a reasonable amount of time.

\section{Mapping Scheduling onto GC}

Again, the mapping between a simple case of class scheduling and a
graph-based representation goes as follows: The events are represented
by the vertices of the graph, and a pair of vertices are joined by an
indirected edge if and only if the corresponding events cannot take
place at the same time. Scheduling the events subject to the given
constraints is therefor equivalent to coloring the corresponding graph
such that no two adjacent vertices are of the same color. The
determination of the minimum number of intervals of time needed for
the schedule is therefore the same as finding the minimum number of
colors required for the graph. This is known as the chromatic number
of the graph, and its determination for an arbitrary graph is yet
unsolved problem.

Let us look at a simple example to illustrate the mapping pictorially.
Suppose we have a graph with vertex set V and edge set E, where the
ordered pair (R,S) is in E if and only if an edge exists between the
vertices R and S. Two vertices in a graph are said to be adjacent if
an edge exists between them. Given these sets the overall GC problem 
is to partition the vertices into a minimum number of sets in such a
way that no two adjacent vertices are placed in the same set. Then, a
different color is assigned to each set of vertices, as shown in
Figure~\ref{fig.colored_graph_1}. This is known as a proper graph
coloring.

\begin{figure}[htb]
\large
   \centerline{\psfig{figure=colored_graph_1.eps,width=5in}}
   \caption{A proper graph coloring using three colors.}
   \label{fig.colored_graph_1}
\end{figure}

In regard to the scheduling problem, our objective is an attempt in
finding a schedule satisfying all of the hard constraints and if
possible, most of the soft constraints. One essential subset of the
hard constraints set is the time-based constraints, and the way to map 
them onto Figure~\ref{fig.colored_graph_1} is as follows: 

Let each course be represented by a vertex.
Two vertices are connected by an edge if and only if there is a reason
that the courses they represent may not be offered at the same time.
Initially, there are two such reasons for vertices to be linked:
either the courses they represent are taught by the same instructor,
or required by the same set of students.
Upon adding in the links between vertices, we assign colors to the
graph. Each color represents a different time slot, so every vertex
with the same color will be offered at the same time.

Now assume we have, for example, four physics courses: PHY 101,
PHY 234, PHY 300, and PHY 300 LAB. The first three which are lectures
are taught by the same professor, and the fourth which is a laboratory 
is taught by another professor. In addition, students enrolled in the
lecture section of PHY 300 need also to be enrolled in the lab section 
of the same course, and vice versa. These time-based hard constraints
are represented in the mapping as shown in
Figure~\ref{fig.temporal_constraints_2}. An edge exists between each
of the pairs of courses taught by the same professor, since these
courses cannot be offered at the same time. Also, an edge exists between
the nodes of PHY 300 and PHY 300 LAB, because the same set of students
must enroll in both courses. Figure~\ref{fig.temporal_constraints_2}
also shows a proper coloring with each node of the graph representing
a different time slot, so only three different time slots are needed
to properly schedule these four courses.
PHY 101 and PHY 300 LAB will be offered during the same time
slot, PHY 234 will be in a second time slot, and PHY 300 in a third
time slot.  Note that this system only partitions the courses into
groups which will be offered at the same time; it does not assign the
actual time of day. This assignment of groups to actual hours of the
day can be done in another phase of the scheduling process in which
soft constraints are handled.

\begin{figure}[htb]
\large
   \centerline{\psfig{figure=temporal_constraints_2.eps,width=5in}}
   \caption{A graph representing temporal hard constraints.}
   \label{fig.temporal_constraints_2}
\end{figure}


\section{Graph Coloring Algorithm}
When dealing with this kind of mapping between course scheduling and
graph coloring, the first algorithm that a researcher would
investigate would be the simple 
{\it saturation algorithm (DSatur, for short)} of Brelaz (ref:
Brelaz-79). As we mentioned in the previous section that the
timetabling problem need to be simple in order for methods such as
DSatur to be effective. Before outlining this algorithm, we would like
to briefly state one of the characteristics of the problem we have
dealt with to show our justification or reasoning for using this
algorithm. In addition, we also believe that our observations apply to
other similar instance of the problems. 

It is often the case that after carrying out the mapping, the
representative graphs tend to be loosely connected. One particular
reason for this that any college professor cannot be assigned to teach 
more than few courses per semester, perhaps maximum of four or
five. Therefore, graphs sometimes would show fully-connected clumps of
vertices representing those courses. That is partly the reason of
having fully (or almost fully) connected components within the overall
graph. Also, these components are usually loosely connected among
themselves, resulting in a somewhat sparse graphs.

Graph coloring algorithms such as {\it DSatur} have been shown to work
particularly quite well on sparse graphs. Figure~\ref{DSatur-1} and
Figure~\ref{DSatur-2} show two different versions of the same
algorithm. At the time when we used this technique, in the summer of
95, we tweaked with it and made two modifications to accommodate our
problem setup.
\begin{enumerate}
\item One of the main constraints of course scheduling is the fixed
number of available time slots per week, and the preference to
distribute the courses among each of these time slots so that students 
have many options when selecting courses. Therefore, we modified
{\it DSatur} to select colors for vertices so that, among the
previously used legal colors for a vertex in {\bf V}, the one used the 
fewest number of times previously was selected. This small
modification to the algorithm served to distribute the courses more
evenly over the time slots. In a typical graph coloring setup, a user
usually tries to minimize the number of colors used.

\item The second modification to {\it DSatur} is that, due to our use
of two sets of timeslots (lecture and laboratory timeslots) and also
due to our criterion of scheduling one set prior to the other, we had
to modify the method to color the lecture-of-course set of vertices
first, followed by the lab-of-course set of vertices. Without this
modification there is no distinction between various sets of
vertices. Also, during the scheduling process we needed to do
``re-coloring'' of the graph that was constructed to get a legal
schedule.
\end{enumerate}

\begin{figure}
\begin{center}
Let {\bf V} denote the vertex set, and {\bf E} denotes the set of
edges of the graph.
\begin{itemize}
\item {\bf Repeat} until all vertices are colored
\begin{enumerate}
\item Choose the next vertex {\bf v} from {\bf V} to be colored by
selecting the one whose neighbors have already used the most
colors. Break ties by choosing the one with the most uncolored
neighbors.
\item Color vertex {\bf v} with the first color in the set of all
colors that have not been already used by one of the neighbors, {\bf
x} of {\bf V}, such that {\bf v} and {\bf x} are not equal.
\end{enumerate}
\item End {\bf Repeat}.
\end{itemize}
\end{center}
\caption{DSatur Graph Coloring Algorithm -- version 1}
\label{DSatur-1}
\end{figure}

\begin{figure}
\begin{center}
Let {\bf V} denote the vertex set, and {\bf E} denotes the set of
edges of the graph.
\begin{enumerate}
\item Initially take any node with the largest possible number of
neighbors and color it with the smallest color.
\item In general, for each {\bf v} of {\bf V}, there is a set {\bf
F(v)} of forbidden colors (these may be colors which have already been 
assigned to neighbors of {\bf v}).
\item At each step, we choose a node {\bf x} of {\bf V} for which the
cardinality, {\bf |F(x)|}, of {\bf F(x)} is maximum (highest
connectivity with the neighbors), and we color it with the smallest
possible color.
\end{enumerate}
\end{center}
\caption{DSatur Graph Coloring Algorithm -- version 2}
\label{DSatur-2}
\end{figure}

It is interesting to notice that the {\it DSatur} method is an example 
of a heuristic procedure for general graphs which is derived from an
exact method designed for coloring bipartite graphs (for these we have 
$|F(x)| \leq 1$ at each step). There are other coloring methods that
slightly differ from {\it DSatur} in their choice of the next node to
be colored as well as the color which it will receive.

\section{Some Experimental Results}

--- More on the work done in 1995 using a small set of data (about 450 
science and engineering courses from Fall 93 at SU) here ...
---

