%% 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
Timetabling as a Generalized 

\vspace{0.25cm}

Assignment-Type Problem}

\vspace{0.75cm}

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

\end{center}


\section{Generalized Assignment-Type Problem}

The Assignment-Type Problem (ATP) can be summarized as follows:

{\it Given $n$ items and $m$ resources, the problem is to determine an
  assignment of each item to a resource in order to optimize an
  objective function and to satisfy $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.

\section{Timetabling}

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, 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.

\end{document}

