Approximation algorithms for scheduling and two-dimensional packing problems

Schwarz, Ulrich Michael

This dissertation thesis is concerned with two topics of combinatorial optimization : scheduling and geometrical packing problems. Scheduling deals with the assignment of jobs to machines in a ‘good’ way, for suitable notions of good. Two particular problems are studied in depth : on the one hand, we consider the impact of machine failure on online scheduling, i.e. what are the consequences of the fact that in real life, machines do not work flawlessly around the clock, but need maintenance intervals or can break down? How do we need to adapt our algorithms to still obtain good overall schedules, and in what settings do we even have a chance to succeed? Our second problem is of a more static nature : in some settings, not every job is permitted on all the machines. A classical example would be that of workers which needs special qualification to execute some jobs, or a certain minimum requirement of memory size of computers, etc. The problem in general is notoriously hard to tackle; we present improved approximation ratios for several special cases. In particular, we derive a polynomial-time approximation scheme for nested interval restrictions, which occur naturally in many practical applications. Our final topic is two-dimensional geometric bin packing, the problem of packing rectangular objects into the minimum number of containers of identical size (figuratively speaking, we are arranging advertisements of fixed dimensions into the minimum number of print pages). It is known that no approximation ratio better than 2 is possible for this problem, unless P = NP; we present an algorithm that guarantees this ratio.

Diese Promotionsschrift behandelt zwei Arten kombinatorischer Optimierungsprobleme : Ablaufplanungsprobleme und geometrische Packungsprobleme. Ablaufplanungsprobleme handeln davon, eine Menge von Aufgaben, die Jobs, auf eine Menge von ausführenden Maschinen oder Arbeitern zu verteilen, so dass der entstehende Ablaufplan in geeignetem Sinne gut ist. Wir betrachten hier insbesondere folgende zwei Probleme der Ablaufplanung: einerseits untersuchen wir den Einfluß von Maschinenausfällen auf die Online-Ablaufplanung: im wirklichen Leben sind Maschinen nicht fehler- und unterbrechungslos verfügbar. Wir geben eine teilweise Antwort auf die Frage, mit welchen Änderungen Algorithmen trotz unerwartet auftretender Maschinenausfälle gute Pläne erstellen können, und in welchen Fällen es prinzipiell nicht möglich ist, gute Ablaufpläne zu erstellen. Unser zweites Ablaufplanungsproblem ist von statischerer Natur: in der praktischen Anwendung ist es häufig der Fall, dass nicht jede Maschine jeden Job ausführen kann. Ein einfaches Beispiel sind menschliche Arbeiter, die gewisse formale Qualifikationen für gewisse Jobs haben müssen. Diese Problem erweist sich als in voller Allgemeinheit bekannt hartnäckig; wir stellen hier Algorithmen für einige Spezialfälle vor. Insbesondere präsentieren wir ein polynomielles Approximationsschema für den wichtigen Fall verschachtelter Restriktionen, der in der Mitarbeiterplanung auf natürliche Weise auftritt. Schlussendlich untersuchen wir das zweidimensionale geometrische bin packing-Problem. Fragestellung dieses Problem ist es, rechteckige Objekte in die minimale Anzahl von Containern gleicher Größe zu packen. Salopp gesprochen versuchen wir, eine vorgegebene Menge von Anzeigen mit vorgegebenen Abmessungen auf eine möglichst kleine Zahl von Druckseiten gleicher Größe zu platzieren. Es ist bekannt, dass dieses Problem keine Algorithmus mit Approximationsgüte besser als 2 erlaubt, es sei denn, P = NP; wir stellen einen Algorithmus mit Güte 2 vor.

Cite

Citation style:

Schwarz, Ulrich: Approximation algorithms for scheduling and two-dimensional packing problems. 2010.

Rights

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

Export