Arbeitsgruppe Algorithmen und Komplexität

Projekt Operations Research (WInf-ProjOR)

Wir konnten in diesem Jahr wieder einen Kooperationspartner aus der Wirtschaft – die NPZ Innovation GmbH – für das Projekt Operations Research gewinnen und bieten daher zwei Themen an:

  1.  Ein Realweltproblem aus dem Bereich der Saatgutverarbeitung, dass von der NPZ Innovation ausgeschrieben ist und kooperativ betreut wird.
  2.  Ein Tourenplanungsproblem, dass von uns betreut wird und an Benchmarkinstanzen aus einem Programmierwettbewerb getestet werden soll.

Sie können sich online für das Projekt anmelden. Für Informationen zu den Prüfungsleistungen verweisen wir auf die Moduldatenbank. Im Folgenden werden die Themen genauer beschrieben.

Optimierte Saatgutverarbeitung anhand von Bilddaten

Grundlage

IBild optische Begutachtungm Rahmen der Produktion von Saatgut im großen Maßstab (mehrere tausend Tonnen / Jahr), müssen enge gesetzliche Vorgaben zur Qualität eingehalten werden. Um diese zu erfüllen wird das Saatgut einer Vielzahl an Analysen und Reinigungsschritten unterzogen. Ein Teil dieses Prozesses ist die automatisierte optische Begutachtung von repräsentativen Mustern pro Saatgut Charge. Diese Aufnahmen werden vollautomatisch verarbeitet und verschiedene Parameter auf Einzelkornbasis erhoben. Dazu zählen: Länge/Breite/Pixelfläche/Solidity usw. Diese Parameter stehen zusammen mit weiteren Metadaten zur Verfügung. Pro Jahr entstehen so ca. 10 mio. Datenpunkte. Für die nachfolgende Aufgabe müssen Daten von max. 3 Jahren (~30 mio. Datenpunkte) verarbeitet werden.

Aufgabenstellung

  1.  Aufbau einer Datenstruktur zur Speicherung der Daten, welche einen effizienten Zugriff erlaubt. Der Einsatz von Techniken wie NoSQL, In-Memory Datenbanken sowie vorgeschaltete Aggregationen oder der Aufbau von Hilfsstrukturen sind ausdrücklich erwünscht, wenn sie dem Hauptziel des Projekts dienen (Punkt 4).
  2. Aufbau einer Plattform zur Visualisierung der Daten (Histogramm, Boxplot). Nach Möglichkeit in Form einer Website unter Nutzung von D3 (https://d3js.org/)
  3. Erweiterung der Plattform, sodass man (hypothetische) Mischungen von Chargen beurteilen kann, sowie errechnet wird, wie viel Prozent einer Charge / Chargenmischung verworfen werden muss, wenn man bestimmte Größenfraktionen abtrennt.
  4. Eine Vorhersage soll ermöglicht werden, die es erlaubt, auf Grundlage von definierten Ziel-Parametern (Max. Größe / Min. Größe) bestimmte Chargen / Chargenmischungen vorzuschlagen, welche bei dem geringsten Verlust an Tonnage die Zielparameter möglichst optimal trifft.

Sequential ordering problem

Grundlage

Das Sequential ordering problem (SOP) ist eine Variante des bekannten Problem des Handlungsreisenden (Traveling Salseman Problem, TSP). Beim SOP sollen Aufträge an verschiedenen Orten erledigt werden und Aufträge können voneinander abhängen, d.h. manche Aufträge können erst bearbeitet werden nachdem andere abgeschlossen wurden. Das Ziel ist es eine möglichst kurze Tour zu finden, bei der alle Orte besucht und alle Abhängigkeiten eingehalten werden. Formal kann das Problem wie folgt definiert werden:

Eingabe: Vollständiger Graph mit Kantengewichten und Präzedenzrelation auf Knoten.
Ziel: Finde einen Pfad minimalem Gewichts über alle Knoten, der alle Präzedenzen erfüllt.

Beispiel: Im ersten Bild ist eine Instanz mit 4 Knoten gegeben, die Zahlen an den Schwarzen Kanten sind die Kantengewichte und die roten Pfeile die Präzedenzen. Im Zweiten Bild ist eine optimale Lösung gegeben.

sop instanzSOP Lösung

Aufgabenstellungen

Es sollen Optimierungsalgorithmen für das SOP entworfen und implementiert werden, sowie mit Benchmarkinstanzen aus der TSPLIB und SOPLIB getestet werden.