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