% Contact: kiaer@nextwork.rose-hulma 
\documentstyle[12pt]{article}

\title{Solving Practical Timetabling Problems With Simulated Annealing}
\author{ Trevis Litherland \and Ken Schmidt \and Kevin Neier \\ {\em Rose-Hulman  
Institute of Technology} \\ {\em Terre Haute, IN 47803}}
\date{January 15, 1993}

\begin{document}

\maketitle

We propose to examine the usefulness of simulated annealing for a collection of practical  
problems based on final examination scheduling at Rose-Hulman Institute of Technology.   
The final examination scheduling problem at Rose-Hulman is made especially difficult  
because of the large number of common final exams together with the relatively small (11)  
number of timeslots.

There are three principal elements of this research project: first, the collection and  
formulation of real timetabling problems; second, the generation of `random' problems that  
have the same general structure as the actual problems encountered, and the generation  
of random problems withour any particular structure; and finally, the evaluation of the  
performance of one or more simulated annealing algorithms on both actual and random  
problems.  In addition, the solutions obtained by simulated annealing will be compared  
with traditional `by-hand' final examination schedules.

The problem will be modelled both as a traditional vertex coloring problem and as a  
weighted graph coloring problem, with the weights on the edges representing the number  
of students enrolled in the two courses represented by the endpoints of the edge.  This will  
enable a `Fixed-$k$' approach to find an optimal final examination schedule if the  
chromatic number of the graph is larger than the number of available timeslots.  We are  
also examining ways to discourage consecutive examinations, either within the simulated  
annealing algorithm or as a post-optimization procedure.

As with all real problems, there are additional constraints to be dealt with.  One of the main  
ones at Rose-Hulman involves room assignment.  Due to the computer-oriented nature of  
many of Rose-Hulman's courses, only certain workstation-equipped rooms can be used for  
certain finals;  class and classroom size are also factors, and classroom space is very  
tight.  Thus, in addition to solving standard and weighted-graph vertex coloring problems,  
we also intend to incorporate the room assignment problem in the simulated annealing  
algorithm.

Preliminary investigation of the structure of the timetabling graph suggests that vertices  
tend to be clustered, with some clusters representing majors and others representing  
course levels.  We will examine the effect on the simulated annealing algorithm of graphs  
with clusters that are comparatively disjoint as well as those in which many vertices  
belong to more than one cluster.

\end{document}