Approximative Algorithmen für 2-dimensionale Packungs- und verwandte Schedulingprobleme

Main subject of this thesis are approximation algorithms for scheduling and packing, two classical geometrical problems in combinatorial optimization. It is divided into three parts. In the first part we consider a generalization of the strip packing problem or geometrical cutting stock problem. In strip packing a given set of rectangles has to be placed into a strip of fixed width and infinite height minimizing the total height used. In the generalized problem setup there are N strips available in which the rectangles have to be allocated and the objective is to minimize the maximum height used. The second part deals with a related scheduling problem. Here we are given parallel jobs instead of rectangles that have to be executed in $N$ platforms of processors. Such a job can be identified with a rectangle, but in contrast to rectangle packing in parallel job scheduling we are allowed to cut the jobs into vertical slides and place them into the platforms as long as all slides of a job start at the same time in the same platform. In the third part we investigate scheduling on uniform processors, a fundamental 1-dimensional scheduling problem. Here the jobs are described by a processing time only and have to be assigned to a set of processors that may run at different speeds.Zentrales Thema dieser Dissertation sind approximative Algorithmen für Ablaufplanungs- und Packungsprobleme, zwei klassische Problemstellungen der kombinatorischen Optimierung. Die vorliegende Arbeit besteht aus drei Teilen. Im ersten Teil betrachten wir eine Verallgemeinerung des Strip Packing Problems, auch geometrisches Zuschnittsproblem genannt. Beim Strip Packing soll eine gegebene Menge von Rechtecken in einen Streifen fester Breite und unendlicher Höhe platziert werden, so dass die genutzte Gesamthöhe minimal wird. Bei dem generalisierten Problem stehen N Streifen zur Verfügung, in welchen die Rechtecke angeordnet werden sollen. Ziel ist es das Maximum der genutzten Gesamthöhen zu minimieren. Der zweite Teil beschäftigt sich mit einem verwandten Problem der Ablaufplanung. Hierbei soll statt der Rechtecke eine Menge von parallelen Aufträgen in N Plattformen von Prozessoren ausgeführt werden. Solch ein Auftrag kann mit einem Rechteck identifiziert werden, aber im Gegensatz zum Packen von Rechtecken dürfen die Aufträge in vertikale Scheiben geschnitten und diese dann in den Plattformen angeordnet werden, solange alle Scheiben eines Auftrags zur gleichen Zeit in ein und derselben Plattform starten. Im dritten Teil untersuchen wir die Ablaufplanung auf uniformen Prozessoren, eine fundamentale 1-dimensionale Problemstellung der Ablaufplanung. Hierbei sind die Aufträge nur durch eine Ausführungszeit gegeben und sollen einer Menge von Prozessoren zugewiesen werden, die verschiedene Geschwindigkeiten haben können