Blog

Wie Schwerkraft, Reibung oder elektrische Ladung mit der Fabrik-Layoutplanung zusammenhängen und wie sie beim Finden eines automatisch erstellten und optimierten Fabrik-Layout helfen, erfahren Sie in diesem Artikel.

Eine Testumgebung mit Beispieldaten eines Fabrik-Layouts zum selber Ausprobieren finden Sie am Ende des Artikels.

Arbeitsplätze lassen sich in Fabriklayouts mit verschiedenen Methoden anordnen. Einige davon habe ich schon vorgestellt. Die bisher gezeigten Verfahren waren dabei immer iterativ. Die Layoutbildung erfolgt Schritt für Schritt durch den Fabrikplaner. Bei der Schwerdtfeger-Methode durch Probieren und regelunterstützt beim Schmigalla-Verfahren. Der Planer hat den größten Einfluss auf die Entwicklung des Layouts.

Das hat seine Berechtigung, die notwendige Erfahrung des Planerteams berücksichtigt dabei mehrere Faktoren als nur berechenbare Relationen. Meiner Meinung sind diese Verfahren am besten für die Layoutentwicklung geeignet.

Allerdings ist das auch die zeitintensivste Möglichkeit, ein oder mehrere Layouts zu entwickeln. Aus Sicht der Material-Logistik sind die Transportbeziehungen zwischen Arbeitsplätzen die einflussreichsten Faktoren für die Positionierung. Für erste Überlegungen ist das deswegen ein guter Ausgangspunkt.

Grundlage für die Layoutplanung sind gerichtete oder ungerichtete Transportmatrizen. Wie diese erstellt werden können, habe ich im Artikel Materialflussmatrix aus ERP-Daten vorgestellt.

Die Matrizen stellen die Transportbeziehungen zwischen den Arbeitsplätzen dar. Für eine datentechnische Betrachtung ist aber eine Listenform besser geeignet. Die Liste stellt die gerichtete Transportbeziehung zwischen zwei Arbeitsplätzen dar. Sie wird deswegen auch als Von-Nach-Liste bezeichnet.

Der Arbeitsplatz Drehen1 steht mit drei anderen Arbeitsplätzen über die Transportbewegungen in Verbindung: Sägen, Schleifen2 und Bohren1. Hier ist es noch einfach eine günstige Positionierung im Layout zu finden. Drehen1 sollte Nahe zwischen Sägen und Schleifen2 und Bohren1 angeordnet werden.

Konkurrieren aber noch andere Arbeitsplätze Schleifen1, Schleifen3, Bohren2 usw. um Layoutpositionen wird die Anordnung komplex.

Der Weltraum, unendliche Weiten…

Nein jetzt kommt kein Wechsel zu Star Trek, obwohl der Bordcomputer sicherlich ein perfektes Layout vorschlagen würde.

Stellt man sich das gesamte System Arbeitsplätze und Transportverbindungen transformiert auf das Universum vor, wären die Arbeitsplätze die Planeten. Die Summe der Transportverbindungen würde ihrer Masse entsprechen. Die Masse reagiert über die Anziehungskraft mit den anderen Planeten/Arbeitsplätzen.

Würde sich jetzt der ganze „Weltraum“ mit diesen Kräfteverhältnissen einpendeln, stellt sich eine kräftebasierte Anordnung ein, indem alle Arbeitsplätze um die besten Plätze, entsprechend ihrer Masse/Transportverbindungen, konkurrieren.

Genau dieses Verhalten lässt sich auch für die Layoutoptimierung nutzen. Es kann über eine spezielle Diagrammart, die als selbst-organisierende Diagramme (self-organizing graphs) bezeichnet werden, nachgebildet werden. Einen interessanten Einblick in das Thema gibt Sue. H. Whitesides im Buch Graph Drawing.

Nach den ersten Seiten ist klar, das Thema ist mathematisch anspruchsvoll und nur mit spezieller Software zu lösen.

D3.js

Mein Ziel ist in diesem Blog aber das programmiertechnisch selber umzusetzen und eine freie Software einzusetzen.

Im Bereich Data Visualizing hat sich in den letzten Jahren sehr viel getan. Durch freie Daten-API’s im Internet sind auch viele Visualisierungen entstanden. Viele davon dadurch direkt im Browers erstellt mit JavaScript.

Die JavaScript Bibliothek D3.js bietet für viele Diagramme eine hilfreiche Unterstützung an. Am interessantesten ist, dass D3 auch eine Art von selbst-organisierenden Diagrammen anbietet. Es kann Force-Directed-Graphs darstellen.

Diese Force-Directed-Graphs kommen meinem gewünschten Verhalten sehr nahe. Ob sie aber beim Entwickeln von automatischen Fabrik-Layouts helfen können, muss getestet werden.

Vorbereitungen

JavaScript-Code mit D3 bedeutet, dass das Ergebnis im Browser dargestellt wird. Zum Entwickeln muss eine passende Umgebung vorhanden sein. In meinem Fall nutze ich dafür Visual Studio Code und node.js. D3 benötigt keine anderen Bibliotheken oder Abhängigkeiten. Es kann direkt von der Webseite d3js.org verlinkt werden.

Zum Testen ist ein http-Server sinnvoll, da in der Regel Daten zu Arbeitsplätzen und Materialflüssen geladen werden.

Ausgangspunkt ist eine HTML-Datei. Sie besteht nur aus einem minimalen Inhalt. D3 und die Funktionen zum Darstellen des Layouts werden als Script geladen. Der Rest besteht nur aus einem SVG Element. In dieses HTML-Tag erzeugt D3 das Layout.

Beispiel: index.html

<html>
  <head>
    <title>Anordnungsoptimierung mit Force Directed Graph</title>
    <meta charset="utf-8" />
    <script src="https://d3js.org/d3.v3.min.js"></script>
  </head>
  <body>
    <svg id="layout"></svg>
  </body>
</html>

Anmerkung: Ich verwende in diesem Artikel D3.js in der Version 3.

Vergleich mit der Schmigalla-Methode

Um herauszufinden, ob ein kräftebasierte Layoutplanung brauchbare Ergebnisse liefert, vergleiche ich sie mit einer anderen Methode.

Dafür habe ich die Schmigalla-Methode ausgewählt. Im Artikel Dialog-geführtes Dreiecksverfahren nach SCHMIGALLA wende ich die Methode für eine Schneckengetriebeproduktion an.

Basierend auf den Regeln nach Schmigalla ist dieser Vorschlag für ein Layout auf einem Dreiecksraster entstanden:

Im folgenden vergleiche ich den erzeugten Force-Directed-Graph des kräftebasierten Layouts mit dem Ergebnis dieser Schmigalla Layoutplanung.

Datenimport in D3

Die Daten der Schmigalla Methode für Arbeitsplätze und Von-Nach-Liste werden auch als Eingangsdaten für den Force-Directed-Graph benutzt.

D3 kann mit einer Vielzahl von Daten umgehen, wie CSV, TSC, JSON. Die Informationen zu Arbeitsplätzen und Materialflüssen kommen meist aus Datenbanken. Deswegen passt das CSV (comma separated value) Format gut, da in dieses recht einfach exportiert werden kann.

Excel kann Tabellen auch als CSV Datei exportieren. Allerdings verwendet Excel als Trennzeichen einen Strichpunkt. D3 ist hier wählerisch und benötigt ohne Anpassungen ein Komma.

Die notwendigen Eingangsdateien workcenters.csv und flow.csv sehen im Vergleich aus, wie nachfolgend dargestellt.

id,caption,color
ABS280,Sägen,lightgrey
CU72H,Bohren,lightgrey
DEBURR,Entgraten,lightgrey
DMU50V,Drehen,lightgrey
PE150C,Fräsen,lightgrey
PF150,Wälzschälen,lightgrey
RISZ,Räumen,lightgrey
TNC65,Drehen,lightgrey
ZX1,Schleifen,lightgrey
WE,Wareneingang,CornflowerBlue 
WA,Warenausgang,LawnGreen

source,target,transport
WE,ABS280,240
WE,TNC65,204
WE,DMU50V,570
WE,ZX1,120
ABS280,TNC65,240
TNC65,RISZ,60
TNC65,PE150C,60
TNC65,DMU50V,144
TNC65,ZX1,180
PE150C,DEBURR,120
DMU50V,CU72H,570
DMU50V,WA,144
CU72H,DEBURR,570
DEBURR,WA,690
ZX1,PF150,60
ZX1,WA,240
PF150,WA,60

Die Arbeitsplätze werden durch die ID, eine Bezeichnung und eine Farbe beschrieben. Die Transportbeziehungen bestehen aus Von-Nach-Informationen: Von-ID, Nach-ID und der Transportmenge pro Jahr.

Die beiden Dateien werden am Beginn des JavaScripts mit der D3 Funktion d3.csv() gelesen.

d3.csv("workcenters.csv", function(error1, data1) {
    d3.csv("flow.csv", function(error2, data2) {
      createForceLayout(data1,data2); 
    });
  });  

Force-Directed-Graph erzeugen

Damit D3 die Struktur als Netz darstellen kann, müssen zwischen den Arbeitsplätzen Objekt-Verbindungen erzeugt werden. Die können von D3 verarbeitet werden. Dafür eignet es sich, die Arbeitsplätze in eine neue Liste mit der ID als Schlüssel zu kopieren. Damit lassen sich die Eigenschaften source und target einfach mit dem jeweiligen Objekt „Arbeitsplatz“ ersetzen.

  var workcenterHash = {};
  for (i in workcenters) {
    workcenterHash[workcenters[i].id] = workcenters[i];
  }

  for (i in materialflow) {
    materialflow[i].transport = parseInt(materialflow[i].transport);
    materialflow[i].source = workcenterHash[materialflow[i].source];
    materialflow[i].target = workcenterHash[materialflow[i].target];
  }

Generiert wird der Force-Directed-Graph mit dem Befehl d3.layout.force() und force.start(). Über das Ereignis tick erfolgt die Bewegung und damit das Ausrichten der Arbeitsplätze im Layout.

force = d3.layout.force()
    .size([width,height])
    .nodes(workcenters)
    .links(materialflow)
    .on("tick", function () {
      svg.selectAll("line.transport")
      .attr("x1", d => d.source.x)
      .attr("x2", d => d.target.x)
      .attr("y1", d => d.source.y)
      .attr("y2", d => d.target.y);
    
    svg.selectAll("g.workcenter")
      .attr("transform", d => "translate("+d.x+","+d.y+")")      
    });

  svg.selectAll("line.transport").data(materialflow).enter()
    .append("line")
    .attr("class", "transport")
    .style("opacity", .5)    
    .style("stroke", "gray")
    .style("stroke-width", "1px");
    
  var workcenter = svg.selectAll("g.workcenter").data(workcenters, d => d.id).enter()
    .append("g")
    .attr("class", "workcenter");
    
  workcenter.append("circle")
    .attr("r", 15)
    .style("fill", d => d.color)
    .style("stroke", "gray")
    .style("stroke-width", "1px");

  workcenter.append("text")
    .style("text-anchor", "middle")
    .style("font-size", "0.8em")
    .attr("y", 5)
    .text(d => d.id);
    
  force.start();

Das Ergebnis sieht im Browser noch nicht vielversprechend aus. D3 zeichnet zwar alle Arbeitsplätze und ordnet Farben zu, aber alles wird noch in der Bildmitte zusammengezogen.

Das lässt sich mit den Parametern des Force-Directed-Graph aber anpassen.

Charge, Gravity und Friction

In der Version 3 von D3 erfolgt die Einstellung der Anziehungskräfte über die Eigenschaften Charge, Gravity und Friction.

• Charge ist wie eine elektrische Aufladung der Arbeitsplätze zu sehen. Bei negativen Werten stoßen sich die Arbeitsplätze ab, bei positiven ziehen sie sich an.
• Gravity verhindert mit einem Wert größer 0, dass die Arbeitsplätze wandern und sich stattdessen im Zentrum sammeln. Bei einem Wert von 0 „schweben“ die Arbeitsplätze im Graphen.
• Friction teilt D3 mit, wie stark die Bewegung bei jeder Iteration gebremst werden soll. Bei einem Wert von 1 wird das Layout nie langsamer, während 0 alle Arbeitsplätze, sofort anhält.

Der richtige Ort, um die Parameter zu übergeben ist im Chaining der d3.layout.force().

force = d3.layout.force()
    .charge(-1000)
    .gravity(0.1)
    .friction(0.9)

Mit diesen Werten für Charge (-1000 = abstoßend), Gravity und Friction werden bei jedem Aktualisieren der Seite Layouts erzeugt. Jetzt ist auch erkennbar, dass alle Verbindungen korrekt enthalten sind.

Man sieht auch, dass die erzeugten Force-Directed-Graphen schon ähnliche Ergebnisse liefert, wie das Schmigalla-Verfahren.

Der Abstand zwischen benachbarten Elementen ist ungefähr gleich groß. Deshalb lässt sich noch nicht herauslesen, welche Verbindungen stärker sind. Und genau das ist für die Layoutplanung interessant, denn diese sollten anordnungstechnisch bevorzugt werden.

Um das zu berücksichtigen, braucht es weitere Eigenschaften: Abstand und Stärke.

LinkDistance und LinkStrength

Ein Force-Directed-Graph ist etwas anders aufgebaut, als im ersten Beispiel vorgestellt. Die Beziehungen zwischen den einzelnen Elementen sind dabei eher wie Federn zu sehen. Das Federverhalten wird über die beiden Eigenschaften linkDistance und linkStrength festgelegt.

Den Wert der Entfernung linkDistance zwischen zwei Arbeitsplätzen versucht der Force-Directed-Graph durch mehrere Iterationen zu erreichen. Wird für linkStrength als Wert 1 übergeben, versucht D3 genau die linkDistance zu erreichen. Bei kleineren Werten von linkStrength bis auf 0 wird der Abstand nicht genau eingehalten.

Für das Layout soll möglichst der Abstand der Transporthäufigkeit erreicht werden, deswegen ist linkStrength auf 1 gesetzt.

Der Abstand wird in Abhängigkeit des Transportaufkommens berechnet. D3 stellt dafür Skalierungsfunktionen zur Verfügung, um Werte einfach umzurechnen. In domain werden die min- und max-Werte der Transportmatrix hinterlegt. In range der virtuelle Bereich der linkDistance von 1 bis 0,1. Die beiden Grenzwerte haben die umgekehrte Reihenfolge wie die min/max-Werte der Transportmatrix.

  var transportScale1 = d3.scale.linear()
    .domain(d3.extent(materialflow, d => d.transport))
    .range([1,.1]);   

  force = d3.layout.force()
    .charge(-1000)
    .gravity(0.1)
    .friction(0.9)
    .linkDistance(d => transportScale1(d.transport))
    .linkStrength(1)   

Mit dieser Anpassung werden noch bessere Ergebnis-Layouts erreicht. Höhere Transportvolumen erzeugen nun stärkere „Federkräfte“ und damit eine nähere Positionierung der Arbeitsplätze.

Das kommt noch besser zur Geltung, wenn die Haupt-Materialflüsse rot eingefärbt werden.

  svg.selectAll("line.transport").data(materialflow).enter()
    .append("line")
    .attr("class", "transport")
    .style("opacity", .5)    
    .style("stroke", d => lineColor(transportScale(d.transport)))
    .style("stroke-width", d => 10*transportScale(d.transport));


  function lineColor(value) {
    if (value>0.8) {return "red";}
    else {return "black";}
  }

Vergleich kräftebasierte Layout- vs. Schmigalla-Methode

Im direkten Vergleich lässt sich erkennen, dass die Force-Directed-Methode eine sehr ähnliche Anordnung liefert, wie die Schmigalla-Methode. Sie enthält durch die kräftebasierte Anordnung sogar noch mehr Entfernungsinformationen als die Schmigalla-Methode. Das kann für eine spätere Positionierung im Fabriklayout wichtig sein.

Interaktionen

Wie bei der Schmigalla-Methode liefert der Force-Directed-Graph ein statisches Bild für einen Positionsierungsvorschlag. Noch interessanter ist für mich die Möglichkeit, die dahinter liegenden Kräfte selber zu „spüren“.

Genau das ist mit D3 animationstechnisch möglich. Notwendig ist dafür nur eine Zeile Code.

var workcenter = svg.selectAll("g.workcenter").data(workcenters, d => d.id).enter()
    .append("g")
    .attr("class", "workcenter")
    .call(force.drag());

Mit dem Befehl force.drag() lassen sich jetzt die einzelnen Arbeitsplätze mit der Maus per Drag and Drop an eine andere Position verschieben. Durch das Kräftenetz werden die anderen Arbeitsplätze „mitgezogen“. So kann man sehr gut ein Gefühl für die Verbindungen und die Kräfte im Hintergrund entwickeln.

Noch praktischer ist es, wenn einzelne Arbeitsplätze fixiert werden können. Das kann über einen Doppelklick auf den Arbeitsplatz erfolgen.

    .on("dblclick", function (d) {
      d.fixed = !d.fixed;
      if (d.fixed==true) {
        d3.select(this).select("circle")
          .style("stroke-width", 3);
      } else {
        d3.select(this).select("circle")
          .style("stroke-width", 1);
      }

Mit dem Code wird ein weiterer Ereignislistener eingefügt. Bei einem Doppelklick auf einen Arbeitsplatz wird die Eigenschaft fixed von true auf false oder umgekehrt gesetzt. Ist sie auf false, berechnet D3 keine neue Position für den Arbeitsplatz. Zur Visualisierung wird die Umrandung (stroke-width) auf 3 Pixel gesetzt.

Die Funktion erleichert das Auseinanderziehen von starken Verbindungen. Im obigen Beispiel könnten die Layoutpositionen der drei fixierten Arbeitsplätze (WE, DMU50V und WA) nicht veränderbar sein. Durch das Fixieren lassen sie sich auf die ungefähre reale Layoutposition verschieben. Die anderen Arbeitsplätze ordnen sich danach wieder neu und kräftebasiert im Fabrik-Layoutplan an.

Kräftebasierte Positionierung im Test

Aber am besten Sie probieren das selber aus. Über die Schieberegler lassen sich die Eigenschaften verändern. Mit Anklicken des Buttons Aktualisieren werden Eigenschaften übernommen und der Graph wird neu aufgebaut. Die Arbeitsplätze lassen sich mit der Maus anpacken und kräftebasiert verschieben.

Resumé

In dem gezeigten Beispiel trifft der automatisch generierte Force-Directed-Graph sehr genau eine optimale Layoutanordnung. Das liegt sicher auf an dem recht einfachen Materialfluss-Netz mit nur wenigen Verbindungen.

Mit den interaktiven Möglichkeiten mit dem Graphen zu spielen, kann meiner Meinung nach ein gutes Gespür für die Transportbeziehungen gewonnen werden.

Gerade um zu erkennen, was unbedingt nahe zusammenstehen sollte.

Mit dem Grundaufbau des JavaScripts lassen sich jetzt auch größere Anordnungsprobleme untersuchen und völlig automatisch kräftebasierte Fabrik-Layoutplanungsvarianten erzeugen. Dem Quellcode ist es schließlich egal wie viele Arbeitsplätze enthalten sind.

Viel Spaß beim Ausprobieren!

Download

HTML-Datei mit JavaScript Code und CSV-Dateien als ZIP-Datei:
force-directed-layout-planning.zip (3 KB)

Zum Testen ist ein http-Server notwendig

Links

D3js Homepage: https://d3js.org/
Wikipedia D3.js: https://de.wikipedia.org/wiki/D3.js
Wikipedia Artikel zu Force-Directed-Graph: https://en.wikipedia.org/wiki/Force-directed_graph_drawing
Artikel Materialflussmatrix aus ERP-Daten
Artikel Dialog-geführtes Dreiecksverfahren nach SCHMIGALLA