Computeralgebra in der Ablaufplanung

Seminar: Industrielle Anwendungen der Computeralgebra

Vortrag 3

Die Lösungsmethode, die die Computeralgebra liefert, behandelt den Fall, dass das Lossplitting zwar erlaubt, und wegen der Kapazitätsbeschränkungen der Maschinen u.U. auch notwendig ist, aber dies zu erhöhten Kosten und Zeitaufwand führt, da zusätzliches Rüsten erforderlich ist. Die Lösungen, die man hier erhält, sollen des weiteren immer ganzzahlig sein. Das Besondere an dieser Methode ist, dass die Nachfrage nach den Produkten durch eine korrelierte Zufallsvariable beschrieben wird. Die gängigen Lösungsmethoden sind in diesem Fall nicht anwendbar.

Die Kanten des oben erwähnten Graphen erhält man nun mit Hilfe der Computeralgebra:

Man definiert eine geeignete Termordnung TO auf einem Polynomring mit k Unbestimmten, die mit der Kostenfunktion kompatibel ist. Die Kanten entsprechen dann der reduzierten TO-Gröbner-Basis eines gewissen binomialen Ideals, wenn man die Binome der Gröbner-Basis mit Vektoren im Z ^k identifiziert. Aufgrund der Kompatibilität der Termordnung mit der Kostenfunktion kann man in dem Graphen an bestimmten Punkten den weiteren Pfad vernachlässigen, da man nur noch teurere Lösungen finden würde.

Implementation mit CoCoA

Claudia Jung