Forschungsprojekt mit EU-Förderung

Hintergrund

Der Großteil der Produkte muss konfiguriert werden und wird als Einzelmontage für einen spezifischen Kundenauftrag gefertigt. Somit spielen Systeme für die Produktkonfiguration bei KSB eine große Rolle.

KSB betreibt ein Forschungsprojekt zur Entwicklung neuer Methoden, Algorithmen und Software-Programme zur Ermöglichung der zielgerichteten, eindeutigen und effizienten Konfiguration und Auswahl hoch komplexer Produktsysteme (hydraulische Pumpen- und Armaturen-Systeme). Eine Förderung der Europäische Union unter dem IWB-EFRE-Programm Rheinland-Pfalz wurde beantragt.

Empfehlungswissen

Ein konfiguriertes Produkt wird mit technischen und kaufmännischen Merkmalen beschrieben, die jeweils eine (endliche) Anzahl von Werten in ihrer Domäne haben, welche sie annehmen dürfen. Als einige von vielen Beispielen seien genannt Pumpenbaugröße, Werkstoff des Pumpengehäuses und des Laufrades bis hin zu Sprache der beigestellten Betriebsanleitung und der Datenblätter.

Nicht jede beliebige Merkmalsbewertung ist erlaubt. Beispielsweise sollen Pumpengehäuse und Druckdeckel aus dem gleichen Werkstoff sein, und die Gleitringdichtung muss zum Bauform des gewählten Deckels passen. Diese Regeln können technischer Art sein (würde anders gar nicht funktionieren oder könnte sonst nicht gebaut werden), durch Normen und Gesetze bedingt sein (z.B. Druckgrenzen nach Flanschnorm oder Betriebsanleitung in Landessprache), durch Entscheidungen zur Logistik oder Rationalisierung (Auswahl aus einer Reihe vormontierter lagerhaltiger Baugruppen) oder kaufmännisch bedingt sein (nur bestimmte Varianten sollen verkauft werden).

Eine einfache Methode der Produktmodellierung ist die Verwendung so genannter Restriktionstabellen. Eine solche Tabelle beinhaltet alle zulässige Kombinationen für eine Auswahl der Merkmale, typischerweise 3 bis 5 Spalten. Die Merkmale stellen die Spalten in der Tabelle dar, die zulässigen Kombinationen die Zeilen. Eine Erweiterung ist die "bedingte Restriktionstabelle", welche nur dann Merkmalswerte einschränkt, wenn bestimmte Bedingungen wahr sind, z.B. der Werkstoff von Stopfbuchs-Packung und -Ringen soll nur dann Werte aus der Tabelle annehmen, wenn die Wellendichtung als Stopfbuchspackung und nicht als Gleitringdichtung gewählt wurde.

Bei der Abwicklungsart "Einzelmontage" wird für jede Kundenanfrage durch den Verkauf ein Produkt einzeln konfiguriert und angeboten. Eine schnelle Konfiguration ist deswegen äußerst wichtig, damit der Angebots- und Abwicklungsprozessprozess zeiteffizient und kostengünstig gestaltet werden kann.

Ein KSB-Produkt erfordert typischerweise ca. 500 Merkmale und 600 Restriktionstabellen in der Modellierung. Bei dieser Anzahl ist es kaum möglich, dass ein Anwender die Bewertung vollständig manuell durchführt. Der Versuch führt meist schnell zu Regelverletzungen (z.B. die Regelverletzung: Die Wertekombination kommt in einer aktiven Tabelle nicht vor). Bei den Bemühungen, diese Konflikte zu lösen, entstehen wieder andere, neue Konflikte.

Eine automatisierte Merkmalsbewertung löst dieses Problem und kann auch helfen, bevorzugte Varianten durch Setzen von präferierten Default-Werten zu favorisieren. Jedes Merkmal, das nicht vom Anwender explizit ein Wert zugewiesen wurde, soll bei der automatisierten Merkmalsbewertung einen Wert bekommen, damit alle Regeln eingehalten werden und möglichst viele Merkmale ihren präferierten Default-Wert annehmen.

Die automatisierte konsistente Merkmalsbewertung ist hoch komplex und gehört daher zu den so genannten "NP-Complete" Problemen. Das Forschungsgebiet des "Constraint Programming" beschäftigt sich mit der Lösung dieser Probleme. Es gibt inzwischen eine Reihe von generischen "Lösern (Solvern)", welche mit Standardalgorithmen arbeiten.

Standardsolver arbeiten häufig mit einem Algorithmus, bei dem der "Constraint-Propagation" eine "Entscheidung" folgt, der bei Unlösbarkeit die letzte Entscheidung wieder revidiert ("Backtracking") und der ansonsten weiter mit Propagation und Entscheidungen fortfährt, bis alle Merkmale bewertet sind. Die Constraint-Propagation ermittelt, welche Werte aus den Domänen der “noch nicht entschiedenen Merkmale“ aufgrund der Restriktionstabelle gestrichen werden müssen, weil sie nicht mehr mit den Werten der bereits entschiedenen Merkmale zusammen in einer Tabelle vorkommen. Danach haben bereits viele Merkmale einen eindeutigen, einzig noch erlaubten Wert.

Beim ersten Merkmal, bei dem noch mehrere Werte zur Auswahl stehen, wird eine Entscheidung für einen der Werte getroffen. Danach wird die Phase der Constraint-Propagation wieder eingeleitet. Sollte dabei die Domäne eines Merkmals leer werden, d.h., es gibt keinen gültigen Wert mehr, muss die Entscheidung revidiert werden und ein anderer der möglichen Werte herangezogen werden. Wenn keiner der Werte zu einer Lösung geführt hat, muss die vorherige Entscheidung revidiert werden ("Backtracking") und auf Basis dieser Entscheidung mit einem anderen Wert fortgefahren werden. Zum Schluss wird entweder eine Lösung gefunden oder festgestellt, dass es keine Lösung gibt; in diesem Fall wird von einem Konflikt ("Versagen" oder "Infeasibility") gesprochen.

Folgende Zielsetzungen sollen daher im Projekt adressiert werden:

1. Optimierung der Constraint-Propagation für bedingte Restriktions-Tabellen

Es ist bekannt, dass generische Standardsolver nicht für jedes Problem eine Lösung anbieten, und falls sie eine Lösung anbieten, nicht die schnellstmögliche Lösungslaufzeit bieten. Die Constraint-Propagation spielt eine große Rolle beim Laufzeitverhalten der Lösung und die Reihenfolge der Entscheidungen ist maßgeblich für die Effizienz des der Lösungsprozedur. Eine für bedingte Restriktionstabellen maßgeschneidertes und optimiertes Constraint-Propagation wird höchstwahrscheinlich einen Performance-Gewinn bringen. Denkbar wäre hierfür eine Kriterien-Indizierung und eine Optimierung der Kompilierungszeit – denn Standardlöser bauen das Problem für jede Lösungsanfrage in Prinzip völlig neu auf.

2. Bestimmung der verbleibenden Wertedomäne

Wenn ein Anwender mehrere Merkmale bewertet, schränkt das die Menge der zulässigen Werte für die anderen Merkmale ein. Damit dem Anwender kommuniziert werden kann, welche Werte für die verbleibenden Merkmale noch zu einer gültigen Lösung führen, muss deren Domäne bestimmt werden. Dies ist verwandt mit dem Thema der Constraint-Propagation. Eine ausreichend starke Constraint-Propagation (nach deren Anwendung kein Backtracking für Fehlentscheidungen mehr nötig ist) liefert die korrekten verbleibenden Wertedomänen, welche dann dem Anwender kommuniziert werden können.

3. Erarbeitung von Konfliktlösungen

Hat der Anwender bereits Merkmalsbewertungen getroffen, die eine Lösung unmöglich machen, muss er eine oder mehrere davon rückgängig machen, um zu einer Lösung zu kommen. Um dem Anwender ein Versuch- und Irrtum-Strategie zu ersparen, soll das System mitteilen, welche Bewertungen freigegeben werden können, um zu einer Lösung zu kommen. Junker [2] beschreibt einen Algorithmus, um solche Lösungen zu finden, unter der Annahme, dass die Merkmale priorisiert werden können. Das Verfahren bietet dem Anwender eine (einzige) Lösung, was häufig auf "nehme die letzte Bewertung zurück" hinausläuft - dies ist nicht zufriedenstellend für den Anwender. Bei bestimmten Annahmen zur Modellkonsistenz muss es mehrere Alternativen geben; diese performant zu ermitteln ist Gegenstand dieser Zielsetzung.

4. Erklärung von Konflikten

Wenn die Constraint-Propagation mit einem Versagen endet (ein Merkmal hat keine gültigen Werte mehr), wird das an Hand einer spezifischen Tabelle festgestellt. Zuvor waren aber die Domänen der Merkmale durch die Anwendung anderen Tabellen möglicherweise schon eingeschränkt. Eine Information über die kürzeste Verkettung von Tabellen zur Domänen-Einschränkung ist für den Produktmodellierer, der eine Lösung für die Merkmalsbewertung erwartet, äußerst wichtig. Denn so können Modellierungsfehler und Inkonsistenzen im Modell besser aufgedeckt werden. Standardlöser liefern keine solche Erklärungen. Daher muss eine Methodik entwickelt werden, um diese Informationen zu generieren.

Literatur

[1] Nikolaj van Omme, Laurent Perron, Vincent Furnon, "or-tools User's Manual", Google, 2014 (Originally under http://or-tools.googlecode.com/svn/trunk/documentation/documentation_hub.html but apparently removed; old version available e.g. under https://acrogenesis.com/or-tools/documentation/user_manual/index.html)
[2] Ulrich Junker, " QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems", Constraint Satisfaction & Satisfiability, Proceedings AAAI'04 Proceedings of the 19th national conference on Artifical intelligence, Pages 167-172, San Jose, California — July 25 - 29, 2004, Copyright © 2004, American Association for Artificial Intelligence (www.aaai.org).