\chapter{The Course Scheduling Problem}\label{ch:CSP}
\section{Problem Description}

An instance of the {\it Course Scheduling Problem}~\cite{ECF:scheduling}
is as follows. We are given $K$ courses; a list of $N$ student schedules, 
each listing up to $MAX$ courses a student wishes to take; for each course, 
a section bound $B$ which is the maximum number of students that can be 
in a section of the given course (there are enough sections of each course 
for each student to be mapped into some section of the course they want); 
a bound $S$ on the number of time slots available for scheduling 
sections of courses; $R$ set of rooms of various types (e.g. 
classrooms, auditoriums, etc.), capacities, and locations; a set of 
priorities of each building for different departments; and $P$ set 
of professors and teaching assistants.

The problem is to build a timetable (denoted by a set of triples  
$<$course, section, time$>$) that schedules all sections in no more than 
$S$ time slots, and to place students into sections of the courses 
listed in their schedules. In addition, for such a schedule to be legal,
no professor (or a teaching assistant) or student is scheduled to be 
in more than one place (classroom, auditorium, etc.) at a time, and no 
room of any type is expected to accommodate more than one class at a 
time or more students than its capacity.

We decompose the course scheduling problem into three sub-problems,
denoted as a triplet ({\bf t,g,a}) of assignments, where {\bf t} is 
timetabling assignment of sections of courses into $S$ time slots, 
{\bf g} is assignment of students to sections of their chosen courses, 
and {\bf a} is room (classroom, auditorium, etc.) assignment to the 
course sections.  All of these assignments are subject to constraints 
specified later in the chapter. We would like to note that the problem
of finding the best grouping of the students into the course sections is
called the {\it grouping subproblem}.

%% The NP-complete {\it professors and classes} scheduling problem is a
%% constraint satisfaction problem that can be briefly stated as
%% follows~\cite{ECF:scheduling}:
%%
%% 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 {\it 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. 
%%
%% In addition to that, we wish to schedule all available sections in no
%% more than $N_t$ time slots, and to place $N_s$ into sections of the
%% courses listed in their schedules in a way that maximizes the number
%% of non-conflicts in students' schedules.
%%

\section{Previous Work}

Researchers have tried to solve different versions of this problem
using an assortment of methods and techniques, such as Tabu
Search \cite{H:tabu, H:tabu2, Costa:tabu}, integer/linear
programming \cite{Trip:timetable, GT:allocation}, network
flow \cite{OW:timetable}, genetic algorithms \cite{CDM:genetic}, logic 
programming techniques \cite{FD:logic}, and a 
host of other techniques surveyed by Schaerf~\cite{Sc:survey}. Some of 
these approaches are for high school scheduling, others dealt only with
examination scheduling at the college level, and many other approaches
used either randomly generated data or small sets of real data dealing
with only faculty/staff scheduling or course scheduling for a
particular department. In short, most of the previous work related to
the course scheduling problem, with few exceptions, has ignored the 
issue of student satisfaction, concentrating instead on constraints 
imposed by teachers.

In the case of the examination timetabling problem, as mentioned by 
Carter~\cite{MC:survey}, it is difficult to draw a clear distinction
between the course timetabling problem and the examination 
timetabling problem. 

On the abovementioned problem of high school scheduling, there are 
differences between it and the university timetabling problem. 
For universities the problem becomes more difficult since we 
have to take into account additional constraints. For examples, 
the length of courses may not be uniform, professors may not
be available or may prefer to teach at certain times of the week, 
sufficient time should be provided for students to move from one building to
another if necessary. Moreover, some courses may be option courses and
we want to respect the freedom of choice of the students. Furthermore, 
there are pairs of courses which should not be scheduled in the same day,
and there may be compactness (professors may prefer to be involved in
consecutive time periods) and precedence requirements (there are typically
courses which should be followed by recitation periods in the same day).
There are also the scheduling difficulties of courses which involve a large
number of students and thus have to be repeated several times during the 
week.

In the case of using network flow techniques, Ostermann and de Werra
\cite{OW:timetable} reduce the timetabling problem to a sequence of
network flow problems. The general network model can be formulated as
follows:
\be{nf-1}
\text{min} \sum_{j=1}^m c_j x_j\;\;,
\ee
such that
\be{nf-2}
A x = b\;\;, l\le x \le u
\ee
where $A_{nxm}$ is the vertex edge incidence matrix, $b_{nx1}$ is the vector
of supplies, and $u_{1xm}$, $l_{1xm}$ are vectors of capacities and lower bounds.

Ostermann and de Werra create a network for each period so that the flow in the 
network identifies the lectures given in that period. de Werra 
\cite{DeW:introduction} proposes a similar method creating a network for each
class. A brief summary of the latter method is as follows:

For a given class $c_i$ do the following: 1. introduce a vertex for each period
$k$ and each instructor $t_j$; 2. connect $k$ with $t_j$ if instructor $t_j$ is 
available at period $k$ and has not been assigned to another class for period
$k$ in a previous network; 3. introduce a source vertex $s$ with edges ($s, k$)
for all periods $k$ and a sink vertex $t$ with edges ($t_j, t$) for all
teachers $t_j$; 4. set both the capacities $u(t_j, t)$ and the lower bounds
$l(t_j, t)$ to $r_{ij}$; 5. for all other edges $u=1$ and $l=0$.

The solution of the network, which is always integer due to the total
unimodularity property (\cite{PS:combopt}, pp. 316-318), gives a schedule for
all the lectures for the given class. The construction of the network is
repeated for all classes and eventually, if a solution is found for all networks,
leads to a complete timetable. The problem with this is that, since there is
no backtracking on the classes already scheduled, we have no guarantee whatsoever
that the solution is found whenever it actually exists.

In the case of using the method of Tabu Search, Hertz~\cite{H:tabu, H:tabu2}
considered both students and teachers in constructing a timetable. While his
main result is to build a timetable for instructor-oriented constraints with
variable length courses and groups of students all taking the same courses,
he points out that this solution can easily be extended to students 
with individual schedules without increasing the size of the problem.
Still more constraints can be added to the problem to take into account
the problem of dividing students into sections. Each change would require
a further modification of the objective function, which has several 
components already in the initial conception of the problem. This would
make the objective function un-necessarily quite complicated. Our work 
has the advantage of maintaining simple objective functions regarding
minimizing conflicts. We also concentrate on hybrid heuristics built
around annealing, as the core process, keeping in mind
our aim to study the ability of annealing-based methods to solve real
applications, such as the large scale real-world scheduling 
application we have dealt with.

Tripathy~\cite{Trip:timetable} considered both teachers and students, 
including section assignments. He studies a specific application and breaks 
the solution into three steps: generation of a conflict matrix describing 
the courses that should not be concurrently scheduled; sectioning students; 
and the generation of a class schedule.
No specific algorithm is given for assigning students to sections; this stage
of the overall scheduling process is apparently repeated several times
until it is clear that the assignment allows a feasible timetable to
b constructed or the algorithm gives up. There is a difficulty with this
step and that is it is NP-hard (see Chapter~\ref{ch:complex}) 
to assign students to sections in a way that minimizes the density graph 
(represented in \cite{Trip:timetable} by the conflict matrix).

Vitanyi~\cite{Vit:coloring} considered the problem of constructing a 
$T$-coloring of a graph with the goal of minimizing edge conflicts. This
corresponds to building a timetable with $T$ time slots. He gives a $(1-1/T)$
approximation algorithm for the problem (i.e. no more than $1/T$ of the
edges will conflict. Karger et al.~\cite{KMS:approximate} improved
this result using semi-definite programming.

%% None of these approaches have dealt with
%% student scheduling according to student preferences and majors.

\section{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{Constraints of Course Scheduling}

University course scheduling, like almost all practical problems, poses
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 will have a smaller search space to worry about
and therefore fewer possibilities to consider. 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 `operators' that will act on 
feasible solutions and 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 offers (e.g. white
boards, video projectors, lab equipment, 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}
%
Other examples are space or room constraints:
\begin{itemize}
\item {\bf Room Type}\footnote{Perhaps, this can be relaxed a little
and considered as a 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.

%% This note needs to go into a section on how the actual scheduling
%% of courses is handled at universities and colleges across the US:
%% The problem components are the same but the way the problem is 
%% constructed can differ from one institution to another. Of course, these
%% differences are mainly in preferences and constraints of the problem. 
%% For example, on the constraint of room size, at Syracuse University  there
%% a requirement stating that the room size to be twice as big as the actual
%% class enrollment for the sole reason that examinations of the class can also
%% be scheduled in that room. 
%%

\end{itemize}

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

 For the {\bf Room Size} 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 the {\it $\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 is derived for classes $c_i$ and $c_j$ as follows:

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

where $s(c_i)$ and $s(c_j)$ are functions denoting the start time of 
class $c_i$ and $c_j$, respectively, and $e(c_i)$ and $e(c_j)$ 
denote the end times. The relation between the two class durations is 
defined as follows:

\be{relative-length}
R_{len}(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

where the functions $len(c_i) = e(c_i) - s(c_i)$ and 
$len(c_j) = e(c_j) - s(c_j)$ denote the length or
duration of classes $c_i$ and $c_j$, respectively. 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 handle any
complete overlaps between the two classes.  

\section{Strategy for Problem Solving}

As mentioned above, hard constraints must be 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, Papa:complexity}: 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 satisfies the available
constraints. But then we have other types of constraints to worry
about, and those are {\it medium} and {\it soft}.

\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{In some cases, this must be met and therefore
considered as medium or hard constraint.}
\item Professors may have preferences for specific rooms or types of
  rooms.
\item Number of lecturers assigned to a course in each semester should
be bounded between a lower and an upper bound on the number of
sections of that course.
\item Only professors (as opposed to teaching assistants) 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 by assigning it a higher cost.}
%% \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 buildings $J$ involved in scheduling. 
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$ classes would
be scheduled into buildings $B^{'}$ where $|B^{'}| \leq |B|$ (number
of $d_i$'s buildings of preference is usually less than the overall
available number of buildings), 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^{'}\;,\;\;\; 1\leq i \leq n
\ee

The cost function is the {\it distance ratio} of department $d_i$
buildings of preference to all available buildings multiplied by the
number of  $d_i$ preferred buildings. Notice that for a
particular department the denominator of equation \ref{dist-cost}
stays fixed throughout 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}

\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{Alternatively, 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, students should complete prerequisite courses
before they begin the later courses (this facilitate
learning foundational material prior to advanced material, as is usually
required in the curriculum).
\item Two courses of a same topic are scheduled in two different working
days.\footnote{This can be further relaxed and considered to be soft constraint.}
\end{itemize}

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

Certainly there are many more 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. At this point 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 is 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 discovered, 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 the schedules of students, not just professors 
and classes, satisfying the hard as well as the medium and most of the 
soft constraints.

\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}
\text{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 (or
professors), and classroom availabilities. Note that this formulation
allows for classes (lectures) of different length. Hence, to formulate this
problem as a GATP~\cite{AF:large}, the classes are the items and the
starting times allowed are the resources; then for each class $i$,
$1 \leq i \leq n$, and starting time $j \in J_i$ (the set of
admissible starting times for class $i$) such that $J_i =
\{1,2,\ldots,m\}$: 

\be{form-1}
x_{ij} =
\twoif {1} {\text{if class} i \text{starts at} time 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 class $i$ at time $j$ specified in
terms of lecturer preferences ($c_{ij} = 0$ if $j$ is the most
preferred starting time for class $i$).

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

Define:
$\Gamma_{ij} = \{(k,l)$: lectures $i$ and $k$ have $N$ students or
lecturers in common, and they overlap in time if lecture $i$ starts at
time $j$ and lecture $k$ at time $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:
Let $B =$ number of classroom types, and $U_b =$ number of classrooms of type
$b$ , $1 \leq b \leq B$. This can be somewhat restrictive but if possible
for each class, a unique classroom type is specified. 

Define:
$K_{bt} = \{(i,j)$: class $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}
\text{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 classes $i$ and
  $k$, $1 \leq i \leq n\;$, $\;1 \leq k \leq n\;$.

\item $\gamma_{ik} = 
      \twoif {M + \delta_{ik}} {\text{if classes} 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) = \text{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) = \text{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 \text{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
\text{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.

%%%%% add to this one ....
%%%%%
\section{General Notes on the Problem of Course Scheduling}

Some of the abovementioned proposals and constraints may not necessarily
be applicable in general to different types of institutions.
Furthermore, it is quite possible that within the same institution some of 
these constraints would not be considered desirable by certain students, 
professors, and academic departments.

It is usually that the problem components are the same but the way the 
problem is constructed can differ from one institution to another. 
Of course, these differences are mainly in preferences and constraints 
of the problem. For example, at Syracuse University, on the issue of 
size of the chosen rooms\footnote{Without loss of generality, this 
reference includes classrooms, auditoriums, seminar rooms, and all other 
types of available ``rooms''.}, there is a stated requirement that the room 
size to be twice as big as the actual enrollment of the class assigned 
to it. This is for the sole reason that examinations of the class can 
also be scheduled in the same room. Of course, other universities may have
different requirements when it comes to the size of the chosen rooms.


