Approximative Algorithmen für zwei- und dreidimensionale Packungsprobleme und verwandte Schedulingprobleme

• Applicant: Professor Dr. Klaus Jansen
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 68463026

In den letzten Jahren ist das Interesse an orthogonalen Packungsproblemen erheblich gestiegen. Diese finden häufig Anwendung in Problemen aus dem Scheduling-Bereich, bei denen Jobs auf Maschinen verteilt werden. Diese Zuordnung kann verschiedensten Bedingungen unterliegen und unter verschiedenen Zielfunktionen geschehen. Andere Anwendungsmöglichkeiten finden sich im VLSI Design, wo viele Schaltelemente auf einem Chip angeordnet werden müssen, oder bei Schnittproblemen, wo Gegensände aus einem Material herausgeschnitten werden und der Verschnitt oder die Kosten minimiert werden sollen. Nicht zu vergessen sind logistische Fragestellungen, bei denen Pakete in mehrere Container oder Lagerhallen platziert werden sollen. Diese Probleme stellen häufig eine natürliche Erweiterung von derzeit ziemlich gut erforschten ein-dimensionalen Problemen dar. Die Ergebnisse werden nicht selten auf internationalen Konferenzen wie ICALP [5, 35] oder IPCO [34] und in renommierten Journalen wie Mathematics of Operations Research [4, 11] oder SIAM Journal on Computing [3, 36] veröffentlicht. Wir haben in den vergangenen drei Jahren aus diesem Projekt verschiedene vielversprechende Ansätze und erste Ergebnisse hervorbringen können, die wir weiter entwickeln wollen.

• DFG Programme: Research Grants