Aktionsplan-Informatik: Flexibles online Scheduling

• Applicant: Dr. Matthias Westermann
• Subject Area: Theoretical Computer Science
• Term: from 2003 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5401261

Die in der Theorie untersuchten online Modelle zeichnen sich dadurch aus, dass eine Eingabesequenz von Aufgaben erst nach und nach generiert wird und dass die Aufgaben in der vorgegebenen Reihenfolge bearbeitet werden. Es ist kein Wissen über die komplette Eingabesequenz im voraus vorhanden, stattdessen wird eine neue Aufgabe erst dann erzeugt, wenn die vorherige bearbeitet worden ist. In der Praxis können die Aufgaben jedoch üblicherweise kurzfristig verzögert werden und damit kann die starre Reihenfolge der Aufgaben im begrenzten Umfang verändert werden, um das Leistungsverhalten zu optimieren. Dieser Aspekt ist Thema des flexiblen online Schedulings. Die Aufgaben können z.B. Karosserien sein, die jeweils in einer bestimmten Farbe lackiert werden sollen. Da man bei der Lackierung von aufeinanderfolgenden Karosserien mit derselben Farbe profitiert, kann das Leistungsverhalten mittels eines Sortierpuffers, in dem die Karosserien zwischengespeichert werden können, optimiert werden. Dieses Modell des flexiblen online Schedulings, welches viele Anwendungen aus der Ökonomie und Informatik hat, soll in diesem Forschungsvorhaben umfassend untersucht werden. Ein erste Ziel ist die sorgfältige und realistische Modellierung wichtiger Probleme in diesem Bereich. Dann soll die Komplexität dieser Modelle untersucht werden. Ein Schwerpunkt liegt dabei auf der Entwicklung und theoretische Analyse von effizienten Strategien, die ein beweisbar gutes Leistungsverhalten haben. Neben der theoretischen Analyse sollen die entwickelten Strategien auch experimentell evaluiert werden.

• DFG Programme: Independent Junior Research Groups