als Optimierungsproblem:
- Eingabe:
Anzahl
m
von Prozessoren,
Menge J von Jobs,
jedes j
J besteht aus m Operationen oi, j,
für jedes oi, j eine Dauer li, j,
- Lösung:
ein Open-Shop-Plan für J, d. h. für jeden Prozessor i
eine Funktion
fi : J

,
so daß
fi(j) > fi(j')
fi(j)
fi(j') + li, j'
und für jedes j
J: die halboffenen Intervalle
[fi(j), fi(j) + li, j)
sind alle disjunkt.
- Kriterium:
möglichst geringe Gesamtlaufzeit
fi(j) + li, j
Als Entscheidungsproblem:
zusätzliche Eingabe: eine Zahl
T
Frage: gibt es einen Plan mit Gesamtlaufzeit
T?
Johannes Waldmann
2008-06-18