% paper.tex
% Final report for REU project, summer 1995
\documentstyle[11pt,epsf,psfig]{article}

%\documentstyle[twoside,11pt]{article}
%\include{psfig}
\setlength{\oddsidemargin}{+1in}
\setlength{\evensidemargin}{+.6in}
\setlength{\topmargin}{+5mm}
\raggedbottom

\begin{document}
\cleardoublepage
\pagestyle{myheadings}

\title{\bf Optimizing Timetabling Solutions \\Using Graph Coloring\thanks 
{Project completed as part of the 1995 Research Experiences for
Undergraduates (REU) Program in High-Performance Computing conducted
by the Northeast Parallel Architectures Center (NPAC) at Syracuse
University.  The National Science Foundation provides primary funding
for the NPAC REU program, through NSF Grant CDA-9424332.  Additional
funding is provided by Syracuse University and NPAC.}}

\author{Sara~K.~Miner\thanks{1995 NPAC REU Program, Computer Science
    and Mathematics double major, University of Dayton, {\it
      sminer@npac.syr.edu,
      minersak@udavxb.oca.udayton.edu}.}
\and
Saleh~Elmohamed\thanks{NPAC, Syracuse University,
{\it saleh@npac.syr.edu}.}
\and 
Hon~W.~Yau\thanks{NPAC, Syracuse University, 
{\it hwyau@npac.syr.edu}.} }

\date{}

\maketitle \markboth{Miner \& Elmohamed \& Yau}
{Optimizing Timetabling Solutions}

\begin{abstract}
A method using graph coloring was developed for optimizing solutions
to the timetabling problem, specifically the example of scheduling
courses at a university given fixed time and space constraints.  
Previous work on this problem preprocessed data with an expert system
to arrive at a partial solution, and then performed simulated
annealing to fill out the solution.  The heuristic using graph
coloring was designed to replace this expert system.  The expert
system and simulated annealing (using geometric annealing) combination
often scheduled only a percentage of courses, whereas the graph
coloring method was designed to produce a complete solution on its
own.  This complete solution will then be refined through the use of
other methods such as simulated annealing.
\end{abstract}


\section{Introduction}

In order to find the optimal solution to NP-hard problems, such as the
graph coloring problem, which is discussed in detail in the following
sections, one must consider all possible solutions in order to choose
the best one.  However, solutions to practical problems are often
desired much sooner than an exhaustive search algorithm can provide
them.  Consequently, heuristics, which produce 'near-optimal' or
'sub-optimal' solutions in much less time, have been developed for
such problems. For example Brelaz\cite{Brelaz} and
Leighton\cite{Leighton} have found efficient heuristics which produce
good solutions to the graph coloring problem.

Another NP-hard problem is the timetabling problem, which can be
stated as follows: schedule a set of related events in a minimal block
of time such that no resource is required simultaneously by more than
one event.  Because many practical applications of the timetabling
problem exist, such as the scheduling of courses at a university, the
scheduling of flights for an airline, and the scheduling of computing
tasks to be run on a multiprocessor machine, a heuristic which quickly
produces good solutions would be useful.

In previous work on the scheduling of courses at a university
\cite{Elmohamed}, experiments were done using several methods, 
including an expert system alone, an expert system as a preprocessor
for simulated annealing, and an expert system as a preprocessor for
mean field annealing. Best results were achieved by the expert system
used as a preprocessor to simulated annealing. However, often this
method could not successfully schedule all the courses. The expert
system produced only a partial solution, and the simulated  annealing
effort was not able to fill out the solution entirely in all cases. A
forthcoming paper will report on the abovementioned multi-phase
approach of expert system/simulated annealing.

\subsection{Course Scheduling}

The scheduling of courses at a university is a practical example of
the timetabling problem.  In this example, the resources involved,
which may be required by no more than one course at any particular
time, are instructors, classrooms, and students.  This problem can be
addressed from different angles.  For example, one could assume that a
particular set of courses will be offered during a term by particular
instructors, and first assign them times and rooms, and then allow
students to register only for courses whose times do not conflict.  A
second approach would be to decide which courses would be offered,
allow students to register for them, and then assign times and rooms
to each course, so that the number of students who have course
conflicts is minimized.  The project discussed here looks at the
problem from the first of these two points of view.  The restrictions
involved in creating a schedule of courses from this point of view may
be divided into two categories, 'hard' and 'soft' constraints.

Hard constraints are those which must be satisfied in order to have a
legitimate or {\em legal} schedule.  For example, courses may only be
offered during a fixed set of days and times during the week, and each
course must meet a particular number of hours per week.  No instructor
may be scheduled to teach two courses during the same time slot.
Similarly, courses which enroll the same set of students, such as a
physics lecture course and the accompanying laboratory course, may not
be scheduled in the same time slot, since there is an overlap of
students in the two classes.  Each of these hard constraints deals
with time-related, or temporal, issues.

In addition to temporal constraints, there are other hard constraints
which deal with meeting space assigned to each course.  These
spatial constraints arise from the fact that a fixed number of rooms
exist on a given campus, and any courses held during the same time
slot may not be held in the same room.  In addition, since rooms have
a fixed size, course size must not exceed the capacity of the room it
is assigned.  Furthermore, each room is of a particular type, such as
auditorium, laboratory, or seminar room.  Similarly, each course
requires one of these types of rooms, so room type must be a
consideration in the assignment of rooms.

Soft constraints associated with creating a course schedule are
requests that should be fulfilled, if possible.  However, if soft
constraints are not fulfilled, the schedule is still considered legal
provided that all hard constraints have been satisfied.  For example,
an instructor may request a particular time slot free during the week,
or may want a lecture hall in the same building as his or her office.
All instructors may prefer that, if they teach two courses in
contiguous time slots, the courses are not in different buildings.
These types of constraints are reasonable, but it may not be possible
to fulfill each of these in addition to all of the hard constraints.

\subsection{Graph Coloring}

Many practical constraint satisfaction problems, such as timetabling
problems, can be mapped onto graph coloring problems.  The problem of
graph coloring can be described as follows.  Suppose a graph exists
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.  The problem of graph coloring 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}


\section{Methods}

In order to find an optimal solution to the problem of scheduling
courses, one attempts to find a schedule which satisfies all of the
hard constraints and maximizes the number of soft constraints
satisfied.  The task of the project was to utilize graph coloring to
find a complete schedule which satisfied all of the hard constraints.
Simulated annealing or a similar local search method would then be
used to maximize the number of soft constraints satisfied in the
schedule.

\subsection{Temporal Hard Constraints}

Temporal hard constraints can be mapped onto the graph coloring
problem as follows.  Let each course be represented by a vertex.
Attach two vertices 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 they are taught by the same instructor, or they are required by
the same set of students.  Upon adding in the links, color the graph.
Each color represents a different time slot, so every vertex with the
same color will be offered at the same time.

For example, suppose four physics courses must be scheduled: PHY 101,
PHY 234, PHY 300, and PHY 300 LAB.  The same instructor teaches all
three lectures, and a second instructor teaches PHY 300 LAB.
Additionally, students enrolled in PHY 300 are required to enroll in
PHY 300 LAB concurrently, and vice versa.  The graph shown in
Figure~\ref{fig.temporal_constraints_2} represents these temporal
hard constraints.  An edge exists between each of the pairs of courses
taught by the same instructor, since these courses may not be offered
at the same time.  An edge exists between 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
of the graph.  Each color represents 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 will come from the simulated annealing portion of the method, so
that the number of soft constraints fulfilled can be maximized.

\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}


\subsection{Saturation Graph Coloring Algorithm}

The graphs representing courses will tend to be rather loosely
connected.  Because any given professor teaches at most four or five
courses per semester, we would find many groups, or 'clumps' of four
or five vertices each connected to all of the vertices in that group,
and then very few edges connecting clumps together, since few courses
have co-requisites.  Consequently, the graph coloring algorithm
chosen, known as the Saturation algorithm, or DSatur, and shown in
Figure~\ref{fig.saturation_3}, was selected because of its proven
ability to work well on sparse, or loosely connected, graphs
\cite{Brelaz}.  However, two modifications to the algorithm were
necessary to relate the algorithm to the real-world problem of course
scheduling.  These modifications both dealt with the time slots
available for courses, and are explained in the following two
sections.

\begin{figure}[htb]
\large
   \centerline{\psfig{figure=saturation_3.eps,width=3in}}
   \caption{The standard Saturation algorithm.}
   \label{fig.saturation_3}
\end{figure}


\subsubsection{Fixed Number of Time Slots Available}

In a standard graph coloring, one minimizes the number of colors used.
However, in scheduling courses, there are a fixed number of time slots
per week, and it is preferable to distribute the courses among each of
these time slots, so that students have many options when selecting
courses.  Therefore, the standard coloring algorithm was modified to
select colors for vertices so that, among the previously-used legal
colors for a vertex, the one used the fewest number of times
previously was selected.  This modification served to distribute the
courses more evenly over the time slots.

\subsubsection{Types of Time Slots}

The second modification to the standard graph coloring algorithm was
necessary due to the fact that time slots for university courses can
take different forms.  Specifically, the types of time slots dealt
with in this project 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=4in}}
   \caption{Time slots belonging to two overlapping sets.}
   \label{fig.time_slots_4}
\end{figure}

Consequently, due to the two sets of time slots, the graph coloring
algorithm was modified to color the lecture-course vertices first,
then the lab-course vertices.


\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 and Test Data}
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 to maximized the number of soft constraints
satisfied, using a system such as simulated annealing.

The data used in testing the system was supplied by Syracuse
University.  Over 450 science and engineering courses from the 1993
Autumn semester were scheduled into fewer than 185 rooms.

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

\section{Conclusions}

The main conclusions to be drawn from this project are comparisons
with previous efforts.  Prior to this project, some of the best
results were obtained from a multi-phase approach of an expert system
acting as a preprocessor to simulated annealing using an adaptive
cooling schedule.  However, the expert system ran somewhat slowly,
required a large base of knowledge, and did not handle all of the
constraints in the problem.
 Specifically, it had no restriction on
 the total number of time slots allowed per week, and it did not allow
 for two sets of time slots for lecture and laboratory courses.
Furthermore, it did not always produce a complete solution; sometimes
it would schedule only a percentage of the courses.

In contrast with the expert system, the graph coloring-based system
discussed in this paper runs considerably more quickly, and does
handle all of the hard constraints of the problem.  In addition, it
never produces a partial solution.  One change that would be
worthwhile in the system would be to color the laboratory-course
vertices before the lecture-course vertices, rather than coloring 
in the opposite order.  Initially, no distinction was made between the
two types of vertices, but upon further reflection, the change would
make more efficient use of the coloring algorithm.

It should be noted here that this system does not guarantee a solution
for every set of data where a solution is possible.  This is due to
the fact that the algorithms used here are heuristics.  However, when
it does produce a good solution, it does so much faster than other
automated systems encountered, and certainly with much less effort
than a method where humans are performing the optimization manually.

\section{Future Work}

Future work on this project should include testing the scheduling
system with additional sets of data, especially larger sets.  The next
step would be to fully implement the set of soft constraints in a
simulated annealing system so that the two systems can be used
together to produce an optimal solution to the course scheduling
problem.

\section{An Update - 1996}

We have expanded the expert system to deal with two sets of time
slots, one for lectures and the other for laboratories. Also we have
restricted the overall number of timeslots per day for the
schedule. Furthermore, we have added more rules and knowledge to the
system producing a better result. What is lacking now is that the
expert system still cannot handle all of the soft constraints.

\section*{Acknowledgments}

First, I would like to express my appreciation to Paul Coddington
and Nancy McCracken for giving me the opportunity to spend the
summer at Syracuse, and the National Science Foundation and NPAC for
funding the REU program. Secondly, I would like to thank all of the
people at NPAC, who were very helpful when I needed assistance,
especially Saleh Elmohamed, who put in many hours on the project with
me each day, and who was available any time a problem surfaced.  I
would especially like to thank my project advisor Hon Yau for his
input, advice, patience, and the long hours he put in all summer with
me in the conference room. And, finally, thank you to each of my
fellow REU-ers for making my summer very educational and truly a lot
of fun.


\begin{thebibliography}{99}

\bibitem{Brelaz}
Brelaz, D. ``New Methods to Color the Vertices of a Graph'', 
{\it Communications of the ACM}, 1979, {\bf 22}(4), 251-6.

\bibitem{de_Werra}
de Werra, D. ``An introduction to timetabling,'' 
{\it European Journal of Operational Research}, 1985, {\bf 19}, 151-162. 

\bibitem{Elmohamed}
Elmohamed, S., et al. ``Mean field annealing, simulated annealing, and
non-Euclidean combinatorial optimization problems: The case of
academic course scheduling, (Part I: algorithms, Part II:
implementations),'' NPAC preprint.

\bibitem{Johnson}
Johnson, D.S., et al.  ``Optimization by Simulated Annealing: An
Experimental Evaluation; Part II, Graph Coloring and Number
Partitioning,'' {\it Operations Research}, 1991, {\bf 39}(3), 378-406.

\bibitem{Leighton}
Leighton, F.T. ``A Graph Coloring Algorithm for Large Scheduling Problems,''
{\it Journal of Research of the National Bureau of Standards}, 1979, 
{\bf 84}(6), 489-506.

\end{thebibliography}

\end{document}
