Klausurplanung (examination timetabling)

Spezialfall der allgemeinen Stundenplanung mit Kursen einheitlicher Dauer und unbegrenzten Deputaten
\(\large (\text{ETP})~~\left\{~~ \begin{align*} & \text{Min.} && \bar{t} \\ & \text{u. d. N.} && \sum_{k\in K_j}x_{jk}=1 && (j\in J)\\ & && \sum_{t=1}^T y_{jt}=1 && (j\in J)\\ & && \sum_{j\in J}a_{ij}\,y_{jt} \le 1 && (i\in I;~t=1, \ldots, T) \\ & && \sum_{j\in J:k\in K_j}x_{jk}\le \bar{t} && (k\in K)\\ & && x_{jk}+x_{j'k}+y_{jt}+y_{j't} \le 3 && (j, j'\in J:j\neq j';~k\in K_j\cap K_{j'};~t=1, \ldots, T)\\ & && \bar{t} \ge t\,y_{jt} && (j\in J;~t=1, \ldots, T)\\ & && x_{jk}, y_{jt}\in\{0, 1\} && (j\in J;~k\in K_j;~t=1, \ldots, T) \end{align*}\right. \)
\(a_{ij}\)\(=1\), falls Studiengangsemester \(i\) Klausur \(j\) ablegt, \(=0\), sonst
\(I\)Menge von Studiengangsemestern \(i\)
\(J\)Menge der Klausuren \(j\)
\(K\)Menge der Prüfungsräume \(k\)
\(K_j\)Menge der Prüfungsräume \(k\), in denen Klausur \(j\) stattfinden kann
\(T\)Anzahl an Zeitfenstern \(t\)
\(\ast\)\(\bar{t}\)Benötigte Anzahl an Zeitfenstern \(t\)
\(\ast\)\(x_{jk}\in\{0, 1\}\)\(=1\), falls Klausur \(j\) in Prüfungsraum \(k\) stattfindet, \(=0\), sonst
\(\ast\)\(y_{jt}\in\{0, 1\}\)\(=1\), falls Klausur \(j\) in Zeitfenster \(j\) stattfindet, \(=0\), sonst

Problem \((\text{ETP})\) kann durch Zerlegung in Zuweisung von Prüfungsräumen zu Klausuren (Room Assignment Problem) und Zuweisung von Zeitfenstern zu Klausuren (Vertex Coloring Problem) sequentiell heuristisch gelöst werden

  1. Room Assignment Problem

    \( (\text{RAP})~~\left\{~~ \begin{align*} & \text{Min.} && \bar{t} \\ & \text{u. d. N.} && \sum_{k\in K_j}x_{jk}=1 && (j\in J)\\ & && \bar{t} \ge \sum_{j\in J}a_{ij} && (i\in I)\\ & && \bar{t} \ge \sum_{j\in J:k\in K_j}x_{jk} && (k\in K)\\ & && x_{jk}\in\{0, 1\} && (j\in J;~k\in K_j) \end{align*}\right. \)

  2. Vertex Coloring Problem

    \((\text{VCP})~~\left\{~~ \begin{align*} & \text{Min.} && \bar{t} \\ & \text{u. d. N.} && \sum_{t=1}^T y_{jt}=1 && (j\in J)\\ & && \sum_{j\in J}x_{jk}\,y_{jt} \le 1 && (k\in K;~t=1, \ldots, T)\\ & && \sum_{j\in J}a_{ij}\,y_{jt} \le 1 && (i\in I;~t=1, \ldots, T) \\ & && \bar{t} \ge t\,y_{jt} && (j\in J;~t=1, \ldots, T) \\ & && y_{jt}\in\{0, 1\} && (j\in J;~t=1, \ldots, T) \end{align*}\right. \)