Das Component Commonality Problem

Das Component Commonality Problem ist ein stochastisches Optimierungsproblem aus dem Bereich supply chain optimization, das wie folgt beschrieben werden kann. Es gibt m Produkte, deren zugeordneter Bedarf dem Zufall unterliegt. Jedes dieser Produkte benötigt zur Herstellung einige oder alle der n Komponenten in einer Periode. Die Schwierigkeit liegt darin, daß die Komponenten zu Beginn einer Periode gekauft werden müssen, wenn noch keine Information über den tatsächlichen Bedarf vorhanden ist. Der einzige Hinweis auf den zukünftigen Bedarf ist die Information über die Verteilung des Bedarfs in der Vergangenheit. So könnten zum Beispiel Bedarfsvektoren aus vielen Perioden der Vergangenheit gesammelt worden sein. Das Problem besteht nun darin, die Komponenten so einzukaufen, daß die Kosten minimiert werden, jedoch gleichzeitig die Wahrscheinlichkeit, daß der Bedarf befriedigt wird, nicht unter eine gewisse vorgegebene Grenze sinken darf. Es wurde ein Algorithmus entwickelt, der dieses Problem approximativ löst. Der Algorithmus basiert auf einem geometrischen random walk und stellt den Algorithmus mit der besten zur Zeit bekannten Zeitkomplexität für dieses Problem dar.