Prof. Dr.

Gerhard Wäscher

(Industrielle Zuschneide- und Packprobleme)

Ansprechpartner: Prof. Dr. Gerhard Wäscher

Kurzbeschreibung

Zuschneideprobleme treten immer dort auf, wo die Produktionsbedingungen für die Herstellung standardisierter Produkte in großen Quantitäten sprechen, während auf der anderen Seite von den Abnehmern (Kunden, eigene weiterverarbeitende Abteilungen) zwar Produkte der gleichen Qualitäten, aber tendenziell geringerer Abmessungen und möglicherweise auch verschiedenartiger Formen benötigt werden. Derartige Gegebenheiten sind etwa typisch für die Herstellung von Papier und verwandten Erzeugnissen wie Pappe, Zellstoff usw., Kunststoff- und Klebefolien, Glas, Eisen und Stahl, Textilien und Holz. Gerade in diesen Branchen besteht ein erheblicher Rationalisierungsdruck, so daß die Notwendigkeit einer betriebswirtschaftlich fundierten, modell- bzw. DV-gestützen Zuschnittplanung auf der Hand liegt. Andererseits zeigen Anwendungsberichte aus der Praxis immer wieder umfangreiche Kosteneinsparungspotentiale auf.

Zu den Packproblemen zählt man u.a. Fragestellungen im Zusammenhang mit dem Beladen von Paletten und Containern. Die Ausnutzung der zur Verfügung stehenden Packfläche bzw. des Packraumes hat ganz erhebliche Auswirkungen auf die Logistikkosten. Eine optimierte Anordnung der Packstücke auf Paletten und in Containern reduziert Transport- und Lagerkosten erheblich und ermöglicht darüber hinaus eine verbesserte Nutzung knappen Lagerraumes.

Interessanterweise besitzen Zuschneide- und Packprobleme eine gemeinsame Grundstruktur. Die Problemstellungen des Zerlegens von großen Objekten in kleine (Zuschneiden) und diejenige des Zusammenfügens von kleineren Objekten zu größeren verhalten sich dual zueinander und werden deshalb in einem Forschungsschwerpunkt zusammengefasst. Die Forschungsprojekte des Lehrstuhls haben sowohl die Lösung von Zuschneide- und Packproblemen der industriellen Praxis als auch die Entwicklung von Lösungsansätzen für Standardprobleme zum Gegenstand.

Aktuelle Projekte

Typologie und Review für Zuschneide- und Packprobleme

Die Anzahl der Publikationen auf dem Gebiet des "Cutting and Packing" ist in den letzten zwei Jahrzehnten erheblich angewachsen. Die Typologie von Dyckhoff (1990) stellte über viele Jahre ein hervorragendes Instrument dar, existierende und neue Literatur zu charakterisieren und einzuordnen. Im Laufe der Jahre wurden aber jedoch auch immer mehr Mängel deutlich, die zu Schwierigkeiten führten, aktuelle Entwicklungen zu berücksichtigen und letztlich auch nur eine eingeschränkte Akzeptanz der Typologie zur Folge hatte.

Ein Projekt des Lehrstuhls befasst sich mit der Entwicklung einer neuen, verbesserten Typologie, die teilweise auf den von Dyckhoff gelegten Grundlagen aufbaut, die aber auch neue Einteilungskriterien vorstellt. Die Praktikabilität der neuen Typologie soll durch die Einordnung der in dem letzten Jahrzehnt (1995-2004) publizierten Literatur belegt werden.

Veröffentlichungen von Lehrstuhlmitarbeitern zu diesem Projekt:

• Wäscher, G.; Haußner, H.; Schumann, H. (2007): An Improved Typology of Cutting and Packing Problems. European Journal of Operational Research 183, 1109-1130.

Das Reststückproblem in der eindimensionalen Zuschnittplanung

Zuschneiden von Material bedeutet, aus Vorprodukten individuelle Maße für den Abnehmer bzw. für die Weiterverarbeitung zu erzeugen. Technische Erfordernisse wie die Fertigungsgenauigkeit oder Beschränkungen resultierend aus der Maschinengröße führen in gewissen Fällen dazu, dass ein direkter Zuschnitt nicht möglich ist. In solchen Fällen kommt es zu einem mehrstufigen Zuschneideprozess. Dabei wird das Vorprodukt zunächst in solche Abmessungen zerlegt, die auf der zweiten Stufe weiter verarbeitet werden können.

Schwerpunkt der Betrachtung ist die Frage, wie die Vorprodukte in der ersten Stufe geteilt werden sollen und wie die Zuordnung der gewünschten Endmaße auf die so erzeugten Zwischenprodukte erfolgen soll.

Veröffentlichungen von Lehrstuhlmitarbeitern zu diesem Projekt:

• Koch, S.; König, S.; Wäscher, G. (2009): Integer Linear Programming for a Cutting Problem in the Wood-Processing Industry: A Case Study. International Transactions in Operational Research 16, 715-726.

Das 1D Residual Bin Packing Problem

Beim Zuschnitt von stangenförmigem Material in einer oder in wenigen verschiedenen Ausgangslängen fallen in der Praxis Reststücke in völlig verschiedenen Längen an, die aufgrund von fehlenden Lösungsverfahren nicht effektiv weiterverwendet werden können. Dieses Problem - das 1D Residual Bin Packing Problem wurde bisher in der wissenschaftlichen Forschung noch nicht betrachtet. Deshalb soll zunächst untersucht werden, inwieweit sich existierende Verfahren für eindimensionale Zuschneideprobleme auf diesen Problemtyp anwenden lassen, wobei hauptsächlich heuristische Lösungsverfahren im Mittelpunkt stehen sollen. Das Ziel des Forschungsprojektes ist es, speziell auf die Struktur des Residual Bin PackingProblems abgestimmte heuristische Verfahren zu entwickeln.

Graphentheoretische Methoden zur Lösung von Zuschneideproblemen

Zuschneideprobleme befassen sich mit der Frage, wie man gegebene "große" Objekte in "kleine" Teile zerlegen kann, so dass dabei entweder der Wert des Inputs bzw. der Verschnitt minimiert oder aber der Wert des Outputs maximiert wird. Im Allgemeinen handelt es sich hierbei um schwierig lösbare (NP-schwere) Probleme, zu deren Lösung in der Regel Heuristiken herangezogen werden. In diesem Forschungsprojekt wird speziell ein zweidimensionales Problem betrachtet, bei dem unter Einhaltung gewisser Randbedingungen aus einer gegebenen großen Platte verschiedene gegebene kleine Objekte in beliebiger Anzahl outputmaximierend auszuschneiden sind. Für dieses Problem existiert bereits eine Vielzahl von Lösungsansätzen. Als Besonderheit wird hier jedoch angenommen, dass die Platte rechteckige Defekte aufweist, die nicht verwendet werden können. Es wird nun untersucht, inwieweit bekannte Lösungsansätze auf diese Problemstellung angepasst werden können, so dass sie Lösungen von guter Qualität in akzeptabler Zeit liefern.

Veröffentlichungen von Lehrstuhlmitarbeitern zu diesem Projekt:

• Neidlein, V.; Vianna, A.C.G.; Arenales, M.N.; Wäscher, G. (2009): The Two-Dimensional Guillotineable-Layout Cutting Problem with a Single Defect - An AND/OR-Graph Approach. In: Operations Research Proceedings 2008 (Eds.: Fleischmann, B. et al.). Berlin, Heidelberg: Springer-Verlag, 85-90.
• Neidlein, V.; Wäscher, G. (2008): SLOPPGEN: A Problem Generator for the Two-Dimensional Rectangular Single Large Object Placement Problem With a Single Defect. Working Paper No. 15/2008, Faculty of Economics and Management, Otto von Guericke University Magdeburg.

Fehleranalyse in der Palettenbeladung

Die Ausnutzung der auf einer Palette zur Verfügung stehenden Packfläche bzw. des über der Palette zur Verfügung stehenden Packraumes hat ganz erhebliche Auswirkungen auf die Logistikkosten. Eine optimierte Anordnung der Packstücke auf der Palette reduziert Transport- und Lagerkosten erheblich. In diesem Projekt soll untersucht werden, welche Fehler typischerweise bei der Palettenbeladung gemacht werden, mit welchen Methoden sie sich vermeiden lassen und in welchem Umfang sich durch eine verbesserte Palettenbeladung Kosten einsparen lassen.

Veröffentlichungen von Lehrstuhlmitarbeitern zu diesem Projekt:

• Wäscher, G. (2002): Paletten- und Containerbeladung. In: Handbuch Logistik (Hrsg.: Arnold, D. et al.). Berlin et al.: Springer-Verlag, A3-77 - A3-90.

Abgeschlossene Projekte

Fixkosten- und Reihenfolgeprobleme in der Zuschnittplanung

Die Erstellung von Zerlegungsvorschriften bzw. Schnittmustern stellt sicherlich die zentrale Aufgabe der Zuschnittplanung dar. In der Praxis steht jedoch noch eine Reihe weiterer Fragestellungen in engem Zusammenhang mit dieser Planungsaufgabe:

Fixkostenproblem

Zur Vermeidung von Umstellungen, die den Produktionsprozeß unterbrechen, wird ein Schnittmusterprogramm mit einer möglichst geringen Anzahl von Schnittmustern angestrebt. Dabei kann man, ausgehend von einem etwa nach Materialverbrauchsaspekten bestimmten Programm, versuchen, systematisch Paare oder Tripel von Schnittmustern miteinander zu kombinieren.

Reihenfolgeproblem

Hier geht es darum, die Schnittmuster des ermittelten Programms in eine Reihenfolge zu bringen, die eine gegebene Zielsetzung möglichst gut erfüllt. So werden in der glasherstellenden und - verarbeitenden Industrie an den Schneide- und Brechanlagen die zu einem Auftrag gehörenden, bereits zugeschnittenen Teile solange gelagert, bis auch das letzte Maß dieses Auftrags zugeschnitten ist, und dann erst dann - unmittelbar im Anschluss an die Vervollständigung des Auftrags - fortbewegt. Zur Verringerung des Glasbruchrisikos kann man nun versuchen, die (maximale) Anzahl der während des Zuschneideprozesses zwischenzeitlich auftretenden Auftragsstapel durch eine geeignete Schnittmusterreihenfolge zu minimieren.

In einem Dissertationsprojekt hat sich Frau Hildegard Foerster mit Fixkosten- und Reihenfolgeproblemen in der Zuschnittplanung befasst (Abschluss: 06/1997). Da diese Probleme NP-vollständig sind, wurden schwerpunktmäßig heuristische Lösungsverfahren untersucht.

Veröffentlichungen von Lehrstuhlmitarbeitern zu diesem Projekt:

• Foerster, H.; Wäscher, G. (2000): Pattern Reduction in One-dimensional Cutting Stock Problems. In: International Journal of Production Research 38, 1657-1676.
• Foerster, H.; Wäscher, G. (1998): Simulated Annealing for the Order Spread Minimization Problem in Sequencing Cutting Patterns. In: European Journal of Operational Research 110, S. 272-281.
• Foerster, H. (1998): Fixkosten und Reihenfolgeprobleme in der Zuschnittplanung. Frankfurt am Main: Peter Lang-Verlag.

Die Bestimmung ganzzahliger Lösungen für das Standardproblem der eindimensionalen Zuschnittplanung

Das Standardproblem der eindimensionalen Zuschnittplanung besteht darin, aus Inputmaterial, das in einer bestimmten Standardlänge verfügbar ist, ein Auftragsprogramm gegebener kleinerer Längen derart zuzuschneiden, dass die Anzahl der benötigten Standardlängen minimiert wird. Dieses Problem lässt sich grundsätzlich als ein lineares Optimierungsproblem formulieren, bei dem sämtliche Variablen ganzzahlige Werte annehmen müssen. Diese Ganzzahligkeitbedingungen machen das Auffinden optimaler Lösungen bzw. den Nachweis der Optimalität außerordentlich schwierig. Zwar steht zur Lösung des in Bezug auf die Ganzzahligkeitsbedingungen relaxierten Optimierungsproblems ein schnelles Verfahren zur Verfügung, das nicht einmal die explizite Formulierung des linearen Modells erfordert, jedoch liefern nahe liegende Ansätze zur Erzwingung der Ganzzahligkeit (einfache Rundungstechniken) oft Lösungen, die weit vom Optimum entfernt liegen. In einem Dissertationsprojekt ist es Herrn Thomas Gau gelungen, schnelle Lösungsverfahren zu entwickeln, die nahezu jedes Problem des geschilderten Typs optimal lösen. In umfangreichen Rechentests mit mehr als 12.000 Testproblemen lag der gefundene Zielwert nicht mehr als eine Einheit (Standardlänge) über dem Optimum.

Veröffentlichungen von Lehrstuhlmitarbeitern zu diesem Projekt:

• Gau, T. (1997): Lösungsverfahren für das Standardproblem eindimensionalen Zuschneidens. Heidelberg: Springer-Verlag.
• Wäscher, G.; Gau, T. (1996): Heuristics for the Integer One-Dimensional Cutting Stock Problem - A Computational Study. In: OR Spektrum 18, S. 131 - 144.

Testprobleme, Benchmarks und Problemgeneratoren

Die Aussagefähigkeit vieler wissenschaftlicher Untersuchungen leidet - nicht nur im Bereich der Zuschneide- und Packprobleme - darunter, dass Rechentests, mit denen die Lösungsgüte bzw. die Rechengeschwindigkeit von (exakten oder heuristischen) Lösungsverfahren belegt werden sollen, ungeeignete Testprobleme zugrunde gelegt werden. Die Ergebnisse von Tests in verschiedenen Veröffentlichungen sind aufgrund unterschiedlicher Testprobleme nicht unmittelbar miteinander vergleichbar. Die Mitarbeiter des Lehrstuhls haben sich hier die Aufgabe gestellt, eine einheitliche Basis für zukünftige Tests vorzubereiten. Zum gegenwärtigen Zeitpunkt liegt jeweils ein Problemgenerator für das Standardproblem der eindimensionalen Zuschnittplanung (CUTGEN1) und für das eindimensionale Bin Packing-Problem (BPPGEN) vor. Beide Generatoren sind frei über das Internet verfügbar und erlauben es, einmal erzeugte Testprobleme nahezu auf jedem Rechner zu reproduzieren. Mit Hilfe der Generatoren wurden Einzelprobleme und Problemklassen als Benchmarks identifiziert. Außerdem steht eine Sammlung von Testproblemen zur Verfügung, die sowohl Literaturprobleme als auch Praxisprobleme umfasst.

Veröffentlichungen von Lehrstuhlmitarbeitern zu diesem Projekt:

• Gau, T.; Wäscher, G. (1995): CUTGEN1: A Problem Generator for the One-dimensional Cutting Stock Problem. In: European Journal of Operational Research 84, S. 572 - 579.
• Schwerin, P.; Wäscher, G. (1997): The Bin-Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP. In: International Transactions in Operational Research 4, S. 337-389.
• Wäscher, G.; Gau, T. (1994): Test Data for the One-dimensional Cutting Stock Problem. In: Berichte des Instituts für Wirtschaftswissenschaften der Technischen Universität Braunschweig Nr. 93/09. ISBN 3-930 166-08-6.

Zuschnittplanung in einem Unternehmen der Verpackungsmittelindustrie

Ein Unternehmen der Verpackungsmittelindustrie fertigt Mehrwegbehälter aus Holz. Jeder dieser Behälter besteht aus einer Boden- und Deckelplatte sowie vier Seitenplatten, die mit speziellen Clips zu einem vielseitig verwendbaren Behälter zusammengebaut werden können.

Im Laufe der Fertigung werden von Zulieferern bezogene Sperrholzplatten gegebener Standardmaße auf die erforderlichen Abmessungen zugeschnitten. Hierfür stehen zwei Anlagen zur Verfügung, zum einen eine Plattenaufteil-Winkelanlage, zum anderen eine Plattenschäftanlage, mit der mehrere Standardplatten fest zu größeren Platten verleimt werden können. Während dieses Schäftprozesses besteht bereits die Möglichkeit, Zuschnitte durchzuführen. Auf beiden Anlagen sind eine Reihe von Restriktionen bezüglich der erzeugbaren Schnittmuster zu beachten.

Der hohe Anteil der Materialkosten an den Gesamtkosten, verbunden mit einem extremen Preisdruck sowohl auf dem Absatz- als auch auf dem Beschaffungsmarkt, machte eine verbesserte Materialausnutzung unumgänglich. Eine Optimierung des Zuschnitts fand nur ansatzweise statt. Rechentests zeigten, dass überhöhte Schnittverluste auftraten. Zudem erwies sich die Plattenschäftanlage als betrieblicher Engpass. Für die Zuschnittplanung wurde ein Software-Tool entwickelt, das eine Zuordnung von Aufträgen auf die Schneideanlagen vornimmt und die entsprechenden Schneidepläne hierfür liefert, so dass die gesamten entscheidungsrelevanten Kosten des Zuschnitts minimiert werden.

Aktivitäten

Professor Wäscher ist Mitbegründer der internationalen Arbeitsgruppe SICUP - The Special Interest Group on Cutting and Packing, die sich mit Zuschneide- und Packproblemen befaßt und der gegenwärtig mehr als 200 Praktiker und Wissenschaftler aus der ganzen Welt angehören. Er leitete die Arbeitsgruppe über viele Jahre, 1988-1996 gemeinsam mit Prof. Dyckhoff, RWTH Aachen, 1996 - 2000 gemeinsam mit Dr. Bischoff, Swansea, Wales. Die Mitglieder von SICUP treffen sich üblicherweise in einem zweijährigen Rhythmus zu einem Workshop, der anlässlich einer großen internationalen Tagung über Operations Research ausgerichtet wird. Die bisherigen Treffen fanden 1988 in Paris, 1990 in Athen, 1992 in San Francisco, 1993 in Lissabon, 1995 in Singapore, 1996 in Vancouver, 1998 in Brüssel, 2000 in San Antonio, 2002 in Edinburgh und 2003 in Istanbul statt. Seit dem Beginn des Jahres 2004 wird die Arbeitsgruppe - unter dem Namen ESICUP (EURO Special Interest Group on Cutting and Packing) - als eine EURO Working Group geführt. Ihr gegenwärtiger Leiter ist Prof. Dr. José Fernando Oliveira, Universität Porto. Im März 2004 war der Lehrstuhl Gastgeber der erste Arbeitstagung von ESICUP, die an der Leucorea in Lutherstadt Wittenberg stattfand.

Gemeinsam mit Prof. Dyckhoff war Prof. Wäscher für das wissenschaftliche Programm der Workshops in Paris (16 Vorträge) und Athen (18 Vorträge) verantwortlich. Anläßlich der Tagung in Singapore organisierte er einen "Stream" mit insgesamt 12 Vorträgen.

Prof. Wäscher ist Gründungsmitglied des "International Workshop on Cutting, Packing and Related Topics". Dies ist ein Forum, das vor allem den Doktoranden, die auf dem Gebiet des "Cuting and Packing" arbeiten, eine Möglichkeit zur Diskussion ihrer Forschungsarbeiten geben soll. Mittlerweile ist dieser Workshop zu eine festen Einrichtung geworden und wird in einem zweijährigen Rhythmus veranstaltet (1995 Swansea, Wales; 1997 Lutherstadt Wittenberg; 1999 Porto; 2001 Roscilli, Wales; 2003 Sao Paulo, Brasilien). Regelmäßige Teilnehmer sind von Beginn an Wissenschaftler von der Universität Porto, der University of Wales (Swansea) und die Mitarbeiter der Lehrstühle von Prof. Wäscher an der Martin-Luther-Universität Halle (bis 2001) und der Otto-von-Guericke Universität Magdeburg (seit 2002). Seit 2001 gehören auch Wissenschaftler von der University of Southampton, der Universität Guimaraes in Portugal sowie mehrerer brasilianischen Universitäten zum Teilnehmerkreis. Der Lehrstuhl "BWL VIII: Management Science" ist Gastgeber des 6. Workshops, der Anfang September 2005 in Freudenstadt im Schwarzwald stattfindet.