Jedes Jahr wieder findet an der Hans-Dampf-Schule eine Notenkonferenz für
die Abschlussklassen statt. Dieser Konferenz wird von den betroffenen Lehrerinnen
und Lehrer immer mit Bangen entgegengesehen, weil sie sich immer sehr in die
Länge zieht. Für die Besprechung jeder Klasse wird etwa eine Stunde
angesetzt. Da es acht Klassen gibt, dauert die Konferenz ca. 8 Stunden. Das
Ärgerliche ist, dass die Lehrer nicht in allen Klassen eingesetzt sind
und somit viel unnütze Wartezeit in Kauf nehmen müssen. Wenn alle
Klassen eines Lehrers besprochen worden sind, kann dieser die Konferenz verlassen
Das folgende Tableau zeigt die Verteilung der Lehrer auf die Klassen.
| Lehrer/Klasse |
12A
|
12B
|
12C
|
12D
|
12E
|
12F
|
12G
|
12H
|
Verweilldauer
|
| Abermann |
x
|
x
|
x
|
|
|||||
| Berger |
x
|
x
|
|||||||
| Delitzsch | |||||||||
| Gebhard |
x
|
x
|
x
|
||||||
| Hain |
x
|
x
|
|||||||
| Klausen |
x
|
x
|
|||||||
| Peter |
x
|
x
|
|||||||
| Seibert |
x
|
x
|
x
|
||||||
| Weigand |
x
|
x
|
|||||||
| Summe |
Aufgabe 1: Berechnen Sie die Dauer der Konferenzteilnahme
der einzelnen Lehrer und addieren Sie diese zu einer Gesamtdauer.
Immer wieder wird versucht, die Reihenfolge der Klassen zu verändern, so dass einzelne Lehrer nicht so lange warten müssen. Dies führt allerdings immer wieder zu Ärger, da das Vorziehen einer Klasse automatisch zur Folge hat, dass eine andere Klasse später dran kommt und somit die betroffenen Lehrer länger warten müssen.
Aufgabe 2: Versuchen Sie für obiges Beispiel eine verbesserte Reihenfolge durch Probieren zu finden.
Da das beschriebene Problem jedes Jahr wieder in neuer Konstellation auftaucht, wird versucht, eine allgemeingültige Lösungsstrategie zu entwickeln, die für jeden Fall die optimale Reihenfolge der Klassen ermittelt, so dass die Gesamtwartezeit für alle Lehrer minimal wird.
Aufgabe 3: Entwerfen Sie ein geeignetes Modell!
Lösungshinweise:
Für das vorliegende Problem eignet sich eine softwaretechnische Lösung,
z. B. mit JAVA. Dazu benötigt man ein zweidimensionales Array, in welchem
das
obige Tableaus abgebildet wird. Es müssen mit einem Schleifenkonstrukt
alle möglichen Klassenreihenfolgen durchgerechnet werden. Diese ergeben
sich aus der Permutation n!
Dabei wird für jeden Fall die Gesamtverweildauer der Lehrer berechnet
und mit der bisher optimalen Lösung verglichen.
Am Ende des Schleifendurchlaufs ist die optimale Lösung gefunden.