Approximative Algorithmen für zwei- und dreidimensionale Packungsprobleme und verwandte Schedulingprobleme
Final Report Abstract
Im Zuge dieses Projekts haben wir Algorithmen für mehrdimensionale Packungsprobleme und verwandte Scheduling Probleme untersucht. Mehrdimensionale Packungsprobleme sind Probleme, bei denen mehrdimensionale Formen ohne Überlappungen in Verpackungen möglichst dicht untergebracht werden sollen. Bei Scheduling Problemen geht es darum einen Ablaufplan (Schedule) zu erstellen, der eine Menge von Aufträgen möglichst günstig auf Maschinen verteilt. Packungsprobleme finden aber auch in vielen anderen Bereichen Anwendungen: Z.B. beim VLSI Design, bei Zuschnittproblemen aus der Papier-, Metall- oder Textilindustrie, oder auch beim Platzieren von Anzeigen auf Zeitungsseiten. Der Schwerpunkt unserer Forschung lag in der strukturellen Erforschung dieser Probleme mit dem Ziel, die besten bekannten approximativen Algorithmen zu verbessern. Approximative Algorithmen sind Verfahren, die in polynomieller Laufzeit Lösungen zu einem Optimierungsproblem mit einer beweisbaren Gütegarantie berechnen. Im Folgenden beschreiben wir die von uns untersuchten Probleme etwas genauer und erläutern jeweils unsere Ergebnisse. Beim Scheduling paralleler Jobs besteht eine Eingabe des Problems aus einer Menge von Maschinen und einer Menge von Jobs, wobei jedem Job eine Ausführungszeit und eine Anzahl von benötigten Prozessoren zugeordnet ist. Das Problem kann auch als Packungsproblem aufgefasst werden, bei dem die Jobs Rechtecken entsprechen, deren Breite und Höhe durch Ausführungszeit und Prozessorzahl gegeben ist. Die Rechtecke müssen einem Zielbereich (Strip) unbegrenzter Höhe zugeordnet werden, dessen Breite der Prozessoranzahl entspricht. Dieses Problem wird 2D-Strip Packing genannt, doch müssen beim Scheduling Problem die Jobs nicht von benachbarten Prozessoren ausgeführt werden. Dies bedeutet, dass die Rechtecke vertikal zerschnitten und die Teilstücke horizontal verschoben werden dürfen. Der bisher beste Algorithmus von Garey und Graham hatte eine absolute Güte von 2. Ein von diesem Algorithmus berechneter Ablaufplan ist also maximal doppelt so lang wie ein optimaler Ablaufplan. Uns ist es gelungen eine (1.5 + ε)-Approximation für dieses Problem, sowie für einige Varianten davon, zu entwickeln. Dabei bezeichnet ε einen Wert, der unter Inkaufnahme größerer Laufzeiten beliebig klein gewählt werden kann. Für dieses Problem gilt eine untere Güteschranke von 1.5, d.h. es kann kein approximativer Algorithmus mit Güte < 1.5 entwickelt werden, es sei denn P = NP. Beim Scheduling paralleler Jobs in Clustern stehen für die Bearbeitung der Jobs mehrere Cluster mit jeweils mehreren Prozessoren zur Verfügung. Es ist wiederum eng verwandt mit dem Multiple Strip Packing, bei dem mehrere Streifen zur Verfügung stehen. Mit Bougeret, Dutot und Trystram konnten wir für einen Fall, bei dem die Jobs nur begrenzt groß sind, einen Algorithmus mit Approximationsgüte 2 entwickeln. Ohne diese Beschränkung konnten wir, ebenfalls mit Bougeret, Dutot und Trystram, eine 5/2 , eine 7/3 und später sogar eine 2 + ε Approximation entwickeln, wodurch die Lücke zwischen der oberen Güteschranke von 2 + ε und der unteren von 2 fast geschlossen ist. Die Problemstellung beim zweidimensionalen Bin Packing besteht darin, eine gegebene Menge von Rechtecken in eine minimale Anzahl von quadratischen (1 × 1)-Zielbereichen (Bins) zu packen. Der bisher beste Algorithmus erzielte eine asymptotische Güte von ≈ 1.52. Für dieses Problem haben wir einen Algorithmus entwickelt, der für ein gegebenes ε > 0 und eine Instanz, die optimal in OPT Bins gepackt werden kann, eine Packung in (1.5 + ε) OPT +69 Bins findet. Dies entspricht einer asymptotischen Approximationsgüte von etwa 1.5. Eng verwandt mit dem 2D-Bin Packing, ist das dreidimensionale Strip Packing Problem. Hier muss eine Menge von Quadern in einen Zielbereich mit quadratischer Grundfläche und unbegrenzter Höhe verpackt werden. Wir haben auch hier einen Algorithmus mit asymptotischen Approximationsgüte von 1.5 + ε entwickelt und konnten so die bisher beste Güte von ≈ 1.69 + ε unterbieten.
Publications
- Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. In Discrete Mathematics, Algorithms and Applications, 3(4): 553–586, 2011
M. Bougeret, P.-F. Dutot, K. Jansen, C. Robenek, and D. Trystram
- A (3/2 + ε) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012), pages 224–235, 2012
K. Jansen
- A (2 + ε)-Approximation for Scheduling Parallel Jobs in Platforms. In Proceedings of the 19th European Conference on Parallel Processing (Euro-Par 2013), pages 78-89, 2013
P. Dutot, K. Jansen, C. Robenek, D. Trystram
- New Approximability Results for Two-Dimensional Bin Packing. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pages 919–936, 2013
K. Jansen, L. Prädel
- A New Asymptotic Approximation Algorithm for 3-Dimensional Strip Packing. In SOFSEM 2014: Theory and Practice of Computer Science. Springer International Publishing, pages 327–338, 2014
K. Jansen, L. Prädel
(See online at https://doi.org/10.1007/978-3-319-04298-5_29)
