matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete OptimierungReihenfolgenproblem
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Diskrete Optimierung" - Reihenfolgenproblem
Reihenfolgenproblem < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Optimierung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Reihenfolgenproblem: Frage (überfällig)
Status: (Frage) überfällig Status 
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.


        
Bezug
Reihenfolgenproblem: Antwort
Status: (Antwort) fertig Status 
Datum: 14:05 Mi 27.06.2012
Autor: wieschoo

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.

Bezug
                
Bezug
Reihenfolgenproblem: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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 ?

Bezug
                        
Bezug
Reihenfolgenproblem: Antwort
Status: (Antwort) fertig Status 
Datum: 10:01 Do 28.06.2012
Autor: wieschoo

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.

Bezug
        
Bezug
Reihenfolgenproblem: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:20 Fr 29.06.2012
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Reihenfolgenproblem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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 ?

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Optimierung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]