Nachbargebiete
Next: Transformationen Up: Übersicht über das Spektrum Previous: Raumverteilung (Room Allocation)
Nachbargebiete
- Employee Timetabling
- Dieses Problem unterscheidet sich von der automatischen Stundenplanerstellung nur dadurch, daß es noch wesentlich kompliziertere Nebenbedingungen gibt, die zumeist durch gewerkschaftliche Regelungen entstanden sind. Die bekanntesten Beispiele sind Personalplanungen bei Bus und Bahn, aber auch die Wachpläne in Krankenhäusern[MK98] und die Verteilung von Gebetszeiten[CO97] zählen hierzu.
- Sportveranstaltungen
- Dieses Problem ist dem Examination-Timetabling sehr ähnlich, zeichnet sich aber in der Praxis durch eine große Zahl von Symmetrien aus.
- Flight Scheduling
- Das Flight Scheduling Problem besteht in der Zuordnung von Flugzeugen zu Flugstrecken und Zeiten. Die Bedingungen unterscheiden sich wesentlich von denen des Timetablings, da z.B. die Geographie eine wesentlich größere Rolle spielt. Als zusätzliche Einschränkungen treten verschiedene Flugzeugtypen, Wartungsintervalle etc. auf. Ziel ist es, die Zahl der Leerflüge zu minimieren.
- Crew Roostering
- Das Crew Pairing ist der zweite Schritt bei der Flugplanung. Jeder Mannschaft wird eine Flugstrecke zugeteilt, die bei demselben Flughafen (einer Crew-Base) startet und endet, d.h. der Graph der Flugbewegungen muß in disjunkte Kreise zerlegt werden. Soweit es aus der betrachteten umfangreichen Literatur ersichtlich ist, versucht niemand diese beiden Probleme simultan zu lösen.
- Processor Scheduling
- Dies ist normalerweise ein dynamischer und preemptiver Fall, der von der Timetabling-Thematik weitgehend
abweicht und häufig mit Online - Algorithmen behandelt wird. Stellt man aber Echtzeitanforderungen und muß entschieden werden, ob
ein neuer Task noch angenommen werden kann, so ist das Problem bei Annahme eines minimalen Quotas für die Prozessorzuteilung
mit dem Timetablingim wesentlichen identisch. Im Bereich des Compilerbaus kann auch die statische Variante auftreten, wenn z.B.
mehrere unabhängige Ausführungseinheiten in einem Computer gegeben sind, die von dem zu erstellenden Programm exklusiv
genutzt werden können. Dies ähnelt, je nach Parallelisierbarkeit des Codes, aber eher dem job-shop Problem. Etwas ähnliches
tritt auch bei der Registerverteilung auf; die hier verwendeten Graphen sind aber, sofern es keine verschiedenen Registertypen gibt, perfekt (s.u.).
Next: Transformationen Up: Übersicht über das Spektrum Previous: Raumverteilung (Room Allocation) (c) Martin Loehnertz 1999