Next: Smooth Sets
Up: Randomisierte Algorithmen
Previous: Randomisierte Algorithmen
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.
Webmaster<www@zpr.uni-koeln.de>
1999-07-28