%% LATEX TWICE TO GET THE REFERENCES RIGHT
%%
\documentclass[12pt]{article}
\usepackage[dvips]{epsfig}

\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% For 2by2 partitioned matrices; arguments are: two labels of top, side,
%% 4 entries (row by row).  If entries are themselves matrix or pmatrix,
%% better for readability of source to define first: \def\matrix1{...} etc.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bigframebox}[1]{\framebox{\parbox{\smallerwidth}{#1}}}

\newcommand{\rf}[1]{[\ref{#1}]}            %bibliographical references

\newcommand{\text}[1]{\hbox{\rm \ #1\ \/}}
\newcommand{\be}[1]{\begin{equation}\label{#1}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bl}[1]{\begin{lemma}\label{#1}}
\newcommand{\ble}[1]{\begin{lemmaex}\label{#1}}
\newcommand{\br}[1]{\begin{remark}\label{#1}}
\newcommand{\bn}[1]{\begin{note}\label{#1}}
\newcommand{\bo}[1]{\begin{observation}\label{#1}}
\newcommand{\bt}[1]{\begin{theorem}\label{#1}}
\newcommand{\bd}[1]{\begin{definition}\label{#1}}
\newcommand{\bp}[1]{\begin{proposition}\label{#1}}
\newcommand{\bc}[1]{\begin{corollary}\label{#1}}
\newcommand{\bfact}[1]{\begin{fact}\label{#1}}
\newcommand{\ber}[1]{\begin{exercise}\label{#1}}
\newcommand{\bex}[1]{\begin{example}\label{#1}}
\newcommand{\ec}{\mybox\end{corollary}}
\newcommand{\efact}{\mybox\end{fact}}
\newcommand{\eer}{\mybox\end{exercise}}
\newcommand{\eex}{\mybox\end{example}}
\newcommand{\eem}{\mybox\end{example}}
\newcommand{\el}{\mybox\end{lemma}}
\newcommand{\ele}{\mybox\end{lemmaex}}
\newcommand{\er}{\mybox\end{remark}}
\newcommand{\en}{\mybox\end{note}}
\newcommand{\eo}{\mybox\end{observation}}
\newcommand{\et}{\qed\end{theorem}}
\newcommand{\ed}{\mybox\end{definition}}
\newcommand{\ep}{\mybox\end{proposition}}
\newcommand{\epr}{\end{proof}}
\newcommand{\bpr}{\begin{proof}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This are for choices.  They take 4 or 6 args
%% (carriage returns allowed in between}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\twoif}[4]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\end{array}\right.
}
\newcommand{\threeif}[6]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\\#5&#6\end{array}\right.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  These are just for statements, no "qed" box is put in.
%%  (Also for when we have to finish something after a displayed equation
%%        or itemized.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ecs}{\end{corollary}}
\newcommand{\eers}{\end{exercise}}
\newcommand{\eexs}{\end{example}}
\newcommand{\eems}{\end{example}}
\newcommand{\els}{\end{lemma}}
\newcommand{\eles}{\end{lemmaex}}
\newcommand{\ers}{\end{remark}}
\newcommand{\ens}{\end{note}}
\newcommand{\eos}{\end{observation}}
\newcommand{\ets}{\end{theorem}}
\newcommand{\eds}{\end{definition}}
\newcommand{\eps}{\end{proposition}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\begin{document}

\bibliographystyle{alpha}
\begin{center} 

{\LARGE
Course Timetabling as a GATP}

\vspace{0.5cm}

{\normalsize
Saleh Elmohamed\\}
\vspace{.15cm}
{\tt saleh@npac.syr.edu}

\end{center}


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
general assignment-type problem (GATP), 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 lectures 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}
{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.

\end{document}

