Schulstundenplanung (class scheduling)
Spezialfall der allgemeinen Stundenplanung, bei der jeder Kurs genau einer Klasse zugeordnet ist
| \(\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\) besucht, \(=0\), sonst; es gilt \(\sum_{i\in I}a_{ij}=1\) | |
| \(I\) | Menge von Klassen \(i\) | |
| \(J\) | Menge der Kurse \(j\) | |
| \(K\) | Menge der Lehrer \(k\) | |
| \(K_j\) | Menge der Lehrer \(k\), die Kurs \(j\) unterrichten können | |
| \(p_j\) | Umfang des Kurses \(j\) in Stunden | |
| \(R_k\) | Deputat von Person \(k\) in Stunden | |
| \(T\) | Anzahl an Stunden \(t\) | |
| \(\ast\) | \(\bar{t}\) | Benötigte Anzahl an Stunden \(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 |
Problem \((\text{CSP})\) kann durch Zerlegung in Zuweisung von Lehrern zu Kursen (Teacher Assignment Problem) und Zuweisung von Stunden zu Kursen (Edge Coloring Problem) sequentiell exakt gelöst werden
| \( (\text{TAP})~~\left\{~~ \begin{align*} & \text{Min.} && \bar{t} \\ & \text{u. d. N.} && \sum_{k\in K_j}x_{jk}=1 && (j\in J)\\ & && \sum_{j\in J:k\in K_j}p_j\,x_{jk}\le R_k && (k\in K)\\ & && \bar{t} \ge \sum_{j\in J}a_{ij}\,p_j && (i\in I)\\ & && \bar{t} \ge \sum_{j\in J:k\in K_j}p_j\,x_{jk} && (k\in K)\\ & && x_{jk}\in\{0, 1\} && (j\in J;~k\in K_j) \end{align*}\right. \) |
| \((\text{ECP})~~\left\{~~ \begin{align*} & \rlap{\text{Finde }z_{ikt}} \\ & \text{sodass} && \sum_{t=1}^{\bar{t}} z_{ikt}=\sum_{j\in J:k\in K_j}a_{ij}\,p_j\,x_{jk} && (i\in I;~k\in K)\\ & && \sum_{k\in K}z_{ikt} \le 1 && (i\in I;~t=1, \ldots, \bar{t}) \\ & && \sum_{i\in I}z_{ikt} \le 1 && (k\in K;~t=1, \ldots, \bar{t}) \\ & && z_{ikt}\in\{0, 1\} && (i\in I;~k\in K;~t=1, \ldots, \bar{t}) \end{align*}\right. \) |
| \(z_{ikt}\in\{0, 1\}\) | \(=1\), falls Lehrer \(k\) zur Stunde \(t\) in Klasse \(i\) unterrichtet, \(=0\), sonst |