"Bin Packing" Problem in SPS sinnvoll?!

[SPS-freak1]

Zuviel Werbung?
-> Hier kostenlos registrieren

Guten Morgen,

Ich stehe seit einigen Tagen vor dem Problem, mir vorab unbekannte Kartons in Kisten zu sortieren. Nach einigem an Recherche im Internet bin ich mir bewusst , dass dieses Problem nicht so trivial ist, wie man vielleicht zuerst denken mag.
Natürlich gibt es für dieses Problem mittlerweile einiges an PC Software dafür um die optimale Position in der Kiste zu berechnen. Meistens sind aber vorher schon mehrere Kartons bekannt und der PC berechnet die ideale Reihenfolge wie diese zu handeln sind.
Ich weiß aber aktuell nicht, was nacheinander kommt sondern reagiere nur. Ich habe mittlerweile auch schon eine Lösung erarbeitet, die mich aber nicht so ganz zufrieden stimmt.
Jetzt wollte ich einfach hier mal nachfragen, ob sich jemand diesem Problem schon mal auf "SPS Ebene" angenommen hat?
Aktuell arbeite ich mit vordefinierten Fächern, wo ein Karton je nach Kantenlänge einfach hin gestellt wird. Natürlich "sieht" der Mensch, dass der letzte Karton ja auch wo anders noch mit hingepasst hätte.
Mein zweiter Ansatz wäre es, mir ein Array als Gitter in meiner Kiste aufzuziehen und dort immer nach einer Ablage zu suchen. Dabei sehe ich aber den SPS Zyklus ziemlich kritisch, da es sehr schnell sehr viele Daten bzw Zugriffe werden können. Sollte dann auch noch jemand mit "Best Fit" daher kommen, wird es noch aufwändiger.

Ich will dafür keine Lösung haben, sondern einfach mal eine Meinung von dritten, die sich mit dieser Materie schon mal intensiver beschäftigt haben.

Vielen Dank und schönen Sonntag.


Gesendet von meinem SM-A600FN mit Tapatalk

 

[Lipperlandstern]

Wenn du nicht weißt was da an Kartons auf dich zukommt bleibt dir ja nur die Variante "umpacken"

 

[Blockmove]

Zuviel Werbung?
-> Hier kostenlos registrieren

Naja letztlich lassen sich viele Algorithmen mit mehr oder weniger Aufwand auf die SPS übertragen.
Augenmerk musst du halt auf die Zykluszeit legen.
Und nicht nur auf die max. Zykluszeit, sondern auch die Konstanz.
Hier sind halt Konzepte mit verschiedenen Tasks sinvoll.
Interessant sind da auch "kombinierte" Lösungen. Also z.B. Soft-SPS auf nem PC

 

[SPS-freak1]

Hi,

Was meinst du denn mit Umpacken? Den bestehenden Karton wieder verschieben?!
Mich würde der Ansatz wie ich mir merke, was wo steht bzw. wie man dann herausfindet, was gerade die beste Lösung für den neuen Karton ist umsetzen kann in einer SPS. Und wenn ein Karton nicht mehr in eine Lage passt, soll dieser in die nächste Lage gelegt werden.

Gesendet von meinem SM-A600FN mit Tapatalk

 

[SPS-freak1]

Naja letztlich lassen sich viele Algorithmen mit mehr oder weniger Aufwand auf die SPS übertragen.
Augenmerk musst du halt auf die Zykluszeit legen.
Und nicht nur auf die max. Zykluszeit, sondern auch die Konstanz.
Hier sind halt Konzepte mit verschiedenen Tasks sinvoll.
Interessant sind da auch "kombinierte" Lösungen. Also z.B. Soft-SPS auf nem PC

Ja das denke ich mir schon. Nur fehlt mir da erstmal der richtige Algorithmus um sowas zu ermitteln.
Das habe ich auch mit der Zykluszeit gemeint, natürlich kann ich die Überwachung auf 2 Sekunden stellen. Es sollte schon eine gleichmäßige Zykluszeit sein. Habe mir auch schon überlegt, es auf VBS Basis im Panel zu rechnen. Allerdings sehe ich da die Datenablage als Problem.

Gesendet von meinem SM-A600FN mit Tapatalk

 

[Thomas_v2.1]

Zuviel Werbung?
-> Hier kostenlos registrieren

Ich habe ein ähnliches Problem bei einem Lastabwurf schon einmal in der SPS umgesetzt. Dort gab es bis zu 50 Verbraucher deren Leistung gemessen wurde, und bei Netzausfall musste ein Lastabwurf vollzogen werden, bei dem genau auf ein Zielpunkt hin abgeworfen werden musste. Da das alles in einem SPS-Zyklus geschehen musste, habe ich mich dazu entschieden nicht die beste Lösung zu finden, sondern nur eine Lösung die in einem bestimmten Toleranzbereich liegt (gab dann drei, die 1./2. und 3.-beste Lösung). Das lässt sich dann auch belegen, dass solange bestimmte Voraussetzungen gegeben sind, es immer eine Lösung gefunden werden kann.

Das machen z.B. Routenplaner auch so in der Art, da der Aufwand die beste Lösung zu finden viel zu hoch wäre. Das würde ich bei deinem Problem auch untersuchen, ob du wirklich die beste Lösung finden musst, oder falls das nicht notwendig sein muss, der Algorithmus vereinfacht werden kann.

 

[SPS-freak1]

Ich hab das ja auch aktuell so gelöst, dass ich mir mal den aktuellen Bestand der Kartons angeschaut habe und den Durchschnittlichen Karton bestimmt habe, dadurch hab ich mir ein festes Raster in die Kiste eingelegt und stelle die dann passend der Größe ins zugehörige Feld. Natürlich kommt dann der Kaufmann und sagt "da hätte doch noch der nächste Karton hingepasst" wobei ich halt sage, dass diese Lage dann voll ist. Und um dieses Problem zu lösen, also alle Räume Maximal ausnutzen, dafür fehlt mir aktuell der praktische Ansatz. Sprich, wie lege ich diese Informationen ab, was wo steht. Und das natürlich in 3D und natürlich auch so, dass wenn alles voll ist auch noch der übrige Fleck am Boden verwendet werden kann.

Gesendet von meinem SM-A600FN mit Tapatalk

 

[Heinileini]

Ich weiß aber aktuell nicht, was nacheinander kommt sondern reagiere nur.

Dann hast Du aber gaaanz schlechte Karten! Oder das Problem ergibt sich gar nicht erst.
Du musst doch schon von n Kartons wissen, wie gross sie sind, um entscheiden zu können, welche davon in denselben Kasten passen würden.
Oder hast Du mehrere teils leere, teils ein wenig bepackte Kästen vor Dir und sollst, wenn ein weiterer Karton angeliefert wird, entscheiden, in welchem der Kästen der Karton am wenigsten Platz verschwenden würde, wenn später noch weitere Kartons mit unvorhersehbaren Maßen nachfolgen werden?
Apropos Maße, wie sieht's aus mit der Masse? Musst Du ausser den Maßen der Kartons noch weitere Kriterien berücksichtigen? Gewicht der Kartons? Tragfähigkeit/Belastbarkeit der Kartons? SchwerpunktLage des fertig beladenen Kastens?

Nein, ich habe keinerlei Erfahrung mit dieser Problematik. Habe mir nur mal Gedanken über ein "1-dimensionales" Problem dieser Art gemacht: Es sollen Dateien unterschiedlicher Länge auf CDs bzw. DVDs so verteilt werden, dass diese möglichst voll werden bzw. dass möglichst wenige "Container" genügen.
Meine Strategie dabei war ganz simpel:
Die Dateien nach kleiner werdender Länge sortieren und diese Liste von oben nach unten abarbeiten. Verbleibender Platz reicht noch aus? Dann rein damit. Sonst weiter prüfen. Nächste Datei passt noch mit rein? U.s.w..
Die Ergebnisse waren passabel. Um manuell noch ein wenig herumspielen zu können, habe ich dann eingeführt, jede einzelne Datei vorübergend "sperren" zu können, damit man sehen kann, wie sich die Auswahl zweier oder mehrerer kleinerer Dateien statt der grösseren auswirkt.
Natürlich ist ein 3-dimensionales Problem sehr viel komplexer. Man müsste mindestens auch berücksichtigen, dass ein Karton längs oder quer in den Kasten gestellt werden kann. Die Fälle, wenn ein Karton beliebig (auch "hochkant") in den Kasten gestellt werden darf, sorgen für zusätzliche Komplexität.
Den verbleibenden, freien Raum im Kasten kann man durch quaderförmige "virtuelle, leere Kästen" darstellen und für diese wie gehabt weiter verfahren.
Und hierbei gibt es wieder das Problem, dass verschiedene Lösungen möglich sind, da sich die grösstmöglichen Quader überschneiden. Macht man es so, dass man solche Überschneidungen "verbietet" und sich mit unnötig künstlich verkleinerten Quader begnügt, um es übersichtlich zu halten. Oder nimmt man die ansteigende Komplexität in Kauf?
Für die Lösung drängt sich ein rekursives Verfahren auf ... und das ist leider nicht gut, wenn es darum geht, die ZyklusZeitBelastung in vorgegebenen Grenzen zu halten.

PS:
Hast Du mal ein ZahlenBeispiel, damit wir ein wenig konkreter sehen können, worum es geht? Maße des Kastens? Maße der verschiedenen KartonGrössen? Wie viele Kartons insgesamt bzw. jeden Typs sollen eingeräumt werden?

PPS:
Der Ansatz mit dem "durchschnittlichen Karton" will mir nicht einleuchten. Irgendwie kann ich mir nicht vorstellen, dass dieser halbwegs zielführend zu gebrauchen wäre.

 

[Thomas_v2.1]

Zuviel Werbung?
-> Hier kostenlos registrieren

Einen Universal-Algorithmus scheint es auch nicht zu geben. Vor etlichen Jahren gab es mal eine Art Palettier-Wettbewerb zwischen verschieden Universitäten. Hab das damals nur mitbekommen weil die Simulation mit der Blender Game Engine umgesetzt wurde. Da gab es auch noch weitere Bewertungskriterien zu den möglichst vielen Teilen unterzubringen, wie möglichst niedriger Schwerpunkt der ganzen Palette. Der Code dazu wurde aber nicht veröffentlicht, aber ich schätze mal wenn einen das interessiert findest du dazu etliches.

Wenn ich die Aufgabe bekäme, würde ich das erst mal am PC in einer passenden Programmiersprache ausprobieren, um zu sehen wo Aufwand, Komplexität, Speicher- und Zeitbedarf dann hinlaufen. Das lässt sich immer noch in SCL umschreiben, oder man lässt es auf einem kleinen Mini-PC ablaufen und die fertigen Daten dann mit der SPS austauschen.

Bei der S7-300/400 gibt es auch einen Hintergrund OB90, in dem du auch längere Programme ablaufen lassen kannst. Der nutzt die verbleibende Zeit zur Mindest-Zykluszeit des OB1, und du musst dich um Zykluszeiten oder Aufteilung des Algorithmus nicht mehr kümmern.

 

[SPS-freak1]

Guten Abend,

Danke für die Infos bisher.
Es handelt sich um Kartons, die leider keine Überschneidung ins Ihren Maßen haben, sprich es muss kein vielfaches eines anderen Karton geben. Es sind nur die Grenzabmaße von bis definiert. Konkret geht's von 260x100 MM bis 400x400 MM und die müssen in eine Kiste mit 750x550 Innenmaß.
Zum Thema Durchschnitt. Ich habe mir die Testmuster (>200 Stück) einfach mal in Excel jeweils bei der Kantenlänge den Durchschnitt bzw Median errechnen lassen und davon mal eine Normalverteilung um diese Werte mir anzeigen lassen.. und da hat sich gezeigt, dass ca 80 Prozent der Kartons 320x200 MM haben und somit immer fünf Stück auf die Fläche passen würden ( 3 quer 2 längs).
Das habe ich auch so abgebildet und berechne mir starr mit diesen Fünf Fächern den Ablagepunkt. Ist ein Karton größer als das Fach so "verschiebe" ich die Grenzen zwischen diesen zwei Fächern und in das kleinere passt dann halt nur noch ein kleinerer Karton. Gleichzeitig berücksichtige ich auch die reale Länge des Kartons und bestimme so die Größe des jeweilig angrenzenden Querfachs.
Richtig ist, kommen lauter große Kartons, dann liegen halt ziemlich wenige in der Kiste. Aber ich kann auch mehr als einen Karton pro Fach ablegen, so dass auch 6 kleine Kartons mit einer Breite von 100 nebeneinander liegen können. Das geht schon alles.
Jetzt kommt halt der innere Anspruch und sagt "das muss einfacher und effizienter gehen", deswegen dieser Thread.
Ich hätte 8 Kisten gleichzeitig zur Verfügung, aber ich bekomme die zu Verwendende Kiste von der übergeordneten Steuerung. Aktuell wird nur darauf geachtet, dass die Höhen halbwegs gleich bleiben, da ich pro fertiger Lage immer den höchsten Karton als neue Ablagehöhe verwende. Ansonsten wird es noch komplizierter in alle Richtungen die Störkonturen zu bestimmen.
Ihr seht, es ist sehr spannend wenn alle konstanten variabel sind...
Da würde man doch ab und zu wieder lieber nur Paletten schubsen [emoji2]

Gesendet von meinem SM-A600FN mit Tapatalk

 

[Mrtain]

Erinnert erstmal ein wenig an Tetris
Es wäre sicherlich vorteilhaft, wenn die übergeordnete Steuerungen dir Informationen über mehr als nur einen der nächsten Kartons liefern könnte, oder du die Möglichkeit hättest, Kartons erstmal zwischen zu speichern...

 

[SPS-freak1]

Zuviel Werbung?
-> Hier kostenlos registrieren

Ja es ist auch Tetris.
Ich bin nach aktuellem Stand eigentlich ganz froh, dass ich nichts von den nächsten Karton weiß, dass würde nämliche eine viel höhere Ausnutzung des Stauraums nach sich ziehen. Bei der Applikation geht es auch erstmal darum, dass die Kartons schnell in eine Kiste kommen und danach zu Mitarbeitern transportiert wird. Zum Glück, ist da kein Hochregallager dazwischen, was Geld kosten würde. Ansonsten würden wir da auf jedenfall auf Dritthersteller Software PC basiert wechseln. Da mir dann die Ansätze schon in den ersten Gedankenexperimenten schnell sehr komplex werden gerade wenn es auch noch auf die beste Lösung abzielen soll.
Und dann besteht die Kunst darin, das alles auf einzelne Zyklen zu verteilen.

Gesendet von meinem SM-A600FN mit Tapatalk

 

[Heinileini]

Es wäre sicherlich vorteilhaft, wenn die übergeordnete Steuerungen dir Informationen über mehr als nur einen der nächsten Kartons liefern könnte, oder du die Möglichkeit hättest, Kartons erstmal zwischen zu speichern...

Ja, allerdings! Das unterstelle ich auch weiterhin, dass man die Aufgabe nicht sinnvoll in Angriff nehmen kann, bis man eine genügende Anzahl von Kartons zur Verfügung hat, sei es, dass sie "real existierend" in einem ZwischenLager schon auf das Verstauen warten oder sei es, dass von irgendwo her verlässlich und früh genug angekündigt wird, welche Kartons man unterbringen muss.
Die zweite Variante ("frühzeitige Ankündigung") legt nahe, dass die Optimierung ebenfalls vorgelagert werden könnte/müsste, um zu verhindern, dass sich am Ort des Verstauens die Kartons stapeln müssen, bevor sie verstaut werden können ... und sich einzelne Exemplare ansammeln, die aufgrund eines Algorithmus wiederholt vergeblich auf das Verstautwerden warten müssen.
Die Reihenfolge, in der die unterschiedlich grossen Kartons angeliefert werden, könnte somit auch vorab zweckmässig beeinflusst werden.

Danke für die nachgeschobenen Infos, SPS-freak1.

Deinen DurchschnittsKartonAnsatz habe ich jetzt - glaube ich - besser verstanden. Du meinst nicht, aus den vorkommenden Kartons einen "imaginären" mit DurchschnittsMaßen zu bilden und damit in den Berechnungen NäherungsLösungen zu finden, sondern eher für häufig vorkommende Konstellationen fertige Lösungen parat zu haben.
Anscheinend geht Deine erwünschte Optimierung eher dahin, für das Einräumen eines (der) ersten Kartons in einen Kasten die Position zu finden, die bei den häufigsten Konstellationen einen guten NutzungsGrad verspricht bzw. ihn nicht von vorn herein vermasselt. Das wäre aber keine Optimierung, die in einer SPS laufen müsste!
Fertige "Rezepte" für alle erdenklichen Varianten müssten vorab "irgendwo" nach den statischen Erkenntnissen angefertigt werden ... und ggfs in der SPS Platz finden!

Ich vermisse bei Deinen MaßAngaben die dritte Dimension. Die Aufgabenstellung sieht jetzt nur noch sehr "flach" aus!
Wie sieht es z.B. damit aus, ob die Kartons auch "hochkant" verstaut werden dürfen? Man sieht ja immer wieder Kartons, auf denen penibel aufgedruckt ist, welches die OberSeite ist - ohne dass man beim Auspacken einen plausiblen Grund für diese Festlegung entdecken könnte.

 

[SPS-freak1]

Hi,

Danke für die Gedanken bis daher. Die dritte Dimension habe ich der komplexheit wegen erstmal unbeachtet gelassen. Theoretisch sind Maße von 65 bis 170 MM definiert. Da aber 8 Kisten zur Verfügung stehen, wird von der vorgelagerten Steuerung in 4 Größen Höhenabhängig vorsortiert. Dadurch ist der Höhenversatz erstmal zu ignorieren. Theoretisch mach ich dann pro Lage maximal 25mm kaputt. Was ist noch berücksichtigt habe ist, dass wenn ein Karton auf bereits stehende Karton gestellt werd wo mehr als die Hälfte in der Luft hängt, dann breche ich die Kiste auch ab. Das sind ja auch Kisten, die zu Handarbeitsplätzen fahren. Da macht einer mehr oder weniger erstmal nicht so viel aus.

Gesendet von meinem SM-A600FN mit Tapatalk

 

[Blockmove]

Zuviel Werbung?
-> Hier kostenlos registrieren

Wie kommen die Packungen in die Kiste. Robi?
Auf der Robotersteuerung lassen sich manche Aufgaben leichter lösen als auf der SPS.

 

[RogerSchw85]

Ich würde eine Software kennen, die das bereits sehr gut kann. Allerdings läuft die auf einem PC. Wenn du möchtest kannst du mir eine PN schicken und ich gebe dir den Hersteller.

 

[SPS-freak1]

Hi,

@Blockmove: Ja das passiert per Roboter. Allerdings muss ich das jetzt nicht unbedingt dem gelben Kollegen beibringen. Würde mittlerweile auch eher zu PC Software tendieren.

@Roger: Ein zwei kenn ich schon, aber vielleicht hast du ja einen anderen, der schon was passendes hat.

Danke für eure Mühe

Gesendet von meinem SM-A600FN mit Tapatalk

 

[Thomas_v2.1]

Zuviel Werbung?
-> Hier kostenlos registrieren

Ich habe aus Neugier mal die Tage mal geschaut ob es da in Python etwas fertiges gibt um damit herumzuspielen. Da gibt es auch eine Bibliothek die in identischer Weise auch in anderen Programmiersprachen zur Verfügung steht, die aber gleich bei deinem ersten Beispiel mit den 5 gleichen Paketen es nicht schafft diese in eine Box in eine Ebene zu legen (und noch einen Bug dazu hat).

Der dort verwendete "Algorithmus" ist sehr simpel gehalten, das wäre auch in der SPS möglich zu programmieren. Das Verfahren ist vermutlich eines der ersten Ideen wie man es selber programmieren würde wenn man ohne Vorrauschau immer ein neu eintreffendes Paket direkt packen müsste:

Es werden die zu packenden Pakete der Größe nach sortiert, und dann wird in einer Ecke begonnen und das erste Paket eingefüllt. Passt es nicht, wird es so lange gedreht bis es passt (oder auch nicht) und dann mit den folgenden Paketen in gleicher Weise fortgesetzt. Es gibt keine Backtracking, d.h. alle Pakete die gesetzt sind bleiben auch an dieser Position. Der einzige Vorteil ist die Komplexität n log n, d.h. bei steigender Anzahl an Paketen explodiert dir nicht die Laufzeit.

 

[Blockmove]

@Blockmove: Ja das passiert per Roboter. Allerdings muss ich das jetzt nicht unbedingt dem gelben Kollegen beibringen. Würde mittlerweile auch eher zu PC Software tendieren.

Wenn der Roboter gelb ist, dann ruf doch mal in Neuhausen an.
Fanuc arbeitet mit Systempartnern zusammen und ich kann mir vorstellen, dass es da schon Lösungen gibt.
Sei es nun auf der Robotersteuerung direkt oder in Verbindung mit einem ext. PC.
Auf jedenfall passt das Problem besser auf die Robotersteuerung als auf die SPS.

Gruß
Blockmove

 

[SPS-freak1]

Wenn der Roboter gelb ist, dann ruf doch mal in Neuhausen an.
Fanuc arbeitet mit Systempartnern zusammen und ich kann mir vorstellen, dass es da schon Lösungen gibt.
Sei es nun auf der Robotersteuerung direkt oder in Verbindung mit einem ext. PC.
Auf jedenfall passt das Problem besser auf die Robotersteuerung als auf die SPS.

Gruß
Blockmove

Du wirst lachen, das hab ich schon getan. Nicht konkret um nach einer Software zu fragen, sondern ob ihre 3DV Kamera anstatt rausnehmen auch wieder was reinlegen kann...
Leider ist das nicht möglich. Deswegen laufen jetzt die Anfragen bei zwei anderen Systemhäusern.

Ich habe aber jetzt auch die Freiheit bekommen, mir die beste Ablage (8 Behälter) selbst zu suchen.
Nur macht es das aktuell für mich nicht wirklich besser, da die Entscheidungen nicht weniger aufwändig zu treffen sind. Da ich ja jetzt eine Art Best Fit machen kann. Nur ist da schon entscheidend wie die Daten abgelegt sind. Um zu beurteilen wo liegt mehr drin. Bzw wo mach ich weniger Stauraum damit kaputt.


Gesendet von meinem SM-A600FN mit Tapatalk