Um den betrieblichen Leistungsprozess und das wirtschaftliche Handeln optimal zu
gestalten, bedarf es der Phasen Planung, Entscheidung, Durchführung und Kontrolle.
Die Phasen Planung und Entscheidung innerhalb dieses Prozesses sind eng miteinander
verbunden, da schon während der Planungsphase weitreichende Entscheidungen
zu treffen beziehungsweise vorzubereiten sind [DOMS91, S. 1].
Die Unternehmensforschung, auch Operational Research (OR), dient der Vorbereitung
von Entscheidungen und stellt somit einen wichtigen Bestandteil in der betrieblichen
Leistungserstellung dar. Mit Hilfe von Modellen werden Probleme dargestellt
und Lösungen gesucht, die den Planer bei seinen Entscheidungen unterstützen sollen.
Durch den Einsatz von OR-Verfahren ergeben sich viele Möglichkeiten, erhebliche
Kostensenkungen zu erzielen und so weitere Rationalisierungsmöglichkeiten zu nutzen.
Somit leistet die Unternehmensforschung einen wichtigen Beitrag, um die Konkurrenz-
und Wettbewerbsfähigkeit der einzelnen Unternehmen zu gewährleisten und zu
verbessern. Dies kann in der Regel ohne allzu hohe Investitionen und innerhalb relativ
kurzer Zeitspannen realisiert werden [ELLI81, S. 3].
Besonders bei produzierenden Unternehmen mit einem hohen Anteil an Materialkosten
sind Maßnahmen zur Planung des optimalen Materialeinsatzes unumgänglich. So
sind in diesem Bereich Verbesserungen sowohl durch eine optimale Ausnutzung des
Packraumes, als auch durch eine Minimierung des Verschnittverlustes und durch
damit verbundene geringere Lagerkosten zu erzielen.
Vor allem klein- und mittelständische Betriebe lassen die Möglichkeiten des OR
oftmals ungenutzt, obwohl sie einen wichtigen Beitrag zur Wettbewerbsfähigkeit aller
Unternehmen, unabhängig von ihrer Größe, leisten.
Verschnitt- und Packprobleme stellen spezielle Problemstellungen dar, die mit Hilfe
geeigneter OR-Verfahren gelöst werden können und somit weitere Rationalisierungsmöglichkeiten
bieten.
Inhalt
1 Operational Research – Hilfestellung zur Wettbewerbsfähigkeit
2 Einführung in die Problemstellung
3 Das Packproblem
3.1 Grundklassen von Packproblemen
3.1.1 Bin Packing
3.1.2 Knapsack-Problem
3.1.3 Pallet Loading
3.1.4 Strip Packing
3.2 Problemklassen von Packproblemen
3.2.1 Eindimensionales Packproblem
3.2.2 Zweidimensionales Packproblem
3.2.3 Dreidimensionales Packproblem
3.3 Zusätzliche Nebenbedingungen
3.4 Tabellarische Übersicht der Packprobleme
4 Das Verschnittproblem
4.1 Eindimensionales Verschnittproblem
4.2 Zweidimensionales Verschnittproblem
4.3 Dreidimensionales Verschnittproblem
5 Lösungsverfahren
5.1 Lösung von Packproblemen
5.1.1 Eindimensionales Packproblem
5.1.2 Zweidimensionales Packproblem
5.1.3 Dreidimensionales Packproblem
5.2 Lösung von Verschnittproblemen
5.2.1 Eindimensionale Verschnittprobleme
5.2.2 Zweidimensionale Verschnittprobleme
5.2.3 Dreidimensionale Verschnittprobleme
5.3 Tabellarische Übersicht der Lösungsansätze
6 Fazit und Ausblick
Quellenverzeichnis
1 Operational Research – Hilfestellung zur Wettbewerbsfähigkeit
Um den betrieblichen Leistungsprozess und das wirtschaftliche Handeln optimal zu gestalten, bedarf es der Phasen Planung, Entscheidung, Durchführung und Kontrolle. Die Phasen Planung und Entscheidung innerhalb dieses Prozesses sind eng miteinander verbunden, da schon während der Planungsphase weitreichende Entscheidungen zu treffen beziehungsweise vorzubereiten sind [DOMS91, S. 1].
Die Unternehmensforschung, auch Operational Research (OR), dient der Vorbereitung von Entscheidungen und stellt somit einen wichtigen Bestandteil in der betrieblichen Leistungserstellung dar. Mit Hilfe von Modellen werden Probleme dargestellt und Lösungen gesucht, die den Planer bei seinen Entscheidungen unterstützen sollen.
Durch den Einsatz von OR-Verfahren ergeben sich viele Möglichkeiten, erhebliche Kostensenkungen zu erzielen und so weitere Rationalisierungsmöglichkeiten zu nutzen.
Somit leistet die Unternehmensforschung einen wichtigen Beitrag, um die Konkurrenz- und Wettbewerbsfähigkeit der einzelnen Unternehmen zu gewährleisten und zu verbessern. Dies kann in der Regel ohne allzu hohe Investitionen und innerhalb relativ kurzer Zeitspannen realisiert werden [ELLI81, S. 3].
Besonders bei produzierenden Unternehmen mit einem hohen Anteil an Materialkosten sind Maßnahmen zur Planung des optimalen Materialeinsatzes unumgänglich. So sind in diesem Bereich Verbesserungen sowohl durch eine optimale Ausnutzung des Packraumes, als auch durch eine Minimierung des Verschnittverlustes und durch damit verbundene geringere Lagerkosten zu erzielen.
Vor allem klein- und mittelständische Betriebe lassen die Möglichkeiten des OR oftmals ungenutzt, obwohl sie einen wichtigen Beitrag zur Wettbewerbsfähigkeit aller Unternehmen, unabhängig von ihrer Größe, leisten.
Verschnitt- und Packprobleme stellen spezielle Problemstellungen dar, die mit Hilfe geeigneter OR-Verfahren gelöst werden können und somit weitere Rationalisierungsmöglichkeiten bieten.
2 Einführung in die Problemstellung
Verschnitt- und Packprobleme werden schon seit langem in der Literatur diskutiert. Die Anfänge reichen bis in das Jahr 1939 mit einem Vortrag des russischen Mathematikers Kantorovich zurück [GAU97, S.7].
Generell lassen sich Verschnitt- und Packprobleme allen Bereichen der Logistik zuordnen. Allerdings finden sie verstärkt bei produzierenden Unternehmen und bei Unternehmen mit starker Ausrichtung auf die Distribution Anwendung.
Aus diesem Grund konzentrieren sich diese Problemstellungen vorwiegend auf die Produktions- und Distributionslogistik.
3 Das Packproblem
Packprobleme, auch Verpackungsprobleme genannt, treten vor allem in der Vertriebslogistik auf. Sie werden aber auch im Rahmen des innerbetrieblichen Transportes angewendet.
Als Packprobleme werden solche Aufgabenstellungen bezeichnet, bei denen kleinere Einheiten (Kisten) in größere Einheiten (Container) gepackt beziehungsweise verladen werden müssen. Dabei muss eine bestimmte Zielvorgabe erreicht werden und es müssen gegebenenfalls Nebenbedingungen beachtet werden [EXEL88, S. 5].
Im Allgemeinen lässt sich das Packproblem wie folgt beschreiben:
Die zu packenden Einheiten müssen bei gegebenen Restriktionen so auf eine Fläche oder in einen Behälter gepackt werden, dass der zur Verfügung stehende Platz optimal ausgenutzt wird und dabei nicht zu große Leerflächen entstehen. Dies ermöglicht Kostensenkungen im Transportbereich einerseits, andererseits bei der Lagerung, da weniger Transporteinheiten benötigt werden und auch weniger Material gelagert werden muss.
Die Untersuchung von Packproblemen ist somit in der betrieblichen Praxis unverzichtbar. Sie hat Auswirkungen auf die Planung der Gestaltung von Transporteinheiten, aus Gesichtspunkten der Stabilität und der Ausgeglichenheit, auf die Planung der Verpackung und auf die Planung des eigentlichen Transportes.
In Industriebetrieben wird, vor allem während der Produktion, Material auf Paletten geladen. Bei Handelsunternehmen oder Anbietern von Logistikdienstleistungen, wie zum Beispiel Speditionen, geht es darum, Container auf Lastkraftwagen, Schiffe oder Flugzeuge zu laden. Doch bei jeder Aufgabenstellung ist letztendlich die optimale Ausnutzung des zur Verfügung stehenden Platzes das Ziel [DYCK92, S. 15].
In der Praxis existieren viele unterschiedliche Arten von Packproblemen, die in Grundklassen, Problemklassen und Nebenbedingungen aufgegliedert werden.
3.1 Grundklassen von Packproblemen
Beim Packproblem werden die Grundklassen Bin Packing, Knapsack-Problem, Pallet Loading und Strip Packing unterschieden. Jede dieser Klassen ist durch spezielle Merkmale und Zielsetzungen definiert. Auch unterscheiden sie sich hinsichtlich der Art und Anzahl der Kisten und Container.
3.1.1 Bin Packing
Charakteristisch hierfür ist, dass mehrere unterschiedliche Kisten in mehrere Container gepackt werden müssen. Ziel ist es, alle Kisten in möglichst wenige Container zu laden. Weisen die Container unterschiedliche Abmessungen auf, so werden diesen Kosten zugeordnet. Dies kann nach der Fläche oder nach dem Volumen geschehen. Das Ziel ist es dann, die daraus resultierende Kostensumme zu minimieren.
Hierbei handelt es sich um ein heterogenes Problem, da die Kisten unterschiedliche Abmessungen aufweisen. Da es sich um sehr komplexe Problemstellungen handelt, werden sie in der Regel unter Zuhilfenahme von schnellen Heuristiken, wie zum Beispiel Next-Fit oder First-Fit, gelöst, worauf im Abschnitt zu den Lösungsverfahren noch näher eingegangen wird. Besonders bei der Beladung von Lastkraftwagen ist diese Problemstellung relevant [DYCK92, S.41].
3.1.2 Knapsack-Problem
Ein in der Literatur viel diskutiertes Problem ist das sogenannte Knapsack- oder auch Rucksack-Problem. Ein Wanderer hat die Möglichkeit mehrere Gegenstände in seinen Rucksack zu packen. Allerdings muss er einige Restriktionen beachten. Diese können zum Beispiel das Gewicht oder das Fassungsvermögen sein. Er muss sich nun entscheiden, welche Gegenstände er mitnehmen will, um den für sich größten Nutzen zu erzielen.
In der Praxis stellt sich diese Aufgabenstellung folgendermaßen dar. Es müssen mehrere unterschiedliche Kisten in einen oder mehrere Container geladen werden, wobei die Anzahl der Container feststeht. Ziel ist es, den Wert der gepackten Kisten zu maximieren, beziehungsweise den Wert der nicht untergebrachten Kisten zu minimieren [EXEL88, S. 7].
Auch hierbei handelt es sich um ein heterogenes Problem. Lösungen können hier durch die Anwendung eines Branch & Bound-Verfahrens oder durch dynamische Programmierung erreicht werden [DYCK92, S. 41].
3.1.3 Pallet Loading
Beim Pallet Loading sind mehrere identische Kisten und ein vorgegebener Container gegeben. Es sollen so viele Kisten wie möglich in den Behälter oder auf die Palettegepackt werden.
Hierbei handelt es sich um ein homogenes Packproblem, da die zu packenden Einheiten alle die gleichen Abmessungen haben. Sind die zu beladenden Container auch identisch, so existiert nur eine relevante, optimale Lösung.
Angewendet wird diese Problemstellung vor allem im innerbetrieblichen Transport, wenn Paletten beladen und transportiert werden müssen.
3.1.4 Strip Packing
Bei dieser Grundklasse geht es darum, mehrere unterschiedliche kleinere Einheiten in eine größere Einheit zu packen. Der Container (größere Einheit) ist nach einer Seite hin offen und somit in seinen Abmessungen unbegrenzt. In der Regel werden die Seiten begrenzt und die Höhe unbestimmt belassen. Diese soll dann so gering wie möglich gehalten werden. Ein weiterer Unterschied zum Bin Packing besteht darin, dass nur ein Container bepackt werden soll [SMIT01].
Hier sollen alle Kisten verpackt und die letztendlich benötigte Containerdimension minimiert werden. Dieses Problem ist heterogen.
3.2 Problemklassen von Packproblemen
Jede der oben genannten Grundklassen lässt sich zusätzlich anhand ihrer Dimension klassifizieren. Diese Unterteilung nach den Dimensionen der einzelnen Einheiten und Behälter ist von großer praktischer Relevanz, da dadurch die einzelnen Problemstellungen grundlegend verändert werden. Sie unterscheiden sich sowohl in der vorgegebenen Zielsetzung, als auch in den angewandten Lösungsverfahren. Dabei sind weniger die räumlichen Dimensionen von Bedeutung, als vielmehr die minimale Anzahl an Dimensionen, die benötigt werden, um das Problem geometrisch beschreiben zu können [DYCK92, S.26]. Somit kommt der Unterteilung in die Dimensionen eine sehr hohe Bedeutung zu, da dadurch die eigentliche Problemstellung erst eindeutig charakterisiert wird. Man unterscheidet in ein-, zwei- und dreidimensionale Packprobleme.
3.2.1 Eindimensionales Packproblem
Diese Problemklasse ist nur vereinzelt in der Praxis relevant. Gelegentlich ist sie im Rahmen eines Knapsack-Problems oder beim Bin Packing zu finden.
Bei eindimensionalen Packproblemen werden die zu betrachtenden Gegenstände nach ihrer Länge definiert. Dies können beispielsweise Rohre oder Stangen sein, welche in kleinere Einheiten aufzuteilen sind [DYCK92, S. 26]. Dies soll bei den Verschnittproblemen näher erläutert werden.
Es ist eine bestimmte Menge von Einheiten mit ihrem Kapazitätsbedarf sowie die Anzahl der Behälter einschließlich ihrer Kapazitäten gegeben. Die Kisten sind so in die Container zu packen, dass keine Kapazitätsrestriktionen verletzt werden und die vorgegebene Zielfunktion optimiert wird.
Es lassen sich drei verschiedene Situationen betrachten [EXEL88, S.6-8]:
- Alle Einheiten können in die Behälter untergebracht werden, da deren Gesamtkapazität mindestens so groß wie der Kapazitätsbedarf der Einheiten ist.
- Es können nicht alle Einheiten in die Behälter untergebracht werden, obwohl deren Kapazität größer als der Kapazitätsbedarf der Einheiten ist.
- Die Gesamtkapazität der Behälter ist kleiner als der Kapazitätsbedarf der Einheiten.
Auch kommen verschiedene Zielsetzungen in Betracht:
- Es soll die Anzahl (der Wert) der benötigten Behälter minimiert werden.
- Der ungenutzte Platz der nur teilweise gefüllten Behälter soll minimiert werden.
- Es soll der Wert der untergebrachten Einheiten maximiert werden. Dies entspricht dem klassischen Knapsack-Problem.
- Minimiere den Wert der benötigten Behälter und der nicht untergebrachten Einheiten. Diese Zielsetzung ist sehr praxisrelevant, da man nur ungern einen kaum beladenen LKW einsetzen möchte.
[...]
-
-
-
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.