Frage zur einer Textaufgabe (Optimierung)

Question

mal eine etwas andere Aufgabe aus dem Bereich der Optimierung

Firma "Blechi" schneidet Bleche zu. Es gibt m verschiedene Formen (F) auf die zugeschnitten werden kann und es sollen alle Bestellungen zugeschnitten werden, die auf der Bestellliste stehen. Eine Bestellung besteht aus der Anzahl bestellter Bleche einer Form B_Fi. Es muss nicht für jede Form eine Bestellung vorliegen und es gibt nur eine Schneidmaschine. Das Umstellen der Maschine von einer Form F_i auf eine andere Form F_j dauert eine gewisse Zeit t_wechsel,ij. Am Anfang ist die Maschine bereits auf eine Form eingestellt, für die auch eine Bestellung vorliegt und das Zuschneides eines Blechs auf eine Form befarf Zeit auf der Maschine (t_Fi, abhängig von der Form).

Blechi beauftagt mich eine Lösung zu finden, so dass alle bestellten Bleche in möglichst kurzer Zeit zugeschnitten werden können. In welcher Einstellung (welche Form eingestellt) die Maschine zum Schluss ist, ist egal.

a) Wie oft muss die Maschine umgestellt werden?

b) Sind die Zeiten t_Fi relevant? (Müssen sie in der Evaluierungsfunktion berücksichtigt werden?)

c) Kann davon ausgegangen werden, dass das Problem symmetrisch ist?

Mein Ansatz:

a) Ich würde sagen: Anzahl der Bestellungen auf der Bestellliste - 1 (da sie am Anfang bereits eingestellt ist).

b) Nein, da sowieso alle Bleche zugeschnitten werden müssen und die Zeit hierfür konstant ist.

c) keine Ahnung

Wahrscheinlich liege ich völlig daneben.

Danke vorab und viele Grüße

Answer 1

a) Ich würde sagen: Anzahl der Bestellungen auf der Bestellliste - 1 (da sie am Anfang bereits eingestellt ist).

Anzahl verschiedener Formen in den Bestellungen - 1

b) Nein, da sowieso alle Bleche zugeschnitten werden müssen und die Zeit hierfür konstant ist.

Doch. Nehmen wir an es sollen 3 Bleche (1, 2 und 3) produziert werden.

Das umstellen von 1 auf 2 kostet 1 Minute

Das umstellen von 2 auf 3 kostet auch 1 Minute

Alle anderen Umstellungen kosten 5 Minuten.

Jetzt sollte natürlich in der Reihenfolge 1-2-3 gefertigt werden.

c)

Ich denke nicht dass man davon ausgehen kann, dass das Problem symmetrisch ist.

Comments

Danke für deine Antwort Mathecoach. Okay a) sehe ich ein. Bei der b) geht es jedoch um die Zeit t_Fi (also die Zeit, die benötigt wird die bestimmte Blechform herzustellen) und nicht um die Zeit t_wechsel,ij. Daher spielt es meiner Meinung nach keine Rolle, wie lange das Zuschneiden eines Bleches dauert.

---

Ja da hast du recht die eigentlichen Fertigungszeiten sind irrelevant. Wichtig sind nur die Rüstzeiten zum Wechseln der Maschine.

---

Danke für die Rückmeldung. Bei der c) verstehe ich nicht ganz, wie das gemeint ist. Also normalerweise ist die Aufgabenstellung ein wenig anders, habe sie etwas verändert, weil die eigentliche c) ins Detail geht, aber vielleicht kennst du dich mit Optimierungs etwas aus.

c) Vergleichen Sie das Blechi-Problem mit dem TSP (Traveling Saleman Problem, Problem des Handlungsreisenden)

- jede Form ist Stadt
- Durchzählen aller Formen
- eine Form Mutation
- gehe nicht zurück

d) Kann davon ausgegangen werden, dass das Problem symmetrisch ist (sich wie ein symmetrisches TSP verhält)?

Ich weiß nicht, welche Informationen Rückschlüsse darauf geben, ob es sich hierbei um ein symmetrisches Problem handelt?

---

Zum TSP habe ich auf Wikipedia folgendes gefunden:

Asymmetrisches und symmetrisches TSP

Beim allgemeinen asymmetrischen TSP können die Kanten in Hin- und Rückrichtung unterschiedliche Längen haben, so dass dieses Problem mit Hilfe eines gerichteten Graphen modelliert werden muss. Es reicht also nicht, bloß von der Verbindung zwischen zwei Knoten und ihrer Länge zu sprechen; zusätzlich muss noch die Richtung angegeben werden.

Beim symmetrischen TSP dagegen sind für alle Knotenpaare ( i , j ) {\displaystyle (i,j)} die Kantenlängen in beide Richtungen identisch, d. h. es gilt c i j = c j i {\displaystyle c_{ij}=c_{ji}} . Als Konsequenz davon hat jede Tour in beide Richtungen dieselbe Länge. Die Symmetrie halbiert also die Anzahl der möglichen Touren. Ein symmetrisches TSP wird üblicherweise mit Hilfe eines ungerichteten Graphen modelliert (wie im Bild).


Kannst du mir sagen, wie sich dies auf das Blechi-Problem beziehen lässt? Stehe momentan echt auf dem Schlauch.

---

Reisen wir von Stadt 1 nach Stadt 2 so ist eventuell zu erwarten das die Zeit die dafür benötigt wird in etwa gleich lang ist. Es sei denn es gibt eine Autobahn die gerade in eine Richtung gesperrt ist oder dumme Einbahnstrassen.

Das heißt man kann eventuell nicht davon ausgehen das es hier symmetrisch ist.

Nun ist die Frage ob das Umrüsten der Maschine von Teil 1 auf Teil 2 genau so lange dauert wie das Umrüsten von Teil 2 auf Teil 1?

Grundsätzlich muss das nicht so sein, sodass wir nicht notwendiger Weise davon ausgehen können, dass es symmetrisch ist.

---

Okay nochmal kurz. Ich würde sagen: jede Form lässt sich mir einer Stadt vergleichen und der Wechsel der Form ist die Route von einer Stadt zur nächsten. Jeder Stadt soll nur einmal besucht werden, kann mit jeder Form soll nur einmal benutzt werden um alle Blechformen herzustellen gleichgesetzt werden.

So nun ist es so, dass bei asymmetrischen TSP der Weg von einer Stadt in die nächste auf dem Hinweg länger oder kürzer dauern kann als auf dem Rückweg. Grund dafür können in etwa Baustellen oder Einbahnstraßen.

Bei symmetrischen TSP dauert der Weg in eine Stadt in die nächste auf dem Hinweg genau so lange wie auf dem Rückweg.

Wenn ich das jetzt auf das Blechi-Problem beziehen würde, würde ich sagen, es handelt sich um ein symmetrisches Problem. Mit fällt kein Grund ein, warum der Wechsel von einer Form länger bzw. kürzer dauern sollte, wenn man am Ende wieder den "Rückweg" einschlägt.

Kannst du mir einen Grund nennen, warum das nicht so sein muss? Ich meine welches Problem kann auftreten, wenn das alles automatisch verläuft? Klar, kann z.B. ein Defekt auftreten oder sowas aber in der Regel müsste es ja in der gleichen Zeit geschehen. Echt eine doofe Aufgabe ...

---

Nur ein Beispiel. Dauert es genau so lange einen Faden durch ein Nadelöhr zu stecken oder den Faden aus dem Nadelöhr hinaus zu ziehen.

Im Zweifel gehst du immer von einem asymmetrischen Problem aus. Es sei denn es ist klar etwas anderes gesagt.

---

Alles klar, danke für deine Hilfe!