Open-Shop Scheduling

als Optimierungsproblem:

• Eingabe: Anzahl m $\in$ $\mathbb {N}$ von Prozessoren, Menge J von Jobs, jedes j $\in$ J besteht aus m Operationen o_{i, j}, für jedes o_{i, j} eine Dauer l_{i, j},
• Lösung: ein Open-Shop-Plan für J, d. h. für jeden Prozessor i eine Funktion f_i : J$\to$$\mathbb {N}$, so daß f_i(j) > f_i(j') $\Rightarrow$ f_i(j)$\ge$f_i(j') + l_{i, j'} und für jedes j $\in$ J: die halboffenen Intervalle [f_i(j), f_i(j) + l_{i, j}) sind alle disjunkt.
• Kriterium: möglichst geringe Gesamtlaufzeit $$\max_{{1\le i\le m, j\in J}}^{}$$f_i(j) + l_{i, j}

Als Entscheidungsproblem:

zusätzliche Eingabe: eine Zahl T $\in$ $\mathbb {N}$

Frage: gibt es einen Plan mit Gesamtlaufzeit $\le$T?