\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 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 usually 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 Graph Coloring}

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~\cite{B:color}. As we mentioned in the previous section that
the course scheduling problem needs to be simple in order for methods such as 
{\it 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 is 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 well on sparse graphs. Figure~\ref{DSatur-1} and
Figure~\ref{DSatur-2} show two different versions of the same
algorithm.

\begin{figure}[htb]
\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 (I)}
\label{DSatur-1}
\end{figure}

\begin{figure}[htb]
\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 (II)}
\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.

At the time when we used this algorithm we tweaked with it 
and made two modifications, both dealing with the available time slots
for courses in order 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}  was
necessary due to the fact that time slots for university courses can
take different forms. Specifically, the types of time slots dealt
with were of two types, although the modification to
the graph coloring algorithm can be generalized to more than two
types. The first type of time slots, called lecture time slots, were
three-credit hour courses that met either three times per week for an
hour at a time, two times per week for an hour and a half at a time.
The second type of time slots, called laboratory time slots, meet for
one three-hour period each week.  In order to accurately represent
these time slots with colors, two related sets of colors were
developed, as illustrated in Figure~\ref{fig.time_slots_4}.
 
For example, consider three lecture courses exist which have been colored
red, blue, and green.  Suppose these colors represent the slots which
meet for one hour each on Monday, Wednesday, and Friday at 9:00,
10:00, and 11:00, respectively.  Then consider a laboratory course
which is taught by the same professor as one of the lecture courses
already colored red, blue or green.  This lab course may not be
assigned the time slot that corresponds to Monday 9-12:00, Wednesday
9-12:00, or Friday 9-12:00, since it would overlap the lecture course.
So those three laboratory time slots must be represented by colors
which clearly identify the fact that no vertex adjacent to a red,
blue, or green lecture course vertex may be given these colors.
Therefore, these time slots were labeled with all three conflicting
lecture vertex colors, as red-blue-green.  However, two different
laboratory courses taught by the same instructor could both be
scheduled for the red-green-blue time slots, as long as they were on
different days.  So the red-green-blue laboratory time slots that met
on Monday, Wednesday, and Friday were called red-blue-green-Monday,
red-blue-green-Wednesday, and red-blue-green-Friday, respectively, to
distinguish them from one another.

\begin{figure}[htb]
\large
   \centerline{\psfig{figure=time_slots_4.eps,width=5in}}
   \caption{Time slots belonging to two overlapping sets.}
   \label{fig.time_slots_4}
\end{figure}

Consequently, 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}

\subsection{Spatial Hard Constraints}
Once the modified graph coloring algorithm has partitioned the
vertices into time slots, a room must be assigned for each course in
each time slot.  One constraint that must be fulfilled is that no
course may be assigned to a room which has a smaller capacity than the
maximum enrollment of the course.  Additionally, each room available
on campus is of a particular type, such as lecture, seminar,
laboratory, etc.  Each course requires one of these types of rooms.
Furthermore, some rooms are reserved by particular departments for
their courses only, such as a chemistry laboratory room, while other
rooms are general usage rooms, for any department to use.  An
algorithm was developed to assign all of the courses which have been
assigned to the same time slot to appropriate rooms, assigning courses
to the rooms reserved by department first, then the general purpose
rooms, always considering the largest capacity rooms and largest
courses first.

However, this simple algorithm alone is not sufficient.  Consider the
case where 25 courses of maximum enrollment 100 are assigned to the
same time slot.  Suppose that only 20 rooms of capacity 100 or greater
exist on campus.  There is no way to create a legal schedule of
courses with all 25 courses in the same time slot.  The solution to
this problem was to re-color the graph, having added edges between
each of the vertices representing ``leftover'' courses, that is, those
who did not get assigned a room, and then re-assign rooms.  Adding the
edges between these vertices ensures that they will not end up
assigned to the same time slot, and therefore will not vie for the
same rooms at the same time.

\subsection{Structure of Code}
The structure of the code, when the algorithms for both temporal and
spatial constraints are included, is shown in
Figure~\ref{fig.code_structure_5}.  This code produces a full legal
solution to the course scheduling problem, that is, one that satisfies
all of the hard constraints.  Ideally, this solution would then be
slightly altered or fed into the next phase of simulation to satisfy the
maximum number of the soft constraints.

\begin{figure}[htb]
\large
   \centerline{\psfig{figure=code_structure_5.eps,width=5in}}
   \caption{The overall structure of the course scheduling algorithm.}
   \label{fig.code_structure_5}
\end{figure}


