-2-

Inhaltverzeichnis

Inhaltverzeichnis   2

Einleitung   3

1.  Literaturüberblick und Begriffsbestimmungen  4

1.1  Literaturüberblick.  4

1.2  Lösungen für Bin-Packig Problem.  5

1.3  Bedeutung und Definition  6

2  Modellierung des gewählten Problems  7

2.1  Prozessbeschreibung  7

2.1Modellbeschreibung   8

2.3  Lösungsdarstellung.  10

Fazit.   12

Literaturverzeichnis   16

-3- Einleitung

Im betriebswirtschaftlichen Alltag steht oft das Problem, maximal effiziente Leistung mit minimalen Aufwendungen zu kombinieren. Egal ob in der Textilproduktion, bei Dienstleistungsanbietern oder bei anderer betrieblicher Situation, die Frage bleibt immer aktuell. Wobei bekannt ist, dass Mathematik die Basis für die Wirtschaftstheorie ist. Wissenschaftler haben allgemeine Optimierungsprobleme in Teiloptimierungsprobleme zerteilt, Spezifick dementsprechend, und dadurch haben sie die Lösungssuche vereinfacht.

Jedes Objekt könnte von verschieden Seiten betrachtet werden. Und Objekt der vorliegenden Seminararbeit sind Verschnittsprobleme, was eigentlich sehr intensiv im Bereich Operations-Research untersucht wird. Die Probleme solcher Natur sind genau der Überschneidungspunkt des Betrieblichen Alltags, Produktionstheorie, angewandte Mathematik und Programmierung. In vielen Bereichen der Industrie sowie im Transportwesen spielen Packungs- und Verschnittsprobleme eine wichtige Rolle. Heute werden in vielen Unternehmen Computer eingesetzt, um weiter beschriebene Optimierungsprobleme zu lösen.

Untersuchungen und Analysen des oben genannten Problems, werden mit Hilfe von Beispielen durchgeführt. Genauso ein Problem wird berücksichtigt in den Fallstudien „Zur Planung von Gießprogrammen in der Eisen- und Stahlindustrie.“ In dieser Fallstudie wird ein Gießverfahren anhand eines Bin-Packing Problem ¹ Lösungsansatzes in der Gießindustrie an einer Salzgitter AG beschrieben.

Jeder Wissenschaftler aus dem Bereich „Operation Research“ hätte sein „aber“ in jedem Vorgehensschritt, wobei in dieser Arbeit ein Versuch durchgeführt wird, die genaue wirtschaftliche Sicht zu vertreten. Schwerpunkt dieser Untersuchung sind Kosten, bzw. durch eine Lösungsanwendung ersparte Kosten.

In der vorliegenden Seminararbeit wird ein Verfahren zur Lösung eines Stahlverschnittproblems beschrieben. Es handelt sich dabei um ein aus der Industrie kommendes Problem, welches einem um Nebenbedingungen erweiterten zweidimensionalen Bin Packing Problem,

¹ Bestimmung einer Partition und Zuordnung einer Menge von Objekten, so, dass eine bestimmte Bedingung erfüllt bzw. eine Zielfunktion minimiert oder maximiert wird. ( Siehe Internet: die freie Enzyklopädie „Wikipe- dia“)

-4-auch Strip Packing oder Behälter Problem genannt entspricht. Die Nebenbedingungen erge-ben sich aus den Eigenschaften des Gießprogramms. Die werden in zweiten Teil näherer be-trachtet.

Das Hauptthema dieser Hausarbeit ist ein spezielles Verschnittproblem in der Stahlindustrie und deren Einfluss auf das Kostenrechnungssystem des Unternehmens, welches weiter erläutert wird. Im ersten Teil werden grundlegende und in der Literatur bekannte Packungsprobleme und unterschiedliche Lösungen dafür erläutert. In dem darauf folgenden zweiten Teil wird ein vorgeschlagener Lösungsansatz, in einem Artikel von Thomas Sprengler und Oliver Seerfried „Zur Planung von Gießprogrammen in der Eisen- und Stahlindustrie“, dieses Problems angesichts der Kostenanalyse beschrieben. Im Anschluss daran werden ein Ausblick und eine kritische Würdigung dazu dargestellt.

1. Literaturüberblick und Begriffsbestimmungen

1.1 Literaturüberblick

Aus allgemeiner Sicht handelt es sich in der vorliegender Seminararbeit um die Zuschnittsprobleme. Zuschnittprobleme entstehen dort, wo Produkte in großer Zahl und in Standard-formen auf Grund günstiger Herstellungsbedingungen gefertigt werden, und die Abnehmer Produkte der gleichen Qualität aber mit kleineren Größen und möglicherweise auch in verschiedenen Formen verlangen. Zuschnittprobleme behandeln dann die Aufgabe, Material so in kleine Teile zu schneiden, dass die Menge von ungeschnittenem Material und somit unverbrauchtem Material maximal bleibt. Eine äquivalente Formulierung ist, den Materialverbrauch zu minimieren. Deshalb werden solche Probleme auch Verschnittprobleme genannt. Die Problemstellungen des Zerlegens von großen Objekten in kleinere und des Zusammenfügens von kleineren Objekten zu größeren. Sie zu einander im dualen Verhältnis. Deshalb werden sie in der Literatur gemeinsam behandelt.

Obwohl solche Problemstellungen schon vor Jahrhunderten untersucht werden, wurden Lösungsansätze im Bereich der Zuschnittprobleme erst in den letzten fünfzig Jahren intensiver entwickelt. Hauptsächlich entstehen die Antworten auf die aktuelle Fragen Forschung auf diesem Gebiet wohl aus der Anwendungsbereiche in der heutigen Wirtschaft, denn Ver- schnittprobleme sind kombinatorische Optimierungsaufgaben für bestimmte Ressourcen.

-5-Im Weiteren wird es sich reinspezifisch um eine Arte der Zuschnittsprobleme, bzw. Bin Pa-cking Problem handeln.

Im Wesentlichen ist es bekannt, dass die Problemstellungen nach räumlichen oder abstrakten Dimensionen klassifiziert werden könnten.

Im Operation Research Fachgebiet ist zum Themengebiet der Verschnitt- und Packungsprobleme umfangreiche Literatur vorhanden, meistens auf Englisch. Anfang der 50er Jahre nach der Ausgabe des Buches von Fejes (Fejes (1953)) sind Packungsproblemuntersuchungen intensiver geworden. In diesem werden Probleme im zwei-und dreidimensionalen Raum behandelt. Die hauptsächliche Theorieentwicklung hat in den letzten 30 Jahren stattgefunden.

Übersichtsarbeiten zur Theorie des Bin Packing Probelm findet man bei Coffman, Gary und Johnson (Coffmann/Gary/Johnson (1996), S.46-93)

1.2 Lösungen für Bin-Packig Problem

Die bis heute erfolgreichsten Algorithmen für ein zweidimensionales Bin Packing Problem basieren auf einer Kombination von einfachen Heuristiken ² mit Metaheuristiken wie Simulated Annealing, Genetische Algorithmen oder Tabu-Suche. (Vgl. Coffmann/Gary/Johnson 1996, S. 48-52)

Die Entwicklungen in der Informatik haben die Forschung zu Bin Packing, die grundlegende Modellösung für weiter beschriebene Beispiel ist, stark beeinflusst. Neben Approximationsverfahren sind auch exakte Verfahren für die Lösung des Bin Packing Problems in der Literatur untersucht worden. Diese Verfahren sind in der Lage, die optimale Lösung zu finden, können aber nur bei bestimmten Problemtypen effektiv angewendet werden. Exakte Lösungsverfahren werden erst dann benutzt, wenn die Menge der zu packenden

² Lösungsverfahren, dass typischerweise zulässige Lösungen liefert in relativ kurzer Zeit, aber keine Information darüber, wie gut diese im Vergleich zu einer Optimallösung sind. Wenn eine Heuristik keine Lösung findet, ist nicht bekannt, ob dies am Algorithmus liegt oder ob das betrachtete Optimierungsproblem prinzipiell unlös- bar ist.