Verschnittoptimierung

[Moesi]

Hey Leute

Vor einiger Zeit hat mich meine Mutter gefragt ob ich es schaffen würde ein Programm zu schreiben, dass ihr auf der Arbeit einiges an Zeit sparen könnte.
Und zwar muss sie von Zeit zu Zeit große Bestellungen (Fensterbänke) aufnehmen und so optimieren dass so wenig wie möglich Verschnitt übrig bleibt. Per Hand dauert das dementsprechend lange und das Programm das sie benutzen sollte lässt nur wenige Eingaben zu und ist somit nicht sehr effizient.

Ich bin jetzt im 2. Jahr an einer höheren Schule und wir nehmen gerade Threads durch. Gearbeitet wird vorzugsweise mit NetBeans. Die Stangen aus denen herausgeschnitten wird sind standardmäßig 405 cm lang, die Fensterbänke unterschiedlich.

Meine ersten Überlegungen waren einfach jede Eingabe mit jeder zu vergleichen und falls der Restplatz größer als die kleinste Eingabe ist nochmal zu vergleichen welche Eingabe Platz hat.
Könnte das funktionieren oder habt ihr andere Ansätze ?
PS: Nein, das ist wirklich nichts schulbezogenes

 

[klauskarambulut]

Bei n verschiedenen Fensterbänken gibt es bis zu
n! Möglichkeiten diese auf das Rohmaterial anzuordnen.

Bruteforce und Algorithmisch wird das sehr schwierig.

Um das ganze in ein Lineares Optimierungsproblem umzumünzen fehlt dir höchstwahrscheinlich das KnowHow.

Aber seis drum.

Im ersten Schritt schaut man sich alle Möglichen Kombinationen an wie man eine Stange zersägen kann.

Bspl.
Bänke mit den Längen 1m, 2m und 3m sind gefordert.
Rohmateriel 4,05m

Dann gibt es folgende Möglichkeiten
a: 3m, 1m (1, 3 ist äquivalent zu 3, 1 und wird deshalb weggelassen)
b: 2m, 2m
c: 2m, 1m, 1m
d: 1m, 1m, 1m, 1m


Jetzt schaut man sich an wieviele von diesen Kombinationen man jeweils nutzen muss um eine
Bestellung auszuliefern.
Bestellung
20 * 1m
12 * 2m
7 * 3m

Daraus Ergibt sich folgendes Optimierungsproblem mit den 3 Restriktionen. sowie der Prämisse (a, b, c, d >= 0.

a + b + c + d =>min
R1: a >= 7
R2: 2b + c >= 12
R3: a + 2c + 4d >= 20

Das gibt man in einen Solver ein z.B. GLPK lässt das durchlaufen und erhält ein vernünftiges Ergebnis.

a + b + c + d sind die verschiedenen Zuschnittsarten in die das Rohmaterial aufgeteilt werden kann.
1 + 0 + 0 + 0 bedeutet nimm nur eine Stange und zersäge sie in 3m und 1m.

R1 bedeutet dass nur Kombination a, exakt ein 3m Stück hervorbringen kann.
Da wir 7 * 3m benötigen folgt daraus a größer 7
Für die 12 2m Stücke sind die Kombinationen b und c von Belang. b liefert 2 2m Stücke und c nur eins.
Also folgt daraus 2b + c >= 12


Und so stellt man sich eben das Lineare Optimierungsproblem zusammen und läßt dies lösen.


Den geringsten Verschnitt definiere ich hier als Gesamtverschnitt und somit die minimale Menge an verwendetem Rohmaterial.