|
|
Verschnittproblem
I. Begriff: Variante des Grundproblems der Zuschnittplanung mit folgenden Spezifikationen: a) Sämtliche potentiellen Inputmaterialien besitzen die gleichen Abmessungen. b) Diejenigen Teile der tatsächlich eingesetzten Inputmaterialien, die jetzt nicht zur Auftragserfüllung verwendet werden können (Verschnitt), sind auch später nicht mehr einsetzbar und müssen als Abfall angesehen werden. c) Angestrebt wird deshalb eine Minimierung des Verschnitts. d) Sonstige Beschränkungen werden nicht wirksam.
II. Mathematische Formulierung: Minimiere
wobei: I = Indexmenge aller Auftragsformate; J = Indexmenge aller Schnittmuster, zu denen sich die Auftragsformate für den betrachteten Inputmaterialtyp kombinieren lassen; xj = Anzahl der Inputmaterialien, die nach dem Schnittmuster j (j J) aufgeteilt werden soll; xo = insgesamt einzusetzende Anzahl von Inputmaterialien; aij = Häufigkeit, mit der das Auftragsformat i (i I) im Schnittmuster j (j J) vorkommt; bi = gewünschte Liefermenge des Auftragsformates i (i I). Die Minimierung der Anzahl xo der eingesetzten Materialien ist unter den gemachten Annahmen äquivalent zur Minimierung des Verschnitts.
III. Lösungsverfahren: Es handelt sich um ein ganzzahliges lineares Optimierungssystem, bei dem die Anzahl | J | der möglichen Schnittmuster sehr groß sein kann. Die durch die Ganzzahligkeitsforderungen hervorgerufenen Schwierigkeiten umgeht man in der Praxis häufig dadurch, daß man zunächst eine optimale Lösung des Problems ohne Berücksichtigung der Ganzzahligkeitsforderungen bestimmt und dann daraus eine ganzzahlige Lösung durch Runden entwickelt. - Als exaktes Lösungsverfahren für das Verschnittproblem eignet sich insbes. ein auf Gilmore und Gomory (1961) und (1963) zurückgehendes Verfahren, bei dem es sich um eine Variante der revidierten Simplexmethode handelt und das geeignet ist, auch Probleme mit einer großen Anzahl möglicher Schnittmuster zu behandeln. Bei diesem Verfahren ist es nicht erforderlich, sofort das gesamte Optimierungsproblem aufzustellen, vielmehr konstruiert man sich die zur Durchführung eines Simplexschritts jeweils geeignete Koeffizientenspalte nach Bedarf, wobei jedoch jeweils ein Rucksackproblem zu lösen ist. - Dieser Umstand kann zu unbefriedigenden Rechenzeiten führen, so daß man bei den Verschnittproblem der Praxis häufig auf den Einsatz von Heuristiken zurückgreift.
IVerschnittproblem Ökonomische Bedeutung: Verschnittproblem bilden die Grundstruktur einer Vielzahl von Zuschneideproblemen der Praxis ab. Sie dienen in diesem Zusammenhang als Vorbild bei der Modellierung derartiger Probleme. Für den Einsatz in der Praxis ist das Modell insbes. im Hinblick auf die jeweils wirksamen Beschränkungen und Ziele zu modifizieren (vgl. im einzelnen Zuschnittplanung).
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
