Matching Heuristiken

Diese Heuristiken erzeugen einen Plan für Open Shop Probleme. Dabei wird versucht Operationen so anzuordnen, das solche mit ähnlichen Bearbeitungszeiten parallel laufen. Die Fortschrittsanzeige gibt die aktuelle Gesamtbearbeitungszeit nach jedem Einfügen an.

So werden Matching Heuristiken gestartet:

Stellen sie sicher, das der Problemtyp und alle Problemparameter definiert sind. Wählen sie Heuristische Verfahren|Matching Heuristiken aus dem Menu Algorithmen , editieren sie die Optionen und  drücken sie OK.

Optionen:

Art des Algorithmus:
BOTTLENECK
Die Wichtungen werden sortiert, anschliessend wird die grösste Wichtung p bestimmt, so das M = {p(i,j) | p(i,j) >= p} ein perfektes Matching enthält. Die entsprechenden Operationen aus diesem Matching werden in den Plan eingefügt und die Wichtungen gelöscht. Der Vorgang wir solange wiederholt, bis alle Operationen in den Plan eingefügt sind.
WEIGHTED
Ein maximal gewichtetes Matching wird berechnet. Die entsprechenden Operationen werden in den Plan eingefügt und die Wichtungen gelöscht (d.h. auf den kleinsten zulässigen Wert gesetzt). Der Vorgang wir solange wiederholt, bis alle Operationen in den Plan eingefügt sind.
Art des Matchings:
 Mit dieser Option legt man fest wie die Wichtungen berechnet werden.
MIN
Die Bearbeitungszeiten werden vom grössten zulässigen Wert abgezogen, das Ergebnis ergibt die Wichtung. Auf diese Weise wird die durchschnittliche Bearbeitungszeit aller Operationen in einem Einfügeschritt minimiert.
MAX
Die Bearbeitungszeiten werden direkt als Wichtung benutzt. Auf diese Weise wird die durchschnittliche Bearbeitungszeit aller Operationen in einem Einfügeschritt maximiert.
HEADS
Die erste einzufügende Menge wird wie mit dem MIN Parameter berechnet. Nachdem eine Menge von Operationen eingefügt wurde werden für alle noch nicht eingefügten Operationen die Heads bestimmt. Diese werden zur Bearbeitungszeit addiert und das Ergebnis wird vom grössten möglichen Wert abgezogen. Dies ergibt die Wichtungen für das nächste Matching. Auf diese Weise minimiert der Algorithmus in jedem Schritt die aktuelle Gesamtbearbeitungszeit.
Inhaltsverzeichnis
29.10.00