DE69131687T2

DE69131687T2 - Verfahren zur Ressourcenverteilung und -planung, und System dafür

Info

Publication number: DE69131687T2
Application number: DE69131687T
Authority: DE
Inventors: Tomoko Matsunaga; Tamotsu Nishiyama
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1991-06-13
Filing date: 1991-12-06
Publication date: 2000-06-08
Anticipated expiration: 2011-12-07
Also published as: JPH04365162A; KR0145287B1; EP0517953A3; US5440675A; KR930001055A; EP0517953B1; EP0517953A2; DE69131687D1

Description

HINTERGRUND DER ERFINDUNG

1. Gebiet der Erfindung

Die vorliegende Erfindung betrifft ein Verfahren zur Ressourcen-Zuordnung/Untersuchung und -Planung und ein System dafür, das zur optimalen Zuordnung von Arbeitern oder Materialien in der Produktinns-Steuerung und Planung des Herstellungsvorganges oder Berechnungsprozeduren oder das Layout von Logikdiagrammen oder Funktionsdiagrammen etc. ausgebildet ist.

2. Beschreibung des Standes der Technik

Um die Zuordnung von Ressourcen zu untersuchen und zu lösen, Planungsprobleme oder den maximalen Durchfluss, welche durch ein Netzwerk darstellbar sind, gab es ein Verfahren unter Verwendung der graphischen Theorie und eines linearen Programmierverfahrens.
Gemäß dem Verfahren bei der Verwendung der graphischen Theorie wird ein Konzept eines Flusses auf ein Netzwerk angewendet, so dass die zuvor erwähnte Art von Problemen als ein Problem des Flusses untersucht wird. Das Problem des Maximalflusses ist eines der Flussprobleme. Das Flussproblem kann z. B. entsprechend einer Prozedur untersucht werden, die von Dinic vorgeschlagen wurde, welche offenbart ist in "Graph Theory with Exercises" von Ing. Dr. Masao Iri et al., veröffentlicht 1983. Entsprechend dem Verfahren nach Dinic wird der Maximalfluss von einem Eingang zu einem Ausgang des Netzwerkes erhalten durch wiederholtes Suchen nach dem kürzesten inkrementierbaren Pfad aus zulässigen Flüssen, die für jede Verzweigung eingestellt werden. Ein Fluss wird, wenn der kürzeste inkrementierbare Pfad nicht auftritt, als der maximale Fluss betrachtet.
Inzwischen wird gemäß dem linearen Programmierungsverfahren die Beziehung zwischen dem Zulauf und dem Ablauf in dem gesamten Netzwerk oder an jedem Knoten und die Beschränkungen der Flussmenge etc. an jeder Verzweigung und eine entsprechende objektive Funktion durch ein Simplex-Verfahren untersucht, dargelegt im "Guide to Linear Programming Method (1980), Karmarkar's Verfahren, gefunden in der JP-A-02-244261, etc. Das Simplex-Verfahren ist das allgemeinste aus den linearen Programmierverfahren, wobei verschiedene Beschränkungen in dem Netzwerk in ein Modell eingebaut sind, so dass eine Lösung, die Zielfunktion zu optimieren, wiederholt ausgewählt wird, um dadurch die optimale Lösung zu erhalten, während eine praktikable Lösung zum Erfüllen der Beschränkungen als ein Anfangswert eingestellt wird. Karmarkar's Verfahren ist vorgesehen zum Beschleunigen des linearen Programmierverfahrens. Da die Wirksamkeit zum Auswählen einer Lösung mehr als durch das Simplex-Verfahren erhöht wird, wird die Anzahl von Wiederholungen, bis der Optimalwert erhalten wird, soweit verringert, dass die Lösung in Echtzeit erhalten wird. Weiterhin kann auch der Fall, in welchem eine Lösung durch ein Simplex-Verfahren nicht erhalten werden kann, nach Karmarkar's Verfahren untersucht werden.
Es ist jedoch ein Nachteil des konventionellen Untersuchungsverfahrens, d. h. des Verfahrens von Dinic, dass, wenn der Umfang des Netzwerkes zunimmt oder infolge der wiederholten Vorgänge zum Suchen des inkrementierbaren Pfades von dem Eingang zu dem Ausgang des Netzwerkes komplizierter wird, mehr Zeit dafür benötigt wird.
Wenn eine Lösung wiederholt gesucht wird oder ein Wert der Aufgabenfunktion berechnet wird, ist es bei dem Simplex-Verfahren erforderlich, Matritzen von Geraden proportional zu der Anzahl der Beschränkungen zu verarbeiten und daher wird die Verarbeitungs- oder Berechnungs-Zeit proportional einem Quadrat der Anzahl der Beschränkungen, ungeachtet des Umfangs des Netzwerkes. In vielen Fällen ist es auch unmöglich, eine Lösung zu erhalten.
Obwohl Karmarkar's Verfahren andererseits eine Hochgeschwindigkeitsverarbeitung fast in Echtzeit verwirklicht, sind Operationen von Matritzen immer noch erforderlich und das Verfahren dafür kann nicht helfen, sondern wird als Folge der Vergrößerung des Umfangs des Netzwerkes verkompliziert.

ZUSAMMENFASSUNG DER ERFINDUNG

Eine Aufgabe der vorliegenden Erfindung ist es daher, ein Verfahren zur Ressourcen-Zuordnung und ein Planungsverfahren und ein System dafür anzugeben, wobei ein zu untersuchendes Objekt durch ein Netzwerk einschließlich einer geschlossenen Schleife, gebildet aus Knoten und Verzweigungen, ausgedrückt wird und die Gewichtung jeder Verzweigung wird bestimmt durch partielle Suche des Netzwer kes ohne Verwendung des Suchverfahrens eines inkrementierbaren Pfades durch Dinic o. ä. oder lineare Programmierverfahren, sondern durch Wiederholen einfacher Abläufe in einer kurzen Zeit.
Um die vorstehende Aufgabe zu verwirklichen, ist erfindungsgemäß ein Ressourcen-Zuordnungs-Untersuchungs- und/oder Planungs-System vorgesehen, mit einer Eingabevorrichtung zum Eingeben verschiedener Information für die Ressourcen- Zuordnung und/oder -Planung und einer Ausgabevorrichtung zum Ausgeben des Ergebnisses, und einem computerisierten Prozessor, wobei der Prozessor ein Modell verarbeitet, welches durch einen Graphen aus Knoten, welche einen Status zur Ressourcen-Zuordnung und/oder Ressourcenplanung darstellen, und Verzweigungen, die jede zwei Enden an einem Knotenpaar aufweisen und einen Statusübergang darstellen, besteht, und beinhaltet wenigstens eine geschlossene Schleife entsprechend einem Fluss von vorab eingestellten Prozeduren, wobei der Fluss von Prozeduren Schritt 1 umfasst zum Auswählen eines Knotens, von welchem der Ablauf der Bestimmung der Gewichtung der Verzweigungen zwischen sämtlichen Knoten beginnt, und Schritt 2 zum Klassifizieren der Knoten abhängig von dem Bestimmungszustand der Gewichtung der Eingangsverzweigungen und der Ausgangsverzweigungen des ausgewählten Knotens, und zum Gewichten sämtlicher Eingangsverzweigungen xji (zu einem Knoten i) und Ausgangverzweigungen xij (von einem Knoten i) jedes klassifizierten Musters von Knoten i, so dass Fxij so klein wie möglich ist unter einer durch die folgende Gleichung (1) dargestellten Beschränkung,
xij ≥ 0 (1)
Schritt 3 zum Bestimmen der Gewichtung sämtlicher Verzweigungen in dem Graphen durch Wiederholen der Schritte 1 und 2, und Schritt 4 zum Erfassen einer Verzweigung mit der maximalen Gewichtung aus sämtlichen Verzweigungen.
Weitere vorteilhafte Ausführungsformen sind durch die Unteransprüche gekennzeichnet.
Da Knoten, die zu verarbeiten sind, um die Gewichtung von Verzweigungen bei der Ressourcen-Zuordnung, Planung oder Untersuchung eines maximalen Flusses zu verarbeiten sind, in Mustern klassifiziert werden, kann die Verarbeitung erfindungsgemäß in der Reihenfolge der Prozeduren proportional zu der Nummer in der Gesamtanzahl von Verzweigungen ausgeführt werden. Dadurch wird die Verarbeitung unter Verwendung eines linearen Programmierverfahrens einfach und zeitsparend.

KURZBESCHREIBUNG DER ZEICHNUNGEN

Diese und andere Aufgaben und Merkmale der vorliegenden Erfindung werden aus der folgenden Beschreibung in Verbindung mit deren bevorzugten Ausführungsformen anhand der beigefügten Zeichnungen klar, in welchen gleiche Teile durch gleiche Bezugszeichen bezeichnet sind. Dabei zeigen:
Fig. 1 ein Flussdiagramm eines Untersuchungsvorganges zur Ressourcen-Zuordnung gemäß Ausführungsform 1 der vorliegenden Erfindung;
Fig. 2 ein Flussdiagramm eines Auswahlvorganges eines Anfangsknotens;
Fig. 3 ein Flussdiagramm eines Auswahlvorganges eines nächsten Knotens;
Fig. 4 eine vereinfachte Darstellung eines Systems, welches den Untersuchungsvorgang zur Ressourcen-Zuordnung gemäß der vorliegenden Erfindung ausführt;
Fig. 5 ein Blockschaltbild eines zu verarbeitenden Objektes;
Fig. 6 eine Darstellung, welche das in Ausführungsform verwendete Verkehrsnetzwerk erläutert;
Fig. 7 eine Darstellung, welche klassifizierte Muster von Knoten abhängig von der Gewichtung von Bögen;
Fig. 8 eine Darstellung eines Knotens mit einer in sich geschlossenen Schleife;
Fig. 9 eine Darstellung, welche den Fluss von Knoten durch gerichtete Bögen zeigt;
Fig. 10 eine Darstellung, welche zeigt, wie die Gewichtung eines Knotens des Musters 5 zu bestimmen ist;
Fig. 11 eine Darstellung, welche zeigt, wie eine vorläufige Entscheidung getroffen wird, wenn 1 als die Gewichtung addiert wird und wie die Gewichtung bestimmt wird;
Fig. 12 ist eine Darstellung eines Beispiels eines fehlerhaften Knotens;
Fig. 13 ist eine Darstellung davon, wie ein nächster Knoten ausgewählt wird, wenn eine Eltern-Kind-Beziehung vorhanden ist;
Fig. 14 ist eine Darstellung, die den Grad der Konzentration (stark zusammenhängende Teile) in einem Wegenetzwerk von Ausführungsform 1 zeigt;
Fig. 15 ist ein Flussdiagramm eines Planungsvorganges gemäß Ausführungsform 2 der vorliegenden Erfindung;
Fig. 16 ist eine Darstellung, welche die Zusammenfüge-Reihenfolge von Komponenten gemäß der Ausführungsform 2 zeigt;
Fig. 17 ist eine Darstellung, welche die Zusammenfüge-Priorität von Komponenten in Ausführungsform 2 zeigt;
Fig. 18 ist ein Flussdiagramm eines Untersuchungsvorganges des Maximalflusses in Ausführungsform 2;
Fig. 19 ist eine Darstellung des gesamten Zusammenfügungsvorgangs von Komponenten in Ausführungsform 2;
Fig. 20 ist ein vereinfachtes Flussdiagramm einer Verarbeitung gemäß Ausführungsform 3 der vorliegenden Erfindung;
Fig. 21 ist eine Darstellung logischer Schaltungen von Ausführungsform 3;
Fig. 22 ist eine Darstellung, welche die Anschluss-Beziehungen logischer Gatter und Signalleitungen in Fig. 21 zeigt;
Fig. 23 ist eine Darstellung stark zusammenhängender Komponenten (a) und (b), die in Fig. 22 enthalten sind;
Fig. 24 ist eine Darstellung einer stark zusammenhängenden Komponente (c);
Fig. 25 ist eine Darstellung des Grades der Duplizierung von Signalleitungen jeder stark zusammenhängenden Komponente; und
Fig. 26 ist eine Darstellung, wenn die Logikgatter von Fig. 21 in einer lateralen Richtung angeordnet sind.

DETAILLIERTE BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORMEN

Vor der Fortsetzung der Beschreibung der vorliegenden Erfindung wird an erster Stelle ein Blockschaltbild (Fig. 5) einschließlich für die Beschreibung der vorliegen den Erfindung verwendeter Schleifen beschrieben. In Fig. 5 bezeichnen die Bezugszeichen 51 und 52 einen Block eines Ereignisses und eine Verbindungslinie zwischen Blöcken 51, welche den Übergang von einem Ereignis zu dem anderen ausdrückt. Daher steht in einem Beispiel eines Schaltbildes der Block 51 für ein Schaltungselement und die Verbindungslinie 52 zeigt den Fluss eines Signals. Die vorliegende Erfindung handhabt im wesentlichen solch ein Objekt oder Ereignis, das durch das vorstehend erwähnte Blockschaltbild darstellbar ist, welches in einen streng zusammenhängenden Graphen konvertierbar ist. Ein allgemeines Blockschaltbild ist jedoch ebenfalls akzeptabel, wenn streng zusammenhängende Komponenten vor der Anwendung der vorliegenden Erfindung extrahiert werden. Der oben erwähnte, streng zusammenhängende Graph ist ein ausgerichteter Graph, der stets einen oder mehr Wege zwischen zwei optionalen Punkten in dem Graphen aufweist. Ein Algorithmus zum Extrahieren der streng zusammenhängenden Komponenten wird zum Beispiel offenbart in "Basic Calculation" (1983), Iwanami Data Engineering 10, Seiten 57-60, o. ä., und auf deren Beschreibung wird hier verzichtet.

[Ausführungsform 1]

In Ausführungsform 1 wird ein solches Wege-Netzwerk, wie in Fig. 6 gezeigt, verwendet. Eine Verbindung 61 und ein Weg 62 in Fig. 6 entsprechen dem Block 51 und der Verbindungslinie 52 in Fig. 5. Ein Fahrzeug fährt auf einem Weg in einer Richtung eines Pfeiles von einer Verbindung 61 zu einer anderen Verbindung 61. Der Grad der Konzentration des Weges 62 wird unter der Annahme erfasst, dass der Zufluss und der Abfluss von Fahrzeugen an jeder Verbindung 61 gleich ist, ohne dass ein Fahrzeug in der Mitte des Weges 62 hinzukommt oder sich entfernt.
Fig. 6 kann als ein streng zusammenhängender Graph 63 betrachtet werden, der aus Knoten (Verbindungen) 61 und Bögen (Wegen) 62 aufgebaut ist. Der Grad der Konzentration des Weges kann ausgedrückt sein als die Gewichtung des Bogens und daher kann sie durch eine Verarbeitung zum Erhalten der Gewichtung des Bogens erhalten werden.
Fig. 4 zeigt vereinfacht den Aufbau einer Vorrichtung zum Ausführen der obigen Verarbeitung, nämlich erhalten des Grades der Konzentration. Eine Netzliste von Verbindungen oder Wegen in dem Wege-Netzwerk wird aus einer Eingabevorrichtung 21 als eine Datei gelesen, durch einen Prozessor 22 für einen Arbeitsplatz kopiert und in einem an den Prozessor 22 angeschlossenen Speicher 23 zusammen mit dem Original gespeichert. Die Netzliste gibt die Verbindungsbeziehung der Knoten und Bögen an. Jeder Knoten hat Informationen der angeschlossenen Bögen an einer Eingangsseite oder an einer Ausgangsseite davon als Daten und jeder Bogen hat eine Information des an einer Quellenseite oder an einer Senke davon angeschlossenen Knotens.
Die folgenden drei Formeln werden als die Bedingung zum Bestimmen der Gewichtung sämtlicher in jeder Schleife eines streng zusammenhängenden Graphen enthaltenen Bögen gesetzt. Das heißt, angenommen, dass ein Satz von Knoten, die in einem streng zusammenhängenden Graphen enthalten sind G = (U,E) U ist, ein Satz von Bögen E ist und ein komplementärer Satz der Bögen /E ist und ein Bogen von einem Knoten (i) zu einem Knoten (j) in einem Knoten i,j (i,j U) ausgedrückt wird durch (i,j) und die Gewichtung des Bogens xij ist,

(Nr. 2)

xij ≥ 1 (i,j) E
xij = 0 (i,j) /E
in dem Knoten i,

(Nr. 3)

Σjxij - Σjxji = 0 (i,j) E, (j,i) E
für eine Zielfunktion (Nr. 4)
(Nr. 2) gibt an, dass die Gewichtung sämtlicher in dem Graphen dargestellter Bögen nicht kleiner als 1 ist und die Gewichtung der Bögen, die in dem Graphen nicht vorhanden sind, zu 0 gemacht wird (Nr. 3) bedeutet, dass der Zufluss gleich dem Abfluss für die Gewichtung der Bögen in jedem Knoten ist, da der Graph ein streng zusammenhängender Graph ist. (Nr. 4) bedeutet, dass die Summe der Gewichtungen sämtlicher Bögen in dem Netzwerk kleinstmöglich sein soll, mit anderen Worten, die Gewichtung soll kleinstmöglich gesetzt werden, um dadurch zu verhindern, dass die Gewichtung einen großen Wert annimmt, um in dem Fall zu dispergieren, in dem der Ziel-Graph eine Schleife beinhaltet.
Das Berechnungsverfahren der Gewichtung sämtlicher eine Schleife bildenden Bögen in dem Graphen unter Verwendung der oben beschriebenen Bedingungen wird unten anhand eines vereinfachten Flussdiagramms in Fig. 1 erläutert.
Zum leichten Verständnis der Beschreibung werden Knoten in mehreren Mustern entsprechend dem Einstellzustand der Gewichtung eines Eingangsbogens in einem Knoten und eines Ausgangsknotens aus einem Knoten klassifiziert. Hier ist anzumerken, dass die Einstell-Gewichtung des Bogens ein virtueller Wert ist. Daher ist es weiterhin wichtig, die Gewichtung positiv ohne eine Annahme zu setzen, oder nächstmöglich zu einem wahren Wert, wenn er auf einer Annahme basiert. Weiterhin ist es ebenfalls essentiell, die Möglichkeit der Bestimmung der Gewichtung der Bögen eines nächsten Knotens durch Erhöhen der Einstellanzahl der Häufigkeiten der Gewichtung der Bögen eines Knotens zu erhöhen, nämlich Einstellen der Anzahl virtueller Werte. Knoten werden in einer folgenden Weise unter Berücksichtigung des obigen Faktes klassifiziert.
Ein Knoten eines Musters 1 ist ein Knoten mit nur einem Bogen, dessen Gewichtung noch nicht aus der Gesamtheit der Bögen (Eingangsbögen + Ausgangsbögen) bestimmt ist. Die Gewichtung des nicht bestimmten Bogens in dem Knoten von Muster 1 wird bestimmt, um die obige (Nr. 3) mit der höchsten Bestimmtheit zu erfüllen. Ein Beispiel des Knotens in Muster 1 ist in Fig. 7(a) dargestellt.
Ein Knoten eines Musters 2 hat einen nicht bestimmten Bogen an einer Seite und zwei oder mehr nicht bestimmte Bögen an der anderen Seite. Weiterhin ist die Gesamtgewichtung der Bögen an einer Eingangsseite, wobei die Gewichtung dieser Bögen bereits bestimmt ist, gleich der Gesamtgewichtung der Bögen an einer Ausgangsseite, deren Gewichtung bereits bestimmt ist. In dem Knoten von Muster 2 ist die angenommene Anzahl der Gewichtungen groß und die Gewichtung des nicht bestimmten Bogens an einer Seite wird als ein großer Wert angenommen. Ein Beispiel dieses Musters des Knotens ist in Fig. 7(b) gezeigt.
Die Anzahl nicht bestimmter Bögen an einer Eingangsseite ist die gleiche wie diejenige an einer Ausgangsseite eines Knotens eines Musters 3. Weiterhin ist die Gesamtgewichtung der bereits bestimmten Bögen an der Eingangsseite gleich der Gesamtgewichtung der bereits bestimmten Bögen an der Ausgangsseite. Die Anzahl der nicht bestimmten Bögen ist jedoch an der Eingangsseite und an der Ausgangsseite nicht kleiner als 2. Der Knoten des Musters 3 hat eine große Anzahl von angenommenen Gewichtungen. Ein Beispiel des Knotens ist in Fig. 7(c) dargestellt.
Ein Knoten eines Musters 4 ist ein Knoten, welcher einen nicht bestimmten Bogen an der Eingangsseite und einen nicht bestimmten Bogen an der Ausgangsseite aufweist. Da die Gewichtung des einen nicht bestimmten Bogens leicht bestimmt wird aus (Nr. 3), wenn die Gewichtung des anderen nicht bestimmten Bogens in dem Knoten des Musters 4 bestimmt wird, hat der Knoten eine höhere Sicherheit als die Knoten der Muster 2, 3. Der Knoten des Musters 4 übt jedoch einen geringen Einfluss auf die anderen Knoten aus. Ein Beispiel ist in Fig. 7(d) gezeigt. Knoten, die nicht zu einem der vorstehenden Muster gehören, sind in einem Muster 5 (Vorgabe) klassifiziert, wie in Fig. 7(e).
Jetzt wird ein Vorgang zum Erfassen eines Bogens mit der maximalen Gewichtung in einem streng zusammenhängenden Teil anhand der obigen Muster von Knoten beschrieben.

[Vorgang 1] Entfernung einer in sich geschlossenen Schleife

In einem Vorgang 1 wird ein Bogen oder werden Bögen erfasst, welche eine in sich geschlossene Schleife bilden, und aus dem Graphen entfernt. Die in sich geschlossene Schleife ist solch eine wie durch Bezugszeichen 81 in Fig. 8 bezeichnet, die einen Bogen aufweist, der aus einem Knoten hervorkommt und zu diesem Knoten zurückkehrt.

[Vorgang 2] Auswahl eines Anfangsknotens

Ein Knoten, von welchem die Untersuchung ausgeht (Anfangsknoten) wird in einem Vorgang 2 ausgewählt. Der Ablauf des Vorgangs 2 ist in Fig. 2 gezeigt. Da es erforderlich ist, einen Anfangswert der virtuellen Gewichtung eines Eingangs/Ausgangs-Bogens eines Knotens zu setzen, um die Gewichtung sämtlicher Bögen in dem Graphen zu bestimmen, wird der Anfangsknoten ausgewählt, um den Anfangswert entsprechend der durch das Muster von Knoten vorläufig bestimmten Priorität zu setzen. Diese Priorität ist sequentiell von den Mustern 2, 3, 4 und 5 höher. Wenn der Anfangsknoten in den Knoten des Musters 2 nicht erfasst wird, wird er in den Knoten von Muster 3 gesucht. Wenn der Anfangsknoten nicht unter den Knoten von Muster 5 gefunden wird, wird der Vorgang zum Bestimmen der Gewichtung beendet, um dadurch den gesamten Vorgang zu beenden. Der Knoten von Muster 1 ist weder vorhanden, wenn der Vorgang 2 zuerst ausgeführt wird, noch wird er als der Anfangsknoten ausgewählt, um die Möglichkeit der Bestimmung der Gewichtung der anderen Knoten zu steigern, wenn der Vorgang 2 das zweitemal und danach ausgeführt wird.
Der Auswahlvorgang des Anfangsknotens in jedem Muster von Knoten wird wie folgt ausgeführt.
In dem Fall, in welchem der Anfangsknoten aus Knoten von Muster 2 ausgewählt wird, wird zuerst ein Knoten mit der größten Differenz in der Anzahl von nicht bestimmten Bögen zwischen der Eingangsseite und der Ausgangsseite erfasst. Danach wird ein Knoten oder werden Knoten stromoberhalb des oben erfassten Knotens aus den benachbarten Knoten erhalten, welche durch Bögen an dem Knoten angeschlossen sind. Der Knoten stromoberhalb ist nicht nur ein Knoten, an welchem der Bogen beginnt, sondern ein Knoten, der zuerst in Betracht gezogen wird, um die obigen (Nr. 3) und (Nr. 4) beim Bestimmen der Gewichtung der Bögen zu erfüllen. In Fig. 9 ist ein Knoten A stromoberhalb von einem Knoten B. Wenn aus den benachbarten Knoten kein Knoten im Strom oberhalb vorhanden ist, d. h., wenn der oberste Knoten gefunden ist, wird der Knoten als Anfangsknoten bestimmt.
Wenn der Anfangsknoten aus dem Knotenmuster 3 ausgewählt wird, wenn die Gesamtgewichtung der bereits bestimmten Bögen an der Eingangsseite und der Ausgangsseite zueinander gleich sind, wird ein Knoten mit der größten Anzahl nicht bestimmter Bögen an der Eingangsseite (oder an der Ausgangsseite) ausgewählt. Wenn die Gewichtung der bereits bestimmten Bögen sämtlich 1 ist, wird ein Knoten mit der größten Gesamtanzahl von Bögen an der Eingangsseite (oder an der Ausgangsseite) als der Anfangsknoten ausgewählt.
Um den Anfangsknoten aus Knoten des Musters 4 auszuwählen, wird ein Knoten mit der größten Differenz der Gesamtgewichtung der bereits bestimmten Bögen zwischen denjenigen an der Eingangsseite und denjenigen an der Ausgangsseite ausgewählt.
Wenn es unmöglich ist, den Anfangsknoten aus einem der Knoten der Muster 2, 3, 4 auszuwählen, wird der Anfangsknoten aus Knoten des Musters 5 ausgewählt. Das Auswahlverfahren ist das gleiche wie im Fall des Musters 4, d. h., ein Knoten mit größter Differenz in der Gesamtgewichtung der bereits bestimmten Bögen zwischen der Eingangsseite und der Ausgangsseite wird ausgewählt.
Als Gegenmaßnahme gegen eine unendliche Schleife, bei welcher die Gewichtung für den ausgewählten Knoten nicht bestimmt werden kann, ist, wenn ein Element in einem Satz von Knoten vorhanden ist, dessen Gewichtung in einem Vorgang 3 nicht bestimmt werden kann, vorgesehen, dass diese Knoten nicht als Anfangsknoten ausgewählt werden.
Ein experimentelles Verfahren oder andere Klassifizierungsverfahren können anstelle des Verfahrens in Fig. 2 verwendet werden, um den Anfangsknoten auszuwählen.

[Vorgang 3] Bestimmen der Gewichtung eines Bogens

Die Gewichtung jedes Bogens des in den Vorgängen 2 und 4 ausgewählten Knotens wird in einem Vorgang 3 bestimmt. Das Verfahren wird abweichend für jedes Muster von Knoten ausgebildet, die Gewichtung des Eingangs/Ausgangs-Bogens wird aber so bestimmt, dass die obigen (Nr. 3) und (Nr. 4) in jedem Fall erfüllt werden. Das Verfahren wird unten für jedes Muster erläutert.
Da in den Knoten von Muster 1 ein Bogen vorhanden ist, dessen Gewichtung nicht bestimmt ist, kann die Gewichtung des Bogens allein aus (Nr. 3) bestimmt werden.
In Knoten von Muster 2 wird 1 zu jedem einer Mehrzahl der nicht bestimmten Bogen an der Eingangsseite oder der Ausgangsseite addiert. Die Gewichtung des nicht bestimmten Bogens an der anderen Seite wird aus (Nr. 3) erhalten.
In Knoten von Muster 3 wird 1 als die Gewichtung für sämtliche nicht bestimmten Bögen gesetzt.
In Knoten von Muster 4 wird die Gewichtung der nicht bestimmten Bögen an der Seite mit der kleineren Gesamtgewichtung der bereits bestimmten Bögen mit 1 bestimmt. Die Gewichtung für die nicht bestimmten Bögen an der anderen Seite wird entsprechend (Nr. 3) gesetzt.
Die Gewichtung jedes der nicht bestimmten Bögen wird so klein wie möglich für die Knoten des Musters 5 gesetzt und erfährt eine größere Bedeutung für (Nr. 4).
Insbesondere wird die Gewichtung der nicht bestimmten Bögen sämtlich als 1 vorgeschlagen und ein Vergleich von (Nr. 5) wird dann zwischen denen an der Eingangsseite und denen an der Ausgangsseite ausgeführt. Es sei vorgegeben, dass die Anzahl der nicht bestimmten Bögen an der Eingangsseite NA ist, die Anzahl der nicht bestimmten Bögen an der Ausgangsseite NB ist, ein Satz der Bögen an der Eingangsseite ist A(A E) und ein Satz von Bögen an der Ausgangsseite ist B(B E), (Nr. 5)
In der vorstehenden Gleichung wird die Gewichtung der nicht bestimmten Bögen eines größeren Wertes sämtlich auf 1 gesetzt.
Dann wird die Gewichtung der nicht bestimmten Bögen eines kleineren Wertes als kleinstmöglich festgelegt, um (Nr. 3) zu erfüllen. Ein Beispiel, wie die Gewichtung der Bögen in dem Knoten von Muster 5 zu bestimmen ist, ist in Fig. 10 gezeigt,
Fig. 10(a) zeigt den Zustand des Knotens, bevor die Gewichtung der Bögen bestimmt ist, während Fig. 10(b) den Zustand des Knotens zeigt, nachdem die Gewichtung bestimmt ist. Bei diesem Verfahren sollte in dem Fall, in welchem die Gewichtung von 1 für die Bögen der Muster 2, 3, 4, 5 gesetzt wird, besondere Aufmerksamkeit gewidmet werden, da es unmöglich ist, 1 zu setzen, wenn die Gewichtung aus dem Signalfluss sicher größer als 1 ist. Daher ist es erforderlich, vorab zu prüfen, ob 1 für die Gewichtung gegen wird. D. h., es sollte geprüft werden, ob der Freiheitsgrad ausreichend bleibt, um (Nr. 3) zu erfüllen, wenn die Gewichtung für den benachbarten Knoten, der durch den in Frage stehenden Bogen verbunden ist, auf 1 gesetzt ist. In diesem Fall, wenn der benachbarte Knoten vom Muster 4 ist, kann das Ergebnis nicht von dem benachbarten Knoten alleine erhalten werden. Daher sollte ein weiterer benachbarter Knoten, der mit dem weiteren nicht bestimmten Bogen verbunden ist, geprüft werden. Gleichzeitig wird, wenn 1 für die Gewichtung unmöglich ist, ein korrekter Wert der Gewichtung erhalten. Das obige Verfahren wird wiederholt zurückgeführt, bis das Ergebnis erhalten wird und 1 wird als die Gewichtung gesetzt, wenn es möglich ist. Wenn es unmöglich ist, wird der resultierende, korrekte Wert als die Gewichtung bestimmt. Die Fig. 11(a) und 11(b) zeigen, wann die Gewichtung als 1 angenommen wird und wann die Gewichtung eingestellt wird.
In dem Fall, in welchem der Knoten zu dem Muster 3 gehört, ist es, auch wenn der korrekte Wert der Gewichtung zurückgegeben wird, unmöglich, die Gewichtung der anderen Bögen aus der Sicht der Verarbeitung zu bestimmen. In solch einem Fall wird, nachdem die korrekte Gewichtung dem nicht bestimmten Bogen zugeordnet ist, die Bestimmung der Gewichtung in dem Knoten beendet.
Weiterhin wird, wenn (Nr. 3) durch den Originalknoten nicht erfüllt wird, wenn der korrekte Wert zurückgegeben wird, die Gewichtung als 1 bestimmt. Dieses Verfahren ergibt jedoch möglicherweise einen Knoten, der nicht (Nr. 3) erfüllt. Solch ein fehlerhafter Knoten wie oben wird gefunden, wenn einer, mehrere und die Gesamtgewichtung der eingegebenen Bögen bei jedem Knoten in dem gesamten Graphen gleich der Gesamtgewichtung der Ausgangsbögen an dem Knoten ist und daher die Erhöhung und Verringerung der Gewichtung für sämtliche fehlerhaften Knoten gemäß (Nr. 3) sich auf 0 summiert. Wenn z. B. die Gesamtgewichtung der Eingangsbögen an einem Knoten um 2 größer ist als die Gesamtgewichtung der Ausgangsbögen, ist die Gesamtgewichtung der Ausgangsbögen an einem anderen Knoten um 2 größer als die Gesamtgewichtung der Eingangsbögen. Daher ist es möglich, den fehlerhaften Knoten durch Extrahieren einer Schleife, welche sämtliche fehlerhafte Knoten durchläuft und Anpassen der Erhöhung und Verringerung der fehlerhaften Knoten für die die Schleife bildenden Bögen (s. Fig. 12) auf einen normalen zurückzuführen.
Wenn die Gewichtung für sämtliche Bögen bestimmt ist, wenn der Knoten nicht (Nr. 3) erfüllt, wird der Knoten als ein Element zu einem Satz von Knoten addiert, deren Gewichtung nicht bestimmbar ist. Wenn im Gegensatz dazu (Nr. 3) erfüllt ist, wird eine Möglichkeit erzeugt, dass eine neue Gewichtung bestimmt wird, auch wenn der obige Satz von Knoten bereits das Element enthält, und daher wird der Satz entfernt.

[Vorgang 4] Bestimmung des nächsten Knotens

In einem Vorgang 4 wird ein Knoten zum Bestimmen der Gewichtung der nächsten Bögen (des nächsten Knotens) ausgewählt. Der Vorgang 4 ist in einem Flussdiagramm in Fig. 3 gezeigt. Der nächste Knoten wird aus den dem Vorgang 3 unterworfenen Knoten benachbarten Knoten ausgewählt. Da mehrere benachbarte Knoten vorhanden sind, wird der nächste Knoten durch das Muster bestimmt. Die Auswahlpriorität ist in der Reihenfolge von den Mustern 1 zu 2 zu 3. Wenn ein Knoten des Musters 1 zwischen den benachbarten Knoten vorhanden ist, wird der Knoten des Musters 1 als nächster Knoten ausgewählt. Ohne einen Knoten des Musters 3 wird der Vorgang 4 beendet.
Obwohl ein Knoten des Musters 2 ausgewählt wird, wenn ein Knoten des Musters 1 nicht vorhanden ist, wenn mehrere Knoten des Musters 2 unter den benachbarten Knoten vorhanden sind und die Knoten des Musters 2 miteinander verbunden sind, wird ein stromaufwärtiger Knoten als ein Eltern-Knoten bezeichnet, wobei ein stromabwärtiger Knoten ein Kind-Knoten ist, um dadurch die Eltern-Kind- Beziehung zu bilden. Wenn Knoten der Eltern-Kind-Beziehung zwischen den benachbarten Knoten vorhanden sind, wird der Eitern-Knoten als der nächste Knoten ausgewählt. Wenn weiterhin ein Knoten stromoberhalb des Eltern-Knotens vorhanden ist, wird der Knoten stromoberhalb als der nächste Knoten vergleichbar mit dem Vorgang 2 ausgewählt, Fig. 13 zeigt ein Beispiel, wenn der nächste Knoten im Fall der Eltern-Kind-Beziehung ausgewählt wird. In dem Beispiel in Fig. 13 wird der nächste Knoten aus den benachbarten Knoten ausgewählt, nachdem die Gewichtung des Knotens A bestimmt ist. Ein Knoten C wird zuerst ausgewählt, da er ein Eltern-Knoten eines Knotens B ist und dann wird ein Knoten D ausgewählt, da er ein Knoten stromoberhalb des Knotens C ist. Dementsprechend wird der Knoten D schließlich als der nächste Knoten ausgewählt.
Wenn kein Knoten des Musters 2 in dem obigen Verfahren vorhanden ist, wird ein Knoten des Musters 3 aus den benachbarten Knoten ausgewählt. In dem Fall, in welchem eine Mehrzahl von Knoten des Musters 3 vorhanden ist, wird ein Knoten mit der größten Anzahl nicht bestimmter Bögen daraus ausgewählt. Wenn auch kein Knoten des Musters 3 vorhanden ist, kann ein nächster Knoten nicht aus den benachbarten Knoten erhalten werden.
Wenn der nächste Knoten zum Bestimmen der Gewichtung aus den benachbarten Knoten ausgewählt wird, wird der Vorgang 3 zurückgegeben, um die Gewichtung zu bestimmen. Anderenfalls folgt ein Vorgang 5.

[Vorgang 5] Entscheidung der Beendigung der Bestimmung der Gewichtung sämtlicher Bögen

Wenn erfasst wird, dass die Gewichtung sämtlicher Bögen in dem Graph bestimmt ist, ist die Verarbeitung beendet. Wenn die Gewichtung noch nicht für sämtliche Bögen bestimmt ist, kehrt der Vorgang 2 zurück, um einen neuen Anfangsknoten aus dem Graphen auszuwählen.
In Fig. 2 werden zu verarbeitende Daten aus einer Netzliste innerhalb des Speichers 23 in den Prozessor 22 ausgelesen, wobei die Vorgänge 1-5 ausgeführt werden. Die Muster der in den Vorgängen erfassten Knoten werden in jedem Knoten als Daten konserviert und die bestimmte Gewichtung jedes Bogens wird in jedem Bogen als Daten konserviert. Weiterhin wird ein Fehlerflag durch den fehlerhaften Knoten als Daten innerhalb des Knotens gesetzt. Wenn die Gewichtung sämtlicher Bögen in der Netzliste in dem Vorgang 5 bestimmt ist, wird die Gewichtung als das Ergebnis der Ressourcenzuordnung von einer Ausgabevorrichtung 24 ausgegeben.
Das Ausgabeergebnis ist in Fig. 14 gezeigt. Die Gewichtung der Bögen stellt den Grad der Häufung in dem Weg 62 dar. Der Weg 62 mit der größeren Gewichtung wird deutlich mehr gehäuft angesehen und Verkehrswege können für diesen Weg 62 vergrößert werden.

(Ausführungsform 2)

Ausführungsform 2 betrifft die Bestimmung der Zusammenfüge-Reihenfolge von Komponenten einer Vorrichtung. Die Vorrichtung wird aus verdrahteten Verbindungen der Komponenten aufgebaut. Die Montage-Reihenfolge 152 einer Komponente 151 ist z. B., wie in Fig. 16 gezeigt. Wenn die Beziehung zwischen den Komponenten Schleifen definiert, wie in Fig. 16 gezeigt, kann die Montagereihenfolge bestimmt werden, wobei die Montageeffizienz berücksichtigt wird, d. h. durch weitestmögliches Verringern der Anzahl der Teile, durch welche die Flüsse in der Schleife zurückgegeben werden. Daher wird ein Teil, in welchem Pfeile 152 die Flüsse oder die Beziehung zwischen Komponenten darstellen, die am meisten zusammenführen, gesucht für und ausgewählt als eine Rückkopplung. Ein Pfeil der Rückkopplung wird erfasst und die die Schleife bildenden Komponenten werden in der Reihenfolge angeordnet.
Gemäß der vorliegenden Ausführungsform entsprechen die Komponente 151 und die Montage-Beziehung 152 in Fig. 16 dem Block 51 und der Verbindungslinie 52 in Fig. 5 und eine Vorrichtung zum Bestimmen der Montage-Reihenfolge sämtlicher Komponenten ist in Fig. 4 dargestellt. Jeder Teil der Vorrichtung in Fig. 4 gemäß der Ausführungsform 2 arbeitet mit der gleichen Funktion wie in Ausführungsform 1.
Ausführungsform 2 wird betrachtet als aus Knoten (Blöcken) und Bögen (Verbindungslinien) in der Form eines Graphen einschließlich streng zusammenhängender Komponenten aufgebaut. Die Gewichtung des Bogens stellt die Priorität der Montage-Reihenfolge dar. Ein Graph nur streng zusammenhängender Komponenten, welcher durch Entfernen nicht streng zusammenhängender Komponenten aus einem streng zusammenhängenden Graphen erhalten wird, wird entsprechend einem Flussdiagramm in Fig. 15 verarbeitet. Da die Vorgänge 1-5 in Fig. 15 äquivalent zu denjenigen in der Ressourcenzuordnung von Ausführungsform 1 sind, werden die Abläufe 1-5 auf die gleiche Weise wie in Ausführungsform 1 behandelt und die folgende Beschreibung ist auf einen Vorgang 6 und danach gerichtet.

[Vorgang 6] Erfassung des Bogens mit der maximalen Gewichtung

Wenn die Gewichtung sämtlicher Bögen bestimmt ist, wird die entsprechende Gewichtung an jedem Bogen als Daten konserviert. Die Werte der Gewichtung werden in einem Vorgang 6 verglichen, um die maximale Gewichtung und einen Bogen mit der maximalen Gewichtung zu erfassen. Der Bogen mit der maximalen Gewichtung wird ein Rückkopplungs-Bogen einer Schleife einschließlich der Bögen. Fig. 17 zeigt den Zustand, bei welchem die Gewichtung für jeden Bogen in Fig. 16 bestimmt ist. In Fig. 17 wird der Bogen mit der maximalen Gewichtung von einer Komponente 2 zu einer Komponente 1 zu einem Rückkopplungsbogen 171 gemacht.
Wie in einem Flussdiagramm in Fig. 18 gezeigt, wird, wenn die maximale Gewichtung und der Bogen mit der maximalen Gewichtung nach Beendigung des gesamten Vorgangs in dem Vorgang 6 ausgegeben werden, der maximale Fluss in dem Netzwerk untersucht.

[Vorgang 7] Sortieren von Knoten in einer Schleife

Als Ergebnis des Vorganges 6 wird jeder die Schleife bildende Knoten einschließlich des Rückkopplungsbogens einer gewöhnlichen Zahl zugeordnet. Die gewöhnliche Zahl wird sequentiell von einem Knoten an der Senken-Seite des Rückkopplungsbogens in einer Pfeilrichtung der Bögen zugeordnet. Da die Verdrahtung von der Komponente 2 zu der Komponente 1 als Rückkopplungsbogen 171 ausgewählt ist, wird in Fig. 17 die Montage-Reihenfolge der Komponenten in einer Richtung der Verdrahtung von der Komponente 1 bestimmt.
Der obige Vorgang wird anhand von Fig. 4 erläutert. Die zu verarbeitenden Daten werden aus einer Netzäste innerhalb des Speichers 23 in den Prozessor 22 entnommen, wo die Vorgänge 1-6 ausgeführt werden. Ein Zuordnen der gewöhnlichen Zahlen in dem Vorgang 7 wird für die von der Eingabevorrichtung 21 eingegebene, ursprüngliche Netzliste ausgeführt. Dementsprechend wird die Reihenfolge des Rückkopplungsbogens und der Knoten von der Ausgabevorrichtung 24 ausgegeben.
Wenn jede Komponente entsprechend dem Ergebnis des vorstehenden Vorganges 7 neu angeordnet ist, geht Fig. 17 über zu Fig. 19. Somit ist die Vorrichtung mit der höchsten Effizienz zusammengefügt.

(Ausführungsform 3)

Ausführungsform 3 handhabt die Auswahl einer Rückkopplungs-Signalleitung zum Anordnen von logischen Gattern in einer lateralen Richtung einer logischen Darstellung. Daten der logischen Darstellung werden als Netzliste betrachtet, welche die Verbindungs-Beziehung der logischen Gatter mit Signalleitungen zwischen den logischen Gattern darstellt. Wenn die Signalleitungen eine Schleife bilden, sollte die Anzahl von Kopplungsleitungen zum einfachen Verstehen der logischen Darstellung kleinstmöglich ausgeführt werden. Daher wird eine Signalleitung mit dem höchsten Grad der Verdoppelung von Signalleitungen als Rückkopplungsleitung ausgewählt. Weiterhin ermöglicht ein Auswählen der Rückkopplungsleitung, die Anordnungsreihenfolge logischer Gatter der Schleife zu bestimmen.
Eine in der vorliegenden Ausführungsform 3 verwendete Logikschaltung ist in Fig. 21 gezeigt. Die Anschlussbeziehung zwischen den logischen Gattern und den Signalleitungen in Fig. 21 ist in Fig. 22 dargestellt. In diesem Fall kann die Logikschaltung ebenfalls als ein Blockdiagramm ausgedrückt werden. Ein logisches Gatter 181 und eine Signalleitung 182 in den Fig. 21 und 22 sind äquivalent zu dem Block 51 und zur Verbindungsleitung 52 in Fig. 5. Wenn die logischen Gatter und Signalleitungen in Fig. 22 entsprechend durch Knoten und Bögen ersetzt werden, wird der erhaltene Graph vereinfacht entsprechend einem Flussdiagramm in Fig. 20 verarbeitet. Die Gewichtung des Bogens zeigt den Grad der Verdoppelung der Signalleitung. Eine Verarbeitungsvorrichtung für Ausführungsform 3 ist in Fig. 2 gezeigt. Jedes Teil in Fig. 2 wirkt in der gleichen Weise wie in den Aus führungsformen 1 und 2.
Der Verarbeitungsablauf wird anhand von Fig. 20 beschrieben.
In einem Vorgang 1 in Fig. 20 wird eine in sich geschlossene Schleife gesucht und entfernt. Wenn die Signalleitungen eine Schleife in der logischen Schaltung bilden, werden nur die Schleifen, in welchen die logischen Gatter schwer anzuordnen sind, aus dem Graphen herausgenommen, so dass die die Schleife bildenden logischen Gatter neu angeordnet werden. Dies ist ein Vorgang 201 zum Extrahieren streng zusammenhängender Komponenten. Da die Schleife verkompliziert wird, ist es schwer, die Gewichtung sämtlicher Signalleitungen in einem Vorgang zu erhalten. Daher wird eine Signalleitung mit der maximalen Gewichtung erfasst und herausgeschnitten und dann wird der Extraktionsvorgang erneut ausgeführt. Auch wenn eine einzelne, streng zusammenhängende Komponente in dem Extraktionsvorgang nicht erfasst wird, wird angenommen, dass der Graph nicht eine Schleife enthält und der obige Vorgang wird wiederholt, bis es unmöglich wird, die streng zusammenhängende Komponente zu extrahieren. Die aus Fig. 22 resultierenden, streng zusammenhängenden Komponenten (a), (b) werden nach dem Extraktionsvorgang in den Fig. 23(a) und 23(b) gezeigt. Die Signalleitungen zwischen verschiedenen, streng zusammenhängenden Komponenten werden getrennt.
Eine Signalleitung mit der maximalen Gewichtung wird für eine streng zusammenhängende Komponente erfasst. Der Ablauf von der Auswahl eines Anfangsknotens zu der Auswahl eines Bogens mit der maximalen Gewichtung wird in der gleichen Weise ausgeführt wie in den Vorgängen 2, 3, 4, 5, 6 der Ausführungsformen 1 und 2.
Die Signalleitung mit der maximalen Gewichtung, welche in dem Vorgang 6 erfasst wird, wird in einem Vorgang 202 abgetrennt und als Daten gespeichert. Die Schleife einschließlich der Signalleitung wird durch Trennen der Signalleitung abgetrennt, so dass die objektiv streng zusammenhängende Komponente herausgelöst wird.
Nach dem Vorgang 202 wird in einem Vorgang 203 geprüft, ob eine streng zusammenhängende Komponente, für welche der Ablauf zum Suchen der Signalleitung mit der maximalen Gewichtung noch nicht beendet ist, vorhanden ist oder nicht. Wenn eine unverarbeitete, streng zusammenhängende Komponente zurückbleibt, werden die Vorgänge von 2 bis 203 wiederholt. Wenn keine unverarbeitete, streng zusammenhängende Komponente vorhanden ist, wird der Extraktionsvorgang 201 erneut ausgeführt. Zu diesem Zeitpunkt wird, da es nach dem Auftrennen der Signalleitung mit der maximalen Gewichtung ist, eine streng zusammenhängende Komponente mit einer größeren Anzahl von Knoten (logischen Gattern) als die früher erhaltene, streng zusammenhängende Komponente niemals erhalten. Eine Signalleitung mit der maximalen Gewichtung von einem logischen Gatter E zu einem logischen Gatter G in der streng zusammenhängenden Komponente (b) in Fig. 23 wird abgetrennt und der Extraktionsvorgang wird erneut ausgeführt. Als Ergebnis wird eine streng zusammenhängende Komponente (c), wie in Fig. 24, erhalten. Wenn die streng zusammenhängende Komponente erfasst ist, wird die oben beschriebene Folge von Verarbeitungen für die erfasste, streng zusammenhängende Komponente wiederholt.
Wenn eine streng zusammenhängende Komponente in dem Vorgang 201 nicht erfasst wird, wird beurteilt, dass keine Schleife innerhalb des Graphen vorhanden ist, wodurch die Verarbeitung beendet wird. Die Gewichtung von streng zusammenhängenden Komponenten (a), (b), (c) der Fig. 23 und 24 wird in den Fig. 25(a), 25(b), 25(c) gezeigt. Aus Fig. 25 werden eine Signalleitung von einem logischen Gatter B zu einem logischen Gatter A, eine Signalleitung von logischen Gattern E bis 6 und eine Signalleitung von logischen Gattern I bis H als Rückkopplungs- Signalleitungen der streng zusammenhängenden Komponenten (a), (b), (c) ausgewählt. Wenn jedoch die Gewichtung der Signalleitungen sämtlich 1 ist, wie bei den streng zusammenhängenden Komponenten (a) oder (b), kann jede Signalleitung als die Rückkopplungssignalleitung ausgewählt werden. Das Anordnungsergebnis der logischen Gatter der logischen Schaltung in Fig. 21 in der lateralen Richtung ist in Fig. 26 gezeigt.
Obwohl die logische Schaltung ein in Ausführungsform 3 zu verarbeitendes Objekt ist, wenn das Objekt eine Schaltung der funktionalen Ebene ist, kann die Schaltung vergleichbar einem funktionalen Diagramm verarbeitet werden.
Wie oben vollständig beschrieben, können erfindungsgemäß Probleme in einer einfachen Weise in einer kurzen Zeit durch Erfassung der Gewichtung jeder Verzweigung eines Netzwerkes ohne Verwendung eines linearen Programmierverfahrens verarbeitet und untersucht werden.
Ein streng zusammenhängender Graph wird für ein Modell des Netzwerkes verwendet und der Status zur Ressourcenzuordnung und der Statusübergang werden durch Knoten und Verzweigungen in dem Graphen substituiert. Daher kann die Ressourcen-Zuordnung leicht untersucht werden.
Weiterhin kann der maximale Fluss in dem Netzwerk entsprechend der vorliegenden Erfindung durch Finden einer Verzweigung mit der maximalen Gewichtung erfasst werden.
Weiterhin wird es, wenn die Knoten und Verzweigungen mit dem Arbeitsinhalt und dem Arbeitsfluss in dem streng zusammenhängenden Graphen ersetzt werden, und wenn eine Verarbeitung, bei welcher eine Verzweigung mit der maximalen Gewichtung dadurch entfernt werden, um eine geschlossene Schleife herauszutrennen, addiert werden, wenn der maximale Fluss untersucht wird, möglich, die Planung sämtlicher Knoten in dem Graph zu untersuchen, d. h., den Arbeitsinhalt in der Reihenfolge anzuordnen.

Claims

1. Ressourcen-Zuordnungs-Untersuchungs- und/oder Planungs-System, mit einer Eingabevorrichtung (21) zum Eingeben verschiedener Informationen für die Ressourcen-Zuordnung und/oder Planung, einer Ausgabevorrichtung (24) zum Ausgeben des Ergebnisses und einem computerisierten Prozessor (22), wobei der Prozessor (22) ein durch einen aus Knoten (51; 61; 151; 181) bestehenden Graphen dargestelltes Modelt verarbeitet, welche einen Status zur Ressourcen-Zuordnung und/oder Ressourcen-Planung und Verzweigungen (52; 62; 152; 182) darstellen, von denen jeder beide Enden an einem Knotenpaar aufweist und einen Statusübergang darstellt, und einschließlich wenigstens einer geschlossenen Schleife entsprechend einem Ablauf vorher eingestellter Prozeduren, wobei der Prozessor (22) umfaßt:

eine Einrichtung zum Auswählen eines Knotens, von welchem der Ablauf zum Bestimmen der Gewichtung von Verzweigungen zwischen sämtlichen Knoten beginnt,

eine Einrichtung zum Klassifizieren der Knoten, abhängig von dem Bestimmungszustand der Gewichtung der Eingangsverzweigungen und Ausgangsverzweigungen des selektierten Knotens, und zum Gewichten sämtlicher Eingangsverzweigungen xji (bis zu einem Knoten i) und Ausgangsverzweigungen xij (von einem Knoten i) sämtlicher klassifizierter Muster von Knoten i, so daß Exij unter einer durch die folgende Gleichung (1) dargestellten Annahme kleinstmöglich ist,

Σjxij - Σjxji = 0

xij ≥ 0 (1)

eine Einrichtung zum Bestimmen der Gewichtung sämtlicher Verzweigungen in dem Graphen durch Wiederholen der durch die Selektionseinrichtung und die Klassifizierungseinrichtung ausgeführten Schritte, und

eine Einrichtung zum Erfassen einer Verzweigung mit der maximalen Gewichtung aus sämtlichen Verzweigungen.

2. System nach Anspruch 1, bei welchem der Prozessor (22) weiterhin eine Einrichtung zum Anordnen der die geschlossene Schleife bildenden Knoten umfaßt, in der Reihenfolge durch Entfernen der Verzweigung mit der maximalen Gewichtung, welche von der Erfassungseinrichtung erfaßt wird, und Heraustrennen der geschlossenen Schleife einschließlich der Verzweigung.

3. System nach Anspruch 1 oder 2, bei welchem die Selektionseinrichtung einen Knoten selektiert, welcher Gegenstand für die nächste Bestimmung der Gewichtung aus den mit den früher verarbeiteten Knoten durch Verzweigungen benachbarten Knoten ist.

4. System nach einem der vorstehenden Ansprüche, bei welchem der Prozessor (22) weiterhin eine Einrichtung zum Extrahieren streng zusammenhängender Komponenten aus dem Graphen umfaßt, um dadurch ein durch Entfernen geschlossener Schleifen aus der einen oder einer Mehrzahl von streng zusammenhängenden Komponenten erhaltenes Modell zu verarbeiten.