4.4 Laufzeitverhalten

Um Aussagen über die Laufzeit und insbesondere über den Speicherbedarf des Prototypen machen zu können, war es notwendig, zahlreiche Tests durchzuführen. Ziel dieser Untersuchung war es unter anderem herauszufinden, wie ein Rechner ausgestattet sein muß, um mit dem endgültigen Programm sinnvoll arbeiten zu können.

Um an aussagekräftige Daten zu kommen, haben wird drei Testserien durchgeführt. Zunächst wurden Stundenpläne generiert, die gerade der Minimalanforderung genügen sollten, d. h. es wurden nur die "harten" Restriktionen (4 Restriktionsebenen; siehe Prioritätenliste) berücksichtigt. In der zweiten Testreihe wurden zusätzlich noch sieben¹ weitere Restriktionsebenen aktiviert. Abschließend generierten wir Stundenpläne, bei denen alle 35 Restriktionsebenen berücksichtigt wurden. Alle Tests wurden auf einem PC mit Intel Pentium (166 MHz), 64 MByte Arbeitsspeicher und dem Betriebssystem MS Windows NT 4.0 durchgeführt.

Grundlage für alle Berechnungen waren die Daten für den Stundenplan des Fachbereichs 12 für das Sommersemester 1997. Für die einzelnen Testläufe innerhalb der Testreihen wurde die Anzahl der aktiven Fächer und damit die Anzahl der zu verplanenden Veranstaltungen variiert. Angefangen wurde in jeder Testreihe mit zehn aktiven Fächern. In den folgenden Tests wurde diese Anzahl jeweils um zehn erhöht, bis schließlich alle 119 Fächer verplant wurden. Die zur Verfügung stehenden Räume blieben bei allen Tests konstant (mit insgesamt 580 freien "Zeitfenstern").

Aus den Testergebnissen wurden die auf dieser Seite abgebildeten Diagramme erstellt. Sie zeigen die Anzahl der aktiven Restriktionen, den Speicherbedarf und die Dauer einer Berechnung jeweils in Abhängigkeit von der Anzahl der zu verplanenden Veranstaltungen und der Anzahl der aktiven Restriktionsebenen.

Abbildung 4.4.1: Aktive Restriktionen

Während der Tests wurde schnell deutlich, daß unser Testrechner bei weitem nicht genügend Arbeitsspeicher besitzt. Aufgrund der intensiven Nutzung aller im Speicher befindlichen Daten konnte nicht auf virtuellen Speicher zurückgegriffen werden, da die Prozessorauslastung durch das ständige Auslagern auf unter einen Prozent fiel. Da zum Zeitpunkt der Tests kein Rechner mit mehr Arbeitsspeicher zur Verfügung stand, konnte nur die erste Testserie beendet werden. In der zweiten und besonders in der dritten Testreihe wurde sehr schnell der Arbeitsspeicher knapp (siehe Diagramm Speicherbedarf) und die Testreihe mußte vorzeitig abgebrochen werden.

Abbildung 4.4.2: Speicherbedarf

Somit wurde es erforderlich einige der fehlenden Werte zu berechnen. Da die Anzahl der aktiven Restriktionen und der Speicherbedarf direkt voneinander abhängen und linear ansteigen, war die Berechnung der fehlenden Meßergebnisse leicht durchzuführen. Bei der Laufzeit war eine Berechnung oder Abschätzung nicht möglich, obwohl der gleichmäßige Verlauf der Kurven im Laufzeitdiagramm eventuell das Gegenteil vermuten läßt. Im Gegensatz zum Speicherverbrauch ist die Laufzeit nicht nur von der Anzahl der aktiven Restriktionen abhängig, sondern auch von der Art und Weise, wie diese Restriktionen den Suchraum beeinflussen. Der gleichmäßige Verlauf der Kurven läßt sich wahrscheinlich durch die noch relativ geringe Anzahl aktiver Restriktionen erklären. So ist es möglich, daß die Laufzeit durch eine höhere Anzahl Restriktionen wieder sinkt, da der Suchraum entsprechend verkleinert wird. Dies muß aber durch weitere Tests auf einem "größeren" Rechner überprüft werden.

Abbildung 4.4.3: Laufzeit

¹ Eine Auswahl der – unserer Meinung nach – wichtigsten Restriktionsebenen, wie z. B. Berücksichtigung der Ausschlußzeiten, Raumgrößen, Terminvorgaben, …

Web-Designer: Hans Peter Kunz. Letzte Änderung: 12-03-1998.