Forschungsinstitut für Diskrete Mathematik

Programmierpraktikum Diskrete Optimierung (Modul P2C1)

Sommersemester 2013


Thema: Das Time-Cost-Tradeoff-Problem


Thema dieses Programmierpraktikums ist die Implementierung von Algorithmen für das Diskrete Time-Cost Tradeoff Problem. Welches im Projekt-Scheduling und insbesondere in der Timing-Optimierung im VLSI-Design eine zentrale Rolle spielt. Eine kurze Beschreibung des Problems und der Aufgaben finden Sie hier.

Testinstanzen

Für erste Versuche eignen sich die kleinen Testinstanzen. Später sollten die Algorithmen auf den VLSI-Instanzen laufen.
Kleine Instanzen und VLSI Instanzen.

Minimale Zykluszeiten und obere/untere Schranken für minimale Kosten

Es ist zu beachten, dass die oberen und unteren Schranken gewissen Ungenauigkeiten in Fließkomma-Berechnungen unterliegen, weshalb die Angaben ohne Gewähr sind.
Instanz T LB UB Gap
test1.tct 10 49 49 0.00%
test2.tct 2 12 12 0.00%
test3.tct 0 21569263 21569263 0.00%
test4.tct 10 16 16 0.00%
test5.tct 0 5 5 0.00%
test6.tct 0 7 7 0.00%
vlsi_b1.tct -1 105359000 131730000 20.01%
vlsi_b2.tct -1 3906530000 3975252311 1.87%
vlsi_b3.tct 0 8290380000 8505242984 2.65%
vlsi_b3.tct 0 8290380000 8490536178 2.35%
vlsi_d2.tct -1 13001300000 15833974616 17.90%
vlsi_m2.tct -1 39253700000 60175482719 35.02%
vlsi_n2.tct 460983 35944400000 45799236705 21.52%
vlsi_s1.tct 0 989498 989498 0.00%
vlsi_v2.tct 247459 36042700000 36046790742 0.01%

Bei Fragen zu den Aufgaben wenden Sie sich bitte an den Ihnen zugewiesenen Betreuer oder Stephan Held,

Abgabetermin der Einführungsaufgabe: 30.04.2013.

(per E-Mail an den Betreuer)

Abgabetermin der Abschlussaufgabe: 12.07.2013.

(per E-Mail an den Betreuer)

Anschliessend werden alle Projekte im Rahmen eines Kurzvortrages von 20 Minuten vorgestellt.

Der Termin hierfür wird gegen Semesterende unter Berücksichtigung der Klausurtermine der Teilnehmer festgelegt.

Vorbesprechung:
Montag, 28 Januar, 2013, 15 Uhr c.t.
im Seminarraum des Forschungsinstituts für Diskrete Mathematik, Lennéstraße 2

Studentinnen und Studenten, die an dem Praktikum teilnehmen wollen, aber nicht zur Vorbesprechung kommen können, werden gebeten, sich vorab mit Ulrich Brenner in Verbindung zu setzen.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.-Prof. Dr. S. Held,
Dr. U. Brenner