Approximation Algorithms for Geometric Packing Problems

Prädel, Lars Dennis

In this thesis we present approximation algorithms for two-dimensional, geometric packing problems. We have given a set of rectangles that have to be placed in one or several predetermined target regions. Such packing problems can be found in several branches of industry, for example when placing logic elements on a chip, or when cutting stock. We consider three problems in detail. First, the so-called two-dimensional strip packing problem consists of a set of rectangles and a strip of width 1 and infinite height. The objective is to find an axis-parallel and non-overlapping arrangement of the rectangles in this strip in order to minimize the total packing height. Furthermore, it is not allowed to rotate the rectangles. For any eps>0, we present an approximation algorithm with an absolute approximation ratio of 5/3+\eps for this problem. The second problem that we study is the two-dimensional bin packing problem. For this problem a set of rectangles is given as input again. The objective is to find an axis-parallel and non-overlapping packing of all rectangles into the minimum number of unit-sized squares, which are also called bins. We consider two versions of this problem. In the first version, we are allowed to rotate the rectangles by 90°, i.e. to exchange the widths and the heights of the rectangles. In the second version it is not allowed to rotate the rectangles at all. For both versions, our result is an approximation algorithm with an asymptotic approximation ratio of 3/2+eps for an arbitrary value eps>0. For the third problem, we have given a set of rectangles of heights 1 and arbitrary widths and a strip of a given integral height and infinite width. The objective is to find an axis-parallel and non-overlapping packing of the rectangles into the strip so that the maximum packing width is minimized. In this setting, it is not allowed to rotate the rectangles. This problem is also known as scheduling problem, with machines representing the strip and jobs representing the rectangles. The definition is as follows: Given a set of jobs with certain processing times and a set of identical machines. The objective is to schedule the jobs on the machines in order to minimize the makespan, i.e. the total length of the schedule. We consider a version of this problem in which the first jobs are already assigned to machines and starting times. We give an approximation algorithm with an absolute approximation ratio of 3/2 for this problem.

In dieser Arbeit stellen wir approximative Algorithmen für zwei-dimensionale, geometrische Packungsprobleme vor. Hierbei haben wir eine Menge von Rechtecken gegeben, die in einem oder mehreren bestimmten Zielbereichen angeordnet werden sollen. Solche Packungsprobleme finden in mehreren industriellen Bereichen Anwendung, so zum Beispiel bei der Anordnung von Schaltelementen auf einem Computerchip oder bei Zuschnittproblemen. Wir betrachten drei Probleme im Detail. Das sogenannte zwei-dimensionale Strip Packing Problem hat als Eingabe eine Menge von Rechtecken und einen Streifen der Breite 1 und unendlicher Höhe. Das Ziel ist es eine Anordnung der Rechtecke in diesem Streifen zu finden, so dass die Packungshöhe minimiert wird. Dabei müssen die Rechtecke achsenparallel angeordnet werden und dürfen sich nicht überschneiden. Auch eine Rotation der Rechtecke ist nicht erlaubt. Wir präsentieren für dieses Problem einen approximativen Algorithmus mit einer absoluten Güte von 5/3+eps, für ein beliebiges eps>0. Das zweite Problem, das wir untersuchen, ist das zwei-dimensionale Bin Packing Problem. Bei diesem Problem haben wir ebenfalls eine Menge von Rechtecken gegeben. Das Ziel ist es alle Rechtecke in die kleinstmögliche Anzahl von Quadraten, auch Bins genannt, mit einheitlicher Seitenlänge zu packen. Auch hier ist gefordert, dass die Rechtecke sich nicht überschneiden und achsenparallel angeordnet werden. Wir betrachten hier zwei Varianten des Problems. In der ersten Variante sind Rotationen um 90° erlaubt, d.h. wir können die Breite mit der Höhe eines Rechteckes vertauschen. Bei der anderen Variante sind Rotationen der Rechtecke nicht erlaubt. Für beide Varianten dieses Problems geben wir einen approximativen Algorithmus an mit einer asymptotische Güte von 3/2+eps, wobei eps>0 eine beliebige Zahl ist. Bei dem dritten Problem ist eine Menge von Rechtecken mit einheitlicher Höhe und beliebiger Breite und ein Streifen einer gegebenen ganzzahligen Höhe und unendlicher Breite gegeben. Das Ziel ist es, eine achsenparallele, sich nicht überschneidende Packung der Rechtecke zu finden, so dass die maximale Packungsbreite minimiert wird. Eine Rotation der Rechtecke ist bei diesem Problem nicht erlaubt. Dieses Problem ist auch als Scheduling Problem bekannt, wobei der Streifen von Maschinen repräsentiert wird und die Rechtecke von Aufträgen. Die Problemdefinition ist wie folgt: Gegeben ist eine Menge von Aufträgen, die eine bestimmte Ausführungszeit haben und eine Menge von identischen Maschinen. Das Ziel ist es, die Aufträge auf die Maschinen zu verteilen, so dass die gesamte Ausführungszeit minimiert wird. Wir betrachten eine Variante dieses Problems, bei dem die ersten Aufträge bereits auf bestimmten Maschinen zu bestimmten Zeiten vorplatziert sind. Wir geben für dieses Problem einen approximativen Algorithmus mit einer absoluten Güte von 3/2 an.

Quote

Citation style:

Prädel, Lars Dennis: Approximation Algorithms for Geometric Packing Problems.

Rights

Use and reproduction:
No CC License (german copyright law applies)

Export