Verfahren und Vorrichtung zur rechnergestützten Optimierung einer Belegung von Magazinplätzen mit Werkzeugen innerhalb mindestens eines Werkzeugmagazins für eine Werkzeugmaschine

Die Erfindung betrifft ein Verfahren und eine Vorrichtung Verfahren zur rechnergestützten Optimierung einer Belegung von Magazinplätzen mit Werkzeugen innerhalb mindestens eines Werkzeugmagazins für eine Werkzeugmaschine.

Eine Werkzeugmaschine ist eine automatisierte Fertigungsein ^¬ richtung mit der eine vorgegebene Form an einem Werkstück mittels eines oder mehrerer Werkzeuge erzeugt wird. Mehrere Werkzeuge können einem Werkzeugtyp z.B. Fräsen zugeordnet sein. Ein anderer Werkzeugtyp kann z.B. Bohren sein. Eine Werkzeugmaschine besitzt eine Werkzeugspindel, in der sich das bearbeitende Werkzeug, auch Spindelwerkzeug genannt, bei der Bearbeitung befindet.

Die Werkzeuge, die von der Werkzeugmaschine zur Bearbeitung eines Werkstücks verwendet werden können, sind in einem Werk ^¬ zeugmagazin abgelegt. Davon gibt es verschiedene Arten. Eine sehr häufig verwendete Form sind Kettenmagazine, die z.B. in der Automobilindustrie zum Einsatz kommen.

Eine weitere Magazinart sind Regalmagazine R, wie es bei ^¬ spielsweise in Figur 1 angedeutet ist, in denen sehr viele verschiedene Werkzeuge untergebracht werden können (bis zu 500 Werkzeuge oder sogar eventuell noch mehr) . Die Werkzeuge sind darin auf festen Magazinplätzen P abgelegt. Ein solches Magazin kann aus einer Hauptseite und einer gegenüberliegenden Gegenseite bestehen. Das Regalmagazin besitzt eine Vorrichtung insbesondere ein Magazingerät, das in der Figur 1 nicht dargestellt ist, mit der ein Werkzeug auf seinem Magazinplatz P abgelegt und ge ^¬ holt werden kann. Diese Magazinart wird vor allem dann ver- wendet, wenn eine größere Vielfalt von unterschiedlichen Werkstücken, für die eine Vielzahl an unterschiedlichen Werkzeugen benötigt wird, mit einer Werkzeugmaschine produziert werden soll.

Die Bearbeitung eines Werkstücks eines bestimmten Werkstücktyps erfolgt mit einer vorgegebenen Sequenz von Werkzeugen. Ein Werkzeug kann dabei durchaus mehrmals in dieser Sequenz vorkommen. Die Sequenz ist für alle Werkstücke eines Werk- Stücktyps z.B. Autositz die gleiche. Die Sequenz kann für Werkstücke eines anderen Werkstücktyps eine andere sein.

Während eines Arbeitsschritts der Bearbeitung eines Werk ^¬ stücks mit einem Werkzeug der Sequenz, dem Spindelwerkzeug, wird im Regalmagazin das „Vorgängerwerkzeug" des vorhergehen ^¬ den Arbeitsschritts auf seinen Magazinplatz zurückgefahren bzw. zurückgelegt. Anschließend erfolgt eine Leerfahrt zum Magazinplatz des „Nachfolgerwerkzeugs" des nachfolgenden Arbeitsschrittes. Dieses wird dann aufgenommen und zu einem Be- reitstellungsplatz transportiert. Ist der aktuelle Arbeits ^¬ schritt, d.h. die Bearbeitung mit dem aktuellen Spindelwerkzeug beendet, so erfolgt ein Austausch des Werkzeugs in der Spindel (z.B. mit einem Werkzeugwechsler). Falls die Bearbeitung mit dem Spindelwerkzeug beendet ist, aber das Nachfol- gerwerkzeug für den folgenden Arbeitsschritt noch nicht be ^¬ reit steht, entsteht eine Wartezeit bei der Spindelversor ^¬ gung. Diese einzelnen Wartezeiten reduzieren die Maschinen- Effizienz und erhöhen die Produktionsdauer. Deshalb sollen diese Wartezeiten vermieden werden.

Bei der Minimierung der Wartezeiten bei der Spindelversorgung während der Produktion einer vorgegebenen bzw. vorgebbaren Menge von Werkstücken eines oder mehrerer Werkstücktypen sind folgenden Restriktionen zu beachten:

Ein Werkzeug darf gewöhnlich nicht an jeden Magazinplatz gestellt werden, d.h. es gibt für das Werkzeug zulässige Maga ^¬ zinplätze und unzulässige Magazinplätze: Der Magazinplatztyp des Werkzeugs und der Magazinplatz ^¬ typ des Magazin bzw. Regalplatzes müssen kompatibel sein. So dürfen z.B. große Werkzeuge nicht auf Magazin ^¬ plätze für kleine Werkzeuge gestellt werden und ggf. um- gekehrt .

Werkzeuge dürfen am Rand nicht überragen.

Auf gesperrten Magazinplätzen dürfen keine

Werkzeuge stehen.

Sind Werkzeuge übergroß, so müssen ein oder eventuell sogar mehrere benachbarte Magazinplätze frei gelassen werden .

Die Ausgangssituation ist gewöhnlich ein mit Werkzeugen gefülltes (eventuell auch sehr volles) Regalmagazin. Um die oben genannten Restriktionen beachten zu können, erfolgt eine Umlagerung der Werkzeuge im Regalmagazin. Diese kann nicht hauptzeitparallel (d.h. bei laufender Produktion) durchge ^¬ führt werden und bringt somit eine Stillstandzeit der Werk ^¬ zeugmaschine mit sich. Es ist in diesem Kontext sinnvoll, möglichst viele Werkzeuge wieder auf den alten Magazinplatz zu zuweisen.

Es ist Aufgabe der vorliegenden Erfindung, die Maschineneffi ^¬ zienz und dabei insbesondere die oben genannten Wartezeiten zu optimieren.

Diese Aufgabe wird durch die unabhängigen Ansprüche gelöst. Vorteilhafte Weiterbildungen sind Gegenstand der abhängigen Ansprüche .

Die Erfindung beansprucht ein Verfahren zur rechnergestützten Optimierung einer Belegung von Magazinplätzen mit Werkzeugen innerhalb mindestens eines Werkzeugmagazins für eine Werk ^¬ zeugmaschine, wobei ein oder mehrere Werkstücke eines Werk ^¬ stücktyps mit Hilfe der von einem Magazingerät an einem Be ^¬ reitstellungsplatz bereitgestellten Werkzeug gefertigt werden, aufweisend folgende Schritte: Erfassen einer Menge von Magazinplätzen in mindestens einem Werkzeugmagazin,

Erfassen einer Menge von Werkzeugen,

Erfassen von zulässigen Werkzeugen pro Magazinplatz, Erfassen einer Sequenz von der Werkzeugmaschine durchzuführender Arbeitsschritte an einem Werkstück, wobei ein für einen Arbeitsschritt der Sequenz vorgesehenes Werk ^¬ zeug zur Fertigung des Werkstücks verwendet wird,

Erfassen von Arbeitsschritt-Zeitdauern, die jeweils zur Durchführung eines einzelnen Arbeitsschritts an dem Werkstück gebraucht wird,

Erfassen einer oder mehrerer Bereitstellungszeitdauern abhängig von der Sequenz der durchzuführenden Arbeits schritte und der Belegung der Magazinplätze, welche je weils für die Bereitstellung eines Werkzeugs für den folgenden Arbeitsschritt vom Magazingerät am Bereitstel lungsplatz gebraucht wird,

Optimierung der Belegung der Magazinplätze mit Werkzeu gen, so dass die gesamte Wartezeit minimiert wird, wobei sich die gesamte Wartezeit zusammensetzt aus einzelnen Wartezeiten, die sich jeweils aus der Differenz zwischen der erfassten Bereitstellungsdauer und der erfassten Ar beitsschritt-Zeitdauer ergeben, wenn der Wert der Diffe renz positiv ist, andernfalls die einzelne Wartezeit den Wert Null annimmt.

Die Bereitstellungdauer kann sich aus einer Hol-Zeitdauer, die die Zeitdauer für das Holen eines Werkzeugs durch das Ma ^¬ gazingerät zum Bereitstellungsplatz von je einem für das Werkzeug zulässigen Magazinplatz umfasst, und aus einer

Zurückleg-Zeitdauer, die die Zeitdauer für das Zurücklegen eines Werkzeugs durch das Magazingerät vom Bereitstellungs ^¬ platz zu je einem für das Werkzeug zulässigen Magazinplatz umfasst, und aus einer Leerfahrt-Zeitdauer für eine Leerfahrt des Magazingeräts von einem ersten Magazinplatz zu einem anderen zweiten Magazinplatz zusammensetzen. Wenn die der folgende Arbeitsschritt der erste Arbeitsschritt in der Sequenz der Arbeitsschritte ist, dann gibt es keine Zurückleg-Zeitdauer, d.h. sie beträgt Null, und keine Leerfahrt, d.h. die Leerfahrt-Zeitdauer beträgt Null.

Es können alle Magazinplatzpaar-Kombinationen von ersten und zweiten Magazinplätzen berücksichtigt werden. Die Anzahl der Magazinplatzpaar-Kombinationen kann gegebenenfalls dadurch reduziert werden, dass diese in Abhängigkeit der zu verwen- denden Werkzeuge nach der Reihenfolge der Arbeitsschritte in ^¬ nerhalb der Sequenz berücksichtigt werden.

Zudem kann eine Menge von Werkstücktypen und Stückzahlen der zu fertigenden Werkstücke jedes Werkstücktyps der Menge er- fasst und diese bei der Optimierung der Belegung der Magazinplätze mit Werkzeugen berücksichtigt werden.

Die genannte Optimierung kann mittels gemischt ganzzahlig linearer Optimierung oder mittels einer heuristischen ganzzah- ligen linearen Optimierung durchgeführt werden, die jeweils in den nachstehenden Ausführungsbeispielen näher erläutert werden .

Eine Weiterbildung der Erfindung sieht weitere Schritte vor:

- Erfassen einer Menge aller Halbplätze,

- Erfassen einer Untermenge von Halbplätzen, die überdeckt werden, wenn jeweils ein Werkzeug auf je einen Magazinplatz liegt, wobei diese Mengen bei der Optimierung der Belegung berücksichtigt werden mit dem Zweck, dass kein Halbplatz von mehreren Werkzeugen überdeckt wird.

Ein Magazinplatz kann ein oder mehrere Halbplätze umfassen. Diese können links, rechts oder oben, unten sich befinden. Dies sind Stellen am jeweiligen Magazinplatz, die durch andere Werkzeuge an benachbarten Magazinplätzen überdeckt werden können . Eine Weiterbildung der Erfindung sieht vor, dass die Optimierung der Belegung der Magazinplätze mit Werkzeugen derart durchgeführt wird, dass die Anzahl der Magazinplätze, die von anderen Werkzeugen als den Werkzeugen vor der Optimierung be- legt werden, möglichst gering ist.

Eine Weiterbildung der Erfindung sieht vor, dass eine Menge von Magazinplätzen erfasst wird, die jeweils mit einem Werkzeug fest belegt sind, welche die Optimierung nicht mit ande- ren Werkzeugen belegt werden dürfen.

Eine Weiterbildung der Erfindung sieht vor, dass die Optimierung der Belegung der Magazinplätze mit Werkzeugen derart durchgeführt wird, dass die Werkzeuge, für die die genannte Wartezeit den Wert Null annimmt, auf Magazinplätze nahe des Bereitstellungsplatzes platziert werden.

Die Erfindung bringt folgende Vorteile mit sich:

Die Optimierung bringt kürzere Verfahrwege des Magazingeräts eines Regalmagazins mit sich, das letztendlich auch zur Energieeinsparung und längerer Haltbarkeit führt. Es gehen damit auch kürzere Produktionszeiten der Werkzeugmaschinen einher.

Ein weiterer Aspekt der Erfindung sieht eine Steuerungsein- richtung vor, die insbesondere zur Durchführung des Verfahrens nach oben genannter Art und dessen Ausführungsformen ausgebildet ist. Die Steuereinrichtung (nicht in Figur 1 ge ^¬ zeigt) kann ein der Werkzeugmaschine beigeordneter und ggf. abgesetzt angeordneter Rechner oder in die Werkzeugmaschine integriertes Steuerungsmodul sein.

Die Steuerungseinrichtung zur rechnergestützten Optimierung einer Belegung von Magazinplätzen mit Werkzeugen innerhalb mindestens eines Werkzeugmagazins für eine Werkzeugmaschine, wobei ein oder mehrere Werkstücke eines Werkstücktyps mit Hilfe der von einem Magazingerät an einem Bereitstellungs ^¬ platz bereitgestellten Werkzeuge gefertigt werden, aufweisend : a) Mittel zum Erfassen einer Menge von Magazinplätzen in mindestens einem Werkzeugmagazin,

b) Mittel zum Erfassen einer Menge von Werkzeugen, c) Mittel zum Erfassen von zulässigen Werkzeugen pro Magazinplatz,

d) Mittel zum Erfassen einer Sequenz von der Werkzeugmaschine durchzuführender Arbeitsschritte an einem Werkstück, wobei ein für einen Arbeitsschritt der Sequenz vorgesehenes Werkzeug zur Fertigung des Werkstücks verwendet werden kann,

e) Mittel zum Erfassen von Arbeitsschritt-Zeitdauern, die jeweils zur Durchführung eines einzelnen Arbeitsschritts an dem Werkstück gebraucht wird,

f) Mittel zum Erfassen einer oder mehrerer Bereitstellungszeitdauern abhängig von der Sequenz der durchzuführenden Arbeitsschritte und der Belegung der Maga ^¬ zinplätze, welche jeweils für die Bereitstellung eines Werkzeugs für den folgenden Arbeitsschritt vom Maga- zingerät am Bereitstellungsplatz gebraucht wird, und g) Mittel zur Optimierung der Belegung der Magazinplätze mit Werkzeugen, so dass im Ergebnis der Optimierung die gesamte Wartezeit minimiert ist, wobei sich die gesamte Wartezeit zusammensetzt aus einzelnen Warte- zeiten, die sich jeweils aus der Differenz zwischen der erfassten Bereitstellungsdauer und der erfassten Arbeitsschritt-Zeitdauer ergeben, wenn der Wert der Differenz positiv ist, andernfalls die einzelne Warte ^¬ zeit den Wert Null annimmt.

Ein weiterer Aspekt der Erfindung ist ein Computerprogramm ( - produkt) mit Programmcodemitteln zur Durchführung des Verfahrens nach einem der vorangehenden Verfahrensansprüche, wenn es auf einer Steuerungseinrichtung der oben genannten Art ab- läuft oder auf einem computerlesbaren Medium gespeichert ist.

Das Computerprogramm bzw. -produkt kann auf einem computerlesbaren Medium gespeichert sein. Das Computerprogramm bzw. - produkt kann in einer üblichen Programmiersprache (z.B. C++, Java) erstellt sein. Die Verarbeitungseinrichtung kann einen marktüblichen Computer oder Server mit entsprechenden Eingabe-, Ausgabe- und Speichermitteln umfassen. Diese Verarbei- tungseinrichtung kann in der Steuerungseinrichtung oder in deren Mitteln integriert sein.

Die Steuerungseinrichtung sowie das Computerprogramm ( - produkt) können analog zum oben genannten Verfahren weiter- bzw. ausgebildet sein.

Weitere Vorteile, Einzelheiten und Weiterbildungen der Erfindung ergeben sich aus der nachfolgenden Beschreibung von Ausführungsbeispielen in Verbindung mit den Zeichnungen.

Es zeigen:

Fig. 1 die eingangs erwähnten Plätze in einem Regalmagazin, wobei die Hauptseite rechts und die Gegenseite links angeord- net sind,

Fig. 2 schematisch ein Ablaufdiagram zum iterativen Verfahren mit einer Startkonfiguration, bei dem das heuristische ganzzahlige lineare Optimierungsverfahren angewandt wird,

Fig. 3, 4 und 5 eine Ausgangsbelegung und optimierte Belegung mit dem gemischt ganzzahlig linearer Optimierungsverfahren.

Ein Spezialfall von Optimierungsmethoden ist die lineare Op- timierung. Sie befasst sich mit der Optimierung linearer

Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Sie ist Grundlage der Lösungsverfahren der (gemischt-) ganzzahligen linearen Optimierung. Ein sogenannter Solver (Löser) ist eine Sammel- bezeichnung für spezielle mathematische Computerprogramme, die mathematische Probleme numerisch lösen können. Im Zusammenhang mit MILP (mixed integer linear programming bzw. gemischt ganzzahlige lineare Programmierung) können für IP- Programme (ganzzahlige Optimierungsmodelle) Standardsolver wie z.B. CPLEX, Scip, Gurobi, Xpress verwendet werden.

Im Folgenden wird ein Beispiel beschrieben, in dem mittels eines MILP-Modell (Mixed Integer Linear Programming) eine rechnergestützte Optimierung einer Belegung von Magazinplät ^¬ zen mit Werkzeugen innerhalb mindestens eines Werkzeugmaga ^¬ zins für eine Werkzeugmaschine, wobei ein oder mehrere Werk ^¬ stücke eines Werkstücktyps mittels einer Belegung der Maga ^¬ zinplätze mit Werkzeugen gefertigt werden können.

In der MILP-Formulierung gelten die folgenden Bezeichnungen:

Indices :

L Menge aller Magazinplätze

T Menge der Werkzeuge

HP Menge aller Halbplätze

P _l,t Menge der Halbplätze, die überdeckt werden, wenn Werkzeug t auf Magazinplatz 1 liegt

W Menge der Werkstücktypen

Op w Sequenz von der Werkzeugmaschine durchzuführender Arbeitsschritte (oder Operationen) bei Werkstücktyp w

Menge der für Magazinplatz 1 zulässigen

Werkzeuge

Parameter : quantity _w Zu fertigende Stückzahl von Werkstücktyp w Werkzeug in

prodTime ⁱ w Dauer von

putTime _{t, l} Zeitdauer für das Zurückbringen bzw. Zurücklegen von Werkzeug t vom Bereitstellungsplatz zum Magazinplatz 1 getTime _{t, l} Zeitdauer für das Holen von Werkzeug t vom Ma ^¬ gazinplatz 1 zum Bereitstellungsplatz

moveTimei,i- Zeitdauer für die Leerfahrt vom Magazinplatz 1 zum Magazinplatz 1'

moveTime _l Zeitdauer für die Leerfahrt vom Bereitstel ^¬ lungsplatz zum Magazinplatz 1

Variablen : setup _{t, l} Zuordnung bzw. Zuweisung von Werkzeug t

zu Magazinplatz 1

(In diesem Fall nimmt sie den Wert 1 an, anderenfalls den Wert 0)

covers _t,h Werkzeug t überdeckt den Halbplatz h

(In diesem Fall nimmt sie den Wert 1 an, ande ^¬ renfalls den Wert 0) waitingTime^ (einzelne) Wartezeit, die bei der Fertigung eines Werkstücks von Werkstücktyp w nach Ope- ration i entsteht

QIP-Formulierung (Quadratische IP-Formulierung) :

Minimierungszielfunktion :

Nebenbedingungen :

(1) Jedes Werkzeug muss auf einem Magazinplatz liegen.

(2) Auf einem Magazinplatz darf höchstens ein Werkzeug liegen .

(3) Auf einem Magazinplatz darf kein für diesen Magazinplatz unzulässiges Werkzeug liegen.

(4) Ein Halbplatz darf höchstens von einem Werkzeug überdeckt werden .

(5) Liegt ein Werkzeug auf einem Platz, so überdeckt

entsprechenden Halbplätze

(6) Es entsteht eine Wartezeit, wenn die Operation kür ^¬

zer ist, als die Zeitdauer, die das Magazin für das Zurückle gen des vorherigen Werkzeugs, welches für die vorhergehende Operation verwendet wird, die Zwischen- bzw. Leerfahrt zum nächsten Werkzeug und das Holen des nächsten Werkzeugs, wel ^¬ ches für die nachfolgende Operation, benötigt.

Es entsteht eine Wartezeit nach der ersten Operation, wenn die Leerfahrt vom Bereitstellungsplatz zum Magazinplatz des Werkzeugs für die folgende zweite Operation länger als die erste Operation dauert.

(7) Variablenrestriktionen,

MILP-Reformulierung :

Da das Testproblem mit 250 Plätzen, 60 Werkzeugen und 20 Operationen mit der QIP-Formulierung nicht lösbar ist. Deshalb wird das QIP als MILP formuliert:

Zusätzliche Variablen: Hilfsvariable, die den Wert 1 annimmt, falls auf Platz 1 und auf Magazinplatz l' liegen und damit eine leere Zwischenfahrt von 1 nach l' erforderlich ist.

Geänderte Restriktionen:

Die Restriktionen (6) werden durch die Restriktionen (9) ersetzt .

(8) Befinden sich die Werkzeuge auf Magazinplatz 1 und auf Magazinplatz 1', dann ist

(9) Falls erfolgt eine leere Zwischenfahrt von 1

nach 1 ' .

Befinden sich das Werkzeuge nicht auf Magazinplatz 1 oder nicht auf Magazinplatz 1', so sorgt die Minimie-

rungszielfunktion dafür, dass gilt.

Performanz-Maßnahmen :

Um die Laufzeit, auch Performanz genannt, zu senken, sind die folgenden weiteren Performanz-Maßnahmen sinnvoll.

Betrachtung ausschließlich kritischer Operationen: Die maximale Zeitdauer eines Zyklus (Zurückbringen bzw. Zurücklegen, Zwischenfahrt und (Ab) holen) lässt sich berechnen. Man kann sich in (9) deshalb nur auf die Operationen beschränken, die eine kleinere Produktionszeit als die maximale Zyklusdauer aufweisen. Diese Operationen werden als kritisch bezeichnet. Als kritische Werkzeuge werden diejenigen Werk ^¬ zeuge bezeichnet, die während kritischer Operationen im Re ^¬ galmagazin zurückgebracht oder geholt werden müssen. Einschränkung des Lösungsraums:

In Abhängigkeit der Anzahl kritischer Werkzeuge lässt sich der Lösungsraum für die möglichen Magazinplätze der kritischen Werkzeuge einschränken, da die Dauer für das Zurück- bringen und das Holen der Werkzeuge mit größerem Abstand zum Bereitstellungsplatz zunimmt.

Die Fahrtdauern zur Gegenseite des Regalmagazins sind extrem lang. Sind nur wenige Werkzeuge kritisch, so kann z.B. auf die komplette Gegenseite als potentielle Magazinplätze für die kritischen Werkzeuge verzichtet werden.

Zusätzliche Restriktionen (Cuts) :

Lower Bounds (untere Schranken) : Es lassen sich minimale Zyklenzeiten ermitteln, die abzüglich der Produktionszeit eine untere Schranke für die Wartezeit liefern .

Erweiterungen :

Durch eine Zielfunktion, die sich aus mehreren gewichteten Komponenten zusammensetzt, lassen sich weitere Zielkriterien mit optimieren. Demnach wird eine Start- Werkzeugmagazinplatzbelegung erfasst und die Maximierung der Anzahl der übereinstimmenden Belegungen der Start-Belegung und der optimierten Belegung gilt als zweites weniger hoch gewichtetes Zielkriterium. Das Hauptkriterium bleibt die Mi- nimierung der Wartezeit.

Bevorzugung alter Magazinplätze:

Die von der Optimierung berechnete neue Belegung der Magazin- platze mit Werkzeugen muss physikalisch in der Werkzeugmaschine durch Umrüstungen erzeugt werden. In dieser Zeit steht die Werkzeugmaschine voraussichtlich still. Es ist deshalb günstig, wenn ein Werkzeuge t durch die Optimierung möglichst auf dem alten Magazinplatz landet und deshalb die Anzahl

solcher Werkzeuge maximiert wird:

Umplatzierte Werkzeuge nahe am Bereitstellungsplatz ablegen: Zusätzlich kann es aus optischen Gründen und auch aus Performance-Gründen sinnvoll sein, wenn mit einer sehr niedrigen Gewichtung die umplatzierten, nicht kritischen, Werkzeuge nahe am Bereitstellungsplatz landen und deshalb die Summe der zeitlichen Abstände der Werkzeuge zum Bereitstellungsplatz minimiert wird.

Festgerüstete Werkzeuge:

Für eine Menge FixedSetups von Paaren mit und l _t

wird gesetzt:

MILP-Heuristik: Für große Probleminstanzen ist die Performanz nicht ausreichend und es wird dafür folgende auf MILP basierende Heuris ^¬ tik zur Minimierung der Wartezeiten für einen Werkstücktypen vorgeschlagen : Für eine Menge FixedSetup von Werkzeug-Magazinplatz-Paaren und eine Menge OpSubset von Operationen (w,i) sei

MILP (FixedSetup, OpSubset) das MILP (siehe oben) mit zusätz ^¬ lich festgerüsteten Werkzeugen gemäß der Menge FixedSetup und einer Einschränkung der Restriktion (9) auf die Operationen der Menge OpSubset, d.h. nur die Wartezeiten der Operationen aus OpSubset werden minimiert.

Gemäß Figur 2 wird iterativ wie folgt vorgegangen:

Nach Schritt Sl (Start) wird von einer Sequenz bzw. Liste (Set) von Operationen bzw. Arbeitsschritten (ListOp) aufsteigend sortiert nach der Produktionszeit ausgegangen, wobei ListOp alle Arbeitsschritte umfasst, die zur Herstellung des Werkstücktyps notwendig sind, außer dem ersten und letzten Arbeitsschritt (die Reihenfolge der Arbeitsschritte dieser sortierten Liste entspricht gewöhnlich nicht mehr der Reihenfolge der Arbeitsschritte innerhalb der Sequenz, so wie sie mit der Werkzeugmaschine abgearbeitet werden.) Eine Menge mit festgerüsteten Werkzeugen und jeweils dazugehörigen Magazinplätzen (FixedSetup) beginnt mit einer leeren Menge. In

Schritt S2 wird die erste Operation opl bzw. durchzuführender Arbeitsschritt aus der Liste ListOP ausgewählt (Operation mit kürzester Bearbeitungsdauer) . Für die erste Operation opl gibt es ein Vorgänger- und Nachfolge-Werkzeugpaar (tp, ts) , wobei tp im vorhergehenden Arbeitschritt und ts im nachfol ^¬ genden Arbeitsschritt verwendet wird.

Gemäß Schritt S3 umfasst die Menge OpSubset alle Operationen, deren Vorgänger- und Nachfolgewerkzeuge bereits fest gerüstet sind oder gleich den oben genannten tp bzw. ts sind. In

Schritt S4 wird eine Optimierung mit einer MILP-Formulierung MILP (FixedSetup, OpSubset) durchgeführt. In Schritt S5 wird Operation opl aus der Liste ListOP entfernt. Die Werkzeuge tp, ts werden mit den aus der Optimierung resultierenden und zugewiesenen sowie zulässigen Magazinplätzen in die Menge FixedSetup aufgenommen, wobei FixedSetup jeweils Paare aus einem Werkzeug und dem zugehörigen Magazinplatz umfasst. Somit drückt FixedSetup die Belegung der Magazinplätze mit Werkzeugen aus. Nach Erfüllung der Bedingung B wird das Verfahren beendet, das mit E gekennzeichnet ist. Die Werkzeug- Magazinplatz-Zuordnung der MILP-Lösung dieser Iteration stellt dann die Lösung der Heuristik dar. Ansonsten wird es mit Schritt 2 fortgesetzt bzw. wiederholt. Die Bedingung ist erfüllt, wenn ListOP leer ist. Letztendlich soll sich eine optimierte Belegung aus dieser MILP-Heuristik ergeben, die letztendlich zu einer Minimierung der eingangs beschriebenen gesamten Wartezeit führt. Eine einzelne Wartezeit nach einem Arbeitsschritt wird durch den positiven Wert der Differenz zwischen der Zurückleg-Zeitdauer für das Zurücklegen des für den vorhergehenden Arbeitsschritt vorgesehenen Werkzeugs tp, der Leerfahrt-Zeitdauer der Leerfahrt des Magazingeräts vom Magazinplatz des für den vorhergehenden Arbeitsschritt vorgesehenen Werkzeugs ts zum Magazinplatz des für den nachfolgen- den Arbeitsschritt vorgesehenen Werkzeugs tp sowie der Hol- Zeitdauer für das Holen des für den nachfolgenden Arbeitsschritt vorgesehenen Werkzeugs ts und der erfassten Zeitdauer des aktuell durchzuführenden Arbeitsschritts ergibt. Die Heuristik lässt sich auch erweitern auf mehrere Werkstücktypen mit gleichen oder unterschiedlichen Stückzahlen von zu fertigenden Werkstücken je Typ durch eine entsprechende Priorisierung/Umsortierung von ListOp. In den folgenden Figuren 3 bis 5 wird ein Regalmagazin mit Anfangsbelegung und optimierter Belegung dargestellt. Der linke Teil der Graphik zeigt maßstabsgetreu die Hauptseite des Regalmagazins R. Die Gegenseite wird auf dem rechten Teil der Graphik ebenfalls maßstabsgetreu dargestellt. Diese Art der zweidimensionalen Darstellung wurde gewählt, da die

Verfahrdauer von einem Bereitstellungsplatz im dargestellten Koordinatensystem der Punkt (0,0) zur Gegenseite deutlich länger sind als zur Hauptseite.

In den dort gezeigten Spalten 23, 21 und 31 befinden sich die Magazinplätze für die größeren Werkzeuge. Die Werkzeuge sind mit Nummern versehen.

Die Punkte stellen die Magazinplätze dar, wobei die kleinen Punkte die Magazinplätze sind, auf denen nur kleinere Werk ^¬ zeuge und die großen Punkte diejenigen Magazinplätze sind, auf denen sowohl kleinere als auch größere Werkzeuge liegen dürfen. Die schraffierten Kreisscheiben stellen die gerüsteten Werkzeuge dar. Die hellen Kreisscheiben stellen die Werkzeuge der Operationen dar.

In dem dargestellten Zyklus in der Figur 3 wird erst das Werkzeug 341 zurückgebracht bzw. zurückgelegt, dann erfolgt eine Leerfahrt zum Magazinplatz des Werkzeugs 416 und es wird das Werkzeug 416 zum Bereitstellungsplatz gebracht.

In der Regel gilt: Je näher die hellen Kreisscheiben am Be- reitstellungsplatz liegen und je kürzer die Strecken der Zwischenfahrten sind, desto kürzer sind die Wartezeiten.

In den folgenden Figuren 4 und 5 sind eine Ausgangsbelegung der Magazinplätze mit Werkzeugen (Figur 4) und die optimierte Belegung (Figur 5) sowie die Leerfahrten, welche mit Linien gekennzeichnet sind, dargestellt. Die Linie von 151 nach 341 bedeutet z.B., dass in einem Zyklus das Werkzeug 151 zurück ^¬ gebracht werden muss, vom Magazinplatz des Werkzeugs 151 zum Magazinplatz des Werkzeugs 341 eine Leerfahrt erfolgt und das Werkzeug 341 anschließend zum Bereitstellungsplatz gebracht werden muss. Es ist sichtbar, dass in Figur 5 durch die

Umplatzierung der Werkzeuge, d.h. neue Belegung der Magazin- platze mit Werkzeugen, kürzere Wege für die Leerfahrten not ^¬ wendig sind und die Wege zum Abholen und Zurückbringen der Werkzeuge ebenfalls kürzer sind als in Figur 4.

Obwohl die Erfindung im Detail durch das bevorzugte Ausfüh- rungsbeispiel näher illustriert und beschrieben wurde, so ist die Erfindung nicht durch die offenbarten Beispiele einge ^¬ schränkt und andere Variationen können vom Fachmann hieraus abgeleitet werden, ohne den Schutzumfang der Erfindung zu verlassen .

Die Implementierung der vorstehend beschriebenen Prozesse oder Verfahrensabläufe kann anhand von Instruktionen erfol ^¬ gen, die auf computerlesbaren Speichermedien oder in flüchtigen Computerspeichern (im Folgenden zusammenfassend als com- puterlesbare Speicher bezeichnet) vorliegen. Computerlesbare Speicher sind beispielsweise flüchtige Speicher wie Caches, Puffer oder RAM sowie nichtflüchtige Speicher wie Wechselda ^¬ tenträger, Festplatten, usw. Die vorstehend beschriebenen Funktionen oder Schritte können dabei in Form zumindest eines Instruktionssatzes in/auf einem computerlesbaren Speicher vorliegen. Die Funktionen oder Schritte sind dabei nicht an einen bestimmten Instruktions ^¬ satz oder an eine bestimmte Form von Instruktionssätzen oder an ein bestimmtes Speichermedium oder an einen bestimmten

Prozessor oder an bestimmte Ausführungsschemata gebunden und können durch Software, Firmware, Microcode, Hardware, Prozes ^¬ soren, integrierte Schaltungen usw. im Alleinbetrieb oder in beliebiger Kombination ausgeführt werden. Dabei können ver- schiedenste Verarbeitungsstrategien zum Einsatz kommen, beispielsweise serielle Verarbeitung durch einen einzelnen Prozessor oder Multiprocessing oder Multitasking oder Parallelverarbeitung usw. Die Instruktionen können in lokalen Speichern abgelegt sein, es ist aber auch möglich, die Instruktionen auf einem entfernten System abzulegen und darauf via Netzwerk zuzugreifen.

Unter „rechnergestützt" kann im Zusammenhang mit der Erfindung beispielsweise eine Implementierung des Verfahrens ver ^¬ standen werden, bei dem insbesondere ein Prozessor mindestens einen Verfahrensschritt des Verfahrens ausführt.

Der Begriff "Prozessor", "zentrale Signalverarbeitung",

"Steuereinheit" oder "Datenauswertemittel " , wie hier verwen ^¬ det, umfasst Verarbeitungsmittel im weitesten Sinne, also beispielsweise Server, Universalprozessoren, Grafikprozesso- ren, digitale Signalprozessoren, anwendungsspezifische inte ^¬ grierte Schaltungen (ASICs) , programmierbare Logikschaltungen wie FPGAs, diskrete analoge oder digitale Schaltungen und be ^¬ liebige Kombinationen davon, einschließlich aller anderen dem Fachmann bekannten oder in Zukunft entwickelten Verarbei- tungsmittel. Prozessoren können dabei aus einer oder mehreren Vorrichtungen bzw. Einrichtungen bzw. Einheiten bestehen. Besteht ein Prozessor aus mehreren Vorrichtungen, können diese zur parallelen oder sequentiellen Verarbeitung bzw. Ausführung von Instruktionen ausgelegt bzw. konfiguriert sein. Un- ter einer „Speichereinheit" kann im Zusammenhang mit der Erfindung beispielsweise ein Speicher in Form von Arbeitsspeicher (engl. Random-Access Memory, RAM) oder eine Festplatte verstanden werden.