Zum Inhalt springenZur Suche springen

Unsere Forschung

  • Analyse von Graphparametern für gerichtete Graphen
    • In diesem Projekt beschäftigen wir uns mit der Analyse von Graphparametern für gerichtete Graphen. Hierzu betrachten wir gerichtete Formen der Cliquenweite, NLC-Weite und Rangweite sowie verschiedene Ansätze für eine gerichtete Form der Baumweite. Es sollen sowohl graphentheoretische Ergebnisse als auch Fortschritte in der Algorithmik spezieller Graphen erzielt werden.
    • gefördert durch die Deutsche Forschungsgemeinschaft (DFG)
    • seit 2017
  • Algorithmen zur Steuerung von Abstapelanlagen
    • Dieses Forschungsvorhaben beschäftigt sich mit der Entwicklung und Analyse effizienter Algorithmen für diskrete Optimierungsprobleme, wie sie insbesondere bei der Steuerung von automatischen Abstapelanlagen in der Versandindustrie auftreten. Das Ziel ist es, die auf einem Förderband in ungeordneter Reihenfolge ankommenden Versandbehälter entsprechend ihrer Auftragszugehörigkeit umzuordnen, um sie mit den zur Verfügung stehenden Betriebsmitteln von den Transportbändern auf Paletten zu stapeln. Die Umordnung muss dabei mit den vorhandenen Puffermöglichkeiten und Techniken zur Umpositionierung erfolgen. Effiziente Steuerungen für solche Abstapelanlagen können in der Versandindustrie die Kosten für die Abwicklung der Aufträge ereduzieren. Die Entwicklung von solchen Steuerungen erfordert jedoch eine detaillierte theoretische Analyse der unterliegenden kombinatorischen Probleme. Zu diesem Zweck liegt der Schwerpunkt in diesem Forschungsvorhaben in der Modellbildung von Abstapelanlagen und der Lösung der daraus resultierenden algorithmischen Problemen. (Projektbeschreibung)
    • Kooperation mit Prof. Jochen Rethmann (Hochschule Niederrhein)
    • seit 2013
  • Algorithmen für Rucksackprobleme
    • Das Rucksackproblem (KP) ist ein sehr bekanntes schweres Problem in der kombinatorischen Optimierung. Die Eingabe besteht aus einer Menge $A$ von $n$ Objekten. Jedes Objekt $j$ besitzt einen Profit $p(j)$ und eine Größe $s(j)$. Weiterhin ist eine Kapazität $c$ für den Rucksack gegeben. Die Aufgabe besteht darin, eine Teilmenge $A'$ von $A$ zu finden, so dass der Profit der Objekte in $A'$ möglichst groß wird und die Größe der Objekte in $A'$ die Kapazität $c$ nicht überschreitet. Im d-dimensionalen Rucksackproblem ($d$-KP) wird diese Problemstellung auf Objekte mit Größen in mehreren Dimensionen erweitert. Aus der Literatur sind bereits zahlreiche Methoden zum Lösen von schweren Problemen auf Rucksackprobleme angewendet worden. Hierzu zählen Pseudopolynomielle Algorithmen, Approximationsalgorithmen und Ganzzahlige Lineare Programme (ILP). Wir haben auf Grundlage dieser Ergebnisse zahlreiche parametrisierte Algrithmen zeigen können und arbeiten an Verbesserung der im Parameter exponentiellen Laufzeiten. Weiterhin entwickeln wir für spezielle Instanzen verschiedener Rucksackprobleme Lösungen mit polynomieller Laufzeit.
    • seit 2016
Verantwortlichkeit: