Allgemeine Stundenplanung (general course scheduling)
\(\large (\text{CSP})~~\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}=p_j && (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}p_j\,x_{jk}\le R_k && (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 Klasse \(i\) Kurs \(j\) belegt, \(=0\), sonst | |
\(I\) | Menge von Klassen \(i\) | |
\(J\) | Menge der Kurse \(j\) | |
\(K\) | Menge der Lehrpersonen \(k\) | |
\(K_j\) | Menge der Lehrpersonen \(k\), die Kurs \(j\) unterrichten können | |
\(p_j\) | Umfang des Kurses \(j\) in Perioden | |
\(R_k\) | Deputat von Person \(k\) in Perioden | |
\(T\) | Anzahl an Perioden \(t\) | |
\(\ast\) | \(\bar{t}\) | Benötigte Anzahl an Perioden \(t\) |
\(\ast\) | \(x_{jk}\in\{0, 1\}\) | \(=1\), falls Lehrperson \(k\) Kurs \(j\) unterrichtet, \(=0\), sonst |
\(\ast\) | \(y_{jt}\in\{0, 1\}\) | \(=1\), falls Kurs \(j\) in Periode \(t\) stattfindet, \(=0\), sonst |