\chapter{The Course Scheduling Problem}

\section{Introduction to the Problem}

A course schedule is characterized by a triplet ({\bf t,g,a}) -- or
assignments, where {\bf t} is timetabling assignment of time slots to
a set of events, {\bf g} is assignment of students to sections of the
given courses, and {\bf a} is classroom assignment to the course
sections, all subject to constraints on these assignments. 

The NP-complete {\it professors and classes} scheduling problem is a
constraint satisfaction problem that can be briefly stated as follows:

For a certain school with $N_p$ professors, $N_q$ classes, $N_x$
classrooms and lecture halls, and $N_s$ students, it is required to 
schedule $N_l$ professor-class pairs within a time
limit of $N_t$ time slots producing a legal schedule. A legal schedule
needs to be found such that no professor, class, or student is in more
than one place at a time, and no room is expected to accommodate more
than one lesson at a time or more students than its capacity. 

\subsection{Constraints of the Problem}

University course scheduling, like almost all practical problems pose
constraints in varying degrees that need to be satisfied in order to
generate feasible solution(s) to the problem. Perhaps at first we
might think that constraining problems like this would make things
easier -- after all, we'll have a smaller search space to worry about
and therefore fewer possibilities to consider. Well, that may be
partially true but we need to keep in mind that to search for
improved solutions we may have to be able to move from one solution to 
the next. Therefore, we need some kind of 'operators' that will act on 
feasible solutions and hopefully in turn generate new feasible
solutions that are an improvement over what we have already found. It
is really here where the geometry of the search space gets quite
complicated as we found out dealing with a real world large scale
academic scheduling problem.

To start with, for a single semester, we have to make a list of all
the courses that will be offered. Then, we need a list of all students 
assigned to each class, and the professor assigned to each class
too. Also, we need a list of all available classrooms noting the
location, size, and other facilities that each offer (e.g. white
boards, video projectors, lab equipments, and so forth). In addition,
we would like to have a list of buildings including the actual
distances between them.

Given the above data we have tackled the problem with respect to three 
types of constraints: hard, medium and soft. 

\noindent
{\bf Hard constraints} are usually constraints that physically cannot be
violated. They absolutely must be satisfied in order to have a
feasible solution. This type of constraints includes events that must
not overlap in time, such as:
\begin{itemize} 
\item classes taught by the same professor;
\item classes held in the same room;
\item a class and a recitation or a lab of the same class.
\end{itemize}
%
Another examples are space or room constraints:
\begin{itemize}
\item {\bf Room Type}\footnote{This can be considered as medium
constraint.}: Some classes, such as laboratories, require a 
certain type of room with the requisite facilities for the type of
instruction. For example, a chemistry lab must have beakers, Bunsen
burners, the appropriate chemicals, safeguards, etc.)
\item {\bf Room Size}: A class cannot be assigned to a
particular room unless the capacity of the room (denoted by $R_c$) 
is greater than or equal to the class enrollment (denoted by $C_e$). 
The smaller the difference between these two sizes, the better the
assignment.
\end{itemize}


There is a cost associated with any violation of these
constraints. 

 For the {\bf Room Size}\footnote{This can be considered as medium
or soft constraint.} constraint our cost function
$C_{rs}$ computes the magnitude of the difference between the room
capacity $R_c$ and the class enrollment $C_e$ as follows:

\be{room-constraint}
C_{rs}=
\twoif{{(C_e - R_c)}^2} {\text{if} C_e > R_c\,,}
{\tanh((1.0 - {C_e \over R_c}) \beta \gamma) (R_c - C_e)}
{\text{otherwise.}}
\ee

In our experiments, the parameters $\beta$ and $\gamma$ were set to
0.4 and 0.8, respectively. When the class enrollment is larger than
the room size, this function will always yield a much higher cost
than the cost incurred from the assignment of a class with an
enrollment that is smaller than the room size. The use of $\tanh$
function is to non-linearize the cost and not to make its increase
directly proportional to the difference between room size and class
enrollment.

There is also a cost assigned to any violation to the constraint that
certain classes cannot be scheduled at the same time or have any
overlap in the scheduled times. This is called {\it exclusion cost}
$C_x$ and derived as follows:


\be{exclusion-constraint}
C_x =
\fourif{(end(c_i) - s(c_j)) Rlen(c_i,c_j)} {\text{if} (s(c_j) > s(c_i))\,
\text{and} \, (end(c_i) \geq s(c_j))\,,}
{(end(c_j) - s(c_i)) Rlen(c_i,c_j)} {\text{if} (s(c_j) < s(c_i))\,
\text{and} \, (end(c_j) \geq s(c_i))\,,}
{(end(c_j) - s(c_i)) Rlen(c_i,c_j)} {\text{if} (s(c_j) \geq s(c_i))\,
\text{and} \, (end(c_i) \geq end(c_j))\,,}
{(end(c_i) - s(c_j)) Rlen(c_i,c_j)} {\text{if} (s(c_i) \geq s(c_j))\,
\text{and} \, (end(c_j) \geq end(c_i))\,.}
\ee

where the relation between the two class durations is defined as
follows:

\be{relative-length}
Rlen(c_i,c_j)=
\twoif {len(c_i) / len(c_j)} {\text{if} len(c_i) \geq
len(c_j)\,,}
{len(c_j) / len(c_i)} {\text{otherwise.}}
\ee

The first and second choices of $C_x$ take care of any partial
overlaps between $c_i$ and $c_j$, while the third and fourth
choices take care of any complete overlaps between the two classes. 

\subsection{Strategy for Problem Solving}

As mentioned above, hard constraints must satisfied to have a feasible 
solution. So, from what we have presented so far, we could say that
any assignment that meets those hard constraints would solve our
problem. This means that our task is quite similar to the
satisfiability problem (SAT)~\cite{SKC:sat, SLM:sat, SK:sat, GJ:candi,
CLR:algorithms}: to find an assignment of classes (as compared with
Boolean variables) such that an overall evaluation function returns a
value of TRUE. Anything that violates the constraints means that our
evaluation function returns a value of FALSE. But this alone does not
give us sufficient information to guide the search for a feasible
solution.

Well, we might be able to employ a certain strategy 
that could provide this additional information. For example, we might
judge the quality of the solution not just by whether or not it
satisfies the constraints, but for those assignments that fail to meet 
the constraints, we could tally the number of times that the
constraints are violated (for example, each time a student is assigned 
to two classes that meet at the same time we increase the tally). This 
would give us a quantitative measure of how poor our infeasible
solutions were, and it might be useful in guiding us toward
successively better solutions, minimizing the number of constraint
violations. We could apply different operators for reassigning courses 
to classrooms, professors to courses, and so forth, and over time we
would hope to generate a solution that met the available
constraints. But then we have other types of constraints to worry
about, and those are {\it medium} and {\it soft}.

\noindent
{\bf Medium constraints} are usually considered to be those
constraints that fall into the gray area between the hard and soft
constraints~\cite{EL:combinatorial}.  
In our implementation, we define medium constraints to be constraints
such as time and space conflicts which, like hard constraints, cannot
physically be violated (for example, it is not possible for one person
to be in two different classes at the same time). However we consider
these constraints to be medium rather than hard if they can be avoided
by making adjustments to the specification of the problem. The primary
example is student preferences. We cannot expect to be able to satisfy
all student class preferences, in some cases, certain students will
have to adjust their preferences since certain classes will clash, or
will be oversubscribed.

Medium constraints have a high penalty attached to them, although not
as high as that associated with the hard constraints. In the final 
schedule the penalty of these constraints should be minimized and 
preferably reduced to zero. Some examples of medium constraints are:

\begin{itemize}
\item Avoid time conflicts for classes with students in
common.\footnote{This can be considered a hard constraint.}
\item Eligibility criteria for the class must be met.  
\item Do not enroll athletes in classes that conflict with their sport
      practice time (of course, depending on the sport).
\item The predecessor-successor relation between the topics is
  satisfied. That is, if undergraduate prerequisite courses are
scheduled for the same day as their counterpart graduate courses, they 
should be given earlier than the graduate course (this facilitate
learning foundational material prior to advanced material in the same
day).\footnote{This can be considered as soft constraint.}
\item Two courses of a same topic are scheduled on two different
  working days.\footnote{This can be considered as soft constraint.}
\end{itemize}

\noindent
{\bf Soft constraints} are preferences that do not deal with time
conflicts, and have a lower penalty (or cost) associated with them. We
aim to minimize the cost, but do not expect to be able to reduce it to
zero. Some examples are:
\begin{itemize}
\item Balance or spread out the lectures over the week. That is,
courses that meet three times per week should preferably be assigned
to Mondays, Wednesdays, and Fridays. Other assignments are not
desired. Also, courses that meet twice a week should preferably be
assigned to Mondays and Wednesdays or Tuesdays and Thursdays. Having
these courses meet on consecutive days or with two or more days in
between is not desired.
\item For each student, balance the three-day ({\it Mon, Wed, Fri}) 
      as well as the two-day ({\it Tue, Thu}) schedules.
\item Classes may request contiguous time slots.
\item Balance enrollment in multi-section classes.
\item Lunch and other break times may be specified.
\item Professors may request periods in which their classes are not
  taught.\footnote{This can be considered as medium or hard constraint.}
\item Professors may have preferences for specific rooms or types of
  rooms.
\item Number of teachers assigned to a course in each semester should
be bounded between a lower and an upper bounds on the number of
sections of that course.
\item Only professors can teach graduate courses.
\item No professor can teach more than a specified number of graduate
courses per year.
\item Once a class enrollment exceeds the upper limit, the class is
split into multi-sections.
\item Minimize the distance between the room where the class is
  assigned and the building housing its home department.\footnote{This
can be considered as medium constraint.}
\item Faculty having the ideal number of teaching days.
\end{itemize}

Some soft constraints may have higher priority (and thus higher cost)
than others. For example, preferences involving professors will have
higher priority than the preferences of students.

We have dealt with the distance minimization constraint in the
following way. Given the various building preferences of the
departments, we have constructed a matrix $M_{IJ}$ between all the
academic departments $I$ and all the buildings involved in scheduling 
$J$. Using $M_{IJ}$ in conjunction with the (appropriately scaled)
distance between all buildings involved in the process,  a final
distance matrix $Q$ is derived and directly used in the scheduling
process. Also, unless otherwise stated, a department's home building
is always the first preference for the department classes to be
assigned.

Let $B$ denote the set of all $k$ buildings, $D$ denote the set of all
$n$ departments. Also for department $d_i$ where $1\leq i \leq n$ the
distance to all buildings $B$ is a vector denoted by $<d_i,b_j>$ where
$b_j \in B$ and $1\leq j \leq k$.  At each step of the scheduling
process and according to $d_i$ space preferences, $d_i$ courses would
be scheduled into buildings $B^{'}$ where $|B^{'}| \leq |B|$ and the
distance is denoted by the vector $\ll d_i, b_j \gg$ where $b_j \in
B^{'}$. In addition, let $|B^{'}| = k^{'}$.

Now the cost associated with the distance of department $d_i$ is
computed as follows:

\be{dist-cost}
C_{d_i}^{dist} = {{\sum_{j=1}^{k^{'}} \ll d_i, b_j \gg} \over  
{\sum_{j=1}^k <d_i, b_j>}}\;\; k^{'}
\ee

The cost function is the {\it distance ratio} of department(i)'s
buildings of preference to all available buildings multiplied by the
number of  department(i)'s preferred buildings. Notice that for a
particular department the denominator of equation \ref{dist-cost}
stays fixed the scheduling process.

Other constraints that may need to be taken into account during the
scheduling process:
\begin{itemize}
\item It is not the case, in general, that all classrooms are
  available for all subjects. In reality, many subjects require
  special purpose rooms. 
\item Some rooms may be declared unavailable during any time period.
\item Daily limits must be specified to restrict the assignment of
more than a specified number of classes per day to each professor.
\end{itemize}


\subsection{Constraint handling in Course Scheduling -- problem
solving strategies}

Certainly there are many more such soft constraints than those listed
above. Any assignment that meets the hard constraints is feasible, but
not necessarily optimal in light of the medium and soft (non-hard)
constraints. Here is where the problem gets quite tricky. First, we
have to quantify each of the non-hard constraints into mathematical
terms so that we can evaluate any two candidate assignments and decide
that one is better than the other. Next, we have to be able to modify
one feasible solution and, hopefully, generate another feasible
solution that better meets the non-hard constraints. 

In terms of the first issue: each non-hard constraint has to be
quantified. For example, consider the above first soft constraint, we
could say that for each case where a solution is feasible, we could
count up the number of times twice-a-week courses become separated by
two or more days, or are placed on consecutive days, and use this as a 
penalty term. The lower the term, the better the solution. In fact, we 
could employ a similar approach to each of the non-hard
constraints. But what would we do when we are done? We would still
need an overall method for considering the degree of violation of each 
of these constraints. That is, we would have to determine the answers
to questions such as: which is worse, scheduling a certain percentage
of students to have back-to-back classes, or scheduling back-to-back
classrooms at the opposite ends of the campus? each of these possible
tradeoffs would have to be considered and quantified in some
evaluation function, which poses quite a challenge!

Of course it is worse than that, because even after all these non-hard 
constraints have been quantified, we are still left with the problem
of searching for the best assignment: the solution that is both
feasible and minimizes our evaluation function for the non-hard
constraints. Suppose we have a feasible solution, but it does not do
very well with regard to the non-hard constraints. Say, we apply some
variation operators (i.e swapping rooms or classes) to this solution
and significantly improve the situation with respect to the soft
constraints, but in so doing, we generate a solution that violates one 
hard constraint. Now what? We might choose to discard the solution
since it is infeasible, or we might see if we can repair it to
generate a feasible solution that still handles the non-hard
constraints well. Either way, this typically a difficult task. It
would be even better to come up with variation operators that never
corrupt a feasible solution into an infeasible solution while still
searching vigorously over the space of feasible solutions to find
those that best handle the non-hard constraints, or the soft
constraints in particular. 

Overall, as we found out this is one of the most challenging 
real-world constrained problems to handle. We have tackled it through 
a multi-phase heuristic approach. It successfully produced legal
schedules, including those of students, satisfying the hard as well as
the medium and most of the soft constraints.

\subsection{Cost Function}

The {\bf cost function} measures the quality of the current schedule
and generally involves the weighted sum of penalties associated with 
different types of constraint violations. The aim of the optimization
technique is to minimize the cost function. We consider the following
as part of the cost function:

\begin{itemize}
\item {\it Class cost} is the sum of costs incurred from scheduling a 
class in a particular time period, including  having a certain class
and its lab scheduled in the same time period; spreading classes over
the week and within each of the weekdays; and gluing to fill in holes
in the timetable and allow contiguous time periods for a class that
requests them.

\item {\it Professor cost} is the sum of costs associated with each
professor, including teaching two or more classes that overlap in
time; being assigned more classes than the maximum number allowed to
be taught; and not having a long enough time interval between classes
taught by the same professor.

\item {\it Student cost} is the sum of costs associated with each
student, including clashes in class times; not having the classes
evenly spread out over the week; having to schedule a class from the
list of alternates rather than the list of first preferences; or
classes that do not satisfy eligibility criteria.

\item {\it Room cost} is the sum of costs associated with each classroom, 
including the distance cost obtained from the distance constraint;
not being able to schedule a room of the specified type; and the room
size cost obtained from the room constraint.
\end{itemize}

\section{As a Generalized Assignment-Type Problem}

The notion of the assignment-type problem and its generalized version
appear to be powerful modeling tools. In particular, such models are
very appropriate for formulating timetabling and scheduling problems
where time periods have to be determined for activities according to
several specific constraints.

The Assignment-Type Problem (ATP)~\cite{FHL:object, FL:exchange} can
be summarized as follows: 

{\it Given $n$ items and $m$ resources, denote by $c_{ij}$ the cost of 
assigning (scheduling) item $i$ to resource $j$. The problem is to
determine an optimal assignment of items to resources minimizing the
total cost and satisfying $K$ additional side constraints.}

The mathematical model associated with an ATP is formulated as
follows: 

{\bf (ATP)}

\be{gatp-1}
\text{Min}\;F(x)
\ee
{\it subject to}
\be{gatp-2}
G_k(x) \leq 0 \;\;\;\;\;\; 1\leq k\leq K
\ee
{\it and}
\be{gatp-3}
x \in X(1)
\ee

{\it where}

\be{gatp-4}
X(1) = \{ x : \sum_{j \in J_i} x_{ij} = 1, 1 \leq i \leq n; x_{ij} = 0
\;\;\text{or}\;\; 1,\; 1 \leq i \leq b, j\in J_i \}
\ee

and $J_i \subset \{1, 2, \ldots, m\}$ is the set of admissible
resources for item $i$, $1\leq i \leq n$.

The decision variables $x_{ij}$ are such that:

\be{gatp-5}
x_{ij} =
\twoif {1} {\text{if item} i \text{assigned to resource} j}
       {0} {\text{otherwise.}}
\ee

The objective function $F$ and the side constraints $G_k$, $1 \leq k
\leq K$, are only required to be calculable.

A Generalized Assignment-Type Problem (GATP) is an ATP where each
item $i$ has to be assigned to $a_i$ resources, $a_i \geq 1$. The
mathematical model associated with a GATP is: 

{\bf (GATP)}

\be{gatp-6}
\text{Min}\;F(x)
\ee

{\it subject to}
\be{gatp-7}
G_k(x) \leq 0 \;\;\;\;\;1\leq k\leq K
\ee
{\it and}
\be{gatp-8}
x \in X(a)
\ee

{\it where}

\be{gatp-9}
X(a) = \{ x : \sum_{j \in J_i} x_{ij} = a_i, 1 \leq i \leq n; x_{ij} = 0
\;\;\text{or}\;\; 1,\; 1 \leq i \leq n, j\in J_i \}
\ee

{\it and}

\be{gatp-10}
a = {[a_1, a_2, \ldots, a_n]}^T
\ee
and $a_1 \geq 1$ and integer $1 \leq i \leq n$. It is easy to see that
an ATP is a GATP where $a = {[1, 1, \ldots, 1]}^T$.

The constraints $x \in X(a)$ underly several timetabling and
scheduling problems. Furthermore, to take advantage of the simple
structure of the constraints $x \in X(a)$, a {\it penalty approach} is
used to deal with GATP. In this approach, let $V_k(x)$ denote the
violation of constraint $G_k(x) \leq 0$; i.e.

\be{gatp-11}
V_k(x) = \text{Max} \{0, G_k(x) \}.
\ee

Hence, for each $x\in X(a)$, let $V(x)$ denote the 
{\it total weighted violation}:

\be{gatp-12}
V(x) = \sum_{k=1}^K \beta_k V_k(x)
\ee

where $\beta_k \geq 0$ is proportional to the relative importance of
the {\it k}th constraint. Then, instead of solving GATP, the
solution techniques already introduced, are applied to the following
{\it penalized version} of GATP: 

{\bf (PGATP)}

\be{gatp-13}
{Min}_{x \in X(a)} P(x) = \alpha F(x) + V(x)
\ee

where $\alpha \geq 0$. The values of $\alpha$ and $\beta_k$, $1 \leq k
\leq K$, are parameters that can be adjusted according to the specific
application. For instance, larger values for $\beta_k$, $1 \leq k \leq
K$, allow putting more emphasis on feasibility.


\subsection{Representation of Course Scheduling as GATP}

Consider the problem of establishing the schedule of lectures
accounting for individual student registrations, lecturers, and 
classroom availabilities. Note that this formulation allows for
lectures of different length. Hence, to formulate this problem as a
GATP~\cite{AF:large}, the lectures are the items and the starting times allowed are
the resources; then for each lecture $i$, $1 \leq i \leq n$, and
starting time $j \in J_i$ (the set of admissible starting times for
lecture $i$) such that $J_i = \{1,2,\ldots,m\}$:

\be{form-1}
x_{ij} =
\twoif {1} {\text{if lecture} i \text{starts at} j}
       {0} {\text{otherwise.}}
\ee

The objective function accounts for the lecturer preferences:

\be{form-2}
F(x) = \sum_{i=1}^{n} \sum_{j \in J_i} c_{ij} x_{ij}
\ee

where $c_{ij}$ is the cost of starting lecture $i$ at $j$ specified in
terms of lecturer preferences ($c_{ij} = 0$ if $j$ is the most
preferred starting time for lecture $i$).

A first set of side constraints is specified to eliminate the
conflicting situations where students or lecturers are involved in
lectures taking place simultaneously. Define:

$\Gamma_{ij} = \{(k,l)$: lectures $i$ and $k$ have students or
lecturers in common, and they overlap in time if lecture $i$ starts at
$j$ and lecture $k$ at $l$ $\}$.

The conflicting constraints are specified as follows:

\be{form-3}
x_{ij} x_{kl} \leq 0\;\;\;\;\;\;(k,l) \in \Gamma_{ij}\;,\; 1\leq i
\leq n\;,\; j\in J_i\;.
\ee

Other side constraints are introduced to account for classroom
availability. Partition the set of classrooms available into several
subsets including classrooms of the same type. Define:

$B =$ number of classroom types
$U_b =$ number of classrooms of type $b\;$,$\; 1 \leq b \leq B$.

For each lecture, a unique classroom type is specified. Define:

$K_{bt} = \{(i,j)$: lecture $i$ requires a classroom of type $b$ and
it takes place during teaching hour $t$ of the week whenever its
starting time is $j$ $\}$.

The classroom availability constraints are as follow:

\be{form-4}
\sum_{(i,j) \in K_{bt}} x_{ij} - U_b \leq 0 \;\;\;\;\;\; 1\leq
b \leq B\;,\; 1\leq t \leq T
\ee

where $T$ is the total number of teaching hours of the week.

The course timetabling problem can be summarized as follows:

\be{form-5}
Min \sum_{i=1}^n \sum_{j \in J_i} c_{ij} x_{ij}\;.
\ee

Subject to:

\be{form-6}
x_{ij} x_{kl} \leq 0 \;\;\;\;\;\; (k,l) \in \Gamma_{ij},\;\;\; 1\leq i
\leq n\;,\; j \in J_i
\ee

Next, we need to derive the associated penalized version of this
problem (i.e. the penalized GATP), with weights specified to indicate
the relative importance of violating the corresponding
constraints. For the conflicting constraints, the weights account for
the length of the conflict and the number of individuals
involved. Define:

\begin{itemize}
\item $L_{ijkl} =$ length (in number of hours) of the conflict $(k,l)
  \in \Gamma_{ij}\;$ , $1 \leq i \leq n\;$,$\; j \in J_i\;$. 

\item $\delta_{ik} =$ number of students taking both lectures $i$ and
  $k$, $1 \leq i \leq n\;$, $\;1 \leq k \leq n\;$.

\item $\gamma_{ik} = 
      \twoif {M + \delta_{ik}} {\text{if lectures} i \text{and} k
                                \text{have lecturers in common}}
             {\delta_{ik}} {\text{otherwise}}
$

For  $1 \leq i \leq n , 1 \leq k \leq n\;$.
\end{itemize}

where $M$ is a parameter to indicate the relative importance of
conflicts due to lecturers. Let $V_{kl}^{ij}(x)$ denote the violation
of the conflicting constraints:

\be{form-7}
V_{kl}^{ij}(x) = Max\{0, x_{ij} x_{kl}\} = x_{ij} x_{kl}\;\;.
\ee

Let $V_{bt}(x)$ denote the violation of the classroom availability
constraints:

\be{form-8}
V_{bt}(x) = Max\{0, \sum_{(i,j) \in K_{bt}} x_{ij} - U_b \}\;\;.
\ee

Furthermore, let the weight $\beta_{kl}^{ij}$ associated with
$V_{kl}^{ij}(x)$ be specified as follows:

\be{form-9}
\beta_{kl}^{ij} = \gamma_{ik} L_{ijkl}\;\;.
\ee

Also, let the weight $\beta_{bt}$ associated with $V_{bt}(x)$ be equal
to a scalar $\rho$ for all $1 \leq b \leq B\;$, $\; 1 \leq t \leq
T\;$. Then, the penalized GATP for this problem is as
follows:

\be{form-10}
{\displaystyle {Min}_{x \in X(1)} \sum_{i=1}^n \sum_{j \in J_i}
\left[ \alpha c_{ij} x_{ij} + \sum_{(k,l) \in \Gamma_{ij}} \gamma_{ik}
  L_{ijkl} x_{ij} x_{kl} \right] + \rho \sum_{b=1}^B \sum_{t=1}^T
Max\left\{ 0, \sum_{(i,j) \in K_{bt}} x_{ij} - U_b \right\}}\;\;. 
\ee

The weight parameters $\alpha$, $\rho$, and $M$ are selected according
to the specific context. For instance, if the priority is to reduce
the conflicts, then $\alpha$ and $\rho$ take smaller values.


