Reihenfolgenproblem < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:23 Mi 27.06.2012 | | Autor: | Joshkar |
Hallo zusammen,
es geht darum die Produktionsreihenfolge verschiedener Produkte an einer Maschine zu optimieren. An der Maschine sollen bspw. 50 Produkte bearbeitet werden, die verschiedene Eigenschaften, wie Gewicht, chemische Zusammensetzung, usw. haben. Je größer die Unterschiede zwischen den aufeinanderfolgenden Produkten sind, desto höher sind auch die jeweiligen Kosten. Das eigentliche Problem besteht also daraus eine Kostenfunktion zu minimieren, bei der die Kosten von der Reihenfolge abhängig sind.
Auf der suche nach ähnlichen Problemen bin ich auf das Travellings Salesman Problem gestoßen, welches mit dem Concorde Solver zu lösen ist. Außerdem habe ich den ILOG CPLEX Solver gefunden, der mit Constrainit Programming Reihenflogeprobleme behandeln kann.
Hat jemand bereits Erfahrungen mit ähnlichen Problemen gehabt, und kann mir erläutern, ob das Travelling Salesman Problem als Ansatz für meine Aufgabe geeignet ist? Oder setze ich besser auf die CP-Methoden um möglichst schnell eine Lösung zu finden?
Später soll das Modell eventuell um Fertigungsfristen ergänzt werden, sodass einige Produkte vor anderen fertigestellt werden müssen. Außerdem gibt es noch weitere produktionsbedingte Einschränkungen, sodass meine Problemstellung ja nicht ohne weiteres auf ein TSP übertragbar ist.
Das TSP wird ja in der Regel mit Branch&Bound bzw. Heuristik gelöst. Kann mir jemand näher erläutern, auf welchen Ansätzen oder Algorithmen die Constraint Programmierung des CPLEX CP Solvers beruhen ?
Vielen Dank für eure Hilfe
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Zu der Hälfte mit dem TSP kann ich dir etwas sagen.
Betrachtest du die Orte als Analogon zu den Produkten und als Abstände zwischen den Orten die Wechselkosten zwischen Produkten hast du ein TSP. Was dir ja klar ist.
Für eine Maschine ist es also geeignet.
Natürlich kann kann man nun mit Branch and Cut draufschlagen. Nur in der Regel genügen auch Heuristiken. Ich denke da an n-Opt was so viel macht, wie n Teilstücke zu permutieren.
Damit steht dir auch die Moeglichkeit offen mit SA und LS, oder genetischen Algorithmen zu arbeiten.
Kommt halt drauf an, wie groß dein Problem wird. Wenn es bei den 50 Sachen bleibt und du Glück mit den Schranken hast, dann geht auch BranchCut.
Zu den anderen kann ich nichts beitragen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:53 Do 28.06.2012 | | Autor: | Joshkar |
Ok vielen Dank schonmal.
Mit den Heuristiken habe ich mich noch nicht so sehr beschäftigt.
Kannst du mir vielleicht erklären was n-opt ist ? Ich kann zum Thema Optimierungsheuristik lediglich k-opt finden!
Und wofür stehen SA und Ls ??
Wahrscheinlich werden doch ca. 100 Produkte behandelt. In dem Fall sind deine vorgeschlagenen Verfahren wohl effektiver, oder ?
|
|
|
| |
|
In meiner Welt heißt es n-opt 
Aber damit meine ich k-opt natürlich.
Die Frage ob ein deterministischer Algorithmus oder eine Heuristik (Lokale Suche, Simulated Annealing,...) besser ist, kann man erst hinterher beantwortet.
TSP ist Np-vollständig. Verwendet man Heuristiken, so ist man schneller hat aber nicht die Garantie die optimale Lösung zu finden.
Letztlich ist es eine Glaubenssache.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Fr 29.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:53 Do 05.07.2012 | | Autor: | Joshkar |
Ich habe nun probiert das Problem als TSP zu modellieren, habe nun aber festgestellt, dass beim TSP dahingehend optimiert wird einen möglichst kurzen Hamiltonkreis zu finden.
In meinem Problem soll allerdings eine Reihenfolge gebildet werden, sprich ein offener Kreis, wo (zum Beispiel nur bei Berücksichtigung des Gewichts) die Produkte von leicht nach schwer sortiert sind.
Später natürlich auch unter Einfluss der anderen Kostenfaktoren.
Meine Frage ist jetzt, ob es Sinn macht, das Problem trotzdem als TSP zu modellieren, zum Beispiel durch Einfügen zweier zusätzlicher Knoten (Start und Ende). Oder ob es für ein Problem meiner Art auch andere evtl einfachere Ansätze gibt ?
|
|
|
|
