Dienstplanung (days-off scheduling)

\(\large (\text{DOSP})~~\left\{~~ \begin{align*} & \text{Max.} && \rlap{f(x)=\sum_{k\in K}\sum_{t=1}^T\sum_{s\in S_t}u_{ks}\cdot x_{kts}} \\ & \text{u. d. N.} && \sum_{s\in S_t}x_{kts}=1 && (k\in K;~t=1, \ldots, T)\\ & && x_{kts}+x_{k(t+1)s'}\le 1 && (k\in K;~t=1, \ldots, T-1;~(s, s')\in F) \\ & && \sum_{k\in K_q} x_{kts}\ge r_{tsq} && (t=1, \ldots, T;~s\in S_t\setminus\{s_0\};~q\in Q) \\ & && n^{min}_{ks}\le\sum_{t=1:s\in S_t}^T x_{kts} \le n^{max}_{ks} && (k\in K;~s\in S)\\ & && x_{kts}\in\{0,1\} && (k\in K;~t=1, \ldots, T;~s\in S_t) \end{align*}\right. \)
\(F\)Menge verbotener Schichtmusterpaare \((s, s')\)
\(K\)Menge der Mitarbeiter \(k\)
\(K_q\)Menge der Mitarbeiter \(k\), die Qualifikation \(q\) besitzen
\(n^{max}_{ks}\)Maximale Anzahl an Tagen, an denen Mitarbeiter \(k\) Schichtmuster \(s\) zugewiesen werden darf
\(n^{min}_{ks}\)Minimale Anzahl an Tagen, an denen Mitarbeiter \(k\) Schichtmuster \(s\) zugewiesen werden muss
\(Q\)Menge an Qualifikationen \(q\)
\(r_{tsq}\)Benötigte Anzahl an Mitarbeitern mit Qualifikation \(q\) an Tag \(t\) in Schichtmuster \(s\)
\(S\)Menge der Schichtmuster \(s\)
\(S_t\)Menge der Schichtmuster \(s\) des Tags \(t\) einschließlich Freischicht \(s_0\)
\(T\)Anzahl der Tage \(t\) im Planungszeitraum
\(u_{ks}\)Nutzenbewertung von Schichtmuster \(s\) durch Mitarbeiter \(k\)
\(\ast\)\(x_{kts}\in\{0, 1\}\)\(=1\), falls Mitarbeiter \(k\) an Tag \(t\) dem Schichtmuster \(s\) zugewiesen wird, \(=0\), sonst