Erarbeitung von Ansätzen zur Lösung des Rossmann

Erarbeitung von Ansätzen zur Lösung des
Rossmann-Problems
Praxisprojektbericht
vorgelegt von
Tim Metzler
4. Mai 2015
Fachhochschule Bonn-Rhein-Sieg
Fachbereich Informatik
Grantham-Allee 20
53757 Sankt-Augustin
Inhaltsverzeichnis
Inhaltsverzeichnis
1
1 Problemstellung
2
2 Stand der Forschung
3
3 Analyse der Ansätze
3.1 Prioritätsregeln . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Taktfahrpläne im Nahverkehr . . . . . . . . . . . . . . . . . .
3.3 Online-Algorithmen . . . . . . . . . . . . . . . . . . . . . . .
4
4
5
5
4 Lösungsansatz für die statische Variante
4.1 Einfacher Greedy-Algorithmus . . . . . . . . . . . . . . . . .
4.2 Optimierter Greedy-Algorithmus . . . . . . . . . . . . . . . .
6
6
8
5 Modellierung des Lagers mit Petri-Netzen
5.1 Einführendes Beispiel . . . . . . . . . . . .
5.2 Mathematische Definition . . . . . . . . . .
5.3 Coloured Petri Nets . . . . . . . . . . . . .
5.4 Zeitbehaftete Petri-Netze . . . . . . . . . .
5.5 Modellierung des Rossmann Lagers . . . . .
5.6 Erkenntnisse aus dem Modell . . . . . . . .
5.7 Bewertung des Modells . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
9
10
10
12
13
14
15
6 Zusammenfassung
17
Abbildungsverzeichnis
19
1
1
Problemstellung
In dieser Projektarbeit werden verschiedene Ansätze zur Lösung des Rossmann-Problems untersucht. Im Lager der Firma Rossmann in Landsberg
gibt es eine Anlage, in die Aufträge der Verkaufsstellen eingebracht werden. Diese Aufträge werden auf Kisten verteilt und an einer Quelle in das
System eingespeist. Von der Hauptstrecke gibt es Abzweigungen zu Schleifen, in denen sich mehrere Bahnhöfe befinden. An diesen Bahnhöfen werden
die Kisten automatisch auf ein Abstellgleis gefahren, von den Mitarbeitern
befüllt und von diesen wieder manuell auf die jeweilige Nebenstrecke (in die
Schleife) geschoben. Nach dem Passieren einer Schleife fahren die Kisten
wieder auf die Hauptstrecke und steuern entweder weitere Bahnhöfe oder
den Ausgang der Anlage an.
Im Lager kommt es häufig zu Staus. Diese entstehen bei einem sehr hohen Kistenstrom. Dabei kommt es einerseits dazu, dass die Kapazität des
Bahnhofs ausgeschöpft ist und keine weiteren Kisten diesen Bahnhof mehr
anfahren können. Andererseits kommt es dazu, dass der Kistenstrom am jeweiligen Bahnhof so hoch ist, dass der Mitarbeiter keinen Platz auf der Nebenstrecke findet, um eine befüllte Kiste wieder in den Strom einzubringen.
Kisten, die nun nicht in einen vollen Bahnhof einfahren können, überspringen
diesen. Dabei werden zuerst alle unbesetzten nachfolgenden Bahnhöfe angefahren, und anschließend wird die Kiste wieder an der Quelle in das System
eingebracht, um die übersprungenen Bahnhöfe anzufahren. Kommt eine Kiste ein drittes Mal an einem Bahnhof vorbei und kann diesen immer noch
nicht anfahren, stoppt die Kiste und verweilt solange vor dem Bahnhof, bis
dieser wieder genug Kapazitäten hat, um die jeweilige Kiste aufzunehmen.
Die Feststellung, ob ein Bahnhof voll ist wird erst getroffen, wenn sich die
Kiste direkt vor dem Bahnhof befindet. Somit werden Schleifen mit vollen Bahnhöfen nicht einfach übersprungen, sondern die Kiste passiert jede
Schleife in der sich ein Bahnhof für diese Kiste befindet. Die Staus führen zu
einer längeren Verweilzeit von Kisten im System, zum mehrfachen Durchlaufen des Systems und zu einer Blockierung der Strecken, so dass keine
bearbeiteten Kisten auf die Strecke zurückgeschoben werden können.
Ein Faktor, der die Staus noch verstärkt, ist, dass leere Behälter aus denen
die Ware zur Befüllung der Kisten entnommen wird, an den Bahnhöfen über
die gleiche Strecke abtransportiert werden, über die auch die Kisten transportiert werden. Im Gegensatz zu den Kisten fahren die leeren Behälter auf
dem schnellsten Weg aus der Anlage hinaus. Der einzige Parameter, über
den sich das System beeinflussen lässt, ist die Reihenfolge, in der die Kisten
in die Anlage eingebracht werden. Daher stellt sich nun die Frage, in welcher
Reihenfolge eine gegebene Menge von Aufträgen in das System eingespeist
werden soll.
2
2
Stand der Forschung
Nachdem im vorigen Kapitel das Problem vorgestellt wurde, soll nun ein
Überblick über einige Ansätze aus der Literatur gegeben werden. Grundsätzlich gibt es zwei Ansätze das Rossmann-Problem zu lösen. Dies ist zum
einen die statische Lösung des Problems. Hierbei wird von einer leeren Anlage und einer Menge von Aufträgen ausgegangen. Die Schwierigkeit besteht
dabei darin, dass die Reihenfolge im Vorhinein bestimmt werden muss. Zum
anderen kann ein dynamischer Ansatz gewählt werden, bei dem, abhänging
vom Zustand des Systems, der jeweils passende Auftrag aus einer Menge
von Aufträgen ausgewählt wird.
In der Literatur gibt es bereits einige Ansätze, um ähnliche Probleme zu
lösen. Dabei gibt es beispielsweise die Reihenfolge- und Kapazitätsplanung
als Untergebiet der Produktionsplanung. Im Unterschied zum RossmannProblem wird dabei eine optimale Reihenfolge bestimmt, in der n verschiedene Produkte auf m verschiedenen Maschinen so zu bearbeiten sind, dass
die Durchlaufzeiten minimiert werden. Jedoch geht man hier entweder von
der Prämisse aus, dass jedes Produkt von jeder Maschine bearbeitet werden
muss, oder dass jedes Produkt an jeder Maschine bearbeitet werden kann.
Im ersten Fall muss also ein Produkt jede Maschine durchlaufen, und im
zweiten Fall muss jedes Produkt auf einer von m gleichen Maschinen bearbeitet werden. Die Lösungsstrategien, welche in der Reihenfolgeplanung
angewandt werden, basieren in der Regel auf Prioritätsregeln. In Abbildung
1 ist eine Auswahl üblicher Regeln aufgetragen.
Abbildung 1: Prioritätsregeln
Weitere Ansätze in der Literatur zur Lösung ähnlicher Probleme sind beispielsweise die Planung von Taktfahrplänen im öffentlichen Nahverkehr.
Hierbei könnten die einzelnen Aufträge als Bahnlinien aufgefasst werden.
Allgemein weist die Verkehrsplanung einige Gemeinsamkeiten mit dem Rossmann-Problem auf.
Die bis hier vorgestellten Ansätze betrachten die Reihenfolgeoptimierung
des Rossmann-Problems unter statischen Gesichtspunkten. Eine weitere Be3
trachtungsweise besteht darin, das System dynamisch aufzufassen. Dabei
sind Online-Algorithmen besonders interessant. Bei diesen Algorithmen sind
zu Beginn der Berechnungen nicht alle Eingabedaten verfügbar. Hierbei
könnte zu Beginn eine Reihenfolge bestimmt werden. Diese Reihenfolge wird
dann jeweils mit dem Systemzustand abgeglichen. Wenn der aktuelle Systemzustand mit der vorberechneten Reihenfolge zu Ressourcenkonflikten
führt, werden die Aufträge, welche noch nicht in das System eingebracht
wurden, umsortiert, um diese Konfilkte zu vermeiden. Jedoch gibt es in
der Literatur bisher keine Online-Algorithmen, die das Rossmann-Problem
lösen. Daher müsste ein neuer Algorithmus entworfen werden.
3
Analyse der Ansätze
Nachdem im vorigen Kapitel einige potentielle Ansätze vorgestellt wurden,
stellt sich nun die Frage, inwieweit diese auf das Rossmann-Problem übertragbar sind. Dabei wird besonders auf die Unterschiede zum RossmannProblem eingegangen. Darüber hinaus erfolgt eine grobe Einschätzung der
Erfolgsaussicht und des zu erwartenden Aufwands der Lösung.
3.1
Prioritätsregeln
Prioritätsregeln sind in der Industrie stark verbreitet. Jedoch fehlt bei diesen zum einen der Kapazitätsfaktor und zum anderen muss jeder Auftrag
eine individuelle Bahnhofsreihenfolge durchlaufen. Im folgenden einfachen
Beispiel wird die Diskrepanz deutlich.
Auf tragsmenge = {{Bf 1}, {Bf 1}, {Bf 1}, {Bf 2, Bf 3}, {Bf 3, Bf 4}} (1)
Die Auftragsmenge ist nach der kürzesten Operationszeit geordnet. Wenn
nun jeder Bahnhof eine Kapazität von 2 aufweist, kommt es am Bahnhof 1 zu
einem Ressourcenkonflikt. Daraus wird deutlich, dass Prioritätsregeln ohne
Nebenbedingungen bezüglich der Kapazitäten keinen geeigneten Lösungsansatz für das Rossmann-Problem darstellen. Um diesen Aspekt einfließen zu
lassen, könnten beispielsweise Untermengen von Aufträgen ohne Ressourcenkonflikte gebildet werden. Innerhalb dieser Untermengen kann dann der
Einfluss von Prioritätsregeln untersucht werden. Andererseits können diese Untermengen auch wieder als einzelne Aufträge aufgefasst werden, die
mit Hilfe von Prioritätsregeln sortiert werden. Erste Untersuchungen am
im Kapitel 2 vorgestellten Modell zeigen, dass sich Prioriätsregeln durchaus
eignen, um die Durchlaufzeit von konfliktfreien Aufträgen zu optimieren.
Hierbei verspricht besonders die Regel Bahnhof mit höchster Entfernung
”
zuerst“ gute Ergebnisse. Dabei werden zuerst alle Aufträge in die Anlage
eingebracht, die den letzten Bahnhof enthalten. Danach wird für die weiteren Bahnhöfe genauso verfahren. Obwohl sich Prioritätsregeln alleine nicht
4
für die Lösung des Rossmann-Problems eignen, können diese als Teilaspekt
in eine andere Lösung integriert werden.
3.2
Taktfahrpläne im Nahverkehr
Ein weiterer Ansatz ist der Versuch, das Rossmann-Problem mittels der
Methoden aus der Verkehrsplanung zu lösen. Dabei sind vor allem Straßenbahnnetze interessant, da bei diesen die einzelnen Linien verschiedene
Bahnhöfe anfahren müssen. Weiterhin gibt es keine oder nur sehr wenige Überholmöglichkeiten. Auf das Rossmann-Problem übertragen würden
die Bahnlinien den Aufträgen entsprechen. Ein Auftrag, der die Bahnhöfe
1, 2 und 3 anfahren muss, könnte dann als Bahnlinie modelliert werden,
die genau diese Bahnhöfe anfährt. Allerdings gibt es dann eine sehr große
Zahl an Linien. Bei n verschiedenen Bahnhöfen gibt es 2n - 1 verschiedene
mögliche Bahnlinien. Für das Lager mit 70 Bahnhöfen ergibt sich damit die
Anzahl der Möglichkeiten zu 270 - 1 ≈ 1021 . Dieser Ansatz verspricht also nur
dann Erfolg, wenn es häufig Aufträge mit der gleichen Bahnhofsreihenfolge
gibt (beispielweise wenn jeder nte Auftrag die gleiche Reihenfolge aufweist).
Dann könnte alle x Minuten ein Platz für diese Linie freigehalten werden.
Ist dies nicht der Fall, eignet sich dieser Ansatz auf Grund der Vielzahl an
Möglichkeiten und des daraus resultierenden Berechnungsaufwand nicht zur
Lösung des Rossmann-Problems.
3.3
Online-Algorithmen
Mit Hilfe eines Online-Algorithmus könnte das Rossmann-Problem in mehrere Teilprobleme zerlegt werden. Dabei wird zuerst von einer leeren Anlage und einer Menge von Aufträgen ausgegangen. Die Bearbeitungszeit
an jedem Bahnhof wird als fest angenommen. Das erste Teilproblem besteht damit darin, eine gute Reihenfolge für die Anlage vorzuberechnen. Die
Aufträge werden anhand dieser Reihenfolge in die Anlage eingebracht. Das
zweite Teilproblem bestünde darin, den Zustand des Systems zu überprüfen
und potentielle Konflikte zu erkennen. Wenn nun ein Konflikt prognostiziert
wird, kann die Reihenfolge der Aufträge, die noch nicht in die Anlage eingebracht wurden, entsprechend angepasst werden. Die Lösung des Problems
erfolgt dann in drei Schritten:
1. Bestimmung einer Reihenfolge unter der Annahme, dass alle Bearbeitungszeiten bekannt sind
2. Analyse des Systemzustandes und Konfliktvorhersage
3. Umsortierung zur Vermeidung der Ressourcenkonflikte
Da jedes dieser Probleme für sich genommen schon eine hohe Komplexität
aufweist, ist bei diesem Ansatz mit einem hohen Entwicklungsaufwand zu
5
rechnen. Jedoch ist dies bisher der einzige Ansatz, mit dem sich sowohl der
statische, als auch der dynamische Aspekt des Systems erfassen lässt.
4
Lösungsansatz für die statische Variante
In diesem Abschnitt wird ein Ansatz zur Lösung der statischen Variante
vorgestellt. Dabei wird von einer festen Auftragsmenge und einer leeren
Anlage ausgegangen. Weiterhin sind alle Bearbeitungszeiten fest und für
jede Kiste an jedem Bahnhof gleich. Nun soll unter diesen Bedingungen ein
Belegungsplan erstellt werden. Als Grundlage wird ein Greedy-Algorithmus
genommen.
4.1
Einfacher Greedy-Algorithmus
Für den Greedy-Algorithmus wird zunächst eine Belegungsmatrix für die
Ressourcen im System erstellt. Dabei entsprechen die Spalten den Ressourcen und die Zeilen den Zeitschritten. Nun sollen die Aufträge so auf die
Belegungsmatrix aufgeteilt werden, dass zum einen zu jeder Zeit einer hohe
Auslastung der Anlage gegeben ist und zum anderen die Gesamtbearbeitungsdauer der Aufträge möglichst gering ist.
Zu Beginn wird die Belegungsmatrix mit den Kapazitäten befüllt. Abbildung
2 zeigt die initiale Belegungsmatrix für eine Anlage mit vier Bahnhöfen, fünf
Zeitschritten und einer Kapazität am Bahnhof von vier. Jeder Bahnhof hat


4 4 4 4
4 4 4 4



M=
4 4 4 4
4 4 4 4
4 4 4 4
Abbildung 2: Beispielmatrix
also anfangs zu jedem Zeitschritt eine Kapazität von 4. Nun werden aus der
Auftragsmenge solange Aufträge herausgenommen, bis der Belegungsvektor
zum Zeitpunkt t keine nutzbaren Restkapazitäten mehr enthält. Diese Aufträge werden dann zum Zeitpunkt t in die Anlage eingebracht. Danach wird
das Verfahren für den Zeitschritt t+1 wiederholt. Dies geschieht solange, bis
alle Aufträge auf die Belegungsmatrix verteilt wurden.
Als Ergebnis erhält man nun Listen von Aufträgen, die zu einen bestimmten
Zeitpunkt in die Anlage eingebracht werden sollen. Die Aufträge einer Liste
werden auf einmal in die Anlage eingebracht. Danach wird eine bestimmte
Zeit abgewartet, bis die Aufträge aus der nächsten Liste eingebracht werden.
6
Am folgenden Beispiel wird dies einmal vorgestellt.
A = {{1, 2, 4}, {1, 3}, {1}, {1}, {1, 4}, {1, 2, 3}, {2}, {1, 3, 4}, {4}, {1, 2, 3}}
(2)
Die Menge A entspricht der Menge der Aufträge. Jede Untermenge entspricht einem Auftrag. Die Zahlen in den Untermengen symbolisieren die
einzelnen Bahnhöfe, die der Auftrag anfahren muss.
Geht man nun nach dem beschriebenen Greedy-Algorithmus vor, erhält man
folgende Belegungsmatrix.


0 3 4 3
0 1 3 4



M=
4 4 1 1
4 4 4 4
4 4 4 4
Abbildung 3: Belegungsmatrix
t=0
t=1
{1, 2, 3}
{1, 3}
{1, 2, 3}
{1, 4}
{1, 2, 4}
{1}
{1, 3, 4}
{1}
{2}
{4}
Abbildung 4: Auftragsreihenfolge
t=0
t=1
{4}
{1, 3}
{2}
{1, 4}
{1, 3, 4}
{1}
{1, 2, 4}
{1}
{1, 2, 3}
{1, 2, 3}
Abbildung 5: Auftragsreihenfolge sortiert
Die Abbildung 4 zeigt nun die Aufträge, die zu jedem Zeitschritt in die Anlage eingebracht werden sollen. Aus der Belegungsmatrix lässt sich ablesen,
dass die Bearbeitung aller Aufträge auf der Anlage 3 Zeitschritte dauert.
Dabei entspricht ein Zeitschritt der Bearbeitungsdauer an einem Bahnhof,
multipliziert mit der Kapazität eines Bahnhofs. Die reale Bearbeitungszeit
ergibt sich somit zu 18 * (Bearbeitungszeit\Bahnhof). Obwohl nun auf dem
Papier konfliktfreie Auftragsmengen entstanden sind, können diese nicht
einfach in einer beliebigen Reihenfolge in die Anlage eingebracht werden.
Stattdessen müssen diese nochmals sortiert werden. Dies geschieht absteigend nach dem ersten anzufahrenden Bahnhof. Innerhalb der Aufträge, bei
denen dieser Bahnhof gleich ist, wird für den zweiten anzufahrenden Bahnhof
genauso verfahren. Ohne diese Sortierung müsste beispielsweise der Auftrag
{1}, wenn er vor dem Auftrag {1, 3} eingebracht wurde, diesen irgendwo
7
auf der Anlage überholen. Dies führt zu kleineren Staus und damit zu mehr
Rücksprüngen. Abbildung 5 zeigt die sortierten Auftragsmengen.
4.2
Optimierter Greedy-Algorithmus
Der im vorigen Abschnitt vorgestellte Greedy-Algorithmus lässt sich noch
verbessern. Wenn die Aufträge, aus denen der Greedy-Algorithmus wählt,
vorsortiert werden, kann die Effizienz des Algorithmus nochmals gesteigert
werden.
Dabei werden die Aufträge zunächst absteigend nach der Anzahl der anzufahrenden Bahnhöfe sortiert. Dies soll verhindern, dass lange Aufträge
erst am Ende eingebracht werden und somit die Gesamtbearbeitungsdauer
verlängern. Danach werden die Aufträge mit der gleichen Länge sortiert.
Aufträge gleicher Länge werden absteigend nach den Bahnhöfen sortiert.
Daraus ergibt sich das der Auftrag {1, 3, 4} vor dem Auftrag {2, 3} gewählt
wird. Weiterhin wird der Auftrag {1, 3, 4} auch vor dem Auftrag {1, 2, 3}
ausgewählt.
In mehreren tausend Testdurchläufen wurde nun jeweils der vorsortierte
Greedy-Algorithmus mit einem zufällig sortierten Greedy-Algorithmus verglichen. Dabei hat sich gezeigt, dass der vorsortierte Algorithmus in 90% der
Fälle ein gleich gutes oder besseres Ergebnis liefert. In den restlichen 10%
war der zufällige Algorithmus um höchstens einen Zeitschritt schneller.
Weiterhin hat sich gezeigt, dass der vorsortierte Algorithmus immer besser
wird, wenn sich die Anzahl der Bahnhöfe pro Auftrag stark unterscheidet.
Bei 700 Aufträgen, 70 Bahnhöfen in der Anlage, einer Kapazität von 6 pro
Bahnhof und einer Anzahl von 10 bis 30 Bahnhöfen pro Auftrag, liefert der
verbesserte Algorithmus sogar in 95% der Fälle ein besseres Ergebnis. Dabei
wurde der vorsortierte Algorithmus mit 1000 zufälligen Sortierungen verglichen. Die höchste Ersparnis gegenüber der schlechtesten Zufallssortierung
beträgt bis zu 16%. Im Beispiel muss der Bahnhof mit den meisten Aufträgen 179 Kisten bearbeiten. Dies entspräche bei einer perfekt parallelen
Abarbeitung einer Bearbeitungszeit von 179 * (Bearbeitungszeit\Bahnhof).
Eine perfekte parallele Abarbeitung ist jedoch nicht möglich, da sich eine
Kiste immer nur an genau einem Bahnhof befinden kann.
Der vorsortierte Algorithmus kommt auf 49 Zeitschritte. Dies entspricht bei
einer Kapazität von 6 Kisten am Bahnhof einer Gesamtdauer von 294 * (Bearbeitungszeit\Bahnhof). Im Beispiel bräuchte der optimierte Algorithmus
also nur 1,64 mal länger, als der unerreichbare Idealzustand.
Ein weiterer Vorteil des optimierten Algorithmus ist, dass die Vorsortierung
einen geringen Zeitaufwand benötigt. Für eine Liste von 10.000 Aufträgen,
die auf einer Anlage mit 70 Bahnhöfen jeweils zwischen 1 und 30 Bahnhöfe
anfahren müssen, benötigt die Vorsortierung auf einem handelsüblichen Rechner weniger als 100ms.
8
5
Modellierung des Lagers mit Petri-Netzen
Bei dem Rossmann-Problem konkurrieren die Kisten mit den Aufträgen um
die jeweiligen Betriebsmittel im Lager. Diese sind die Förderstrecke und
die Bahnhöfe. Zur Modellierung von Ressourcenkonflikten werden in der
Informatik häufig Petri-Netze verwendet. Ein Petri-Netz ist ein gerichteter
bipartiter Graph mit zwei Knotentypen. Dies sind Plätze und Transitionen.
Bipartite Graphen zeichnen sich dadurch aus, dass nur Kanten zwischen unterschiedlichen Knoten erlaubt sind. In einem Petri-Netz können also nur
Kanten zwischen Plätzen und Transitionen vorkommen. Da ein Petri-Netz
ein gerichteter Graph ist, ist die Navigationsrichtung an den einzelnen Kanten vorgegeben. Um nun die Dynamik eines modellierten Systems darzustellen, kommt noch ein weiteres Element hinzu. Dabei handelt es sich um
Marken. Ein Platz kann eine Menge von Marken enthalten. Die Transition enthält dann eine Schaltvorschrift, die bestimmt nach welchen Regeln
sich die Marken zwischen den Plätzen bewegen. In der einfachsten Art von
Petri-Netzen kann eine Transition schalten, wenn sich in jedem Platz vor
der Transition mindestens eine Marke befindet. Dann wird aus jedem dieser
Plätze eine Marke entnommen und zu jedem Platz hinter der Transition eine Marke hinzugefügt. Zur Modellierung des Petri-Netzes wird die Software
CPN Tools der Universität Eindhoven verwendet.
5.1
Einführendes Beispiel
In Abbildung 6 ist ein einfaches Beispiel für ein Petri-Netz gegeben. Die
Abbildung 6: Einfaches Petri-Netz
grünen Kreise symbolisieren hierbei die Marken. Im oberen Teil der Abbildung ist das Petri-Netz vor dem Schaltvorgang gezeigt. Die Transition kann
9
schalten, da sich in jedem Platz vor der Transition mindestens eine Marke
befindet. Hier enthält Platz 1 genau eine Marke. Das Petri-Netz nach dem
Schaltvorgang ist im unterem Teil der Abbildung dargestellt. Es wurde also
die Marke aus Platz 1 entnommen und zu Platz 2 hinzugefügt. Im vorgestellten Beispielnetz ist nun keine Transition mehr aktiv. In diesem Fall spricht
man von einem terminierenden Netz.
5.2
Mathematische Definition
Ein elementares Petri-Netz (PN) wird als Quintupel dargestellt.
P N = (P, T, F, W, m0 )
(3)
Dabei bezeichnet P die Menge der Plätze und T die Menge der Transitionen.
F ist die Flussrelation, die die Kanten zwischen den Plätzen und Transitionen angibt.
F ⊆ (P × T ) ∪ (T × P )
(4)
Des Weiteren bezeichnet W die Kantengewichtungsfunktion, die jeder Kante
ein Gewicht zuordnet. Das Kantengewicht gibt dabei an, wieviele Marken
über diese Kanten fließen müssen.
W :F →N
(5)
Das letzte Element des Quintupels ist die Anfangsmarkierung m0 , die jedem
Platz eine Anzahl von Marken zuordnet.
m0 : P → N0
5.3
(6)
Coloured Petri Nets
Elementare Petri-Netze eignen sich nur bedingt für die Modellierung des
Rossmann Lagers. Mit den bisher vorgestellten Elementen kann bereits die
Dynamik eines Systems erfasst werden. Jedoch sind alle Marken ununterscheidbar. Da die Marken aber die einzelnen Kisten symbolisieren sollen,
muss eine Unterscheidung möglich sein.
Dafür eignen sich Coloured Petri Nets (CPN). Hierbei kommt der Aspekt
der Farbe hinzu. Es können sogenannte Colour Sets definiert werden. Dies
sind Mengen, die den Marken, Plätzen und Kanten eine Menge von Farben
zuordnet. So kann beispielweise ein Colour Set vom Typ Integer definiert
werden. Dann kann jeder Marke aus diesem Colour Set ein Integer-Wert
zugeordnet werden. Am folgenden Beispiel aus Abbildung 7 lässt sich die
Verwendung von Colour Sets nachvollziehen. Unter jedem Platz ist nun das
Colour Set für diesen Platz angegeben. Dies ist für alle Plätze INT“. Also
”
können die Plätze Marken vom Typ Integer aufnehmen. Die Kantenbeschriftung i“ ist eine Variable vom gleichen Typ. Dies bedeutet, dass über diese
”
10
Abbildung 7: Beispiel für ein CPN
Kanten beliebige Marken vom Typ Integer fließen dürfen. Anfangs befinden
sich im Platz Platz 1“ drei Marken. Eine Marke mit dem Wert 0, eine Mar”
ke mit dem Wert 1 und eine Marke mit dem Wert 2. Die Transition T1“
”
ist grün hinterlegt. Dies bedeutet, dass die Transition schalten kann. Dabei
wählt die Transition nun zufällig eine der drei Marken aus. Dies kann durch
Bedingungen an den Transitionen gesteuert werden.
In Abbildung 8 ist ein Beispiel hierfür gegeben. Im Platz Platz 1“ befinden
”
Abbildung 8: Einfacher Sortierer
sich die gleichen Marken wie im vorigen Beispiel. Nun möchten wir erreichen,
dass alle Marken mit einer geraden Zahl den Platz Platz 3“ ansteuern. Alle
”
ungeraden Marken sollen im Platz Platz 2“ gesammelt werden. Um dies zu
”
erreichen, wurden Bedingungen an die Transitionen geknüpft. Die Transition gerade“ kann nur schalten, wenn sich im Platz Platz 1“ mindestens
”
”
eine Marke befindet und weiterhin für diese Marke die Bedingung in den
eckigen Klammern erfüllt ist. Der Endzustand des Netzes ist in Abbildung
9 gezeigt.
Wie erwartet befinden sich nun alle Marken mit einer geraden Zahl im Platz
11
Abbildung 9: Sortierer nach dem Schalten
Platz 3“ und alle Marken mit einer ungeraden Zahl im Platz Platz 2“.
”
”
Mit der hier vorgestellten Methode kann nun der Weg der einzelnen Kisten
durch das Lager gesteuert werden.
5.4
Zeitbehaftete Petri-Netze
Ein weiterer Faktor, den elementare Petri-Netze nicht erfassen können, ist
die Zeit. Dafür eignen sich zeitbehaftete Petri-Netze. Dabei wird jeder Marke
ein Zeitstempel zugeordnet. Bisher konnte eine Transition schalten, sobald
sich in den Plätzen vor der Transition die entsprechende Anzahl an Marken
befand. In der zeitbehafteten Variante muss der Zeitstempel dieser Marken
zusätzlich noch kleiner oder gleich der Systemzeit sein. Bei einer Systemzeit von 2 sind also alle Marken mit den Zeitstempeln 0, 1 oder 2 aktiv.
Weiterhin können Transitionen diesen Zeitstempel manipulieren. In Abbildung 10 wird ein einfaches zeitbehaftetes Petri-Netz gezeigt. Das Colour Set
Abbildung 10: Zeitbehaftetes Petri-Netz
für die Plätze ist TIMED INT“. Dies ist ein Tupel aus einem Integer und
”
einem Zeitstempel. Die Kantenbeschriftung i“ symbolisiert eine Variable
”
vom gleichen Typ. Über diese Kanten kann also jeweils eine Marke fließen.
12
Zeitstempel werden mit einem @ hinter der Marke angegeben. Im Beispiel
enthält der Platz Start“ drei Marken mit dem Wert 1 und dem Zeitstempel
”
0.
Wenn die Transition In Bf“ schaltet, wird der Zeitstempel der Marke um
”
6 erhöht. Dies geschieht über die Beschriftung der ausgehenden Kante. Mit
dem Ausdruck i@+6“ wir der Zeitstempel der Marken, die über diese Kan”
te fließen manipuliert. Die nächste Abbildung zeigt das Netz nach einem
Schaltvorgang. Die Transition In Bf“ hat geschaltet. Im Platz Bahnhof“
”
”
Abbildung 11: Zeitbehaftetes Petri-Netz nach dem Schalten
befindet sich jetzt eine Marke mit dem Zeitstempel 6. Diese Marke wird also
erst zu einer Systemzeit von 6 aktiv. Damit beträgt die Verweilzeit für eine
Marke im Platz Bahnhof“ genau 6 Zeitschritte.
”
5.5
Modellierung des Rossmann Lagers
Mit Hilfe der in den vorigen Abschnitten vorgestellten Erweiterungen von
Petri-Netzen kann nun ein Modell des Lagers gebildet werden. In Abbildung
12 ist ein Modell eines Bahnhofs zu sehen. Die einzelnen Marken in den
Abbildung 12: Bahnhof
Plätzen mit dem Colour Set Auftrag sind Integer-Werte mit Zeitstempeln.
Die Variable auftrag“ ist vom selben Typ. Dabei wird jedem Bahnhof eine
”
Primzahl zugeordnet. Für den ersten Bahnhof ist dies die 2. Der Wert eines
Auftrags ist nun das Produkt der Primzahlen, die den jeweiligen Bahnhöfen
zugeordnet sind. Muss ein Auftrag den ersten Bahnhof besuchen, ist der
13
Wert des Auftrags durch zwei teilbar. Um die Kapazität eines Bahnhofs zu
modellieren, kommt der Platz Frei“hinzu. Für jede Marke, die vom Platz
”
P1“ über die Transition In Bf“ den Platz Bahnhof1“ ansteuern möchte,
”
”
”
muss eine Marke aus dem Platz Frei“ entnommen werden. Beim Verlassen
”
des Bahnhofs wird wieder eine Marke zum Platz Frei“ hinzugefügt. Damit
”
kann die Kapazität des Bahnhofs über die initiale Anzahl der Marken im
Platz Frei“ gesteuert werden. Um nun zu kennzeichnen, dass eine Marke
”
einen Bahnhof erfolgreich passiert hat, wird der Wert des Auftrags beim
Verlassen des Bahnhofs durch die jeweilige Primzahl geteilt.
Weiterhin müssen die Transitionen priorisiert werden. Wenn sich eine Marke im Platz P1“ befindet, soll zuerst überprüft werden, ob die Transition
”
In Bf“ schalten kann. Nur wenn dies nicht der Fall ist, soll die Transiti”
on Nicht in Bf“ schalten. Daher erhält die Transition In Bf“ eine höhere
”
”
Priorität als die Transition Nicht in Bf“. Ähnlich verhält es sich mit den
”
Transitionen Aus Bf“ und Nicht in Bf“. Aufträge sollen den Bahnhof nur
”
”
verlassen können, wenn kein Verkehr auf dem Nebengleis ist. Daher wird
die Transition Nicht in Bf“ gegenüber der Transition Aus Bf“ priorisiert
”
”
geschaltet. Die Priorität einer Transition entspricht dem Integer Wert an
der Transition. Schlussendlich sorgen die beiden Plätze Key“ dafür, dass
”
sich in den Plätzen P1“ und P2“ nur jeweils eine Marke befinden kann.
”
”
Die Kante mit dem kreisförmigen Ende ist eine sogenannte Inhibitorkante. Diese sorgt dafür, dass die entsprechende Transition nur schalten kann,
wenn sich im Platz von dem diesen Kante ausgeht, keine aktive Marke (mit
einem Zeitstempel kleiner oder gleich der Systemzeit) befindet. Mit den hier
vorgestellten Konzepten lässt sich nun ein Modell des Lagers bilden. Die
beigefügte CPN Datei enthält ein Modell des Rossmann Lagers mit vier
Bahnhöfen, einer Bearbeitungszeit am Bahnhof von vier Zeitschritten und
einer Kapazität am Bahnhof von vier Kisten.
5.6
Erkenntnisse aus dem Modell
Durch eine Untersuchung des Modells und die Betrachtung verschiedener
Einflüsse auf die Bearbeitungszeit können nun einige Schlüsse gezogen werden. Dabei spielt besonders die Bearbeitungszeit eine große Rolle. Zunächst
wurde dafür eine Reihenfolge ohne Rücksprünge, unter der Bedingung, dass
die Bearbeitungszeiten fest sind, gebildet. Wenn nun die Bearbeitungszeiten
an den Bahnhöfen variieren, kommt es zu einer sprunghaften Zunahme der
Rücksprünge. Dabei ist es unerheblich, ob die Bearbeitungszeit kürzer oder
länger ist, als angenommen. Dies verdeutlicht den großen Einfluss der Bearbeitungszeiten an den Bahnhöfen auf die Anzahl der Rücksprünge und die
Gesamtbearbeitungszeit.
Ein weiterer Aspekt, der bei der Betrachtung des Modells deutlich wird, ist,
dass sich Konflikte nicht unbedingt vermeiden lassen. An einem einfachen
Beispiel soll dies verdeutlicht werden. Dabei wird von einer Anlage mit 3
14
Bahnhöfen und einer Kapazität von 2 pro Bahnhof ausgegangen. Die zu
bearbeitenden Aufträge entsprechen der folgenden Liste.
A = {{1, 2, 3}, {1, 2, 3}, {2}, {2}}
(7)
Wenn diese Aufträge gemeinsam in die Anlage eingebracht werden, bearbeitet der erste Bahnhof zunächst die beiden Aufträge mit der Reihenfolge {1,
2, 3}. Gleichzeitig werden die Aufträge mit der Reihenfolge {2} parallel am
zweiten Bahnhof bearbeitet. Bei festen Bearbeitungszeiten führt dies nicht
zu Problemen. In der Zeitspanne, die der erste Bahnhof benötigt, um seine beiden Aufträge zu bearbeiten, hat der zweite Bahnhof seine Aufträge
bereits bearbeitet. Somit stehen dann wieder genug freie Kapazitäten am
zweiten Bahnhof zu Verfügung, um die Aufträge mit der Reihenfolge {1, 2,
3} zu bearbeiten.
Kommt es jedoch zu Verzögerungen am zweiten Bahnhof, stehen nach der
Bearbeitung der Aufträge am ersten Bahnhof nicht genügend freie Plätze am
zweiten Bahnhof zur Verfügung. Damit kommt es zu Rücksprüngen. Diese
potentiellen Verzögerungen treten jedoch erst nach dem Einbringen der Aufträge in die Anlage auf. Somit kann darauf nicht reagiert werden und die
Konflikte lassen sich nicht verhindern. Die Alternative dazu bestünde darin,
dass nie mehr Aufträge in die Anlage einbracht werden, als die Gesamtkapazität der Bahnhöfe zulässt. Dann könnten aber nur die beiden Aufträge
mit der Reihenfolge {1, 2, 3} gleichzeitig eingebracht werden. Erst danach
könnten die Aufträge mit der Reihenfolge {2} freigegeben werden. Da dies
aber einer sequentiellen Abarbeitung entspricht, ist dies in der Realität nicht
praktikabel. Somit gibt es Konflikte, auf die nicht reagiert werden kann. Eine
vollständige Verhinderung dieser Konflikte ist daher nicht möglich.
5.7
Bewertung des Modells
Nachdem in den vorigen Abschnitten ein Modell des Lagers vorgestellt wurde, wird dieses nun bewertet. Das Modell bildet einige Aspekte des Lagers
ab, vereinfacht jedoch an anderen Stellen. Zu den Faktoren, die im Modell enthalten sind, zählen unter anderem die Kapazitätsbedingung und die
Bearbeitungszeit an den Bahnhöfen. Dabei kann, statt einer festen Bearbeitungszeit, auch eine zufällige Auswahl der Bearbeitungszeit gewählt werden.
Hier stehen neben diskreten, gleich verteilten Wahrscheinlichkeitsverteilungen auch Gaußkurven oder Normalverteilungen zur Verfügung. Ein Faktor,
der von der Realität abweicht, ist, dass Kisten auf den Förderbändern zu
anderen Kisten aufschließen können. Dies bedeutet, dass, wenn sich auf einem Förderband ein Stau bildet, Kisten auf diesem Förderband aufrücken
können und damit gegebenenfalls Lücken geschlossen werden. Ein Vorteil der
Modellierung mittels Petri-Netzen liegt darin, dass Petri-Netze gut erforscht
sind und es sich dabei um ein anerkanntes mathematisches Modell handelt.
15
Damit steht auch eine Vielzahl an kommerzieller und nicht-kommerzieller
Software zur Verfügung, um Petri-Netze zu modellieren. Ein Nachteil von
Petri-Netzen und den damit erzeugten Modellen besteht in der Vielzahl der
Zusatzelemente, die benötigt werden, um die Kapazitätsbedingungen darzustellen. Dadurch werden große Netze schnell unübersichtlich. Weiterhin ist
eine Simulation des Lagers in Echtzeit ab einer relativ geringen Anzahl von
mehr als fünf Bahnhöfen nicht mehr möglich. Daher wäre damit zu rechnen,
dass eine Simulation des realen Lagers mit mehr als 40 Bahnhöfen nicht
praktibal ist.
Die Simulation mit Hilfe von Petri-Netzen eignet sich also nur bedingt zur
Modellierung des Lagers. Um jedoch ein Gefühl für die Dynamik des Systems
und eine Testumgebung für erste Ansätze zu erhalten, reichen Petri-Netze
aus.
16
6
Zusammenfassung
In dieser Projektarbeit wurden verschiedene Ansätze zur Lösung des Rossmann-Problems beleuchtet und ein Modell auf der Basis von Petri-Netzen
gebildet. Dabei hat sich herauskristallisiert, dass die Schwankung der Bearbeitungszeiten an den Bahnhöfen das Hauptproblem darstellt. Dieses lässt
sich nicht allein mit Hilfe von optimierten Algorithmen lösen. Der hier vorgestellte Greedy-Algorithmus bildet jedoch schon eine gute Basis für einen
Online-Algorithmus. Eine völlig konfliktfreie Abarbeitung lässt sich hingegen nicht ohne eine Einflussmöglichkeit auf die Bearbeitungszeiten erreichen.
Eine Möglichkeit, die Schwankungen in der Bearbeitungszeit zu minimieren,
bestünde beispielsweise in der Installation von Puffern im System. Wenn der
Mitarbeiter die bearbeiteten Kisten nicht selbstständig zurück auf die Anlage schiebt, sondern die Anlage selbst über den Zeitpunkt bestimmt, können
die Bearbeitungszeiten angeglichen werden. Dabei könnte am Bahnhof ein
Stapel für die bereits bearbeiteten Aufträge bereitstehen. Der Mitarbeiter
legt seine fertigen Aufträge dann auf diesem Stapel ab und die Anlage entscheidet selbstständig über den bestmöglichen Zeitpunkt, zu dem der Auftrag wieder in die Anlage eingebracht wird. Dadurch können Aufträge, die
schneller als erwartet bearbeitet wurden, die Verspätungen von Aufträgen,
die länger brauchen, auffangen.
Weiterhin hat sich gezeigt, dass sich etablierte Verfahren wie die Reihenfolgeplanung nicht ohne Weiteres auf das Rossmann-Problem übertragen
lassen. Jedoch bilden diese mit den richtigen Nebenbedingungen eine gute Grundlage, um Teilaspekte des Problems zu lösen. Grundsätzlich lässt
sich das Problem nicht einseitig lösen, sondern es muss an mehreren Stellen
angesetzt werden. Dies sind zum einen die Vorberechnung einer Reihenfolge unter der Bedingung, dass alle Bearbeitungszeiten fest und bekannt sind.
Andererseits müssen Konflikte erkannt werden und es muss eine Möglichkeit
bestehen, auf diese zu reagieren. Schlussendlich müssen die Schwankungen
der Bearbeitungszeiten, die sich um mehr als den Faktor 10 unterscheiden
können, minimiert werden.
Der Greedy-Algorithmus löst bereits das erste Teilproblem. Da dieser Algorithmus über die Belegungsmatrix parametrisiert wird, kann auch eine
Reihenfolge für eine nicht leere Anlage gebildet werden. Somit könnte in
bestimmten Intervallen immer wieder eine neue Belegungsmatrix auf Basis
des Systemzustands gebildet werden. Der Greedy-Algorithmus könnte dann,
für die noch nicht in die Anlage eingebrachten Aufträge, auf Grundlage der
aktuellen Belegungsmatrix eine vorteilhafte Reihenfolge berechnen. Dabei
können neben den Bahnhöfen auch weitere Ressourcen, wie beispielsweise
Zwischenstrecken und Schleifen, in die Belegungsmatrix aufgenommen werden. Wenn nun noch Puffer in das System integriert würden, bestünde eine
weitere Möglichkeit, auf potentielle Verspätungen und Staus zu reagieren.
Obwohl sich Konflikte und Staus nicht grundsätzlich vermeiden lassen, lässt
17
sich feststellen, dass zwar noch einiger Entwicklungsaufwand besteht, die
hier vorgestellten Ansätze jedoch schon eine gute Grundlage und einen ersten Schritt hin zu einer besseren Lösung bilden.
18
Abbildungsverzeichnis
1
2
3
4
5
6
7
8
9
10
11
12
Prioritätsregeln . . . . . . . . . . .
Beispielmatrix . . . . . . . . . . . .
Belegungsmatrix . . . . . . . . . .
Auftragsreihenfolge . . . . . . . . .
Auftragsreihenfolge sortiert . . . .
Einfaches Petri-Netz . . . . . . . .
Beispiel für ein CPN . . . . . . . .
Einfacher Sortierer . . . . . . . . .
Sortierer nach dem Schalten . . . .
Zeitbehaftetes Petri-Netz . . . . .
Zeitbehaftetes Petri-Netz nach dem
Bahnhof . . . . . . . . . . . . . . .
19
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Schalten
. . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
6
7
7
7
9
11
11
12
12
13
13

Download Report